Random log(n)-CNF are Hard for Cutting Planes (Again)

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


Category:
Vlog
Duration: 58:30
166 views
5

Dmitry Sokolov (EPFL)
https://simons.berkeley.edu/talks/dmitry-sokolov-epfl-2023-03-20-0
Proof Complexity and Meta-Mathematics

In this talk, we will try to present a self-contained simplified proof of hardness of random log(n)-CNF formulas in Cutting Planes. This result was proven by Hrubes, Pudlak, and independently by Fleming, Pankratov, Pitassi and Robere. In both papers, the authors reduce the considered question to the lower bound on monotone circuits and use Jukna's criteria to show the desired result. Instead of it, we do some direct bottleneck counting and discuss related open problems.



Other Videos By Simons Institute for the Theory of Computing


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?
2023-02-17Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity
2023-02-17On Low End Obfuscation and Learning


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