30 citations · 61 across the 15 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.CC2016
Pseudodeterministic Constructions in Subexponential Time
Igor C. Oliveira, Rahul Santhanam
We study pseudodeterministic constructions, i.e., randomized algorithms which output the same solution on most computation paths. We establish unconditionally that there is an infi…
cs.CC2016
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness
Igor C. Oliveira, Rahul Santhanam
We prove several results giving new and stronger connections between learning, circuit lower bounds and pseudorandomness. Among other results, we show a generic learning speedup le…
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…