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
    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.