CS Paper Radar

An $m^{2.943}$ Bohnenblust--Hille Bound on the Boolean Cube

Joseph Slote, Chun-Kai Tseng, Alexander Volberg

cs.IT math.APmath.CA ·submitted 2026-09-17 23:19 UTC · v1

Abstract

Let $q_m=2m/(m+1)$ and put \[ β_0=\frac{3}{2}+\frac{1}{\log 2}=2.9426950408\ldots, \] where $\log$ is the natural logarithm. We give a proof scheme showing that, for every $\varepsilon>0$, there is $C_\varepsilon<\infty$ such that every complex-valued function $f:\{-1,1\}^n\to\C$ of Fourier degree at most $m$ satisfies \[ \left(\sum_{A\subseteq[n]}\abs{\wh f(A)}^{q_m}\right)^{1/q_m} \le C_\varepsilon m^{β_0+\varepsilon}\norm{f}_\infty. \] The improvement over the $m^9$ estimate of the earlier draft has two ingredients. The first three Fourier levels are estimated at the scales $m$, $m^{3/2}$, and $m^{5/3}$. These losses are encoded in the weight $M^{μ_r/r}r^B\min\{r,L_M\}^8$, $L_M\asymp_B \log (M+1)$, with $μ_r=\lceil3r/2\rceil$ for $r\ge2$. A parity-compatible central window handles $r<L_M$, while a shrinking balanced window handles $r\ge L_M\asymp_B\log(M+1)$, no parity is used in this regime. The leading high-degree loss--gain factor is $\ee\,2^{-B}$; careful uniform bounds close the bootstrap for every $B>1/\log2$. The formula for $μ_r$ is explained below.

Comment
31 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Fourier Entropy Bounds via Approximations

cs.CC ·2026-11-04 ·Manaswi Paraashar, Nitin Saurabh
theory similarity 0.61
Abstract

We establish upper bounds on the Shannon entropy $\mathbb H(\widehat f^{\,2})$ of the Fourier distribution of Boolean functions. We prove that $$ \mathbb H(\widehat f^{\,2}) =O\!\left(\log\bigl(1+\|\widehat f\|_{1,1/3}\bigr)\right), $$ where $\|\widehat f\|_{1,1/3}$ denotes the minimum spectral norm of a pointwise $1/3$-approximant to $f$. This implies $\mathbb H(\widehat f^{\,2})=O(\mathsf R^\oplus(f))$, where $\mathsf R^\oplus(f)$ is bounded-error randomized parity-query complexity. We also bound Fourier entropy by the smaller of the two one-sided average unambiguous parity-certificate complexities. More generally, for any exact representation of indicator of $f$ as $\sum_C w_C\mathbf1_C$, with nonnegative weights and affine subspaces $C$, we prove $$ \mathbb H(\widehat f^{\,2}) =O\!\left(\sum_C w_C\,2^{-k_C}k_C\right), \qquad k_C=\operatorname{codim}(C). $$ The quantity on the right is the average conical junta degree of the representation. These results strengthen earlier bounds of (Arunachalam et al. 2021) by extending approximation-based entropy estimates to Shannon entropy and allowing one-sided and overlapping exact representations. The proofs use an entropy bound from a sequence of increasingly accurate approximants of $f$ with \emph{small} spectral norm. Our techniques also find an application in quantum communication complexity, where it improves a lower bound for the bounded-error quantum communication complexity of XOR functions.

0.18

Parity Decision Trees of Depth $O(4^d \log\|\widehat f\|_1)$ for Boolean Functions $f$ of $F_2$-Degree $d$

cs.CC ·2026-11-02 ·Shengyu Zhang
theory similarity 0.59
Abstract · 27 pages

Let $f\colon F_2^n\to\{-1,+1\}$ have $F_2$-degree $d\ge2$. We prove that its deterministic parity decision tree depth satisfies \[ D_{\oplus} (f)= O(4^d \log_2\|\widehat f\|_1) = O(4^d \log_2 s(f)), \] where $\|\widehat f\|_1=\sum_ξ|\widehat f(ξ)|$ is the Fourier spectral norm and $s(f)$ is the Fourier sparsity. The bound is linear in the logarithm of the spectral norm for every fixed degree, with singly exponential dependence on $d$. This improves the previously best known bound of $O(2^{d^2/2} \log^{d-2} \|\widehat f\|_1)$ due to Tsang, Wong, Xie and Zhang (FOCS 2013). Our result establishes the log-rank conjecture for $\mathrm{XOR}$ functions of $F_2$-degree $O(\log\log s(f))$, extending the previously accessible range $d=O(1)$. The proof combines field lifting, multiplicative derivatives, a multiplicity-based generic-rank comparison, a Schur-complement vanishing argument, and dimension-preserving descent to $F_2$ to lower the degree on every coset of a common subspace.

