Rahul Santhanam

ORCID

Publication Activity (10 Years)

Years Active: 2001-2024
Publications (10 Years): 92

Top Venues

Electron. Colloquium Comput. Complex.

Computational Complexity Conference

CoRR

FOCS

Publications

Noel Arteche, Erfan Khaniki, Ján Pich, Rahul Santhanam
From Proof Complexity to Circuit Complexity via Interactive Protocols. CoRR (2024)
Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
On the Complexity of Avoiding Heavy Elements. Electron. Colloquium Comput. Complex. (2024)
Zhenjian Lu, Rahul Santhanam
Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity. ICALP (2024)
Zhenjian Lu, Rahul Santhanam
Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity. Electron. Colloquium Comput. Complex. (2024)
Noel Arteche, Erfan Khaniki, Ján Pich, Rahul Santhanam
From Proof Complexity to Circuit Complexity via Interactive Protocols. ICALP (2024)
Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams
Constructive Separations and Their Consequences. TheoretiCS 3 (2024)
Ján Pich, Rahul Santhanam
Towards P $\neq$ NP from Extended Frege Lower Bounds. Electron. Colloquium Comput. Complex. (2023)
Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
Polynomial-Time Pseudodeterministic Construction of Primes. FOCS (2023)
Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
Polynomial-Time Pseudodeterministic Construction of Primes. CoRR (2023)
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau, Manaswi Paraashar
Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111). Dagstuhl Reports 13 (3) (2023)
Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam
Polynomial-Time Pseudodeterministic Construction of Primes. Electron. Colloquium Comput. Complex. (2023)
Rahul Santhanam
An Algorithmic Approach to Uniform Lower Bounds. CCC (2023)
Rahul Santhanam
An Algorithmic Approach to Uniform Lower Bounds. Electron. Colloquium Comput. Complex. (2023)
Hanlin Ren, Rahul Santhanam, Zhikun Wang
On the Range Avoidance Problem for Circuits. FOCS (2022)
Ján Pich, Rahul Santhanam
Learning Algorithms Versus Automatability of Frege Systems. ICALP (2022)
Michael Saks, Rahul Santhanam
On Randomized Reductions to the Random Strings. CCC (2022)
Hanlin Ren, Rahul Santhanam
A Relativization Perspective on Meta-Complexity. STACS (2022)
Shuichi Hirahara, Rahul Santhanam
Errorless Versus Error-Prone Average-Case Complexity. ITCS (2022)
Rahul Ilango, Hanlin Ren, Rahul Santhanam
Robustness of average-case meta-complexity via pseudorandomness. STOC (2022)
Shuichi Hirahara, Rahul Santhanam
Excluding PH Pessiland. ITCS (2022)
Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams
Constructive Separations and Their Consequences. CoRR (2022)
Rahul Santhanam
Why MCSP Is a More Important Problem Than SAT (Invited Talk). FSTTCS (2022)
Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams
Constructive Separations and Their Consequences. FOCS (2022)
Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
Beyond Natural Proofs: Hardness Magnification and Locality. J. ACM 69 (4) (2022)
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell
Expander-Based Cryptography Meets Natural Proofs. Comput. Complex. 31 (1) (2022)
Michael Saks, Rahul Santhanam
On Randomized Reductions to the Random Strings. Electron. Colloquium Comput. Complex. (2022)
Hanlin Ren, Rahul Santhanam, Zhikun Wang
On the Range Avoidance Problem for Circuits. Electron. Colloquium Comput. Complex. (2022)
Rahul Ilango, Hanlin Ren, Rahul Santhanam
Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity. Electron. Colloquium Comput. Complex. 28 (2021)
Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam
Pseudodeterministic algorithms and the structure of probabilistic time. STOC (2021)
Hanlin Ren, Rahul Santhanam
Hardness of KT Characterizes Parallel Cryptography. Computational Complexity Conference (2021)
Ján Pich, Rahul Santhanam
Learning algorithms versus automatability of Frege systems. CoRR (2021)
Lijie Chen, Ce Jin, Rahul Santhanam, R. Ryan Williams
Constructive Separations and Their Consequences. FOCS (2021)
Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam
Pseudodeterministic Algorithms and the Structure of Probabilistic Time. CoRR (2021)
Hanlin Ren, Rahul Santhanam
Hardness of KT Characterizes Parallel Cryptography. Electron. Colloquium Comput. Complex. 28 (2021)
Rahul Santhanam, Iddo Tzameret
Iterated lower bound formulas: a diagonalization-based approach to proof complexity. STOC (2021)
Ninad Rajgopal, Rahul Santhanam
On the Structure of Learnability Beyond P/Poly. APPROX-RANDOM (2021)
Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, Rahul Santhanam
On the Pseudo-Deterministic Query Complexity of NP Search Problems. Computational Complexity Conference (2021)
Rahul Santhanam, Iddo Tzameret
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity. Electron. Colloquium Comput. Complex. 28 (2021)
Igor Carboni Oliveira, Ján Pich, Rahul Santhanam
Hardness Magnification Near State-of-the-Art Lower Bounds. Theory Comput. 17 (2021)
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau
Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121). Dagstuhl Reports 11 (2) (2021)
Ján Pich, Rahul Santhanam
Strong co-nondeterministic lower bounds for NP cannot be proved feasibly. STOC (2021)
Hanlin Ren, Rahul Santhanam
Hardness of KT Characterizes Parallel Cryptography. IACR Cryptol. ePrint Arch. 2021 (2021)
Hanlin Ren, Rahul Santhanam
A Relativization Perspective on Meta-Complexity. Electron. Colloquium Comput. Complex. 28 (2021)
Ninad Rajgopal, Rahul Santhanam
On the Structure of Learnability beyond P/poly. Electron. Colloquium Comput. Complex. 28 (2021)
Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam
Pseudodeterministic Algorithms and the Structure of Probabilistic Time. Electron. Colloquium Comput. Complex. 28 (2021)
Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams
Constructive Separations and Their Consequences. Electron. Colloquium Comput. Complex. 28 (2021)
Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
Beyond Natural Proofs: Hardness Magnification and Locality. ITCS (2020)
Rahul Santhanam
Pseudorandomness and the Minimum Circuit Size Problem. ITCS (2020)
Michael Saks, Rahul Santhanam
Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions. Computational Complexity Conference (2020)
Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
Beyond Natural Proofs: Hardness Magnification and Locality. CoRR (2019)
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell
Expander-Based Cryptography Meets Natural Proofs. ITCS (2019)
Anna Gál, Rahul Santhanam, Till Tantau
Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121). Dagstuhl Reports 9 (3) (2019)
Ján Pich, Rahul Santhanam
Why are Proof Complexity Lower Bounds Hard? FOCS (2019)
Igor Carboni Oliveira, Ján Pich, Rahul Santhanam
Hardness Magnification near State-Of-The-Art Lower Bounds. Computational Complexity Conference (2019)
Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan
Parity Helps to Compute Majority. Computational Complexity Conference (2019)
Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam
Beyond Natural Proofs: Hardness Magnification and Locality. Electron. Colloquium Comput. Complex. 26 (2019)
Rahul Santhanam
Pseudorandomness and the Minimum Circuit Size Problem. Electron. Colloquium Comput. Complex. 26 (2019)
Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan
Parity helps to compute Majority. Electron. Colloquium Comput. Complex. 26 (2019)
Igor Carboni Oliveira, Rahul Santhanam
Hardness Magnification for Natural Problems. Electron. Colloquium Comput. Complex. 25 (2018)
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell
Expander-Based Cryptography Meets Natural Proofs. Electron. Colloquium Comput. Complex. 25 (2018)
Igor Carboni Oliveira, Rahul Santhanam
Pseudo-derandomizing learning and approximation. Electron. Colloquium Comput. Complex. 25 (2018)
Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits. Computational Complexity Conference (2018)
Igor Carboni Oliveira, Rahul Santhanam
Pseudo-Derandomizing Learning and Approximation. APPROX-RANDOM (2018)
Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. CoRR (2018)
Ninad Rajgopal, Rahul Santhanam, Srikanth Srinivasan
Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds. MFCS (2018)
Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits. Electron. Colloquium Comput. Complex. 25 (2018)
Ruiwen Chen, Igor Carboni Oliveira, Rahul Santhanam
An Average-Case Lower Bound Against \mathsf ACC^0 ACC 0. LATIN (2018)
Igor Carboni Oliveira, Rahul Santhanam
Hardness Magnification for Natural Problems. FOCS (2018)
Igor Carboni Oliveira, Ján Pich, Rahul Santhanam
Hardness magnification near state-of-the-art lower bounds. Electron. Colloquium Comput. Complex. 25 (2018)
Albert Atserias, Jakob Nordström, Pavel Pudlák, Rahul Santhanam
Proof Complexity (Dagstuhl Seminar 18051). Dagstuhl Reports 8 (1) (2018)
Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. Theory Comput. 14 (1) (2018)
Igor Carboni Oliveira, Rahul Santhanam
Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness. Computational Complexity Conference (2017)
Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam
An Average-Case Lower Bound against ACC^0. Electron. Colloquium Comput. Complex. 24 (2017)
Lance Fortnow, Rahul Santhanam
Robust simulations and significant separations. Inf. Comput. 256 (2017)
Shuichi Hirahara, Rahul Santhanam
On the Average-Case Complexity of MCSP and Its Variants. Computational Complexity Conference (2017)
Igor Carboni Oliveira, Rahul Santhanam
Pseudodeterministic constructions in subexponential time. STOC (2017)
Andrew McGregor, Rahul Santhanam
Special Section on the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC 2012). SIAM J. Comput. 45 (4) (2016)
Ruiwen Chen, Rahul Santhanam
Satisfiability on Mixed Instances. ITCS (2016)
Igor Carboni Oliveira, Rahul Santhanam
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness. CoRR (2016)
Lance Fortnow, Rahul Santhanam
New Non-Uniform Lower Bounds for Uniform Classes. Computational Complexity Conference (2016)
Igor Carboni Oliveira, Rahul Santhanam
Pseudodeterministic Constructions in Subexponential Time. CoRR (2016)
Igor Carboni Oliveira, Rahul Santhanam
Pseudodeterministic Constructions in Subexponential Time. Electron. Colloquium Comput. Complex. 23 (2016)
Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. Computational Complexity Conference (2016)
Igor Carboni Oliveira, Rahul Santhanam
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness. Electron. Colloquium Comput. Complex. 23 (2016)
Andrew Drucker, Jesper Nederlof, Rahul Santhanam
Exponential Time Paradigms Through the Polynomial Time Lens. ESA (2016)
Ruiwen Chen, Rahul Santhanam
Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP. Electron. Colloquium Comput. Complex. 22 (2015)
Igor Carboni Oliveira, Rahul Santhanam
Majority is Incompressible by AC^0[p] Circuits. Computational Complexity Conference (2015)
Rahul Santhanam, Richard Ryan Williams
Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity. SODA (2015)
Yuval Filmus, Toniann Pitassi, Rahul Santhanam
-Frege Imply Superpolynomial Frege Lower Bounds. ACM Trans. Comput. Theory 7 (2) (2015)
Ruiwen Chen, Rahul Santhanam
Satisfiability on Mixed Instances. Electron. Colloquium Comput. Complex. 22 (2015)
Ruiwen Chen, Rahul Santhanam
Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP. SAT (2015)
Ruiwen Chen, Rahul Santhanam, Srikanth Srinivasan
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits. Electron. Colloquium Comput. Complex. 22 (2015)
Rahul Santhanam, Ryan Williams
On Uniformity and Circuit Lower Bounds. Comput. Complex. 23 (2) (2014)
Lance Fortnow, Rahul Santhanam
Hierarchies Against Sublinear Advice. Electron. Colloquium Comput. Complex. 21 (2014)
Igor Carboni Oliveira, Rahul Santhanam
[p] circuits. Electron. Colloquium Comput. Complex. 21 (2014)
Olaf Beyersdorff, Edward A. Hirsch, Jan Krajícek, Rahul Santhanam
Optimal algorithms and proofs (Dagstuhl Seminar 14421). Dagstuhl Reports 4 (10) (2014)
Rahul Santhanam, Ryan Williams
On Medium-Uniformity and Circuit Lower Bounds. Computational Complexity Conference (2013)
Maurice J. Jansen, Rahul Santhanam
Permanent does not have succinct polynomial size arithmetic circuits of constant depth. Inf. Comput. 222 (2013)
Rahul Santhanam, Ryan Williams
New Algorithms for QBF Satisfiability and Implications for Circuit Complexity. Electron. Colloquium Comput. Complex. 20 (2013)
Maurice J. Jansen, Rahul Santhanam
Marginal hitting sets imply super-polynomial lower bounds for permanent. ITCS (2012)

Rahul Santhanam.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Rahul Santhanam