标题： 一个近似最优的二次Goldreich-Levin算法 显示英文标题

标题： A near-optimal Quadratic Goldreich-Levin algorithm

摘要： 本文给出了一个接近最优的二次Goldreich-Levin算法，在以下方面接近最优： 给定布尔超立方体$\mathbb{F}_2^n$上的一个有界函数$f$和任意$\varepsilon>0$，该算法返回一个二次多项式$q: \mathbb{F}_2^n \to \mathbb{F}_2$，使得$f$与函数$(-1)^q$的相关性在一个加法因子$\varepsilon$内达到与二次相位函数的最大可能相关性。 该算法运行时间是$O_\varepsilon(n^3)$，并且对$f$进行了$O_\varepsilon(n^2\log n)$次查询，这与信息论下限$\Omega(n^2)$次查询在对数因子内匹配。 由此，我们得到一系列推论： - 一个近似最优的二次Reed-Muller码自校正器，该校正器对布尔函数$O_\varepsilon(n^2\log n)$做$f$次查询，并返回一个与$q$相对汉明距离在最小距离$f$的$\varepsilon$范围内的二次多项式。 - 一个关于三阶Gowers一致性范数的算法逆定理。 一个算法对有界函数$f$进行多项式次数的查询，并将$f$分解为多项式$(1/\varepsilon)$次二次相位函数之和以及误差项，误差项的阶数为$\varepsilon$。 我们的算法采用了最近量子学习理论研究中的思想。 它的构建方式偏离了之前基于三阶一致范数逆定理的算法证明方法（特别是不依赖于近期多项式 Freĭman-Ruzsa 猜想的解决）。 显示英文摘要

摘要： In this paper, we give a quadratic Goldreich-Levin algorithm that is close to optimal in the following ways. Given a bounded function $f$ on the Boolean hypercube $\mathbb{F}_2^n$ and any $\varepsilon>0$, the algorithm returns a quadratic polynomial $q: \mathbb{F}_2^n \to \mathbb{F}_2$ so that the correlation of $f$ with the function $(-1)^q$ is within an additive $\varepsilon$ of the maximum possible correlation with a quadratic phase function. The algorithm runs in $O_\varepsilon(n^3)$ time and makes $O_\varepsilon(n^2\log n)$ queries to $f$, which matches the information-theoretic lower bound of $\Omega(n^2)$ queries up to a logarithmic factor. As a result, we obtain a number of corollaries: - A near-optimal self-corrector of quadratic Reed-Muller codes, which makes $O_\varepsilon(n^2\log n)$ queries to a Boolean function $f$ and returns a quadratic polynomial $q$ whose relative Hamming distance to $f$ is within $\varepsilon$ of the minimum distance. - An algorithmic polynomial inverse theorem for the order-3 Gowers uniformity norm. - An algorithm that makes a polynomial number of queries to a bounded function $f$ and decomposes $f$ as a sum of poly$(1/\varepsilon)$ quadratic phase functions and error terms of order $\varepsilon$. Our algorithm is obtained using ideas from recent work on quantum learning theory. Its construction deviates from previous approaches based on algorithmic proofs of the inverse theorem for the order-3 uniformity norm (and in particular does not rely on the recent resolution of the polynomial Fre\u{\i}man-Ruzsa conjecture).