4 citations · 6 across the 8 of their papers we have counts for
Showing 2016Show all
2 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…