Malvika Raj Joshi

Publications and Preprints

^* Indicates equal contribution by all authors, author order is alphabetical.

• Parity ∉ QAC⁰ ⟺ QAC⁰ is Fourier-Concentrated
  Lucas Gretta, Meghal Gupta, and Malvika Raj Joshi^*.
  In 67th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2026.
  Machtey Best Student Paper Award
  arXiv

  BibTeX

  @misc{gretta2026paritynotinqac0iff,
  title={Parity $\notin$ QAC0 $\iff$ QAC0 is Fourier-Concentrated}, 
  author={Lucas Gretta and Meghal Gupta and Malvika Raj Joshi},
  year={2026},
  eprint={2604.02793},
  archivePrefix={arXiv},
  primaryClass={quant-ph},
  url={https://arxiv.org/abs/2604.02793}
  }

• Polylogarithmic-Weight Dicke States in QAC⁰ and Arbitrary Symmetric States in QAC⁰_f
  Lucas Gretta, Meghal Gupta, and Malvika Raj Joshi^*.
  In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2027.
  arXiv

  BibTeX

  @misc{gretta2026polylogarithmicweightdickestates,
  title={Polylogarithmic-Weight Dicke States in QAC$^0$ and Arbitrary Symmetric States in QAC$^0_f$}, 
  author={Lucas Gretta and Meghal Gupta and Malvika Raj Joshi},
  year={2026},
  eprint={2604.15298},
  archivePrefix={arXiv},
  primaryClass={quant-ph},
  url={https://arxiv.org/abs/2604.15298}
  }

• Shor's Algorithm Requires Fanout
  Lucas Gretta and Malvika Raj Joshi^*.
  2026.
  arXiv

  BibTeX

  @misc{gretta2026shorsalgorithmrequiresfanout,
  title={Shor's Algorithm Requires Fanout}, 
  author={Lucas Gretta and Malvika Raj Joshi},
  year={2026},
  eprint={2608.06703},
  archivePrefix={arXiv},
  primaryClass={quant-ph},
  url={https://arxiv.org/abs/2608.06703} 
  }

• Improved Lower Bounds for QAC⁰
  Malvika Raj Joshi^*, Avishay Tal, Francisca Vasconcelos, and John Wright.
  In 58th Annual ACM Symposium on Theory of Computing (STOC), 2026.
  Proceedings arXiv Slides

  BibTeX

  @inproceedings{joshi2026improvedlowerboundsqac0,
  author = {Joshi, Malvika Raj and Tal, Avishay and Vasconcelos, Francisca and Wright, John},
  title = {Improved Lower Bounds for QAC0},
  year = {2026},
  isbn = {9798400725364},
  publisher = {Association for Computing Machinery},
  address = {New York, NY, USA},
  url = {https://doi.org/10.1145/3798129.3800922},
  doi = {10.1145/3798129.3800922},
  booktitle = {Proceedings of the 58th Annual ACM Symposium on Theory of Computing},
  pages = {2199–2209},
  numpages = {11},
  keywords = {QAC0, analysis of Boolean functions, quantum circuit complexity},
  location = {Salt Lake City, UT, USA},
  series = {STOC '26}
  }

• QAC⁰ Can Prepare Every Logarithmic-Qubit State
  Lucas Gretta, Meghal Gupta, and Malvika Raj Joshi^*.
  2026.
  arXiv

  BibTeX

  @misc{gretta2026qac0preparelogarithmicqubitstate,
  title={QAC0 Can Prepare Every Logarithmic-Qubit State},
  author={Lucas Gretta and Meghal Gupta and Malvika Raj Joshi},
  year={2026},
  eprint={2609.17408},
  archivePrefix={arXiv},
  primaryClass={quant-ph},
  url={https://arxiv.org/abs/2609.17408},}

• Lexicure: Efficient, Encrypted Lexical Search
  Malvika Raj Joshi, Tal Wagner, Shai Halevi, and Nina Mishra.
  2026.
  ePrint

  BibTeX

  @misc{cryptoeprint:2026/2182,
  author = {Malvika Raj Joshi and Tal Wagner and Shai Halevi and Nina Mishra},
  title = {Lexicure: Efficient, Encrypted Lexical Search},
  howpublished = {Cryptology {ePrint} Archive, Paper 2026/2182},
  year = {2026},
  url = {https://eprint.iacr.org/2026/2182}
  }

• Constant-Depth Unitary Preparation of Dicke States
  Malvika Raj Joshi^* and Francisca Vasconcelos.
  2026.
  arXiv

  BibTeX

  @misc{joshi2026constantdepthunitarypreparationdicke,
  title={Constant-Depth Unitary Preparation of Dicke States}, 
  author={Malvika Raj Joshi and Francisca Vasconcelos},
  year={2026},
  eprint={2601.10693},
  archivePrefix={arXiv},
  primaryClass={quant-ph},
  url={https://arxiv.org/abs/2601.10693} 
  }

• 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

  BibTeX

  @InProceedings{akmal_et_al:LIPIcs.ITCS.2022.3,
    author =  {Akmal, Shyan and Chen, Lijie and Jin, Ce and Raj, Malvika and Williams, Ryan},
    title = {{Improved Merlin-Arthur Protocols for Central Problems in Fine-Grained Complexity}},
    booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
    pages = {3:1--3:25},
    series =  {Leibniz International Proceedings in Informatics (LIPIcs)},
    ISBN =  {978-3-95977-217-4},
    ISSN =  {1868-8969},
    year =  {2022},
    volume =  {215},
    editor =  {Braverman, Mark},
    publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
    address = {Dagstuhl, Germany},
    URL =   {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.3},
    URN =   {urn:nbn:de:0030-drops-155991},
    doi =   {10.4230/LIPIcs.ITCS.2022.3},
    annote =  {Keywords: Fine-grained complexity, Merlin-Arthur proofs}
  }

← Back