[Proof Complexity] Prague seminar on Monday - Erfan Khaniki

[thapen]

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