On Separators, Segregators and Time versus Space. - Rahul Santhanam (CCC, 2001)

On segregators, separators and time versus space - Rahul Santhanam (Electron. Colloquium Comput. Complex., 2001)

Lower bounds on the complexity of recognizing SAT by Turing machines. - Rahul Santhanam (Inf. Process. Lett., 2001)

Resource Tradeoffs and Derandomization - Rahul Santhanam (Electron. Colloquium Comput. Complex., 2002)

Holographic Proofs and Derandomization. - Rahul Santhanam; Dieter van Melkebeek (CCC, 2003)

Hierarchy Theorems for Probabilistic Polynomial Time. - Lance Fortnow; Rahul Santhanam (FOCS, 2004)

Promise Hierarchies - Lance Fortnow; Rahul Santhanam; Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2004)

Hierarchies for semantic classes. - Lance Fortnow; Rahul Santhanam; Luca Trevisan 001 (STOC, 2005)

Holographic Proofs and Derandmization. - Dieter van Melkebeek; Rahul Santhanam (SIAM J. Comput., 2005)

Some Results on Average-Case Hardness Within the Polynomial Hierarchy. - Aduri Pavan; Rahul Santhanam; N. V. Vinodchandran (FSTTCS, 2006)

Graph model selection using maximum likelihood. - Ivona Bezáková; Adam Kalai; Rahul Santhanam (ICML, 2006)

Graph splicing systems. - Rahul Santhanam; Kamala Krithivasan (Discret. Appl. Math., 2006)

Uniform Hardness Amplification in NP via Monotone Codes. - Joshua Buresh-Oppenheim; Valentine Kabanets; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2006)

Making Hard Problems Harder - Joshua Buresh-Oppenheim; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2006)

Fixed-Polynomial Size Circuit Bounds. - Lance Fortnow; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2006)

Time Hierarchies: A Survey. - Lance Fortnow; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2007)

Fixed-Polynomial Size Circuit Bounds. - Lance Fortnow; Rahul Santhanam; Ryan Williams 001 (CCC, 2009)

Fractional Pebbling and Thrifty Branching Programs. - Mark Braverman; Stephen A. Cook; Pierre McKenzie; Rahul Santhanam; Dustin Wehr (FSTTCS, 2009)

Branching Programs for Tree Evaluation. - Mark Braverman; Stephen A. Cook; Pierre McKenzie; Rahul Santhanam; Dustin Wehr (MFCS, 2009)

Unconditional Lower Bounds against Advice. - Harry Buhrman; Lance Fortnow; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2009)

Circuit Lower Bounds for Merlin–Arthur Classes. - Rahul Santhanam (SIAM J. Comput., 2009)

Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability. - Rahul Santhanam (FOCS, 2010)

Bounding Rationality by Discounting Time. - Lance Fortnow; Rahul Santhanam (ICS, 2010)

Effectively Polynomial Simulations. - Toniann Pitassi; Rahul Santhanam (ICS, 2010)

Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent. - Maurice J. Jansen; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2011)

Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes. - Maurice J. Jansen; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2011)

On the Limits of Sparsification. - Rahul Santhanam; Srikanth Srinivasan 001 (Electron. Colloquium Comput. Complex., 2011)

Infeasibility of instance compression and succinct PCPs for NP. - Lance Fortnow; Rahul Santhanam (J. Comput. Syst. Sci., 2011)

Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes. - Maurice J. Jansen; Rahul Santhanam (STACS, 2012)

Macroscopes: models for collective decision making - Subramanian Ramamoorthy; András Z. Salamon; Rahul Santhanam (CoRR, 2012)

Instance Compression for the Polynomial Hierarchy and Beyond. - Chiranjit Chakraborty; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2012)

Lower Bounds on Interactive Compressibility by Constant-Depth Circuits. - Arkadev Chattopadhyay; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2012)

Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds. - Rahul Santhanam (Electron. Colloquium Comput. Complex., 2012)

Uniform Circuits, Lower Bounds, and QBF Algorithms. - Rahul Santhanam; Ryan Williams 001 (Electron. Colloquium Comput. Complex., 2012)

