About
Hi everyone! I am a post-doctoral researcher in the Algorithms and Complexity
group at the University of Cambridge, where I am fortunate to be hosted by Tom Gur. I also am a visiting researcher
in the Theory and Foundations group and the
Centre for Discrete Mathematics and its Applications (DIMAP) at the University of Warwick, where I was a post-doctoral researcher previously.
I did my D.Phil at the Algorithms and Complexity Theory group in the University of Oxford, advised by
Rahul Santhanam. Before this, I did my Master’s degree at the
Computer Science and Automation department in the Indian Institute of Science, Bengaluru, and my undergraduate degree was at the
Computer Science department in Sri Jayachamarajendra College of Engineering (SJCE), Mysuru.
My research interests are mainly in Computational Complexity Theory. In particular, I am currently interested in computational
learning theory, interactive proof systems, circuit complexity, meta-complexity, pseudorandomness, and combinatorics.
You can find my DBLP page here.
Publications and Preprints
Distribution-free Proofs of Proximity.
Hugo Aaronson, Tom Gur, Ninad Rajgopal, and Ron Rothblum
Preprint, 2023
On the Power of Interactive Proofs for Learning.
Tom Gur, Mohammad Mahdi Jahanara, Mohammad Mahdi Khodabandeh, Ninad Rajgopal, Bahar Salamatian, Igor Shinkar
STOC 2024
Optimal Testing and Containment Strategies for Universities in Mexico amid COVID-19.
with Luis Benavides-Vázquez, Hector Alonso Guzmán-Gutiérrez, Jakob Jonnerby, Philip Lazos, Edwin Lock, Francisco J.Marmolejo-Cossío, Ninad Rajgopal, and Roberto Tello-Ayala
EAAMO 2021
On the Structure of Learnability Beyond P/Poly.
Ninad Rajgopal and Rahul Santhanam
APPROX/RANDOM 2021.
Under Submission to a Journal.
Optimally Deceiving a Learning Leader in Stackelberg Games.
Georgios Birmpas, Jiarui Gan, Alexandros Hollender, Francisco J. Marmolejo-Cossio, Ninad Rajgopal, and Alexandros A. Voudouris
Journal of Artificial Intelligence Research (JAIR) 2021.
Neurips 2020.
Beyond Natural Proofs: Hardness Magnification and Locality.
Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, and Rahul Santhanam
Journal of the ACM (J.ACM) 2022.
ITCS 2020.
Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds.
Ninad Rajgopal, Rahul Santhanam, and Srikanth Srinivasan
MFCS 2018.
Improved Learning of k-Parities.
Arnab Bhattacharyya, Ameet Gadekar, and Ninad Rajgopal
Theoretical Computer Science (special edition), 2020.
COCOON 2018.
Selection lemmas for various geometric objects.
Pradeesha Ashok, Sathish Govindarajan, and Ninad Rajgopal
International Journal of Computational Geometry & Applications, 2016.
Hitting and Piercing Rectangles Induced by a Point Set.
Ninad Rajgopal, Pradeesha Ashok, Sathish Govindarajan, Abhijit Khopkar, and Neeldhara Misra
COCOON 2013.
