[Proof Complexity] Prague seminar on Monday - Erfan Khaniki
thapen
thapen at math.cas.cz
Thu Mar 10 14:20:05 CET 2022
Erfan Khaniki will give a proof complexity talk in our logic seminar on
Monday 14th March, at 16:00 Prague time - see the announcement below.
It will be broadcast on zoom. To join use the link
https://cesnet.zoom.us/j/472648284?pwd=ZTlxeHhqWlltR1AzZC9CTHgzZ2tRZz09
Passcode: 017107 (if required)
-------------------------------------------------------------------------
Speaker:Erfan Khaniki, Institute of Mathematics
Title: Nisan-Wigderson generators in Proof Complexity: New lower bounds
Abstract
A map g:{0,1}^n --> {0,1}^m (m<n) is a hard proof complexity generator
for a proof system P iff for every string b in {0,1}^m\Rng(g) the
formula \tau_b(g), naturally expressing b \not \in Rng(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 a NP \cap CoNP 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 conjecture for AC0-Frege. We
show that for any symmetric NP \cap CoNP function f that is
exponentially hard for depth two AC0 circuits, NW_{f, A} is a hard proof
complexity generator for AC0-Frege in a natural setting.
For more information see the seminar web page at
https://calendar.math.cas.cz/logic-seminar-actual .
_______________________________________________
Logic-seminar mailing list
Logic-seminar at math.cas.cz
https://list.math.cas.cz/listinfo/logic-seminar
More information about the Proof-Complexity
mailing list