33 citations · 176 across the 16 of their papers we have counts for
6 papers · 1 filter
On proof complexity generators
Jan Krajicek
Motivated by the theory of proof complexity generators we consider the following search problem $\mbox{DD}_P$ determined by a propositional proof system : given a -pr…
On the existence of strong proof complexity generators
Jan Krajicek
Cook and Reckhow 1979 pointed out that NP is not closed under complementation iff there is no propositional proof system that admits polynomial size proofs of all tautologies. Theo…
Information in propositional proofs and algorithmic proof search
Jan Krajicek
We study from the proof complexity perspective the (informal) proof search problem: Is there an optimal way to search for propositional proofs? We note that for any fixed proof sys…
The Cook-Reckhow definition
Jan Krajicek
The Cook-Reckhow 1979 paper defined the area of research we now call Proof Complexity. There were earlier papers which contributed to the subject as we understand it today, the mos…
Consistency of circuit lower bounds with bounded theories
Jan Bydzovsky, Jan Krajicek, Igor C. Oliveira
Proving that there are problems in that require boolean circuits of super-linear size is a major frontier in complexity theory. While such lower bounds are…
On monotone circuits with local oracles and clique lower bounds
Jan Krajicek, Igor C. Oliveira
We investigate monotone circuits with local oracles [K., 2016], i.e., circuits containing additional inputs that can perform unstructured computations on the i…