The Complexity of Explicit Constructions. - Rahul Santhanam (Theory Comput. Syst., 2012)

Pebbles and Branching Programs for Tree Evaluation. - Stephen A. Cook; Pierre McKenzie; Dustin Wehr; Mark Braverman; Rahul Santhanam (ACM Trans. Comput. Theory, 2012)

On Medium-Uniformity and Circuit Lower Bounds. - Rahul Santhanam; Ryan Williams 001 (CCC, 2013)

New Algorithms for QBF Satisfiability and Implications for Circuit Complexity. - Rahul Santhanam; Ryan Williams 001 (Electron. Colloquium Comput. Complex., 2013)

Permanent does not have succinct polynomial size arithmetic circuits of constant depth. - Maurice J. Jansen; Rahul Santhanam (Inf. Comput., 2013)

On Uniformity and Circuit Lower Bounds. - Rahul Santhanam; Ryan Williams 001 (Comput. Complex., 2014)

Optimal algorithms and proofs (Dagstuhl Seminar 14421). - Olaf Beyersdorff; Edward A. Hirsch; Jan Krajícek; Rahul Santhanam (Dagstuhl Reports, 2014)

Hierarchies Against Sublinear Advice. - Lance Fortnow; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2014)

Majority is incompressible by AC0[p] circuits. - Igor Carboni Oliveira; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2014)

Majority is Incompressible by AC^0[p] Circuits. - Igor Carboni Oliveira; Rahul Santhanam (CCC, 2015)

Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity. - Rahul Santhanam; Richard Ryan Williams (SODA, 2015)

Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP. - Ruiwen Chen; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2015)

Satisfiability on Mixed Instances. - Ruiwen Chen; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2015)

Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. - Ruiwen Chen; Rahul Santhanam; Srikanth Srinivasan 001 (Electron. Colloquium Comput. Complex., 2015)

Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds. - Yuval Filmus; Toniann Pitassi; Rahul Santhanam (ACM Trans. Comput. Theory, 2015)

New Non-Uniform Lower Bounds for Uniform Classes. - Lance Fortnow; Rahul Santhanam (CCC, 2016)

Exponential Time Paradigms Through the Polynomial Time Lens. - Andrew Drucker; Jesper Nederlof; Rahul Santhanam (ESA, 2016)

Pseudodeterministic Constructions in Subexponential Time. - Igor Carboni Oliveira; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2016)

Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness. - Igor Carboni Oliveira; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2016)

Special Section on the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC 2012). - Andrew McGregor 001; Rahul Santhanam (SIAM J. Comput., 2016)

On the Average-Case Complexity of MCSP and Its Variants. - Shuichi Hirahara; Rahul Santhanam (CCC, 2017)

An Average-Case Lower Bound against ACC^0. - Igor Carboni Oliveira; Ruiwen Chen; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2017)

Robust simulations and significant separations. - Lance Fortnow; Rahul Santhanam (Inf. Comput., 2017)

An Average-Case Lower Bound Against mathsf ACC^0 ACC 0. - Ruiwen Chen; Igor C. Oliveira 001; Rahul Santhanam (LATIN, 2018)

Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds. - Ninad Rajgopal; Rahul Santhanam; Srikanth Srinivasan 001 (MFCS, 2018)

Proof Complexity (Dagstuhl Seminar 18051). - Albert Atserias; Jakob Nordström; Pavel Pudlák; Rahul Santhanam (Dagstuhl Reports, 2018)

NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits. - Shuichi Hirahara; Igor Carboni Oliveira; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2018)

Hardness magnification near state-of-the-art lower bounds. - Igor Carboni Oliveira; Ján Pich; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2018)

Pseudo-derandomizing learning and approximation. - Igor Carboni Oliveira; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2018)

Hardness Magnification for Natural Problems. - Igor Carboni Oliveira; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2018)

Why are Proof Complexity Lower Bounds Hard? - Ján Pich; Rahul Santhanam (FOCS, 2019)

Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121). - Anna Gál; Rahul Santhanam; Till Tantau (Dagstuhl Reports, 2019)

Beyond Natural Proofs: Hardness Magnification and Locality. - Igor Carboni Oliveira; Lijie Chen 001; Shuichi Hirahara; Ján Pich; Ninad Rajgopal; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2019)

