| 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 | 355 | 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 | 92 | 2010 |
| Circuit lower bounds for Merlin-Arthur classes R Santhanam Proceedings of the thirty-ninth annual ACM symposium on Theory of computing …, 2007 | 82 | 2007 |
| Hierarchy theorems for probabilistic polynomial time L Fortnow, R Santhanam 45th Annual IEEE Symposium on Foundations of Computer Science, 316-324, 2004 | 67 | 2004 |
| Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness IC Oliveira, R Santhanam arXiv preprint arXiv:1611.01190, 2016 | 62 | 2016 |
| Hardness magnification for natural problems IC Oliveira, R Santhanam 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), 65-76, 2018 | 51 | 2018 |
| On the average-case complexity of MCSP and its variants S Hirahara, R Santhanam 32nd Computational Complexity Conference (CCC 2017), 2017 | 50 | 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 | 49 | 2006 |
| 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 | 49 | 2006 |
| Average-case lower bounds and satisfiability algorithms for small threshold circuits R Chen, R Santhanam, S Srinivasan arXiv preprint arXiv:1806.06290, 2018 | 45 | 2018 |
| Hardness magnification near state-of-the-art lower bounds IC Oliveira, J Pich, R Santhanam Theory OF Computing 17 (CCC 2019 Special Issue), 2021 | 44 | 2021 |
| Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP R Chen, R Santhanam Theory and Applications of Satisfiability Testing--SAT 2015: 18th …, 2015 | 39 | 2015 |
| Pseudodeterministic constructions in subexponential time IC Oliveira, R Santhanam Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017 | 36 | 2017 |
| 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 | 35 | 2005 |
| 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 | 34 | 2022 |
| NP-hardness of minimum circuit size problem for OR-AND-MOD circuits S Hirahara, IC Oliveira, R Santhanam Schloss Dagstuhl, 2018 | 30 | 2018 |
| Effectively Polynomial Simulations. T Pitassi, R Santhanam ICS, 370-382, 2010 | 29 | 2010 |
| Pseudorandomness and the minimum circuit size problem R Santhanam LIPIcs 151, 2020 | 28 | 2020 |
| 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 | 26 | 2012 |
