4 citations · 6 across the 8 of their papers we have counts for
11 papers
ETH-Hardness of Learning Monotone Circuits and Approximating Their Size
Bruno Cavalar, Susanna F. de Rezende, Matthew Gray +1
We show the following hardness results for monotone learning and approximation of monotone circuit size: 1. Under the Randomised Exponential-Time Hypothesis (rETH), it requires tim…
Polynomial-Time Pseudodeterministic Construction of Primes
Lijie Chen, Zhenjian Lu, Igor C. Oliveira +2
A randomized algorithm for a search problem is *pseudodeterministic* if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on…
Constructive Separations and Their Consequences
Lijie Chen, Ce Jin, Rahul Santhanam +1
For a complexity class and language , a constructive separation of gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for…
Learning algorithms versus automatability of Frege systems
Ján Pich, Rahul Santhanam
We connect learning algorithms and algorithms automating proof search in propositional proof systems: for every sufficiently strong, well-behaved propositional proof system , we…
Pseudodeterministic Algorithms and the Structure of Probabilistic Time
Zhenjian Lu, Igor C. Oliveira, Rahul Santhanam
We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of : proving hierarchy theorems and showing the e…
Beyond Natural Proofs: Hardness Magnification and Locality
Lijie Chen, Shuichi Hirahara, Igor C. Oliveira +3
Hardness magnification reduces major complexity separations (such as ) to proving lower bounds for some natural problem against…
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…
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…
Macroscopes: models for collective decision making
Subramanian Ramamoorthy, András Z. Salamon, Rahul Santhanam
We introduce a new model of collective decision making, when a global decision needs to be made but the parties only possess partial information, and are unwilling (or unable) to f…
Pebbles and Branching Programs for Tree Evaluation
Stephen Cook, Pierre McKenzie, Dustin Wehr +2
We introduce the Tree Evaluation Problem, show that it is in logDCFL (and hence in P), and study its branching program complexity in the hope of eventually proving a superlogarithm…
Bounding Rationality by Discounting Time
Lance Fortnow, Rahul Santhanam
Consider a game where Alice generates an integer and Bob wins if he can factor that integer. Traditional game theory tells us that Bob will always win this game even though in prac…