Dhiraj Holden

I am a graduate student in Electrical Engineering and Computer Science at MIT in the Theory of Computation Group under the Computer Science and Artificial Intelligence Laboratory (CSAIL). I am currently advised by Shafi Goldwasser.

Research Interests: My main research focus currently is on interactive proofs and applications to various areas of theoretical computer science. Interactive proofs have a wide variety of connections to problems in computational complexity theory, cryptography, and quantum computing.

Email: dholden (at) mit (dot) edu

CV: here


  1. Doubly-Efficient Pseudo-Deterministic Proofs [pdf]
    with Michel Goemans and Shafi Goldwasser
  2. Non-Signaling Proofs with O(sqrt(log n)) Provers are in PSPACE [pdf]
    with Yael Kalai
    STOC 2020
  3. A Note on Unconditional Subexponential-time Pseudo-deterministic Algorithms for BPP Search Problems [pdf]
  4. Pseudo-Deterministic Proofs [pdf]
    with Shafi Goldwasser and Ofer Grossman
    ITCS 2018
  5. On the Power of Statistical Zero Knowledge [pdf]
    with Adam Bouland, Lijie Chen, Justin Thaler, and Prashant Vasudevan
    FOCS 2017
  6. On the Fine Grained Complexity of Polynomial Time Problems Given Correlated Instances [pdf]
    with Shafi Goldwasser
    ITCS 2017
  7. The Minimum Oracle Circuit Size Problem [pdf]
    with Eric Allender and Valentine Kabanets
    STACS 2015
  8. Fast algorithmic self-assembly of simple shapes using random agitation [pdf]
    with Ho-Lin Chen, David Doty,  Chris Thachuk, Damien Woods, and Chun-Tao Yang
    DNA 2014 
  9. Characterization of BshA, bacillithiol glycosyltransferase from Staphylococcus aureus and
    Bacillus subtilis
    with Heather Upton, Gerald L Newton, Melissa Gushiken, Kelly Lo, Robert C Fahey, and Mamta
    FEBS Letters 2012 volume 586, issue 7 2012
  10. Results on the 3x+1 and 3x+d Conjectures
    Fibonacci Quarterly volume 49, issue 2 2011

picture of me