research
∙
08/29/2023
New Codes on High Dimensional Expanders
We describe a new parameterized family of symmetric error-correcting cod...
share
research
∙
08/18/2023
Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers
Given a family X of subsets of [n] and an ensemble of local functions {f...
research
∙
04/04/2023
Coboundary and cosystolic expansion without dependence on dimension or degree
We give new bounds on the cosystolic expansion constants of several fami...
research
∙
01/08/2023
Bipartite unique-neighbour expanders via Ramanujan graphs
We construct an infinite family of bounded-degree bipartite unique-neigh...
research
∙
07/25/2022
Good Locally Testable Codes
An explicit construction of locally testable codes of constant rate, con...
research
∙
03/03/2022
A Characterization of Multiclass Learnability
A seminal result in learning theory characterizes the PAC learnability o...
research
∙
11/08/2021
Locally Testable Codes with constant rate, distance, and locality
A locally testable code (LTC) is an error-correcting code that has a pro...
research
∙
09/11/2020
Explicit SoS lower bounds from high-dimensional expanders
We construct an explicit family of 3XOR instances which is hard for O(√(...
research
∙
05/03/2020
Locally testable codes via high-dimensional expanders
Locally testable codes (LTC) are error-correcting codes that have a loca...
research
∙
09/02/2019
Agreement testing theorems on layered set systems
We introduce a framework of layered subsets, and give a sufficient condi...
research
∙
04/29/2019
Testing tensor products
A function f:[n]^d→F_2 is a direct sum if it is of the form f((a_1,...,...
research
∙
08/01/2018
List Decoding with Double Samplers
We develop the notion of "double samplers", first introduced by Dinur an...
research
∙
05/10/2018
ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network
We study the 2-ary constraint satisfaction problems (2-CSPs), which can ...
research
∙
04/22/2018
Boolean functions on high-dimensional expanders
We initiate the study of Boolean function analysis on high-dimensional e...
research
∙
11/26/2017
Low degree almost Boolean functions are sparse juntas
Nisan and Szegedy showed that low degree Boolean functions are juntas. K...
research
∙
11/26/2017