The discrepancy-maximization conjecture for the middle slice
The discrepancy-maximization conjecture for the middle slice
Let , and define \textit{Disc-\max-}d(A)=1 if and only if
Equivalently, if is the signed discrepancy of the prefix , then \textit{Disc-\max-}d(A) is true exactly when for every . Discrepancy-maximization conjecture. For a suitable constant ,
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
Sign in to submit a solution.
No solutions have been posted yet.