Explore a comprehensive analysis of real Boolean Holant problems in this 27-minute IEEE conference talk. Delve into the complexity classification of Holant problems, examining tractable signatures and gadget construction. Follow an inductive approach to understand Bell signatures and their properties. Investigate the challenges posed by non-affine signatures and the closure conjecture. Discover the intricacies of 6-ary signatures and the strong Bell property. Learn about the non-constructive reduction technique and its application in proving the Real Holant Dichotomy. Gain insights into the future directions and implications of this research in computational complexity theory.
Overview
Syllabus
Intro
Holant Problems
Why Holant?
Complexity Classification
Holant: Limited Results
A Partial Map
Tractable Signatures
Gadget Construction
An Induction Proof
A Visualization of fo
Bell Signatures
A Serious Obstacle
A Closure Conjecture
Another Induction Proof on Non-Affine Signatures
The Inductive Step
A Summary of 6-ary Signatures
Final Obstacle
Strong Bell Property
Bell Binary Signatures are NOT Realizable
A Non-Constructive Reduction
Proof of the Real Holant Dichotomy
Conclusion and Outlook
Taught by
IEEE FOCS: Foundations of Computer Science
