A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion

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


Duration: 26:51
123 views
2

Anastasia Sofronova (EPFL)
https://simons.berkeley.edu/talks/anastasia-sofronova-epfl-2023-03-20-0
Proof Complexity and Meta-Mathematics

The talk is based on a joint work with Dmitry Sokolov. This result improves existing lower bounds on random CNFs using the expansion of an underlying graph of a formula.



Other Videos By Simons Institute for the Theory of Computing


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
2023-03-22Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic
2023-03-21Consistency of NEXP Not in P/poly in a Strong Theory
2023-03-21Lifting to Parity Decision Trees via Stifling (with applications to proof complexity)
2023-03-21A Lower Bound for k-DNF Resolution on Random CNF Formulas via Expansion
2023-03-21The Hitting Proof System
2023-03-21Random log(n)-CNF are Hard for Cutting Planes (Again)
2023-03-20Lower Bounds Against PC With Extension Variables
2023-03-17Strong Bounds for 3-Progressions
2023-03-15The Quantum Fourier Transform Has Small Entanglement | Quantum Colloquium
2023-03-07Writing Workshop with Science Communicator in Residence Adam Becker
2023-02-26What Do the Theory of Computing and the Movies Have in Common?
2023-02-18Unstructured Hardness to Average-Case Randomness
2023-02-18Learning with Distributional Inverters
2023-02-18What (Doesn't) Make Learning Algorithms Generalize?


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