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 | 370 | 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 | 72 | 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 | 59 | 2018 |

On the average-case complexity of MCSP and its variants S Hirahara, R Santhanam 32nd Computational Complexity Conference (CCC 2017), 2017 | 56 | 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 | 54 | 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 | 50 | 2021 |

Average-case lower bounds and satisfiability algorithms for small threshold circuits R Chen, R Santhanam, S Srinivasan arXiv preprint arXiv:1806.06290, 2018 | 43 | 2018 |

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 |

Pseudodeterministic constructions in subexponential time IC Oliveira, R Santhanam Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing …, 2017 | 40 | 2017 |

Improved Algorithms for Sparse MAX-SAT and MAX-*k*-CSPR Chen, R Santhanam International Conference on Theory and Applications of Satisfiability …, 2015 | 39 | 2015 |

Pseudorandomness and the minimum circuit size problem R Santhanam LIPIcs 151, 2020 | 37 | 2020 |

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 | 36 | 2018 |

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 | 35 | 2005 |

Effectively Polynomial Simulations. T Pitassi, R Santhanam ICS, 370-382, 2010 | 30 | 2010 |

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 | 29 | 2012 |

On medium-uniformity and circuit lower bounds R Santhanam, R Williams 2013 IEEE Conference on Computational Complexity, 15-23, 2013 | 28 | 2013 |