| Thursday 12 December 2024 | |
| Events for day: Thursday 12 December 2024 |
| 14:00 - 16:00 Mathematical Logic Weekly Seminar Nisan-Wigderson Generators in Proof Complexity: New Lower Bounds School MATHEMATICS A map $g:{0,1}^n o {0,1}^m$ ($m > n$) is a hard proof complexity generator for a proof system P if and only if for every string $b in {0,1}^msetminus Range(g)$, the formula $ au_b(g)$ naturally expressing $b otin Range(g)$ requires superpolynomial size P-proofs. One of the well-studied maps in the theory of proof complexity generators is the Nisan-Wigderson generator. Razborov [Annals of Mathematics 2015] conjectured that if $A$ is a suitable matrix and $f$ is an NP $cap$ Co-NP function hard-on-average for P/poly, then NW$_{{f,A}}$ is a hard proof complexity generator for Extended Frege. In this talk, we prove a form of Razborov's conjec ... |