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
3552008
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
922010
Circuit lower bounds for Merlin-Arthur classes
R Santhanam
Proceedings of the thirty-ninth annual ACM symposium on Theory of computing†…, 2007
822007
Hierarchy theorems for probabilistic polynomial time
L Fortnow, R Santhanam
45th Annual IEEE Symposium on Foundations of Computer Science, 316-324, 2004
672004
Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness
IC Oliveira, R Santhanam
arXiv preprint arXiv:1611.01190, 2016
622016
Hardness magnification for natural problems
IC Oliveira, R Santhanam
2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 65-76, 2018
512018
On the average-case complexity of MCSP and its variants
S Hirahara, R Santhanam
32nd Computational Complexity Conference (CCC 2017), 2017
502017
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
492006
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
492006
Average-case lower bounds and satisfiability algorithms for small threshold circuits
R Chen, R Santhanam, S Srinivasan
arXiv preprint arXiv:1806.06290, 2018
452018
Hardness magnification near state-of-the-art lower bounds
IC Oliveira, J Pich, R Santhanam
Theory OF Computing 17 (CCC 2019 Special Issue), 2021
442021
Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP
R Chen, R Santhanam
Theory and Applications of Satisfiability Testing--SAT 2015: 18th†…, 2015
392015
Pseudodeterministic constructions in subexponential time
IC Oliveira, R Santhanam
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing†…, 2017
362017
Robust simulations and significant separations
L Fortnow, R Santhanam
Automata, Languages and Programming: 38th International Colloquium, ICALP†…, 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
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
342022
NP-hardness of minimum circuit size problem for OR-AND-MOD circuits
S Hirahara, IC Oliveira, R Santhanam
Schloss Dagstuhl, 2018
302018
Effectively Polynomial Simulations.
T Pitassi, R Santhanam
ICS, 370-382, 2010
292010
Pseudorandomness and the minimum circuit size problem
R Santhanam
LIPIcs 151, 2020
282020
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
262012
The system can't perform the operation now. Try again later.
Articles 1–20