Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913311792037888 |
|---|---|
| author | Dikstein, Yotam Dinur, Irit |
| author_facet | Dikstein, Yotam Dinur, Irit |
| contents | Given a family $X$ of subsets of $[n]$ and an ensemble of local functions $\{f_s:s\toΣ\; | \; s\in X\}$, an agreement test is a randomized property tester that is supposed to test whether there is some global function $G:[n]\toΣ$ such that $f_s=G|_s$ for many sets $s$. A "classical" small-soundness agreement theorem is a list-decoding $(LD)$ statement, saying that \[\tag{$LD$} Agree(\{f_s\}) > \varepsilon \quad \Longrightarrow \quad \exists G^1,\dots, G^\ell,\quad P_s[f_s\overset{0.99}{\approx}G^i|_s]\geq poly(\varepsilon),\;i=1,\dots,\ell. \] Such a statement is motivated by PCP questions and has been shown in the case where $X=\binom{[n]}k$, or where $X$ is a collection of low dimensional subspaces of a vector space.
In this work we study small the case of on high dimensional expanders $X$. It has been an open challenge to analyze their small soundness behavior. Surprisingly, the small soundness behavior turns out to be governed by the topological covers of $X$.We show that:
1. If $X$ has no connected covers, then $(LD)$ holds, provided that $X$ satisfies an additional expansion property.
2. If $X$ has a connected cover, then $(LD)$ necessarily fails.
3. If $X$ has a connected cover (and assuming the additional expansion property), we replace the $(LD)$ by a weaker statement we call lift-decoding:
\[ \tag{$LFD$}
Agree(\{f_s\})> \varepsilon \Longrightarrow \quad \exists\text{ cover }ρ:Y\twoheadrightarrow X,\text{ and }G:Y(0)\toΣ,\text{ such that }\] \[P_{\tilde s\twoheadrightarrow s}[f_s \overset{0.99}{\approx} G|_{\tilde s}] \geq poly(\varepsilon),\] where ${\tilde s\twoheadrightarrow s}$ means that $ρ(\tilde s)=s$.
The additional expansion property is cosystolic expansion of a complex derived from $X$ holds for the spherical building and for quotients of the Bruhat-Tits building. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_09582 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers Dikstein, Yotam Dinur, Irit Computational Complexity Combinatorics Given a family $X$ of subsets of $[n]$ and an ensemble of local functions $\{f_s:s\toΣ\; | \; s\in X\}$, an agreement test is a randomized property tester that is supposed to test whether there is some global function $G:[n]\toΣ$ such that $f_s=G|_s$ for many sets $s$. A "classical" small-soundness agreement theorem is a list-decoding $(LD)$ statement, saying that \[\tag{$LD$} Agree(\{f_s\}) > \varepsilon \quad \Longrightarrow \quad \exists G^1,\dots, G^\ell,\quad P_s[f_s\overset{0.99}{\approx}G^i|_s]\geq poly(\varepsilon),\;i=1,\dots,\ell. \] Such a statement is motivated by PCP questions and has been shown in the case where $X=\binom{[n]}k$, or where $X$ is a collection of low dimensional subspaces of a vector space. In this work we study small the case of on high dimensional expanders $X$. It has been an open challenge to analyze their small soundness behavior. Surprisingly, the small soundness behavior turns out to be governed by the topological covers of $X$.We show that: 1. If $X$ has no connected covers, then $(LD)$ holds, provided that $X$ satisfies an additional expansion property. 2. If $X$ has a connected cover, then $(LD)$ necessarily fails. 3. If $X$ has a connected cover (and assuming the additional expansion property), we replace the $(LD)$ by a weaker statement we call lift-decoding: \[ \tag{$LFD$} Agree(\{f_s\})> \varepsilon \Longrightarrow \quad \exists\text{ cover }ρ:Y\twoheadrightarrow X,\text{ and }G:Y(0)\toΣ,\text{ such that }\] \[P_{\tilde s\twoheadrightarrow s}[f_s \overset{0.99}{\approx} G|_{\tilde s}] \geq poly(\varepsilon),\] where ${\tilde s\twoheadrightarrow s}$ means that $ρ(\tilde s)=s$. The additional expansion property is cosystolic expansion of a complex derived from $X$ holds for the spherical building and for quotients of the Bruhat-Tits building. |
| title | Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers |
| topic | Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2308.09582 |