9 citations · 21 across the 16 of their papers we have counts for
20 papers
Gap Amplification for Local Hamiltonians with Combinatorial Soundness
Mitali Bafna, Quynh T. Nguyen, Tina Zhang
The quantum PCP conjecture is one of the major open problems in quantum complexity theory. It has resisted attack in part because many primitives used in the proof of the classical…
Good Quantum Locally Testable Codes from Product Expansion
Mitali Bafna, Anqi Li, Quynh T. Nguyen
We construct quantum locally testable codes (LTCs) with constant rate, distance, soundness and locality under a variant of a product expansion conjecture of Bafna and Vyas about Re…
Constant Degree Networks for Almost-Everywhere Reliable Transmission
Mitali Bafna, Dor Minzer
In the almost-everywhere reliable message transmission problem, introduced by [Dwork, Pippenger, Peleg, Upfal'86], the goal is to design a sparse communication network that sup…
Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures
Prashanti Anderson, Mitali Bafna, Rares-Darius Buhai +2
We develop a new approach for clustering non-spherical (i.e., arbitrary component covariances) Gaussian mixture models via a subroutine, based on the sum-of-squares method, that fi…
Quasi-Linear Size PCPs with Small Soundness from HDX
Mitali Bafna, Dor Minzer, Nikhil Vyas
We construct 2-query, quasi-linear size probabilistically checkable proofs (PCPs) with arbitrarily small constant soundness, improving upon Dinur's 2-query quasi-linear size PCPs w…
Rounding Large Independent Sets on Expanders
Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari
We develop a new approach for approximating large independent sets when the input graph is a one-sided spectral expander - that is, the uniform random walk matrix of the graph has…
Constant Degree Direct Product Testers with Small Soundness
Mitali Bafna, Noam Lifshitz, Dor Minzer
Let be a -dimensional simplicial complex. A function is said to be a direct product function if there exists a function …
Characterizing Direct Product Testing via Coboundary Expansion
Mitali Bafna, Dor Minzer
A -dimensional simplicial complex is said to support a direct product tester if any locally consistent function defined on its -faces (where ) necessarily come fr…
Solving Unique Games over Globally Hypercontractive Graphs
Mitali Bafna, Dor Minzer
We study the complexity of affine Unique-Games (UG) over globally hypercontractive graphs, which are graphs that are not small set expanders but admit a useful and succinct charact…
Polynomial-Time Power-Sum Decomposition of Polynomials
Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari +1
We give efficient algorithms for finding power-sum decomposition of an input polynomial with component s. The case of linear s is equivale…
Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments
Mitali Bafna, Max Hopkins, Tali Kaufman +1
Hypercontractivity is one of the most powerful tools in Boolean function analysis. Originally studied over the discrete hypercube, recent years have seen increasing interest in ext…
Optimal Fine-grained Hardness of Approximation of Linear Equations
Mitali Bafna, Nikhil Vyas
The problem of solving linear systems is one of the most fundamental problems in computer science, where given a satisfiable linear system , for $A \in \mathbb{R}^{n \times…
Elementary analysis of isolated zeroes of a polynomial system
Mitali Bafna, Madhu Sudan, Santhoshini Velusamy +1
Wooley ({\em J. Number Theory}, 1996) gave an elementary proof of a Bezout like theorem allowing one to count the number of isolated integer roots of a system of polynomial equatio…
High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games
Mitali Bafna, Max Hopkins, Tali Kaufman +1
Higher order random walks (HD-walks) on high dimensional expanders (HDX) have seen an incredible amount of study and application since their introduction by Kaufman and Mass [KM16]…
Playing Unique Games on Certified Small-Set Expanders
Mitali Bafna, Boaz Barak, Pravesh Kothari +2
We give an algorithm for solving unique games (UG) instances whenever low-degree sum-of-squares proofs certify good bounds on the small-set-expansion of the underlying constraint g…
Imperfect Gaps in Gap-ETH and PCPs
Mitali Bafna, Nikhil Vyas
We study the role of perfect completeness in probabilistically checkable proof systems (PCPs) and give a new way to transform a PCP with imperfect completeness to a PCP with perfec…
Thwarting Adversarial Examples: An -RobustSparse Fourier Transform
Mitali Bafna, Jack Murtagh, Nikhil Vyas
We give a new algorithm for approximating the Discrete Fourier transform of an approximately sparse signal that has been corrupted by worst-case noise, namely a bounded numbe…
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation
Mitali Bafna, Badih Ghazi, Noah Golowich +1
We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively ge…
Local decoding and testing of polynomials over grids
Mitali Bafna, Srikanth Srinivasan, Madhu Sudan
The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that -variate polynomials of total degree at most over grids, i.e. sets of the form $A_1 \times A_2 \times \cdots \t…
The Price of Selection in Differential Privacy
Mitali Bafna, Jonathan Ullman
In the differentially private top- selection problem, we are given a dataset , in which each row belongs to an individual and each column correspon…