Low-Degree Testing Over Boolean Slices

Abstract

We study low-degree testing for group-valued functions over a Boolean slice. Specifically given a degree parameter $d$ and oracle access to a function $f:\{0,1{\}}_{n/2}^n\to G$ where $\{0,1{\}}_k^n$ denotes the set of vectors in $\{0,1{\}}^n$ of Hamming weight $k$ and $G$ is an Abelian group, the low-degree testing problem asks us to distinguish the case where $f$ is a polynomial of degree at most $d$ (with coefficients from $G$) or is $\epsilon$-far from the set of all such polynomials. Classical works in this area considered functions with domain ${\mathbb{F}}_q^n$ and range ${\mathbb{F}}_q$. More recent works have considered the setting where the domain is the Boolean cube [Bafna, Srinivasan, Sudan (Random Struct. Algorithms 2020), Amireddy, Srinivasan, Sudan (RANDOM 2023)], or when the domain is the slice (i.e., $\{0,1{\}}_k^n$) and the range is ${\mathbb{F}}_2$ [David, Dinur, Goldenberg, Kindler and Shinkar (SIAM J. Comput. 2017), Kalai, Lifshitz, Minzer and Ziegler (FOCS 2024)]. Each of the changes introduces new challenges in designing and analyzing low-degree tests and this happens again in our setting with domain being a slice and range is general. Our main theorem gives a test that makes $O_d(1)$ queries to $f$ and accepts degree-$d$ functions while rejecting functions that are $\epsilon$-far with probability $\Omega (\epsilon )$. The central proof idea is to reduce this low-degree testing problem to the problem of low-degree testing on the cube. Specifically we show how to randomly embed the $n/2$-dimensional cube $\{0,1{\}}^{n/2}$ in the $n$-dimensional slice while nearly preserving the proximity of $f$ to the space of degree-$d$ polynomials on this cube. While the embedding is simple and natural, the analysis involves a careful induction with a novel use of a basis of degree-$d$ polynomials on slices (from a work of Anstee, Rónyai and Sali (Graphs and Combinatorics 2002)).

47 pages