Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with bounded depth Frege:
TR03-004 | 24th December 2002
Eli Ben-Sasson, Prahladh Harsha

Lower Bounds for Bounded-Depth Frege Proofs via Buss-Pudlack Games

We present a simple proof of the bounded-depth Frege lower bounds of
Pitassi et. al. and Krajicek et. al. for the pigeonhole
principle. Our method uses the interpretation of proofs as two player
games given by Pudlak and Buss. Our lower bound is conceptually
simpler than previous ones, and relies ... more >>>

TR21-182 | 30th December 2021
Ilario Bonacina, Maria Luisa Bonet

On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems

The propositional proof system Sherali-Adams (SA) has polynomial-size proofs of the pigeonhole principle (PHP). Similarly, the Nullstellensatz (NS) proof system has polynomial size proofs of the bijective (i.e. both functional and onto) pigeonhole principle (ofPHP). We characterize the strength of these algebraic proof systems in terms of Boolean proof systems ... more >>>

TR22-023 | 19th February 2022
Erfan Khaniki

Nisan--Wigderson generators in Proof Complexity: New lower bounds

A map $g:\{0,1\}^n\to\{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\setminus Rng(g)$, 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 Nisan--Wigderson generator. Razborov (Annals of Mathematics ... more >>>

ISSN 1433-8092 | Imprint