33 citations · 176 across the 16 of their papers we have counts for
Showing 2015Show all
2 papers · 1 filter
math.LO2015★ 30 cited
Consistency of circuit evaluation, extended resolution and total NP search problems
Jan Krajicek
We consider sets of narrow clauses expressing that no definition of a size circuit with inputs is refutable in resolution R in steps. We show that every CNF…
math.LO2015
Expansions of pseudofinite structures and circuit and proof complexity
Jan Krajicek
I shall describe a general model-theoretic task to construct expansions of pseudofinite structures and discuss several examples of particular relevance to computational complexity.…