I am a graduate student in theoretical computer science at Harvard University where I am advised by Madhu Sudan.

Before this I was an undergrad in computer science at IIT Madras.

I am interested in complexity theory and algorithms, specifically hardness of approximation and sum of squares algorithms.


  • Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments.
    Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett
    STOC 2022
  • High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games.
    Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett
    SODA 2022
  • Optimal Fine-grained Hardness of Approximation of Linear Equations.
    Mitali Bafna, Nikhil Vyas
    ICALP 2021
  • Playing Unique Games on Certified Small-Set Expanders.
    Mitali Bafna, Boaz Barak, Pravesh Kothari, Tselil Schramm, David Steurer
    STOC 2021
  • Local decoding and testing of polynomials over grids
    Mitali Bafna, Srikanth Srinivasan, Madhu Sudan
    Random Structures and Algorithms (Journal)
  • Imperfect Gaps in Gap-ETH and PCPs.
    Mitali Bafna, Nikhil Vyas
    CCC 2019
  • Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation.
    Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan
    SODA 2019
  • Thwarting Adversarial Examples: An L_0-Robust Sparse Fourier Transform.
    Mitali Bafna, Jack Murtagh, Nikhil Vyas
    NeurIPS 2018
  • The Price of Selection in Differential Privacy.
    Mitali Bafna, Jonathan Ullman
    COLT 2017
  • On the Sensitivity Conjecture for Read-k Formulas
    Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker
    MFCS 2016
  • Manuscripts

  • Elementary analysis of isolated zeroes of a polynomial system.
    Mitali Bafna, Madhu Sudan, Santhoshini Velusamy, David Xiang
  • An Exposition of Dinur-Khot-Kindler-Minzer-Safra’s Proof for the 2-to-2 Games Conjecture.
    Mitali Bafna, Chi-Ning Chou, Zhao Song
  • Teaching

  • Information Theory in Computer Science (Harvard CS229r, Spring 2019)
    Graduate Teaching Fellow, assistant to Madhu Sudan.