Symmetric Circuits and Fixed-Point Logics

on YouTube ↗36m

" summary

Characterizes exactly which graph properties symmetric circuits capture: polynomial-size symmetric circuits without majority correspond to fixed-point logic interpreted over the structure plus a separate ordered number sort, and polynomial-size symmetric majority circuits exactly capture fixed-point with counting (FPC). Proof sketch: convert formulas to uniform symmetric circuits by instantiating gates for subformulas, and conversely recover evaluation in FPC by labeling gates with small constant supports so only permutations of those supports matter, using p‑uniformity on the number sort. Consequences: parity and CFI-style obstructions separate these classes.

AI-written summary · about

" chapters (17)

1. 0:00Introduction
2. 3:38FixedPoint Logic
3. 5:04Ordering Operator
4. 6:39Non trivial results
5. 8:07Nonuniform circuits
6. 10:20Lower bounds
7. 11:13Monotone circuits
8. 12:17Properties of graphs
9. 14:02Syntax
10. 17:43Results
11. 20:14Questions
12. 21:16Main Results
13. 23:20Prior Work
14. 24:55Main Theorem
15. 27:32Choiceless polynomial time
16. 28:54Boolean circuits
17. 32:13Polynomial time

" related talks

• 49mCompiling FO Sentences to Circuits: Upper Bounds and Lower Bounds on the Size of the CircuitDan Suciu · Probabilistic Circuits and Logic 2023
• 44mEfficient Enumeration Algorithms via CircuitsAntoine Amarili · Probabilistic Circuits and Logic 2023
• 01h 08mAlgebraic Structures in Logic and Query Evaluation 4Dan Suciu · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 06mSemiring SemanticsErich Graedel · Logic and Algebra for Query Evaluation 2023
• 18mParikh's Theorem Made SymbolicAnthony W. Lin, Matthew Hague, Artur Jez · POPL 2024
• 32mCircuits for Querying Trees: A Little SurveyPierre Bourhis · Logic and Algebra for Query Evaluation 2023
• 01h 24mIntroduction to Constraint Logic ProgrammingSergii Dymchenko · LambdaConf 2015
• 01h 05mAlgebraic Structures in Logic and Query Evaluation 2Val Tannen · Logic and Algorithms in Database Theory and AI Boot Camp