| 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 | 375 | 2008 |
| 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 | 96 | 2010 |
| Circuit lower bounds for Merlin-Arthur classes R Santhanam Proceedings of the thirty-ninth annual ACM symposium on Theory of computing …, 2007 | 90 | 2007 |
| Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness IC Oliveira, R Santhanam arXiv preprint arXiv:1611.01190, 2016 | 75 | 2016 |
| Hierarchy theorems for probabilistic polynomial time L Fortnow, R Santhanam 45th Annual IEEE Symposium on Foundations of Computer Science, 316-324, 2004 | 70 | 2004 |
| Hardness magnification for natural problems IC Oliveira, R Santhanam 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 65-76, 2018 | 60 | 2018 |
| On the average-case complexity of MCSP and its variants S Hirahara, R Santhanam 32nd Computational Complexity Conference (CCC 2017), 2017 | 57 | 2017 |
| 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 | 53 | 2006 |
| Hardness magnification near state-of-the-art lower bounds IC Oliveira, J Pich, R Santhanam Theory of Computing 17 (CCC 2019 Special Issue), 2021 | 51 | 2021 |
| Average-case lower bounds and satisfiability algorithms for small threshold circuits R Chen, R Santhanam, S Srinivasan arXiv preprint arXiv:1806.06290, 2018 | 46 | 2018 |
| Pseudodeterministic constructions in subexponential time IC Oliveira, R Santhanam Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017 | 42 | 2017 |
| 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 | 41 | 2022 |
| Pseudorandomness and the minimum circuit size problem R Santhanam LIPIcs 151, 2020 | 39 | 2020 |
| Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP R Chen, R Santhanam International Conference on Theory and Applications of Satisfiability …, 2015 | 39 | 2015 |
| 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 | 37 | 2018 |
| Hierarchies for semantic classes L Fortnow, R Santhanam, L Trevisan Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of …, 2005 | 36 | 2005 |
| Robust simulations and significant separations L Fortnow, R Santhanam International Colloquium on Automata, Languages, and Programming, 569-580, 2011 | 35* | 2011 |
| 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 | 31 | 2012 |
| Effectively Polynomial Simulations. T Pitassi, R Santhanam ICS, 370-382, 2010 | 31 | 2010 |
| Hardness of KT characterizes parallel cryptography H Ren, R Santhanam Cryptology ePrint Archive, 2021 | 29 | 2021 |
