Circuit Minimization with QBF and SAT-Based Exact Synthesis
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore new methods for re-synthesizing Boolean circuits to minimize gate count in this 44-minute talk by Stefan Szeider from TU Wien. Delve into the proposed approach that rewrites small subcircuits using exact synthesis, with synthesis tasks encoded as Quantified Boolean Formulas (QBFs) or SAT instances. Understand the crucial role of handling "don't cares" in providing additional flexibility. Learn about the prototype implementation that broke records for gate count in benchmark instances. Gain insights into this joint work with Franz-Xaver Reichl and Friedrich Slivovsky, presented as part of the Synthesis of Models and Systems series at the Simons Institute.
Syllabus
Circuit Minimization with QBF and SAT-Based Exact Synthesis
Taught by
Simons Institute
Related Courses
Algebra & AlgorithmsMoscow Institute of Physics and Technology via Coursera Lower Bounds in Complexity Theory, Communication Complexity, and Sunflowers - Toniann Pitassi
Institute for Advanced Study via YouTube Proof and Circuit Complexity - Robert Robere
Institute for Advanced Study via YouTube Undergrad Complexity at CMU - SAT
Ryan O'Donnell via YouTube Improved Non-Interactive Zero Knowledge with Applications to Post-Quantum Signatures
Association for Computing Machinery (ACM) via YouTube