A degree-$d$ polynomial source is the output of a polynomial map of degree at most $d$ over $\mathbb{F}_2$ on arbitrarily many uniform random bits. Khodabandeh and Shinkar (FOCS'26) proved that $\mathrm{Ber}(1/3)^{\otimes N}$ has statistical distance $1-o(1)$ from every constant-degree polynomial source and conjectured exponentially small overlap. Independently of Khodabandeh and Shinkar, Byramji, Kane, Morris, and Ostuni (RANDOM'26) asked for an explicit target distribution at distance $1-\exp(-N^{\Omega_d(1)})$. We resolve both questions. For every fixed $d\geq1$, every degree-$d$ polynomial source has overlap at most $\exp(-c_dN)$ with $\mathrm{Ber}(1/3)^{\otimes N}$, where $c_d>0$ is independent of the seed length. For quadratics, $c_2=2^{-26}$ suffices. We amplify Khodabandeh and Shinkar's uniform separation of acceptance probabilities from non-dyadic parameters (numbers not of the form $a/2^b$ for integers $a$ and $b\geq0$). The result extends to other non-dyadic Bernoulli parameters and to coordinates that are Boolean functions of boundedly many bounded-degree polynomials. We also give a uniform deterministic hierarchy between adjacent degrees. Appending the outputs of disjoint AND gates on $d+1$ inputs to uniform seed bits yields flat degree-$(d+1)$ target distributions of entropy $k$ with overlap $\exp(-\Omega_d(\min\{k,N-k\}))$ against every degree-$d$ source, for $\min\{k,N-k\}\geq2(d+1)$. This entropy dependence is optimal up to constants in the exponent among flat target distributions for fixed $d$. The construction has locality $d+1$ and uses $O(N)$ field operations to sample. At $k=\lfloor N/2\rfloor$, it handles $d\leq(1-\varepsilon)\log_2N/3$ with overlap $\exp(-N^{\varepsilon-o(1)})$ for fixed $0<\varepsilon<1$. The proof combines monotonicity of Gowers uniformity norms, pairwise independence of points in a random affine cube, and relative entropy.
We give a random-bit-efficient construction for the inverse star discrepancy. For every fixed $u\in(0,1)$, $k$-wise independent uniform points $\boldsymbol{X}_1,\ldots,\boldsymbol{X}_N$ with $k=O(d(1+\log(1+N/d)))$ satisfy the Monte Carlo bound $D_N^*(\boldsymbol{X}_1,\ldots,\boldsymbol{X}_N) =O(\sqrt{d/N})$ with proba...
The degree-distortion tradeoff for polynomial approximation of the $d$-dimensional cross-polytope $B_1^d$ is determined, and degree $\Theta(d)$ is necessary and sufficient for constant distortion.
We prove that for every isotropic log-concave distribution $P$ on $\mathbb{R}^d$ and every even $m\ge2$, the polynomial $(Cm)^m\|v\|_2^m - \mathbb{E}_{X\sim P}\langle X,v\rangle^m$ is a sum of squares, where $C>0$ is a universal constant. This improves on the Poincar\'e-dependent bounds (Kothari and Steinhardt, 2017),...
We obtain upper bounds for the number of real zeros of functions of the form $$ f(x) = \sum_{k=1}^{n} c_k \bigl(P_k(x)\bigr)^{\alpha_k}, $$ where $c_k, \alpha_k \in \mathbb{R}$ and each $P_k$ is a real polynomial of degree at most $d$ that is non-negative on an interval $I\subset \mathbb{R}$. We improve previously know...
Gal Binyamini, Avner Kiro, A. Logunov et al.· 0 citations
The proof extends adaptive Wishart deferred decisions to a rectangular factor with a $k$-dimensional nullspace while persistence of small compression eigenvalues controls growing $p$ and the spectral endpoint.
We prove that for every prime power $q$ and every $p \in (0, 1-1/q)$, a random $\mathbb{F}_q$-linear code of rate $1 - h_q(p) - \epsilon$ is $(p, C_{p,q}/\epsilon)$-average-radius list-decodable with probability at least $1 - q^{-\Omega(n)}$, i.e., for every center $y \in \mathbb{F}_q^n$, the $C_{p,q}/\epsilon$ codewor...
V. Guruswami, Shi-Lun Li, Mihir Singhal· 2 citations· ⚡1
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.