All reports by Author Jan Krajicek:

__
TR07-007
| 17th January 2007
__

Jan Krajicek#### An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams

__
TR04-018
| 24th January 2004
__

Jan Krajicek#### Diagonalization in proof complexity

__
TR03-055
| 20th July 2003
__

Jan Krajicek#### Implicit proofs

__
TR00-033
| 22nd May 2000
__

Jan Krajicek#### Tautologies from pseudo-random generators

Revisions: 1

__
TR97-015
| 21st April 1997
__

Jan Krajicek#### Interpolation by a game

__
TR94-018
| 12th December 1994
__

Jan Krajicek, Pavel Pudlak, Alan Woods#### An Exponential Lower Bound to the Size of Bounded Depth Frege Proofs of the Pigeonhole Principle

Jan Krajicek

We prove an exponential lower bound on the size of proofs

in the proof system operating with ordered binary decision diagrams

introduced by Atserias, Kolaitis and Vardi. In fact, the lower bound

applies to semantic derivations operating with sets defined by OBDDs.

We do not assume ...
more >>>

Jan Krajicek

We study the diagonalization in the context of proof

complexity. We prove that at least one of the

following three conjectures is true:

1. There is a boolean function computable in E

that has circuit complexity $2^{\Omega(n)}$.

2. NP is not closed under the complement.

3. There is no ... more >>>

Jan Krajicek

We describe a general method how to construct from

a propositional proof system P a possibly much stronger

proof system iP. The system iP operates with

exponentially long P-proofs described ``implicitly''

by polynomial size circuits.

As an example we prove that proof system iEF, implicit EF,

corresponds to bounded ...
more >>>

Jan Krajicek

We consider tautologies formed from a pseudo-random

number generator, defined in Kraj\'{\i}\v{c}ek \cite{Kra99}

and in Alekhnovich et.al. \cite{ABRW}.

We explain a strategy of proving their hardness for EF via

a conjecture about bounded arithmetic formulated

in Kraj\'{\i}\v{c}ek \cite{Kra99}. Further we give a

purely finitary statement, in a ...
more >>>

Jan Krajicek

We introduce a notion of a "real game"

(a generalization of the Karchmer - Wigderson game),

and "real communication complexity",

and relate them to the size of monotone real formulas

and circuits. We give an exponential lower bound

for tree-like monotone protocols of small real

communication complexity ...
more >>>

Jan Krajicek, Pavel Pudlak, Alan Woods

We prove lower bounds of the form $exp\left(n^{\epsilon_d}\right),$

$\epsilon_d>0,$ on the length of proofs of an explicit sequence of

tautologies, based on the Pigeonhole Principle, in proof systems

using formulas of depth $d,$ for any constant $d.$ This is the

largest lower bound for the strongest proof system, for which ...
more >>>