Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2502.01900 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912217823182848 |
|---|---|
| author | Khot, Subhash Mittal, Kunal |
| author_facet | Khot, Subhash Mittal, Kunal |
| contents | We study linearity testing over the $p$-biased hypercube $(\{0,1\}^n, μ_p^{\otimes n})$ in the 1% regime. For a distribution $ν$ supported over $\{x\in \{0,1\}^k:\sum_{i=1}^k x_i=0 \text{ (mod 2)} \}$, with marginal distribution $μ_p$ in each coordinate, the corresponding $k$-query linearity test $\text{Lin}(ν)$ proceeds as follows: Given query access to a function $f:\{0,1\}^n\to \{-1,1\}$, sample $(x_1,\dots,x_k)\sim ν^{\otimes n}$, query $f$ on $x_1,\dots,x_k$, and accept if and only if $\prod_{i\in [k]}f(x_i)=1$.
Building on the work of Bhangale, Khot, and Minzer (STOC '23), we show, for $0 < p \leq \frac{1}{2}$, that if $k \geq 1 + \frac{1}{p}$, then there exists a distribution $ν$ such that the test $\text{Lin}(ν)$ works in the 1% regime; that is, any function $f:\{0,1\}^n\to \{-1,1\}$ passing the test $\text{Lin}(ν)$ with probability $\geq \frac{1}{2}+ε$, for some constant $ε> 0$, satisfies $\Pr_{x\sim μ_p^{\otimes n}}[f(x)=g(x)] \geq \frac{1}{2}+δ$, for some linear function $g$, and a constant $δ= δ(ε)>0$.
Conversely, we show that if $k < 1+\frac{1}{p}$, then no such test $\text{Lin}(ν)$ works in the 1% regime. Our key observation is that the linearity test $\text{Lin}(ν)$ works if and only if the distribution $ν$ satisfies a certain pairwise independence property. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_01900 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Biased Linearity Testing in the 1% Regime Khot, Subhash Mittal, Kunal Computational Complexity We study linearity testing over the $p$-biased hypercube $(\{0,1\}^n, μ_p^{\otimes n})$ in the 1% regime. For a distribution $ν$ supported over $\{x\in \{0,1\}^k:\sum_{i=1}^k x_i=0 \text{ (mod 2)} \}$, with marginal distribution $μ_p$ in each coordinate, the corresponding $k$-query linearity test $\text{Lin}(ν)$ proceeds as follows: Given query access to a function $f:\{0,1\}^n\to \{-1,1\}$, sample $(x_1,\dots,x_k)\sim ν^{\otimes n}$, query $f$ on $x_1,\dots,x_k$, and accept if and only if $\prod_{i\in [k]}f(x_i)=1$. Building on the work of Bhangale, Khot, and Minzer (STOC '23), we show, for $0 < p \leq \frac{1}{2}$, that if $k \geq 1 + \frac{1}{p}$, then there exists a distribution $ν$ such that the test $\text{Lin}(ν)$ works in the 1% regime; that is, any function $f:\{0,1\}^n\to \{-1,1\}$ passing the test $\text{Lin}(ν)$ with probability $\geq \frac{1}{2}+ε$, for some constant $ε> 0$, satisfies $\Pr_{x\sim μ_p^{\otimes n}}[f(x)=g(x)] \geq \frac{1}{2}+δ$, for some linear function $g$, and a constant $δ= δ(ε)>0$. Conversely, we show that if $k < 1+\frac{1}{p}$, then no such test $\text{Lin}(ν)$ works in the 1% regime. Our key observation is that the linearity test $\text{Lin}(ν)$ works if and only if the distribution $ν$ satisfies a certain pairwise independence property. |
| title | Biased Linearity Testing in the 1% Regime |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2502.01900 |