Mitali Bafna

According to our database, Mitali Bafna authored at least 19 papers between 2016 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Constant Degree Direct Product Testers with Small Soundness.

Mitali Bafna, Noam Lifshitz, Dor Minzer

Electron. Colloquium Comput. Complex., 2024

Quasi-Linear Size PCPs with Small Soundness from HDX.

Mitali Bafna, Dor Minzer, Nikhil Vyas

CoRR, 2024

Rounding Large Independent Sets on Expanders.

Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari

CoRR, 2024

Solving Unique Games over Globally Hypercontractive Graphs.

Mitali Bafna, Dor Minzer

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Characterizing Direct Product Testing via Coboundary Expansion.

Mitali Bafna, Dor Minzer

Electron. Colloquium Comput. Complex., 2023

2022

Hypercontractivity on high dimensional expanders.

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games.

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Polynomial-Time Power-Sum Decomposition of Polynomials.

Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari, Jeff Xu

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments.

Mitali Bafna, Max Hopkins, Tali Kaufman, Shachar Lovett

Electron. Colloquium Comput. Complex., 2021

Playing unique games on certified small-set expanders.

Mitali Bafna, Boaz Barak, Pravesh K. Kothari, Tselil Schramm, David Steurer

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Optimal Fine-Grained Hardness of Approximation of Linear Equations.

Mitali Bafna, Nikhil Vyas

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Local decoding and testing of polynomials over grids.

Mitali Bafna, Srikanth Srinivasan, Madhu Sudan

Random Struct. Algorithms, 2020

Improving Accuracy of Differentially Private Kronecker Social Networks via Graph Clustering.

Arinjita Paul, Vorapong Suppakitpaisarn, Mitali Bafna, C. Pandu Rangan

Proceedings of the 2020 International Symposium on Networks, Computers and Communications, 2020

2019

Imperfect Gaps in Gap-ETH and PCPs.

Mitali Bafna, Nikhil Vyas

Proceedings of the 34th Computational Complexity Conference, 2019

2018

Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation.

Mitali Bafna, Badih Ghazi, Noah Golowich, Madhu Sudan

Electron. Colloquium Comput. Complex., 2018

Thwarting Adversarial Examples: An L₀-RobustSparse Fourier Transform.

Mitali Bafna, Jack Murtagh, Nikhil Vyas

CoRR, 2018

Thwarting Adversarial Examples: An L_0-Robust Sparse Fourier Transform.

Mitali Bafna, Jack Murtagh, Nikhil Vyas

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

2017

The Price of Selection in Differential Privacy.

Mitali Bafna, Jonathan R. Ullman

Proceedings of the 30th Conference on Learning Theory, 2017

2016

On the Sensitivity Conjecture for Read-k Formulas.

Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker

Electron. Colloquium Comput. Complex., 2016