[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
Passcode: 017107 (if required)


Speaker:Erfan Khaniki, Institute of Mathematics
Title: Nisan-Wigderson generators in Proof Complexity: New lower bounds


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 

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

More information about the Proof-Complexity mailing list