论文标题
立方Goldreich-Levin
Cubic Goldreich-Levin
论文作者
论文摘要
在本文中，我们给出了一个立方Goldreich-Levin算法，该算法对功能$ f \ colon \ Mathbb f_p^n \ to \ mathbb c $进行多项式疑问的查询，并产生$ f $的分解作为一个立方相位和小错误术语。这是经典Goldreich-Levin算法的自然高阶概括。古典（线性）Goldreich-Levin算法在学习理论，编码理论和伪随机构建器中具有广泛的应用，并且与傅立叶分析密切相关。另一方面，高阶Goldreich-Levin算法涉及高阶傅立叶分析中的核心问题，即Gowers $ u^k $ norms的反向理论，这些质量在附加组合中得到了充分研究。在这项工作之前，唯一已知的结果是Tulsiani和Wolf在2011年证明的二次Goldreich-Levin定理。其结果的主要步骤涉及$ u^3 $ inverse定理的算法版本。 $ u^4 $和更高规范的逆理论中出现了更多的并发症。我们的Cubic Goldreich-Levin算法是基于Gowers和Milićević的最新工作算法，这些算法证明了$ U^4 $ iNVERES定理的新定量界限。 我们的Cubic Goldreich-Levin算法是由两个主要工具构建的：算法$ u^4 $逆定理和算术分解导致Frieze-Kannan图形规则性引理的样式。作为我们主要定理的一种应用，我们解决了列表解码半径以外的立方芦苇毛刺代码的自我纠正问题。此外，我们给出纯粹的组合结果：$ u^4 $逆定理上的定量界限的改进。
In this paper, we give a cubic Goldreich-Levin algorithm which makes polynomially-many queries to a function $f \colon \mathbb F_p^n \to \mathbb C$ and produces a decomposition of $f$ as a sum of cubic phases and a small error term. This is a natural higher-order generalization of the classical Goldreich-Levin algorithm. The classical (linear) Goldreich-Levin algorithm has wide-ranging applications in learning theory, coding theory and the construction of pseudorandom generators in cryptography, as well as being closely related to Fourier analysis. Higher-order Goldreich-Levin algorithms on the other hand involve central problems in higher-order Fourier analysis, namely the inverse theory of the Gowers $U^k$ norms, which are well-studied in additive combinatorics. The only known result in this direction prior to this work is the quadratic Goldreich-Levin theorem, proved by Tulsiani and Wolf in 2011. The main step of their result involves an algorithmic version of the $U^3$ inverse theorem. More complications appear in the inverse theory of the $U^4$ and higher norms. Our cubic Goldreich-Levin algorithm is based on algorithmizing recent work by Gowers and Milićević who proved new quantitative bounds for the $U^4$ inverse theorem. Our cubic Goldreich-Levin algorithm is constructed from two main tools: an algorithmic $U^4$ inverse theorem and an arithmetic decomposition result in the style of the Frieze-Kannan graph regularity lemma. As one application of our main theorem we solve the problem of self-correction for cubic Reed-Muller codes beyond the list decoding radius. Additionally we give a purely combinatorial result: an improvement of the quantitative bounds on the $U^4$ inverse theorem.
