Rahul Santhanam

164 papers A* 22A 34B 4C 1Misc 1Journal 90Unranked 11
YearRankTypeTitle / Venue / Authors
2026 A conf
AC⁰[p]-Frege Cannot Efficiently Prove That Constant-Depth Algebraic Circuit Lower Bounds Are Hard.
ITCS
Jiaqi Lu, Rahul Santhanam, Iddo Tzameret
2025 J jnl
AC
CoRR
Jiaqi Lu, Rahul Santhanam, Iddo Tzameret
2025 J jnl
AC
Electron. Colloquium Comput. Complex.
Jiaqi Lu, Rahul Santhanam, Iddo Tzameret
2025 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 25111).
Dagstuhl Reports
Swastik Kopparty, Meena Mahajan, Rahul Santhanam, Till Tantau, Ian Mertz
2025 A conf
How to Construct Random Strings.
CCC
Oliver Korten, Rahul Santhanam
2025 J jnl
How to Construct Random Strings.
Electron. Colloquium Comput. Complex.
Oliver Korten, Rahul Santhanam
2025 J jnl
On the Structure of Learnability beyond P/poly.
Comput. Complex.
Ninad Rajgopal, Rahul Santhanam
2024 A ed.
39th Computational Complexity Conference, CCC 2024, Ann Arbor, MI, USA, July 22-25, 2024
CCC
Rahul Santhanam
2024 J jnl
Constructive Separations and Their Consequences.
TheoretiCS
Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams
2024 A* conf
From Proof Complexity to Circuit Complexity via Interactive Protocols.
ICALP
Noel Arteche, Erfan Khaniki, Ján Pich, Rahul Santhanam
2024 J jnl
From Proof Complexity to Circuit Complexity via Interactive Protocols.
CoRR
Noel Arteche, Erfan Khaniki, Ján Pich, Rahul Santhanam
2024 A* conf
Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity.
ICALP
Zhenjian Lu, Rahul Santhanam
2024 J jnl
Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Zhenjian Lu, Rahul Santhanam
2024 A* conf
On the Complexity of Avoiding Heavy Elements.
FOCS
Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
2024 J jnl
On the Complexity of Avoiding Heavy Elements.
Electron. Colloquium Comput. Complex.
Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
2023 A conf
An Algorithmic Approach to Uniform Lower Bounds.
CCC
Rahul Santhanam
2023 J jnl
An Algorithmic Approach to Uniform Lower Bounds.
Electron. Colloquium Comput. Complex.
Rahul Santhanam
2023 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111).
Dagstuhl Reports
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau, Manaswi Paraashar
2023 — ch.
Pebbles and Branching Programs for Tree Evaluation.
Logic, Automata, and Computational Complexity
Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
2023 A* conf
Polynomial-Time Pseudodeterministic Construction of Primes.
FOCS
Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
2023 J jnl
Polynomial-Time Pseudodeterministic Construction of Primes.
CoRR
Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
2023 J jnl
Polynomial-Time Pseudodeterministic Construction of Primes.
Electron. Colloquium Comput. Complex.
Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam
2023 J jnl
Towards P $\neq$ NP from Extended Frege Lower Bounds.
Electron. Colloquium Comput. Complex.
Ján Pich, Rahul Santhanam
2022 A conf
A Relativization Perspective on Meta-Complexity.
STACS
Hanlin Ren, Rahul Santhanam
2022 J jnl
Beyond Natural Proofs: Hardness Magnification and Locality.
J. ACM
Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
2022 J jnl
Constructive Separations and Their Consequences.
CoRR
Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams
2022 A conf
Errorless Versus Error-Prone Average-Case Complexity.
ITCS
Shuichi Hirahara, Rahul Santhanam
2022 A conf
Excluding PH Pessiland.
ITCS
Shuichi Hirahara, Rahul Santhanam
2022 J jnl
Expander-Based Cryptography Meets Natural Proofs.
Comput. Complex.
Igor C. Oliveira, Rahul Santhanam, Roei Tell
2022 A* conf
Learning Algorithms Versus Automatability of Frege Systems.
ICALP
Ján Pich, Rahul Santhanam
2022 A conf
On Randomized Reductions to the Random Strings.
CCC
Michael E. Saks, Rahul Santhanam
2022 J jnl
On Randomized Reductions to the Random Strings.
Electron. Colloquium Comput. Complex.
Michael E. Saks, Rahul Santhanam
2022 A* conf
On the Range Avoidance Problem for Circuits.
FOCS
Hanlin Ren, Rahul Santhanam, Zhikun Wang
2022 J jnl
On the Range Avoidance Problem for Circuits.
Electron. Colloquium Comput. Complex.
Hanlin Ren, Rahul Santhanam, Zhikun Wang
2022 A* conf
Robustness of average-case meta-complexity via pseudorandomness.
STOC
Rahul Ilango, Hanlin Ren, Rahul Santhanam
2022 — conf
Why MCSP Is a More Important Problem Than SAT (Invited Talk).
FSTTCS
Rahul Santhanam
2021 J jnl
A Relativization Perspective on Meta-Complexity.
Electron. Colloquium Comput. Complex.
Hanlin Ren, Rahul Santhanam
2021 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121).
Dagstuhl Reports
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau
2021 Misc ed.
Computer Science - Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28 - July 2, 2021, Proceedings
CSR
Rahul Santhanam, Daniil Musatov
2021 A* conf
Constructive Separations and Their Consequences.
FOCS
Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams
2021 J jnl
Constructive Separations and Their Consequences.
Electron. Colloquium Comput. Complex.
Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams
2021 J jnl
Hardness Magnification Near State-of-the-Art Lower Bounds.
Theory Comput.
Igor C. Oliveira, Ján Pich, Rahul Santhanam
2021 A conf
Hardness of KT Characterizes Parallel Cryptography.
CCC
Hanlin Ren, Rahul Santhanam
2021 J jnl
Hardness of KT Characterizes Parallel Cryptography.
Electron. Colloquium Comput. Complex.
Hanlin Ren, Rahul Santhanam
2021 J jnl
Hardness of KT Characterizes Parallel Cryptography.
IACR Cryptol. ePrint Arch.
Hanlin Ren, Rahul Santhanam
2021 J jnl
Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity.
Electron. Colloquium Comput. Complex.
Rahul Ilango, Hanlin Ren, Rahul Santhanam
2021 J jnl
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity.
Electron. Colloquium Comput. Complex.
Rahul Santhanam, Iddo Tzameret
2021 A* conf
Iterated lower bound formulas: a diagonalization-based approach to proof complexity.
STOC
Rahul Santhanam, Iddo Tzameret
2021 J jnl
Learning algorithms versus automatability of Frege systems.
CoRR
Ján Pich, Rahul Santhanam
2021 A conf
On the Pseudo-Deterministic Query Complexity of NP Search Problems.
CCC
Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, Rahul Santhanam
2021 — conf
On the Structure of Learnability Beyond P/Poly.
APPROX-RANDOM
Ninad Rajgopal, Rahul Santhanam
2021 J jnl
On the Structure of Learnability beyond P/poly.
Electron. Colloquium Comput. Complex.
Ninad Rajgopal, Rahul Santhanam
2021 J jnl
Pseudodeterministic Algorithms and the Structure of Probabilistic Time.
CoRR
Zhenjian Lu, Igor C. Oliveira, Rahul Santhanam
2021 J jnl
Pseudodeterministic Algorithms and the Structure of Probabilistic Time.
Electron. Colloquium Comput. Complex.
Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam
2021 A* conf
Pseudodeterministic algorithms and the structure of probabilistic time.
STOC
Zhenjian Lu, Igor C. Oliveira, Rahul Santhanam
2021 A* conf
Strong co-nondeterministic lower bounds for NP cannot be proved feasibly.
STOC
Ján Pich, Rahul Santhanam
2020 A conf
Beyond Natural Proofs: Hardness Magnification and Locality.
ITCS
Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
2020 A conf
Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions.
CCC
Michael E. Saks, Rahul Santhanam
2020 A conf
Pseudorandomness and the Minimum Circuit Size Problem.
ITCS
Rahul Santhanam
2019 J jnl
Beyond Natural Proofs: Hardness Magnification and Locality.
CoRR
Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
2019 J jnl
Beyond Natural Proofs: Hardness Magnification and Locality.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam
2019 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121).
Dagstuhl Reports
Anna Gál, Rahul Santhanam, Till Tantau
2019 A conf
Expander-Based Cryptography Meets Natural Proofs.
ITCS
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell
2019 A conf
Hardness Magnification near State-Of-The-Art Lower Bounds.
CCC
Igor Carboni Oliveira, Ján Pich, Rahul Santhanam
2019 A conf
Parity Helps to Compute Majority.
CCC
Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan
2019 J jnl
Parity helps to compute Majority.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan
2019 J jnl
Pseudorandomness and the Minimum Circuit Size Problem.
Electron. Colloquium Comput. Complex.
Rahul Santhanam
2019 A* conf
Why are Proof Complexity Lower Bounds Hard?
FOCS
Ján Pich, Rahul Santhanam
2018 B conf
An Average-Case Lower Bound Against \mathsf ACC^0 ACC 0.
LATIN
Ruiwen Chen, Igor C. Oliveira, Rahul Santhanam
2018 J jnl
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits.
CoRR
Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan
2018 J jnl
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits.
Theory Comput.
Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan
2018 B conf
Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds.
MFCS
Ninad Rajgopal, Rahul Santhanam, Srikanth Srinivasan
2018 J jnl
Expander-Based Cryptography Meets Natural Proofs.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell
2018 A* conf
Hardness Magnification for Natural Problems.
FOCS
Igor Carboni Oliveira, Rahul Santhanam
2018 J jnl
Hardness Magnification for Natural Problems.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Rahul Santhanam
2018 J jnl
Hardness magnification near state-of-the-art lower bounds.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Ján Pich, Rahul Santhanam
2018 A conf
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits.
CCC
Shuichi Hirahara, Igor C. Oliveira, Rahul Santhanam
2018 J jnl
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam
2018 J jnl
Proof Complexity (Dagstuhl Seminar 18051).
Dagstuhl Reports
Albert Atserias, Jakob Nordström, Pavel Pudlák, Rahul Santhanam
2018 — conf
Pseudo-Derandomizing Learning and Approximation.
APPROX-RANDOM
Igor Carboni Oliveira, Rahul Santhanam
2018 J jnl
Pseudo-derandomizing learning and approximation.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Rahul Santhanam
2017 J jnl
An Average-Case Lower Bound against ACC^0.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam
2017 A conf
Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness.
CCC
Igor C. Oliveira, Rahul Santhanam
2017 A conf
On the Average-Case Complexity of MCSP and Its Variants.
CCC
Shuichi Hirahara, Rahul Santhanam
2017 A* conf
Pseudodeterministic constructions in subexponential time.
STOC
Igor C. Oliveira, Rahul Santhanam
2017 J jnl
Robust simulations and significant separations.
Inf. Comput.
Lance Fortnow, Rahul Santhanam
2016 A conf
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits.
CCC
Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan
2016 J jnl
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness.
CoRR
Igor C. Oliveira, Rahul Santhanam
2016 J jnl
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Rahul Santhanam
2016 A conf
Exponential Time Paradigms Through the Polynomial Time Lens.
ESA
Andrew Drucker, Jesper Nederlof, Rahul Santhanam
2016 A conf
New Non-Uniform Lower Bounds for Uniform Classes.
CCC
Lance Fortnow, Rahul Santhanam
2016 J jnl
Pseudodeterministic Constructions in Subexponential Time.
CoRR
Igor C. Oliveira, Rahul Santhanam
2016 J jnl
Pseudodeterministic Constructions in Subexponential Time.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Rahul Santhanam
2016 A conf
Satisfiability on Mixed Instances.
ITCS
Ruiwen Chen, Rahul Santhanam
2016 J jnl
Special Section on the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC 2012).
SIAM J. Comput.
Andrew McGregor, Rahul Santhanam
2015 J jnl
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits.
Electron. Colloquium Comput. Complex.
Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan
2015 A* conf
Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity.
SODA
Rahul Santhanam, Richard Ryan Williams
2015 J jnl
Exponential Lower Bounds for AC
ACM Trans. Comput. Theory
Yuval Filmus, Toniann Pitassi, Rahul Santhanam
2015 A conf
Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP.
SAT
Ruiwen Chen, Rahul Santhanam
2015 J jnl
Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP.
Electron. Colloquium Comput. Complex.
Ruiwen Chen, Rahul Santhanam
2015 A conf
Majority is Incompressible by AC^0[p] Circuits.
CCC
Igor Carboni Oliveira, Rahul Santhanam
2015 J jnl
Satisfiability on Mixed Instances.
Electron. Colloquium Comput. Complex.
Ruiwen Chen, Rahul Santhanam
2014 J jnl
Hierarchies Against Sublinear Advice.
Electron. Colloquium Comput. Complex.
Lance Fortnow, Rahul Santhanam
2014 J jnl
Majority is incompressible by AC
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Rahul Santhanam
2014 J jnl
On Uniformity and Circuit Lower Bounds.
Comput. Complex.
Rahul Santhanam, Ryan Williams
2014 J jnl
Optimal algorithms and proofs (Dagstuhl Seminar 14421).
Dagstuhl Reports
Olaf Beyersdorff, Edward A. Hirsch, Jan Krajícek, Rahul Santhanam
2013 J jnl
New Algorithms for QBF Satisfiability and Implications for Circuit Complexity.
Electron. Colloquium Comput. Complex.
Rahul Santhanam, Ryan Williams
2013 A conf
On Medium-Uniformity and Circuit Lower Bounds.
CCC
Rahul Santhanam, Ryan Williams
2013 J jnl
Permanent does not have succinct polynomial size arithmetic circuits of constant depth.
Inf. Comput.
Maurice J. Jansen, Rahul Santhanam
2012 J jnl
Instance Compression for the Polynomial Hierarchy and Beyond.
Electron. Colloquium Comput. Complex.
Chiranjit Chakraborty, Rahul Santhanam
2012 B conf
Instance Compression for the Polynomial Hierarchy and beyond.
IPEC
Chiranjit Chakraborty, Rahul Santhanam
2012 J jnl
Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds.
Bull. EATCS
Rahul Santhanam
2012 J jnl
Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds.
Electron. Colloquium Comput. Complex.
Rahul Santhanam
2012 A* conf
Lower Bounds on Interactive Compressibility by Constant-Depth Circuits.
FOCS
Arkadev Chattopadhyay, Rahul Santhanam
2012 J jnl
Lower Bounds on Interactive Compressibility by Constant-Depth Circuits.
Electron. Colloquium Comput. Complex.
Arkadev Chattopadhyay, Rahul Santhanam
2012 J jnl
Macroscopes: models for collective decision making
CoRR
Subramanian Ramamoorthy, András Z. Salamon, Rahul Santhanam
2012 A conf
Marginal hitting sets imply super-polynomial lower bounds for permanent.
ITCS
Maurice J. Jansen, Rahul Santhanam
2012 — conf
On the Limits of Sparsification.
ICALP (1)
Rahul Santhanam, Srikanth Srinivasan
2012 J jnl
Pebbles and Branching Programs for Tree Evaluation.
ACM Trans. Comput. Theory
Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
2012 A conf
Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes.
STACS
Maurice J. Jansen, Rahul Santhanam
2012 J jnl
The Complexity of Explicit Constructions.
Theory Comput. Syst.
Rahul Santhanam
2012 J jnl
Uniform Circuits, Lower Bounds, and QBF Algorithms.
Electron. Colloquium Comput. Complex.
Rahul Santhanam, Ryan Williams
2011 — conf
Exponential Lower Bounds for AC
ICALP (1)
Yuval Filmus, Toniann Pitassi, Rahul Santhanam
2011 J jnl
Infeasibility of instance compression and succinct PCPs for NP.
J. Comput. Syst. Sci.
Lance Fortnow, Rahul Santhanam
2011 J jnl
Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent.
Electron. Colloquium Comput. Complex.
Maurice J. Jansen, Rahul Santhanam
2011 J jnl
On the Limits of Sparsification.
Electron. Colloquium Comput. Complex.
Rahul Santhanam, Srikanth Srinivasan
2011 — conf
Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth.
ICALP (1)
Maurice J. Jansen, Rahul Santhanam
2011 — conf
Robust Simulations and Significant Separations.
ICALP (1)
Lance Fortnow, Rahul Santhanam
2011 J jnl
Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes.
Electron. Colloquium Comput. Complex.
Maurice J. Jansen, Rahul Santhanam
2010 A conf
Bounding Rationality by Discounting Time.
ICS
Lance Fortnow, Rahul Santhanam
2010 A conf
Effectively Polynomial Simulations.
ICS
Toniann Pitassi, Rahul Santhanam
2010 A* conf
Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability.
FOCS
Rahul Santhanam
2010 J jnl
Pebbles and Branching Programs for Tree Evaluation
CoRR
Stephen A. Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam
2010 J jnl
Robust Simulations and Significant Separations
CoRR
Lance Fortnow, Rahul Santhanam
2010 C conf
The Complexity of Explicit Constructions.
CiE
Rahul Santhanam
2009 J jnl
Bounding Rationality by Discounting Time
CoRR
Lance Fortnow, Rahul Santhanam
2009 B conf
Branching Programs for Tree Evaluation.
MFCS
Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr
2009 J jnl
Circuit Lower Bounds for Merlin--Arthur Classes.
SIAM J. Comput.
Rahul Santhanam
2009 A conf
Fixed-Polynomial Size Circuit Bounds.
CCC
Lance Fortnow, Rahul Santhanam, Ryan Williams
2009 — conf
Fractional Pebbling and Thrifty Branching Programs.
FSTTCS
Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr
2009 — conf
Unconditional Lower Bounds against Advice.
Algebraic Methods in Computational Complexity
Harry Buhrman, Lance Fortnow, Rahul Santhanam
2009 — conf
Unconditional Lower Bounds against Advice.
ICALP (1)
Harry Buhrman, Lance Fortnow, Rahul Santhanam
2009 J jnl
Unconditional Lower Bounds against Advice.
Electron. Colloquium Comput. Complex.
Harry Buhrman, Lance Fortnow, Rahul Santhanam
2008 A* conf
Infeasibility of instance compression and succinct PCPs for NP.
STOC
Lance Fortnow, Rahul Santhanam
2007 J jnl
Circuit Lower Bounds for Merlin-Arthur Classes.
Electron. Colloquium Comput. Complex.
Rahul Santhanam
2007 A* conf
Circuit lower bounds for Merlin-Arthur classes.
STOC
Rahul Santhanam
2007 J jnl
Infeasibility of Instance Compression and Succinct PCPs for NP.
Electron. Colloquium Comput. Complex.
Lance Fortnow, Rahul Santhanam
2007 J jnl
Time Hierarchies: A Survey.
Electron. Colloquium Comput. Complex.
Lance Fortnow, Rahul Santhanam
2006 J jnl
Fixed-Polynomial Size Circuit Bounds.
Electron. Colloquium Comput. Complex.
Lance Fortnow, Rahul Santhanam
2006 A* conf
Graph model selection using maximum likelihood.
ICML
Ivona Bezáková, Adam Kalai, Rahul Santhanam
2006 J jnl
Graph splicing systems.
Discret. Appl. Math.
Rahul Santhanam, Kamala Krithivasan
2006 J jnl
Making Hard Problems Harder
Electron. Colloquium Comput. Complex.
Joshua Buresh-Oppenheim, Rahul Santhanam
2006 A conf
Making Hard Problems Harder.
CCC
Joshua Buresh-Oppenheim, Rahul Santhanam
2006 — conf
Some Results on Average-Case Hardness Within the Polynomial Hierarchy.
FSTTCS
Aduri Pavan, Rahul Santhanam, N. V. Vinodchandran
2006 J jnl
Uniform Hardness Amplification in NP via Monotone Codes.
Electron. Colloquium Comput. Complex.
Joshua Buresh-Oppenheim, Valentine Kabanets, Rahul Santhanam
2005 A* conf
Hierarchies for semantic classes.
STOC
Lance Fortnow, Rahul Santhanam, Luca Trevisan
2005 J jnl
Holographic Proofs and Derandmization.
SIAM J. Comput.
Dieter van Melkebeek, Rahul Santhanam
2004 A* conf
Hierarchy Theorems for Probabilistic Polynomial Time.
FOCS
Lance Fortnow, Rahul Santhanam
2004 J jnl
Promise Hierarchies
Electron. Colloquium Comput. Complex.
Lance Fortnow, Rahul Santhanam, Luca Trevisan
2003 A conf
Holographic Proofs and Derandomization.
CCC
Rahul Santhanam, Dieter van Melkebeek
2002 J jnl
Resource Tradeoffs and Derandomization
Electron. Colloquium Comput. Complex.
Rahul Santhanam
2001 J jnl
Lower bounds on the complexity of recognizing SAT by Turing machines.
Inf. Process. Lett.
Rahul Santhanam
2001 A conf
On Separators, Segregators and Time versus Space.
CCC
Rahul Santhanam
2001 J jnl
On segregators, separators and time versus space
Electron. Colloquium Comput. Complex.
Rahul Santhanam