Connections Between QBF Proof Complexity and Circuit Complexity

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,700
Published on ● Video Link: https://www.youtube.com/watch?v=DMXqWeKgTn4


Duration: 32:51
231 views
1

Olaf Beyersdorff (Friedrich Schiller University Jena)
https://simons.berkeley.edu/talks/olaf-beyersdorff-friedrich-schiller-university-jena-2023-03-23-0
Proof Complexity and Meta-Mathematics

The talk will cover the tight connections between circuit complexity for QBF Frege and Resolution systems to circuit classes.



Other Videos By Simons Institute for the Theory of Computing


2023-03-28Extension-Based Proofs
2023-03-28Toni Counts, Continually!
2023-03-27In Search of the Ideal: Toni Pitassi and her work on Algebraic Proof Systems
2023-03-25TFNP
2023-03-25Lower Bounds for NW-generators in AC0-Frege
2023-03-25Implicit Proof Systems
2023-03-24Unprovability and Other Impossibility Results in Machine Learning
2023-03-24Weak Versions of Extended Resolution
2023-03-24CDCL vs Resolution: The Picture in QBF
2023-03-24Read-Once Branching Programs as Proof Lines
2023-03-24Connections Between QBF Proof Complexity and Circuit Complexity
2023-03-24Certifying Combinatorial Solving Using Cutting Planes with Strengthening Rules
2023-03-24On the Dominance-Based Strengthening Rule
2023-03-23On the Problems Related to Waring Rank and Border Waring Rank
2023-03-23Lower Bounds Against Non-Commutative Models of Algebraic Computation
2023-03-23Natural Proofs in Algebraic Circuit Complexity
2023-03-23Variety Membership Testing, Algebraic Natural Proofs, and Geometric Complexity Theory
2023-03-22Frontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems
2023-03-22Indistinguishability Obfuscation via Mathematical Proofs of Equivalence
2023-03-22Towards P≠NP from Extended Frege Lower Bounds
2023-03-22Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Proof Complexity and Meta-Mathematics
Olaf Beyersdorff