I am a postdoc at CMU hosted by Prof. Aayush Jain and Prof. Pravesh Kothari. Before this, I was a graduate student in theoretical computer science at Harvard University where I was advised by Prof. Madhu Sudan. Even before, I did my undergrad in computer science from IIT Madras.
My research is focussed on complexity theory and algorithms, specifically the complexity of combinatorial optimization problems, sum of squares algorithms and high dimensional expanders.


Publications

  • Solving Unique Games over Globally Hypercontractive Graphs.
    Mitali Bafna, Dor Minzer
  • Polynomial-Time Power-Sum Decomposition of Polynomials.
    Mitali Bafna, Tim Hsieh, Pravesh Kothari, Jeff Xu
    FOCS 2022
  • 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
  • Playing Unique Games on Certified Small-Set Expanders.
    Mitali Bafna, Boaz Barak, Pravesh Kothari, Tselil Schramm, David Steurer
    STOC 2021
  • Optimal Fine-grained Hardness of Approximation of Linear Equations.
    Mitali Bafna, Nikhil Vyas
    ICALP 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.