research
∙
08/29/2023
Adversarial Low Degree Testing
In the t-online-erasure model in property testing, an adversary is allow...
share
research
∙
08/18/2023
Characterizing Direct Product Testing via Coboundary Expansion
A d-dimensional simplicial complex X is said to support a direct product...
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...
research
∙
07/30/2023
On Approximability of Satisfiable k-CSPs: IV
We prove a stability result for general 3-wise correlations over distrib...
research
∙
07/14/2023
Influences in Mixing Measures
The theory of influences in product measures has profound applications i...
research
∙
04/14/2023
Solving Unique Games over Globally Hypercontractive Graphs
We study the complexity of affine Unique-Games (UG) over globally hyperc...
research
∙
04/12/2023
Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries
A local tester for an error correcting code C⊆Σ^n is a tester that makes...
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/17/2022
Rounding via Low Dimensional Embeddings
A regular graph G = (V,E) is an (ε,γ) small-set expander if for any set ...
research
∙
11/17/2022
Approaching the Soundness Barrier: A Near Optimal Analysis of the Cube versus Cube Test
The Cube versus Cube test is a variant of the well-known Plane versus Pl...
research
∙
11/16/2022
Improved Monotonicity Testers via Hypercube Embeddings
We show improved monotonicity testers for the Boolean hypercube under th...
research
∙
04/14/2022
Isoperimetric Inequalities Made Simpler
We give an alternative, simple method to prove isoperimetric inequalitie...
research
∙
02/17/2022
Improved Optimal Testing Results from Global Hypercontractivity
The problem of testing low-degree polynomials has received significant a...
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
∙
05/31/2021
Approximate polymorphisms
For a function g{0,1}^m→{0,1}, a function f{0,1}^n→{0,1} is called a g-p...
research
∙
03/06/2021
New Separations Results for External Information
We obtain new separation results for the two-party external information ...
research
∙
11/08/2020
Optimal tiling of the Euclidean space using symmetric bodies
What is the least surface area of a symmetric body B whose ℤ^n translati...
research
∙
09/11/2020
Hypercontractivity on the symmetric group
The hypercontractive inequality is a fundamental result in analysis, wit...
research
∙
11/24/2019
Revisiting Bourgain-Kalai and Fourier Entropies
The total influence of a function is a central notion in analysis of Boo...
research
∙
11/01/2019