YoVDO

Circuit Minimization with QBF and SAT-Based Exact Synthesis

Offered By: Simons Institute via YouTube

Tags

SAT exam Courses Boolean Circuits Courses

Course Description

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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 & Algorithms
Moscow 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