A Dichotomy for Real Boolean Holant Problems

A Dichotomy for Real Boolean Holant Problems

IEEE FOCS: Foundations of Computer Science via YouTube Direct link

Why Holant?

3 of 22

3 of 22

Why Holant?

Class Central Classrooms beta

YouTube videos curated by Class Central.

Classroom Contents

A Dichotomy for Real Boolean Holant Problems

Automatically move to the next video in the Classroom when playback concludes

  1. 1 Intro
  2. 2 Holant Problems
  3. 3 Why Holant?
  4. 4 Complexity Classification
  5. 5 Holant: Limited Results
  6. 6 A Partial Map
  7. 7 Tractable Signatures
  8. 8 Gadget Construction
  9. 9 An Induction Proof
  10. 10 A Visualization of fo
  11. 11 Bell Signatures
  12. 12 A Serious Obstacle
  13. 13 A Closure Conjecture
  14. 14 Another Induction Proof on Non-Affine Signatures
  15. 15 The Inductive Step
  16. 16 A Summary of 6-ary Signatures
  17. 17 Final Obstacle
  18. 18 Strong Bell Property
  19. 19 Bell Binary Signatures are NOT Realizable
  20. 20 A Non-Constructive Reduction
  21. 21 Proof of the Real Holant Dichotomy
  22. 22 Conclusion and Outlook

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.