9 citations · 16 across the 4 of their papers we have counts for
7 papers
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]…
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…