Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
STOC Conference 2024 Conference Paper
Let X be a family of k -element subsets of [ n ] and let { f s : s →Σ : s ∈ X } be an ensemble of local functions, each defined over a subset s ⊂ [ n ]. Is there a global function G :[ n ]→Σ such that f s = G | s for all s ∈ X ? An agreement test is a randomized property tester for this question.
FOCS Conference 2024 Conference Paper
We prove optimal concentration of measure for lifted functions on high dimensional expanders (HDX). Let $X$ be a $k$ -dimensional HDX. We show for any $i \leq k$ and function $f: X(i)\rightarrow [0, 1]$: \begin{equation*}\underset{s \in X(k)}{\mathbb{P}}[\vert \underset{t \subseteq s}{\mathbb{E}}[f(t)]-\mu\vert \geqslant \varepsilon] \leqslant \exp \left(-\varepsilon^2 \frac{k}{i}\right). \end{equation*} Using this fact, we prove that high dimensional expanders are reverse hypercontractive, a powerful functional inequality from discrete analysis implying that for any sets $A, B \subset X(k)$, the probability a $\rho$ -correlated pair passes between them is at least \begin{equation*}\underset{s, s^{\prime} \sim T_\rho}{\mathbb{P}}\left[s \in A, s^{\prime} \in B\right] \geqslant \mathbb{P}[A]^{O(1)} \mathbb{P}[B]^{O(1)}. \end{equation*} Our results hold under weak spectral assumptions on $X$. Namely we prove exponential concentration of measure for any complex below the ‘Trickling-Down Threshold’ (beyond which concentration may be arbitrarily poor), and optimal concentration for $\sqrt{k}$. skeletons of such complexes. We also show optimal bounds for the top dimension of stronger HDX among other settings. We leverage our inequalities to prove several new agreement testing theorems on high dimensional expanders, including a new 99%-regime test for subsets, and a variant of the ‘Z-test’ achieving inverse exponential soundness under the stronger assumption of $\ell_{\infty}$ -expansion. The latter gives rise to the first optimal testers beyond the complete complex and products, a stepping stone toward the use of HDX in strong soundness PCPs. We also give applications within expansion, analysis, combinatorics, and coding theory, including a proof that two-sided HDX have optimal geometric overlap (giving the first explicit bounded-degree construction), near-optimal double samplers, new super-exponential degree lower bounds for certain HDX, distance-amplified list-decodable and locally testable codes, a Frankl+Rödl Theorem, and more.
FOCS Conference 2024 Conference Paper
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 that our complexes have swap cocycle expansion, which allows us to deduce the agreement theorem by relying on previous work. Derandomized direct product testing, also known as agreement testing, is the following problem. Let $X$ be a family of k-element subsets of $[N]$ and let $\{f_{s}: s\rightarrow\Sigma\vert s\in X\}$ be an ensemble of local functions, each defined over a subset $s\subset\lceil N$. Suppose that we run the following so-called agreement test: choose a random pair of sets $s_{1}, s_{2}\in X$ that intersect on $\sqrt{k}$ elements, and accept if $f_{s_{1}}, f_{s_{2}}$ agree on the elements in $s_{1}\cap s_{2}$. We denote the success probability of this test by Agree $\{f_{s}\})$ Given that Agree $(\{f_{s}\})=\varepsilon > 0$ is there a global function $G: [N]\rightarrow\Sigma$ such that $f_{s}=G\vert _{s}$ for a non-negligible fraction of $s\in X\? $ We construct a family $X$ of k-subsets of $[N]$ such that $\vert X\vert =O(N)$, and such that it satisfies the low acceptance agreement theorem. Namely, $\text{Agree}\left(\left\{f_s\right\}\right)>\varepsilon \Longrightarrow \exists G: [N] \rightarrow \Sigma, \quad \underset{s}{\mathbb{P}}\left[\left. f_s \stackrel{0. 99}{\approx} G\right\vert_s\right] \geqslant \text{poly}(\varepsilon)$. A key idea is to replace the well-studied LSV complexes by symplectic high dimensional expanders (HDXs). The family $X$ is just the k-faces of the new symplectic HDXs. The latter serve our needs better since their fundamental group satisfies the congruence subgroup property, which implies that they lack small covers. We also give a polynomial-time algorithm to construct this family of sym-plectic HDXs.
FOCS Conference 2019 Conference Paper
We introduce a framework of layered subsets, and give a sufficient condition for when a set system supports an agreement test. Agreement testing is a certain type of property testing that generalizes PCP tests such as the plane vs. plane test. Previous work has shown that high dimensional expansion is useful for agreement tests. We extend these results to more general families of subsets, beyond simplicial complexes. These include - Agreement tests for set systems whose sets are faces of high dimensional expanders. Our new tests apply to all dimensions of complexes both in case of two-sided expansion and in the case of one sided partite expansion. This improves and extends an earlier work of Dinur and Kaufman (FOCS 2017) and applies to matroids, and potentially many additional complexes. - Agreement tests for set systems whose sets are neighborhoods of vertices in a high dimensional expander. This family resembles the expander neighborhood family used in the gap-amplification proof of the PCP theorem. This set system is quite natural yet does not sit in a simplicial complex, and demonstrates some versatility in our proof technique. - Agreement tests on families of subspaces (also known as the Grassmann poset). This extends the classical low degree agreement tests beyond the setting of low degree polynomials. Our analysis relies on a new random walk on simplicial complexes which we call the “complement random walk” and which may be of independent interest. This random walk generalizes the non-lazy random walk on a graph to higher dimensions, and has significantly better expansion than previously-studied random walks on simplicial complexes.