# Mitali Bafna

mitalibafna at gmail.com

mitalib@andrew.cmu.edu

Office - 7123

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

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

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.