The discrepancy-maximization conjecture for the middle slice

From papers

Let A([n]n/2)A\in\binom{[n]}{n/2}, and define \textit{Disc-\max-}d(A)=1 if and only if

A[j]j/2d/2for all 1jn.\left|\lvert A\cap [j]\rvert-j/2\right|\le d/2\quad\text{for all }1\le j\le n.

Equivalently, if disc(j)disc(j) is the signed discrepancy of the prefix [j][j], then \textit{Disc-\max-}d(A) is true exactly when disc(j)d|disc(j)|\le d for every 1jn1\le j\le n. Discrepancy-maximization conjecture. For a suitable constant dd,

E_{n/2}(\textit{Disc-\max-}d)=O(1).

This proposes an explicit discrepancy-based Boolean function whose query complexity on the middle slice has bounded excess. The paper presents it as a candidate and does not establish the claim.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Dániel Gerbner, Balázs Keszegh, Dániel T. Nagy, Kartal Nagy, Dömötör Pálvölgyi, Balázs Patkós and Gábor Wiener, “Query complexity of Boolean functions on the middle slice of the cube”, arXiv:2309.13678 (2024).

Solutions 0

No solutions have been posted yet.