Irit Dinur

collaborators

Showing cs.CCShow all

3 papers · 1 filter

cs.CC2024

Sparse juntas on the biased hypercube

Irit Dinur, Yuval Filmus, Prahladh Harsha

We give a structure theorem for Boolean functions on the $p$ -biased hypercube which are $I^µ$ -close to degree $d$ in $L_{2}$ , showing that they are close to sparse juntas. Our structu…

cs.CC2024

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…

cs.CC2024

Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers

Yotam Dikstein, Irit Dinur

Given a family $X$ of subsets of $[n]$ and an ensemble of local functions ${f_{s} : s \to I^£ ∣ s \in X}$ , an agreement test is a randomized property tester that is supposed to test…