33 citations · 176 across the 16 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
math.LO2016★ 6 cited
Randomized feasible interpolation and monotone circuits with a local oracle
Jan Krajicek
We generalize the feasible interpolation theorem for semantic derivations from K.(1997) by allowing randomized protocols (protocols in the sense of K.(1997). We also introduce an e…
math.LO2016★ 30 cited
Unprovability of circuit upper bounds in Cook's theory PV
Jan Krajicek, Igor C. Oliveira
We establish unconditionally that for every integer there is a language $L \in \mbox{P}$ such that it is consistent with Cook's theory PV that . Our…
math.LO2016★ 1 cited
A feasible interpolation for random resolution
Jan Krajicek
Random resolution, defined by Buss, Kolodziejczyk and Thapen (JSL, 2014), is a sound propositional proof system that extends the resolution proof system by the possibility to augme…