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

__
TR13-156
| 15th November 2013
__

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

Revisions: 2

__
TR10-054
| 30th March 2010
__

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

Jan Krajicek, Igor Carboni Oliveira

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 >>>Jan Krajicek

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 >>>

Jan Krajicek

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 >>>