Malvika Raj Joshi

Download CV malvika [at] berkeley [dot] edu Publications
Malvika Raj Joshi

I am a Ph.D. student in Computer Science at the University of California, Berkeley, where I am fortunate to be co-advised by Umesh Vazirani and John Wright. I am drawn to foundational questions about physics and computation, and I enjoy connecting the insights I learn from these questions to real-world applications in cryptography and privacy.

My primary research area is quantum complexity theory, specifically understanding the power of shallow quantum circuits (QAC0). These circuits are particularly relevant in the current NISQ era, where quantum devices are noisy and limited to constant depth. The question that keeps me up at night is whether QAC0 can implement the FANOUT operation (Parity ∈ QAC0?). The answer determines the power of QAC0 relative to classical circuit classes, from AC0 to TC0, as well as its ability to perform inherently quantum tasks such as preparing highly entangled states and the Quantum Fourier Transform.

Before starting my Ph.D. at Berkeley, I completed my Master's at Massachusetts Institute of Technology (MIT), where I was advised by Aram Harrow.
Thesis: Pretending to be Quantum: A Study of IQP-Based Tests of Quantumness.

Outside of research, I enjoy windsurfing at the Berkeley Marina and learning to play the drums.

Publications

  • Parity ∉ QAC0 iff QAC0 is Fourier-Concentrated
    Lucas Gretta, Meghal Gupta, and Malvika Raj Joshi.
    2026. arXiv preprint
  • Super-Constant Weight Dicke States in Constant Depth Without Fanout
    Lucas Gretta, Meghal Gupta, and Malvika Raj Joshi.
    2026. arXiv preprint
  • Improved Lower Bounds for QAC0
    Malvika Raj Joshi, Avishay Tal, Francisca Vasconcelos, and John Wright.
    In 58th Annual ACM Symposium on Theory of Computing (STOC), 2026. arXiv
  • Constant-Depth Unitary Preparation of Dicke States
    Malvika Raj Joshi and Francisca Vasconcelos.
    2026. arXiv preprint
  • Improved Merlin–Arthur Protocols for Central Problems in Fine-Grained Complexity
    Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, and Ryan Williams.
    In 13th Innovations in Theoretical Computer Science Conference (ITCS), 2022. Proceedings, ECCC

Selected Projects

  • Applied Scientist Intern, Amazon
    East Palo Alto, May–Aug. 2025.
    Designed Lexicure, a leakage-free encrypted lexical search protocol with improved communication tradeoffs and new secure primitives for higher-degree arithmetic.
    With Tal Wagner, Shai Halevi and Nina Mishra. Manuscript under submission.
  • Open Source Software Development Intern, PyTorch
    Facebook, New York, May–Aug. 2019.
    Designed and implemented a C++ API for PyTorch Autograd, introducing native C++ support for automatic differentiation.
    PyTorch contributions

For additional research, software engineering, outreach, and teaching experience, see my CV.