Papers for

computer scientists

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

New improved bound on Fourier analysis of Boolean functions

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

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.

Thu 17 SeptInformation Theory
The gist
This paper improves how well we can measure certain aspects of functions defined on Boolean cubes, which are mathematical objects used to model binary inputs. The authors provide a tighter upper limit on a key mathematical expression involving these functions' Fourier coefficients, reducing previous rough estimates drastically. This refined bound helps understand the complexity and behavior of these functions better. Their work focuses on carefully analyzing different layers of the function's structure to get more accurate results.
Open → 2609.21144v1