7 papers
Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes
Irit Dinur, Ting-Chun Lin, Thomas Vidick
We introduce a high-dimensional cubical complex, for any dimension t>0, and apply it to the design of quantum locally testable codes. Our complex is a natural generalization of the…
Coboundary and cosystolic expansion without dependence on dimension or degree
Yotam Dikstein, Irit Dinur
We give new bounds on the cosystolic expansion constants of several families of high dimensional expanders, and the known coboundary expansion constants of order complexes of homog…
Sparse juntas on the biased hypercube
Irit Dinur, Yuval Filmus, Prahladh Harsha
We give a structure theorem for Boolean functions on the -biased hypercube which are -close to degree in , showing that they are close to sparse juntas. Our structu…
Non-commutative error correcting codes and proper subgroup testing
Michael Chapman, Irit Dinur, Alexander Lubotzky
Property testing has been a major area of research in computer science in the last three decades. By property testing we refer to an ensemble of problems, results and algorithms wh…
Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
Yotam Dikstein, Irit Dinur, Alexander Lubotzky
We solve the derandomized direct product testing question in the low acceptance regime, by constructing new high dimensional expanders that have no small connected covers. We show…
Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers
Yotam Dikstein, Irit Dinur
Given a family of subsets of and an ensemble of local functions , an agreement test is a randomized property tester that is supposed to test…