Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR21-076 | 4th June 2021 00:14

#### Pseudorandom Generators, Resolution and Heavy Width

TR21-076
Authors: Dmitry Sokolov
Publication: 4th June 2021 17:38
Keywords:

Abstract:

Following the paper of Alekhnovich, Ben-Sasson, Razborov, Wigderson \cite{ABRW04} we call a pseudorandom generator $\mathrm{PRG}\colon \{0, 1\}^n \to \{0, 1\}^m$ hard for for a propositional proof system $\mathrm{P}$ if $\mathrm{P}$ cannot efficiently prove the (properly encoded) statement $b \notin \mathrm{Im}(\mathrm{PRG})$ for any string $b \in \{0, 1\}^m$.

In \cite{ABRW04} authors suggested the functional encoding'' of considered statement for Nisan--Wigderson generator that allows the introduction of local'' extension variables. These extension variables may potentially significantly increase the power of the proof system. In \cite{ABRW04} authors gave a lower bound $\exp\left[\frac{n^2}{m \Omega\left(2^{2^{\Delta}}\right)}\right]$ on the length of Resolution proofs where $\Delta$ is the degree of the dependency graph of the generator. This lower bound meets the barrier for the restriction technique.

In this paper, we introduce a heavy width'' measure for Resolution that allows showing a lower bound $\exp\left[\frac{n^2}{m 2^{O(\varepsilon \Delta)}}\right]$ on the length of Resolution proofs of the considered statement for the Nisan--Wigderson generator. This gives an exponential lower bound up to $\Delta := \log^{2 - \delta} n$ (the bigger degree the more extension variables we can use). It is a solution to an open problem from \cite{ABRW04}.

ISSN 1433-8092 | Imprint