Nisan-Wigderson generators in proof complexity: New lower bounds

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F22%3A00559510" target="_blank" >RIV/67985840:_____/22:00559510 - isvavai.cz</a>

Result on the web

<a href="https://dx.doi.org/10.4230/LIPIcs.CCC.2022.17" target="_blank" >https://dx.doi.org/10.4230/LIPIcs.CCC.2022.17</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.CCC.2022.17" target="_blank" >10.4230/LIPIcs.CCC.2022.17</a>

Result language

angličtina

Original language name

Nisan-Wigderson generators in proof complexity: New lower bounds

Original language description

A map g:{0,1}ⁿ → {0,1}^m (m > n) is a hard proof complexity generator for a proof system P iff for every string b ∈ {0,1}^m ⧵ Rng(g), formula τ_b(g) naturally expressing b ∉ Rng(g) requires superpolynomial size P-proofs. One of the well-studied maps in the theory of proof complexity generators is Nisan-Wigderson generator. Razborov [A. A. {Razborov}, 2015] conjectured that if A is a suitable matrix and f is a NP∩CoNP function hard-on-average for ????/poly, then NW_{f, A} is a hard proof complexity generator for Extended Frege. In this paper, we prove a form of Razborov’s conjecture for AC⁰-Frege. We show that for any symmetric NP∩CoNP function f that is exponentially hard for depth two AC⁰ circuits, NW_{f,A} is a hard proof complexity generator for AC⁰-Frege in a natural setting. As direct applications of this theorem, we show that:n1) For any f with the specified properties, τ_b(NW_{f,A}) (for a natural formalization) based on a random b and a random matrix A with probability 1-o(1) is a tautology and requires superpolynomial (or even exponential) AC⁰-Frege proofs.n2) Certain formalizations of the principle f_n ∉ (NP∩CoNP)/poly requires superpolynomial AC⁰-Frege proofs. These applications relate to two questions that were asked by Krajíček [J. {Krajíček}, 2019].

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GX19-27871X" target="_blank" >GX19-27871X: Efficient approximation algorithms and circuit complexity</a><br>

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2022

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

37th Computational Complexity Conference (CCC 2022)

ISBN

978-3-95977-241-9

ISSN

1868-8969

e-ISSN

—

Number of pages

15

Pages from-to

1-15

Publisher name

Schloss Dagstuhl, Leibniz-Zentrum für Informatik

Place of publication

Dagstuhl

Event location

Philadelphia

Event date

Jul 20, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—