Rahul Santhanam

University of Oxford — United Kingdom

Computer Science · Physical Sciences

18h-index1.3kcitations132works0.12yr avg
OpenAlex↗ORCID↗Google Scholar↗Lab page↗

Accepting Students?

No reports yet. Know if this professor is taking students?

Research Topics

Complexity and Algorithms in Graphs(94), Machine Learning and Algorithms(45), Cryptography and Data Security(36), Advanced Graph Theory Research(31), Computability, Logic, AI Algorithms(29)

Publications132 total

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)·2025Open Access
Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity
SIAM Journal on Computing·2025
On the Structure of Learnability beyond P/poly
Computational Complexity·2025· 1 citedOpen Access
Learning algorithms versus automatability of Frege systems
Journal of Mathematical Logic·2024
On the Complexity of Avoiding Heavy Elements
2024
Constructive Separations and Their Consequences
TheoretiCS·2024Open Access
From Proof Complexity to Circuit Complexity via Interactive Protocols
DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)·2024Open Access
From Proof Complexity to Circuit Complexity via Interactive Protocols
arXiv (Cornell University)·2024Open Access
Towards P$\ne$NP from Extended Frege lower bounds
arXiv (Cornell University)·2023Open Access
Polynomial-Time Pseudodeterministic Construction of Primes
2023· 6 cited
Polynomial-Time Pseudodeterministic Construction of Primes
arXiv (Cornell University)·2023· 1 citedOpen Access
On the Range Avoidance Problem for Circuits
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)·2022· 18 cited
Beyond Natural Proofs: Hardness Magnification and Locality
Journal of the ACM·2022· 10 cited
Robustness of average-case meta-complexity via pseudorandomness
2022· 13 citedOpen Access
Expander-Based Cryptography Meets Natural Proofs
Computational Complexity·2022· 1 citedOpen Access
Constructive Separations and Their Consequences
2022· 4 citedOpen Access
Analysis of Political Polarization and Economic Recovery in Coronavirus Policy
SSRN Electronic Journal·2022· 1 citedOpen Access
Learning Algorithms Versus Automatability of Frege Systems
arXiv (Cornell University)·2021Open Access
Pseudodeterministic algorithms and the structure of probabilistic time
2021· 1 citedOpen Access
Iterated lower bound formulas: a diagonalization-based approach to proof complexity
2021· 4 cited
page 1 of 7Next →

Frequent Co-authors

Igor Carboni Oliveira(12), Lance Fortnow(9), Ján Pich(5), Shuichi Hirahara(5), Ruiwen Chen(3), Hanlin Ren(3), Lijie Chen(3), Stephen Cook(2), Pierre McKenzie(2), Dustin Wehr(2), Mark Braverman(2), Ryan Williams(2), Ninad Rajgopal(2), Igor C. Oliveira(2), Maurice Jansen(2), Zhenjian Lu(2), Ivona Bezáková(1), Adam Tauman Kalai(1), Luca Trevisan(1), Joshua Buresh-Oppenheim(1)