Analysis of Boolean Functions — Approximate Degree for Approximate Majority

Definitions and mathematical statement

For a positive integer $n$, let $[n]=\{1,\ldots,n\}$. For a real-valued function $f$ on $\{-1,1\}^n$, use its unique multilinear representation \[ f(x)=\sum_{S\subseteq[n]}\widehat f(S)\prod_{i\in S}x_i \] and define $\deg(f)=\max\{|S|:\widehat f(S)\ne0\}$ for nonzero $f$. This is the standard Boolean-cube interpretation of degree; the supplied source does not explicitly define that term.

Let $\mathcal A_n$ consist of all functions \[ f:\{-1,1\}^n\longrightarrow[-1,-2/3]\cup[2/3,1] \] satisfying, for every $x\in\{-1,1\}^n$, \[ \begin{aligned} \sum_{i=1}^n x_i\ge n/2&\implies f(x)\in[2/3,1],\\ \sum_{i=1}^n x_i\le -n/2&\implies f(x)\in[-1,-2/3]. \end{aligned} \] Determine the least possible degree \[ D(n)=\min_{f\in\mathcal A_n}\deg(f) \] as a function of $n$. In particular, at every input with $-n/2<\sum_{i=1}^n x_i<n/2$, the value of $f$ must still lie in $[-1,-2/3]\cup[2/3,1]$, although either sign is permitted. The threshold inequalities include equality. The source does not specify whether an exact formula or an asymptotic characterization of $D(n)$ is intended.

Short English statement

Determine the minimum multilinear polynomial degree of a real-valued function on the Boolean cube that has magnitude between $2/3$ and $1$ everywhere, is positive when the coordinate sum is at least $n/2$, and is negative when that sum is at most $-n/2$. Either sign is allowed between the thresholds, but the magnitude restriction remains.

Sources

• Local UnsolvedMath registry, permanent ID $800455$, source problem code catalogue entry, title: Analysis of Boolean Functions --- Approximate Degree for Approximate Majority. The supplied registry labels the problem open; that label is not an independently verified mathematical or literature assessment.
• O'Donnell, Open Problems in Analysis of Boolean Functions (2012), Problem 26, "Approximate Degree for Approximate Majority": https://arxiv.org/abs/1204.6447. The supplied record reports access on 2026-10-16 and extraction from arXiv LaTeX; these are supplied provenance statements, not claims of access for this draft.
• Attribution: the registry lists O'Donnell and 2012 in its proposer fields, while its background gives "Proposed/Source: Srikanth Srinivasan, 2010." Both attributions are retained without resolving their differing roles.