9 citations · 21 across the 12 of their papers we have counts for
8 papers · 1 filter
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…
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…
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…