0.27

Bounded Relative Boundary Implies Narrow DNF Approximation

cs.CC cs.DM ·2026-08-31 ·Chenghua Liu, Boning Meng
theory similarity 0.58
Abstract · 13 pages; proof and exposition revised, Lean repository linked

We prove Friedgut's conjecture (J. Amer. Math. Soc. 12 (1999)) that every increasing family in the $p$-biased discrete cube with bounded relative boundary can be approximated arbitrarily well by one whose minimal elements have size bounded independently of the dimension and the bias. For $0<p\le 1/2$, every increasing Boolean function with total resampling influence at most $K$ is $\varepsilon$-close under $μ_p^n$ to a monotone DNF of width $\exp(O((K+1)^2/\varepsilon^2))$, from which the full conjecture follows for all $p\in(0,1)$. We build on Hatami's pseudo-junta theorem (Ann. of Math. 176 (2012)), whose approximator need not be increasing. Our randomized shifts produce an increasing approximator that is measurable with respect to a controlled refinement of Hatami's adaptive partition. Retaining only short positive certificates yields the desired narrow DNF.

0.35

Near-Optimal Bounds for Sketching the Schatten Norms

cs.DS cs.CCmath.ST ·2026-08-23 ·Lin F. Yang
theory similarity 0.58
Abstract · 94 pages, added the turnstile streaming lower bound, upper/lower bound for all non-even p>0

Let $k_{1,\varepsilon}(n)$ be the smallest number of real linear measurements needed by a randomized oblivious sketch that estimates the nuclear norm of every fixed real $n\times n$ matrix within a factor $1\pm\varepsilon$, with probability at least $2/3$. For every fixed $0<\varepsilon<1$, we prove \[ \frac{n^2}{(\log n)^{A_\varepsilon}} \le k_{1,\varepsilon}(n) \le C_\varepsilon \frac{n^2\{\log\log(e^e n)\}^2}{\log(e n)}. \] Previously, the best unrestricted bounds for general linear sketches of the Schatten--1 norm were $Ω(n)$ and the trivial $O(n^2)$ upper bound (Li, Nguyen, Woodruff'19), leaving a polynomial gap. Our bounds close that gap up to polylogarithmic factors and give a nontrivial logarithmic saving below the $n^2$-measurement storage bound. The result extends much further. Write $k_{p,\varepsilon}(n)$ for the analogous sketch dimension for the Schatten--$p$ norm. For every fixed finite $p>0$ that is not a positive even integer, there are positive constants $A_{p,\varepsilon},C_{p,\varepsilon},c_p$ such that \[ \frac{n^2}{(\log n)^{A_{p,\varepsilon}}} \le k_{p,\varepsilon}(n) \le C_{p,\varepsilon}\frac{n^2}{(\log n)^{c_p}}, \] so $k_{p,\varepsilon}(n)=n^{2-o(1)}$ throughout the non-even regime. Together with the known tight bounds $Θ_{p,\varepsilon}(n^{2-4/p})$ for positive even $p$ and $Θ_\varepsilon(n^2)$ for $p=\infty$ (Li, Woodruff'16), our results close the remaining polynomial gap across the Schatten family and complete, up to polylogarithmic factors, the polynomial-order classification of general linear sketches for all Schatten-$p$ norms.

0.16

On the Fourier Entropy-Influence Conjecture for Boolean Plateaued Functions

cs.IT math.CO ·2026-09-18 ·Vladimir N. Potapov
theoryhot direction similarity 0.57
Abstract · 8 papes, the paper was written with the assistance of ChatGPT

