
Explicit SoS lower bounds from highdimensional expanders
We construct an explicit family of 3XOR instances which is hard for O(√(...
read it

Locally testable codes via highdimensional expanders
Locally testable codes (LTC) are errorcorrecting codes that have a loca...
read it

Agreement testing theorems on layered set systems
We introduce a framework of layered subsets, and give a sufficient condi...
read it

Testing tensor products
A function f:[n]^d→F_2 is a direct sum if it is of the form f((a_1,...,...
read it

List Decoding with Double Samplers
We develop the notion of "double samplers", first introduced by Dinur an...
read it

ETHHardness of Approximating 2CSPs and Directed Steiner Network
We study the 2ary constraint satisfaction problems (2CSPs), which can ...
read it

Boolean functions on highdimensional expanders
We initiate the study of Boolean function analysis on highdimensional e...
read it

Low degree almost Boolean functions are sparse juntas
Nisan and Szegedy showed that low degree Boolean functions are juntas. K...
read it

Agreement tests on graphs and hypergraphs
Agreement tests are a generalization of low degree tests that capture a ...
read it
Irit Dinur
is this you? claim profile