[Proof Complexity] Prague seminar on Monday - Dmitry Sokolov
thapen
thapen at math.cas.cz
Thu Feb 17 09:10:53 CET 2022
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
More information about the Proof-Complexity
mailing list