We prove the following inequality for Boolean functions: $2\sum_{x\in F_2^n}f(x)wt(x)\geq wt(f)(n-deg(f))$. Using this inequality, we establish the Fourier Entropy-Influence (FEI) conjecture for Boolean plateaued functions. In particular, we show that the sharp FEI constant for the class of plateaued functions is 4. We also prove the FEI conjecture for partially bent functions and show that the corresponding sharp constant is 2. Finally, we derive several estimates for the p-biased distribution on the Boolean hypercube. Keywords: Fourier entropy, total influence, average sensitivity, plateaued function, algebraic degree, Reed-Muller code, p-biased distribution.

0.53

A proof of the Aaronson-Ambainis conjecture

cs.CC quant-ph ·2026-11-06 ·David Turturean
theorycode/data similarity 0.56
Abstract · 60 pages. Lean formalization and reproducibility materials: https://github.com/physical-superintelligence/aaronson-ambainis

Aaronson and Ambainis conjectured that every bounded polynomial of low degree on the discrete cube has an influential variable. They showed that the conjecture implies that the acceptance probability of every quantum algorithm making $T$ queries can be approximated on most inputs by a classical algorithm making $\mathrm{poly}(T)$ queries. We prove their conjecture: every function $f\colon\{-1,1\}^n\to[-1,1]$ of degree at most $d\ge1$ has a variable of influence at least $c\,\operatorname{Var}(f)^{5/2}/d^{6}$, where $c>0$ is an absolute constant. In the original formulation, for polynomials of degree at most $d$ with values in $[0,1]$ on $\{0,1\}^n$ and variance at least $\varepsilon$, this gives a variable of influence at least $(\varepsilon/d)^{7}$. The proof is elementary, with steps inspired by works of others. Thus, as Aaronson and Ambainis anticipated, superpolynomial quantum speedups in the query model require structure, such as a promise on the inputs.

0.62

Fooling Thresholds of Halfspaces

cs.CC ·2026-09-18 ·Minglong Qin, Penghui Yao, Mingnan Zhao, Haigang Zhou
theory similarity 0.55
Abstract · 55 pages, including appendices and references

We initiate the study of constructing explicit pseudorandom generators for thresholds of halfspaces with seed length polylogarithmic in the number of halfspaces. This class of functions lies at the frontier of circuit complexity [CTW26]. We show that the generator designed by O'Donnell, Servedio, and Tan for polytopes [OST22] also fools this broader class. To analyze the generator, we develop a threshold-specific smooth approximation framework based on a Bentkus-type mollifier. We prove derivative bounds for this mollifier and also establish a Boolean anticoncentration theorem for thresholds of halfspaces via a random thinning argument. These ingredients imply that the generator $δ$-fools every $k$-out-of-$m$ threshold of $m$ halfspaces over $\{-1,1\}^n$ with seed length $\widetilde{O}(κ^{6+2\varepsilon}\log^{6+2\varepsilon}\!m\cdotδ^{-(2+2\varepsilon)}\log n)$, for any arbitrarily small constant $\varepsilon>0$, where $κ=\min\{k,m-k+1\}$. The random thinning argument also yields bounds on the noise sensitivity and Gaussian surface area for thresholds of halfspaces, leading to learning algorithms under both the uniform and Gaussian distributions.

0.32

Top-Down Lower Bounds for All Depths

cs.CC ·2026-09-30 ·Oliver Korten
publishedtheory similarity 0.55
Abstract · 20 pages

We prove that Parity requires $2^{n^{Ω(1)}}$ size De Morgan circuits of constant depth using a new method which is completely "top-down" in the sense of [HJP95]. The proof relies crucially on the core ideas developed in a line of work [HJP95, PPZ99, MW19, GRSS24] which previously established top-down lower bounds for circuits of depth 3 and 4. We first present a proof of a lower bound $\exp(n^{3^{-d}})$. In this case, nearly all of the relevant combinatorial ideas necessary for the proof are already present in some form in [GRSS24]. We then present two extensions of this argument, the first achieving a lower bound $\exp(ε_d n^{1/(2d-2)})$ for some $ε_d>0$ depending only on $d$, and the second achieving the essentially tight lower bound $\exp(ε_d n^{1/(d-1)})$. These improved results each hinge on establishing a key lemma which quantifies the extent to which a high entropy random variable in $\{0,1\}^n$ will look close to uniform after projecting it onto a random small set of coordinates $R \subseteq [n]$.

0.46