# Mitali Bafna

mitalibafna at gmail.com

mitalibafna at g.harvard.edu

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.

## Publications

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.