Parity helps to compute Majority. - Igor Carboni Oliveira; Rahul Santhanam; Srikanth Srinivasan 001 (Electron. Colloquium Comput. Complex., 2019)

Pseudorandomness and the Minimum Circuit Size Problem. - Rahul Santhanam (Electron. Colloquium Comput. Complex., 2019)

Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions. - Michael E. Saks; Rahul Santhanam (CCC, 2020)

On the Pseudo-Deterministic Query Complexity of NP Search Problems. - Shafi Goldwasser; Russell Impagliazzo; Toniann Pitassi; Rahul Santhanam (CCC, 2021)

Strong co-nondeterministic lower bounds for NP cannot be proved feasibly. - Ján Pich; Rahul Santhanam (STOC, 2021)

Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121). - Anna Gál; Meena Mahajan; Rahul Santhanam; Till Tantau (Dagstuhl Reports, 2021)

Constructive Separations and Their Consequences. - Lijie Chen 001; Ce Jin 001; Rahul Santhanam; Ryan Williams 001 (Electron. Colloquium Comput. Complex., 2021)

Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity. - Rahul Ilango; Hanlin Ren; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2021)

Pseudodeterministic Algorithms and the Structure of Probabilistic Time. - Zhenjian Lu; Igor Carboni Oliveira; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2021)

Hardness of KT Characterizes Parallel Cryptography. - Hanlin Ren; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2021)

A Relativization Perspective on Meta-Complexity. - Hanlin Ren; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2021)

Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity. - Rahul Santhanam; Iddo Tzameret (Electron. Colloquium Comput. Complex., 2021)

Why MCSP Is a More Important Problem Than SAT (Invited Talk). - Rahul Santhanam (FSTTCS, 2022)

Learning Algorithms Versus Automatability of Frege Systems. - Ján Pich; Rahul Santhanam (ICALP, 2022)

Errorless Versus Error-Prone Average-Case Complexity. - Shuichi Hirahara; Rahul Santhanam (ITCS, 2022)

Excluding PH Pessiland. - Shuichi Hirahara; Rahul Santhanam (ITCS, 2022)

Robustness of average-case meta-complexity via pseudorandomness. - Rahul Ilango; Hanlin Ren; Rahul Santhanam (STOC, 2022)

Expander-Based Cryptography Meets Natural Proofs. - Igor C. Oliveira 001; Rahul Santhanam; Roei Tell (Comput. Complex., 2022)

On the Range Avoidance Problem for Circuits. - Hanlin Ren; Rahul Santhanam; Zhikun Wang (Electron. Colloquium Comput. Complex., 2022)

On Randomized Reductions to the Random Strings. - Michael E. Saks; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2022)

Pebbles and Branching Programs for Tree Evaluation. - Stephen A. Cook; Pierre McKenzie; Dustin Wehr; Mark Braverman; Rahul Santhanam (Logic, Automata, and Computational Complexity, 2023)

Polynomial-Time Pseudodeterministic Construction of Primes. - Lijie Chen 001; Zhenjian Lu; Igor Carboni Oliveira; Hanlin Ren; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2023)

Towards P $ neq$ NP from Extended Frege Lower Bounds. - Ján Pich; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2023)

An Algorithmic Approach to Uniform Lower Bounds. - Rahul Santhanam (Electron. Colloquium Comput. Complex., 2023)

Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111). - Anna Gál; Meena Mahajan; Rahul Santhanam; Till Tantau; Manaswi Paraashar (Dagstuhl Reports, 2023)

From Proof Complexity to Circuit Complexity via Interactive Protocols. - Noel Arteche; Erfan Khaniki; Ján Pich; Rahul Santhanam (ICALP, 2024)

On the Complexity of Avoiding Heavy Elements. - Zhenjian Lu; Igor C. Oliveira 001; Hanlin Ren; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2024)

Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity. - Zhenjian Lu; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2024)

How to Construct Random Strings. - Oliver Korten; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2025)

On the Structure of Learnability beyond P/poly. - Ninad Rajgopal; Rahul Santhanam (Comput. Complex., 2025)