Mitali Bafna
mitalibafna at gmail dot com
I am a postdoc at MIT Math. Before this I did a one-year postdoc at CMU hosted by Prof. Aayush Jain and Prof. Pravesh Kothari. I graduated from Harvard in 2022 advised by Prof. Madhu Sudan and was an undergrad at 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
Characterizing Direct Product Testing via Coboundary Expansion.
Mitali Bafna, Dor Minzer
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.