Circuit Analysis Algorithms

on YouTube ↗01h 09m

" summary

Session argues a concrete algorithm–lower-bound duality and gives a worked algorithm that beats brute force for several circuit classes: constant-depth ACC circuits of subexponential size admit SAT in time 2^{n − n^{ε}} for some ε>0. Key ingredients are a G of H decomposition that represents ACC gates by a symmetric filter over a multilinear polynomial with quasi‑polynomial many monomials, the Razborov–Smolensky random low‑degree polynomials representation, and an FFT‑like multipoint evaluation to evaluate the polynomial on all inputs efficiently. It also surveys hardness/structure results for MCSP and approximation problems.

AI-written summary · about

" chapters (15)

1. 0:00Intro
2. 0:45A conventional view of algorithms and complexity
3. 1:17The tasks of the algorithm designer and the complexity theorist appear to be inherently opposite ones.
4. 3:10"Duality" Between Circuit Analysis Algorithms and Circuit Lower Bounds
5. 7:02Outline of the Lectures
6. 8:30Circuit Analysis Problems Circuit Analysis problems are often computational problems on
7. 10:17Generic Circuit Satisfiability
8. 12:23Circuit SAT Algorithms For simple enough circuits, we know of faster algorithms
9. 26:21Ingredients for Solving ACC SAT 1. Aknown representation of ACC
10. 27:251. Polynomials Representing ACC
11. 35:551. Reducing Aco[@] to polynomials
12. 41:192. Fast Multipoint Evaluation
13. 44:37ACC Satisfiability Algorithm
14. 51:36Circuit Approximation Probability Problem
15. 56:57Circuit Analysis Problems Circuit Analysis problems can also analyze functions directly Canonical Example

" related talks

• 31mFaster Satisfiability Algorithms for Systems of Polynomial Equations over Finite Fields and ACC^0[p]Suguru Tamaki · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 29mImproved Deterministic Algorithms for Sparse Max-SATRahul Santhanam · Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms
• 01h 03mBeyond Boolean Circuits in Garbled CircuitsDavid Heath · Secure Computation 2025
• 01h 05mGraph Algorithms in the MPC ModelSlobodan Mitrovic · Sublinear Algorithms Boot Camp 2024
• 52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance ProblemsKarl Bringmann · Fine-Grained Complexity, Logic, and Query Evaluation 2023
• 17mSatisfiability Algorithms Based on Concentrated ShrinkageRuiwen Chen · Connections Between Algorithm Design and Complexity Theory
• 01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower BoundsArtur Czumaj · Sublinear Algorithms Boot Camp 2024
• 22mClassical Simulation of Quantum Circuits with Partial Interference EffectsAmr Sabry, Sinan Pehlivanoglu · WQS 2024