Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #1 to TR02-023 | 3rd September 2002 00:00

Bounded-depth Frege lower bounds for weaker pigeonhole principles

Revision #1
Authors: Joshua Buresh-Oppenheim, Paul Beame, Ran Raz, Ashish Sabharwal
Accepted on: 3rd September 2002 00:00
Keywords:

Abstract:

Paper:

TR02-023 | 16th April 2002 00:00

Bounded-depth Frege lower bounds for weaker pigeonhole principles

TR02-023
Authors: Josh Buresh-Oppenheim, Paul Beame, Ran Raz, Ashish Sabharwal
Publication: 17th April 2002 19:15
Keywords:

Abstract:

We prove a quasi-polynomial lower bound on the size of bounded-depth
Frege proofs of the pigeonhole principle \$PHP^{m}_n\$ where
\$m= (1+1/{\polylog n})n\$.
This lower bound qualitatively matches the known quasi-polynomial-size
bounded-depth Frege proofs for these principles.
Our technique, which uses a switching lemma argument like other lower bounds
for bounded-depth Frege proofs, is novel in that the tautology to which
this switching lemma is applied remains random throughout the argument.

ISSN 1433-8092 | Imprint