research
∙
08/12/2023
Effective Bounds for Restricted 3-Arithmetic Progressions in 𝔽_p^n
For a prime p, a restricted arithmetic progression in 𝔽_p^n is a triplet...
share
research
∙
07/30/2023
On Approximability of Satisfiable k-CSPs: IV
We prove a stability result for general 3-wise correlations over distrib...
research
∙
11/24/2022
Parallel Repetition for the GHZ Game: Exponential Decay
We show that the value of the n-fold repeated GHZ game is at most 2^-Ω(n...
research
∙
11/16/2022
Improved Monotonicity Testers via Hypercube Embeddings
We show improved monotonicity testers for the Boolean hypercube under th...
research
∙
12/07/2021
Almost Polynomial Factor Inapproximability for Parameterized k-Clique
The k-Clique problem is a canonical hard problem in parameterized comple...
research
∙
10/20/2021
An Invariance Principle for the Multi-slice, with Applications
Given an alphabet size m∈ℕ thought of as a constant, and k⃗ = (k_1,…,k_m...
research
∙
09/06/2020
Optimal Inapproximability of Satisfiable k-LIN over Non-Abelian Groups
A seminal result of Håstad [J. ACM, 48(4):798–859, 2001] shows that it i...
research
∙
10/10/2018
The Andoni--Krauthgamer--Razenshteyn characterization of sketchable norms fails for sketchable metrics
Andoni, Krauthgamer and Razenshteyn (AKR) proved (STOC 2015) that a fini...
research
∙
01/14/2018