The discrepancy-maximization conjecture for the middle slice

At least 2 years old · documented by

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/2∣≤d/2for all 1≤j≤n.\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 1≤j≤n1\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.

References

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).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.