[Proof Complexity] Prague seminar on Monday - Dmitry Sokolov

[thapen]

Dmitry Sokolov will give an online proof complexity talk in our logic 
seminar on Monday 21st February, at 16:00 Prague time - see the 
announcement below. This is the first talk of the new semester.

To join use the link
https://cesnet.zoom.us/j/472648284?pwd=ZTlxeHhqWlltR1AzZC9CTHgzZ2tRZz09
Passcode: 017107 (if required)


  
-------------------------------------------------------------------------

  Speaker:Dmitry Sokolov, St Petersburg State University and PDMI RAS
  Title: Resolution, Heavy Width and Pseudorandom Generators

  Abstract

  Following the paper of Alekhnovich, Ben-Sasson, Razborov, Wigderson we 
call a pseudorandom generator hard for a propositional proof system P if 
P cannot efficiently prove the (properly encoded) statement that b is 
outside of the image for any string b \in {0, 1}^m.

  In ABRW04 the authors suggested the "functional encoding" of the 
considered statement for Nisan--Wigderson generator that allows the 
introduction of "local" extension variables and gave a lower bound on 
the length of Resolution proofs if the number of extension variables is 
bounded by the n^2 (where n is the number of inputs of the PRG).

  In this talk, we discuss a "heavy width" measure for Resolution that 
allows us to show a lower bound on the length of Resolution proofs of 
the considered statement for the Nisan--Wigderson generator with a 
superpolynomial number of local extension variables. It is a solution to 
one of the open problems from ABRW04.



  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