Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Jan Krajicek:

TR16-071 | 1st May 2016
Jan Krajicek, Igor Carboni Oliveira

Unprovability of circuit upper bounds in Cook's theory PV

We establish unconditionally that for every integer $k \geq 1$ there is a language $L \in P$ such that it is consistent with Cook's theory PV that $L \notin SIZE(n^k)$. Our argument is non-constructive and does not provide an explicit description of this language.

more >>>

TR13-156 | 15th November 2013
Jan Krajicek

A reduction of proof complexity to computational complexity for $AC^0[p]$ Frege systems

Revisions: 2

We give a general reduction of lengths-of-proofs lower bounds for
constant depth Frege systems in DeMorgan language augmented by
a connective counting modulo a prime $p$
(the so called $AC^0[p]$ Frege systems)
to computational complexity
lower bounds for search tasks involving search trees branching upon
values of linear maps on ... more >>>

TR10-054 | 30th March 2010
Jan Krajicek

On the proof complexity of the Nisan-Wigderson generator based on a hard $NP \cap coNP$ function

Let $g$ be a map defined as the Nisan-Wigderson generator
but based on an $NP \cap coNP$-function $f$. Any string $b$ outside the range of
$g$ determines a propositional tautology $\tau(g)_b$ expressing this
fact. Razborov \cite{Raz03} has conjectured that if $f$ is hard on average for
P/poly then these ... more >>>

ISSN 1433-8092 | Imprint