Follow
Rahul Santhanam
Rahul Santhanam
Verified email at cs.ox.ac.uk - Homepage
Title
Cited by
Cited by
Year
Infeasibility of instance compression and succinct PCPs for NP
L Fortnow, R Santhanam
Proceedings of the fortieth annual ACM symposium on Theory of computing, 133-142, 2008
3622008
Fighting perebor: New and improved algorithms for formula and QBF satisfiability
R Santhanam
2010 IEEE 51st Annual Symposium on Foundations of Computer Science, 183-192, 2010
962010
Circuit lower bounds for Merlin-Arthur classes
R Santhanam
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing …, 2007
902007
Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness
IC Oliveira, R Santhanam
arXiv preprint arXiv:1611.01190, 2016
722016
Hierarchy theorems for probabilistic polynomial time
L Fortnow, R Santhanam
45th Annual IEEE Symposium on Foundations of Computer Science, 316-324, 2004
702004
Hardness magnification for natural problems
IC Oliveira, R Santhanam
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 65-76, 2018
572018
On the average-case complexity of MCSP and its variants
S Hirahara, R Santhanam
32nd Computational Complexity Conference (CCC 2017), 2017
562017
Graph model selection using maximum likelihood
I Bezáková, A Kalai, R Santhanam
Proceedings of the 23rd international conference on Machine learning, 105-112, 2006
542006
Graph model selection using maximum likelihood
I Bezáková, A Kalai, R Santhanam
Proceedings of the 23rd international conference on Machine learning, 105-112, 2006
542006
Hardness magnification near state-of-the-art lower bounds
IC Oliveira, J Pich, R Santhanam
Theory of Computing 17 (CCC 2019 Special Issue), 2021
472021
Average-case lower bounds and satisfiability algorithms for small threshold circuits
R Chen, R Santhanam, S Srinivasan
arXiv preprint arXiv:1806.06290, 2018
432018
Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
R Chen, R Santhanam
International Conference on Theory and Applications of Satisfiability …, 2015
392015
Beyond natural proofs: Hardness magnification and locality
L Chen, S Hirahara, IC Oliveira, J Pich, N Rajgopal, R Santhanam
ACM Journal of the ACM (JACM) 69 (4), 1-49, 2022
382022
Pseudodeterministic constructions in subexponential time
IC Oliveira, R Santhanam
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017
382017
Pseudorandomness and the minimum circuit size problem
R Santhanam
LIPIcs 151, 2020
362020
NP-hardness of minimum circuit size problem for OR-AND-MOD circuits
S Hirahara, I Oliveira, R Santhanam
33rd Computational Complexity Conference (CCC 2018) 102, 2018
362018
Robust simulations and significant separations
L Fortnow, R Santhanam
International Colloquium on Automata, Languages, and Programming, 569-580, 2011
35*2011
Hierarchies for semantic classes
L Fortnow, R Santhanam, L Trevisan
Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of …, 2005
352005
Effectively Polynomial Simulations.
T Pitassi, R Santhanam
ICS, 370-382, 2010
292010
Pebbles and branching programs for tree evaluation
S Cook, P McKenzie, D Wehr, M Braverman, R Santhanam
ACM Transactions on Computation Theory (TOCT) 3 (2), 1-43, 2012
282012
The system can't perform the operation now. Try again later.
Articles 1–20