Anzeige
Erschienen in:
2021 | OriginalPaper | Buchkapitel
A Refinement of Cauchy-Schwarz Complexity, with Applications
verfasst von : Pablo Candela, Diego González-Sánchez, Balázs Szegedy
Erschienen in: Extended Abstracts EuroComb 2021
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Let \(\varPhi :=(\phi _i)_{i\in \;I}\) be a finite collection of linear forms \(\phi _i:\mathbb {F}_p^d\rightarrow \mathbb {F}_p\). We introduce a 2-parameter refinement of Cauchy-Schwarz (CS) complexity, called sequential Cauchy-Schwarz complexity. We prove that if \(\varPhi \) has sequential Cauchy-Schwarz complexity at most \((k,\ell )\), then \(|\mathbb {E}_{x_1,\ldots ,x_d\in \mathbb {F}_p^n}\prod _{i\in \;I}f_i(\phi _i(x_1,\ldots ,x_d))|\le \min _{i\in I}\Vert f_i\Vert _{U^{k+1}}^{2^{1-\ell }}\) for any 1-boun- ded functions \(f_i:\mathbb {F}_p^n\rightarrow \mathbb {C}\), \(i\in I\). For \(\ell =1\), this reduces to CS complexity, but for larger \(\ell \) the two notions differ. For example, let \(S_{k,M}:=\{z\in [0,p-1]^M:z_1+\cdots +z_M<k\}\), and consider \(\varPhi _{k,M}:=\big \{\phi _z(x,t_1,\ldots ,t_M):=x+z_1t_1+\cdots +z_Mt_M\;|\;z \in \;S_{k,M}\big \}\), a multivariable generalization of arithmetic progressions. We show that \(\varPhi _{k,M}\) has sequential CS complexity at most \((\min (k,M(p-1)+1)-2,\ell )\) for some finite \(\ell \), yet can have CS complexity strictly larger than \(\min (k,M(p-1)+1)-2\). Moreover, we show that \(\varPhi _{k,M}\) has True complexity \(\min (k,M(p-1)+1)-2\).
In [2], we use these results in a new proof of the inverse theorem for \(\mathbb {F}_p^n\).