Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > WEAK PIGEONHOLE PRINCIPLE:
Reports tagged with Weak pigeonhole principle:
TR01-055 | 26th July 2001
Alexander Razborov

Improved Resolution Lower Bounds for the Weak Pigeonhole Principle

Recently, Raz established exponential lower bounds on the size
of resolution proofs of the weak pigeonhole principle. We give another
proof of this result which leads to better numerical bounds. Specifically,
we show that every resolution proof of $PHP^m_n$ must have size
$\exp\of{\Omega(n/\log m)^{1/2}}$ which implies an
$\exp\of{\Omega(n^{1/3})}$ bound when ... more >>>


TR22-120 | 24th August 2022
Jan Krajicek

On the existence of strong proof complexity generators

Revisions: 1 , Comments: 1

The working conjecture from K'04 that there is a proof complexity generator hard for all
proof systems can be equivalently formulated (for p-time generators) without a reference to proof complexity notions
as follows:
\begin{itemize}
\item There exist a p-time function $g$ extending each input by one bit such that its ... more >>>


TR23-008 | 2nd February 2023
Ond?ej Ježil

Limits of structures and Total NP Search Problems

For a class of finite graphs, we define a limit object relative to some computationally restricted class of functions. The properties of the limit object then reflect how a computationally restricted viewer "sees" a generic instance from the class. The construction uses Krají?ek's forcing with random variables [7]. We prove ... more >>>




ISSN 1433-8092 | Imprint