English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given a family $X$ of subsets of $[n]$ and an ensemble of local functions$\{f_s:s\to\Sigma\; | \; s\in X\}$, an agreement test is a randomized propertytester that is supposed to test whether there is some global function$G:[n]\to\Sigma$ such that $f_s=G|_s$ for many sets $s$. A "classical"small-soundness agreement theorem is a list-decoding $(LD)$ statement, sayingthat \[\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]\geqpoly(\varepsilon),\;i=1,\dots,\ell. \] Such a statement is motivated by PCPquestions 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$. Ithas been an open challenge to analyze their small soundness behavior.Surprisingly, the small soundness behavior turns out to be governed by thetopological 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 expansionproperty), we replace the $(LD)$ by a weaker statement we call lift-decoding:  \[ \tag{$LFD$}  Agree(\{f_s\})> \varepsilon \Longrightarrow \quad \exists\text{ cover}\rho:Y\twoheadrightarrow X,\text{ and }G:Y(0)\to\Sigma,\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$\rho(\tilde s)=s$.  The additional expansion property is cosystolic expansion of a complexderived from $X$ holds for the spherical building and for quotients of theBruhat-Tits building.

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