OP-00323 Open

A constant bound for fixed-order prefix discrepancy

Note: Shiva Kintali claims a negative answer in “On the Fixed-Order Strong Komlós Conjecture”, ECCC TR26-242 (2026), https://eccc.weizmann.ac.il/report/2026/242/: explicit ordered families of unit vectors whose fixed-order prefix discrepancy grows with the dimension. ECCC is not a site the registry links papers from, so the claim is neither recorded nor checked here.

Submit a result

For vectors $v_1, \dots, v_T \in \mathbb{R}^d$, taken in this order, and signs $\varepsilon_1, \dots, \varepsilon_T \in \{-1, 1\}$, consider the signed prefix sums $\sum_{i=1}^{k} \varepsilon_i v_i$, $1 \le k \le T$, in the norm $\|z\|_\infty = \max_{1 \le j \le d} |z_j|$. Banaszczyk proved that when $\|v_i\|_2 \le 1$ for all $i$ there are always signs with every prefix sum of norm $O(\sqrt{\log d + \log T})$. Bansal, Jiang, Meka, Singla and Sinha improved this to $O(\sqrt{\log d + \log\log T})$, with high probability, when the vectors are perturbed by a small random noise. Kulkarni, Reis and Rothvoss removed the dependence on $d$: random signs chosen online keep every prefix sum of norm $O(\sqrt{\log T})$ with high probability. Bounding only the full sum, $k = T$, is the Komlós conjecture, which 2026 preprints of Guo, Fang and Lu and of Karingula and Lovett prove.

Problem. Is there an absolute constant $C > 0$ such that for all positive integers $d$ and $T$ and every sequence $v_1, \dots, v_T \in \mathbb{R}^d$ with $\|v_i\|_2 \le 1$, in this order, there are signs $\varepsilon_1, \dots, \varepsilon_T \in \{-1, 1\}$ with $$\max_{1 \le k \le T} \Bigl\| \sum_{i=1}^{k} \varepsilon_i v_i \Bigr\|_\infty \le C?$$ The signs may depend on the whole sequence, but one choice of signs must serve every prefix and every coordinate.

Source: Bansal, Jiang, Meka, Singla and Sinha (2022), Open Problem 6.1 (the strong Komlós conjecture).

Imported from github.com/MColbrook/AIM.

Classification

Primary: CO — Combinatorics
Secondary: MG
Keywords: AIM Open Applied Problems, Komlós conjecture, prefix discrepancy, vector balancing

References

@inproceedings{bansal2022,
  author        = {Bansal, Nikhil and Jiang, Haotian and Meka, Raghu and Singla, Sahil and Sinha, Makrand},
  title         = {Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing},
  booktitle     = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  series        = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume        = {215},
  publisher     = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  year          = {2022},
  pages         = {13:1--13:22},
  doi           = {10.4230/LIPIcs.ITCS.2022.13},
  eprint        = {2111.07049},
  archivePrefix = {arXiv},
}
@article{banaszczyk2012,
  author  = {Banaszczyk, Wojciech},
  title   = {On series of signed vectors and their rearrangements},
  journal = {Random Structures Algorithms},
  volume  = {40},
  number  = {3},
  year    = {2012},
  pages   = {301--316},
  doi     = {10.1002/rsa.20373},
}
@inproceedings{kulkarni2024,
  author        = {Kulkarni, Janardhan and Reis, Victor and Rothvoss, Thomas},
  title         = {Optimal Online Discrepancy Minimization},
  booktitle     = {Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC)},
  publisher     = {ACM},
  year          = {2024},
  pages         = {1832--1840},
  doi           = {10.1145/3618260.3649720},
  eprint        = {2308.01406},
  archivePrefix = {arXiv},
}
@misc{guo2026,
  author        = {Guo, Shengtao and Fang, Ethan X. and Lu, Junwei},
  title         = {Vector Balancing via Directional Total Variation},
  year          = {2026},
  eprint        = {2609.11189},
  archivePrefix = {arXiv},
}
@misc{karingula2026,
  author       = {Karingula, Sankeerth Rao and Lovett, Shachar},
  title        = {An elementary proof of the {K}oml{\'o}s conjecture},
  howpublished = {Electronic Colloquium on Computational Complexity, Report TR26-188},
  year         = {2026},
    url          = {https://eccc.weizmann.ac.il/report/2026/188/},
  eprint       = {2609.20979},
  archivePrefix = {arXiv},
}
@misc{aim-strong-komlos-prefix-discrepancy,
  author       = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
  title        = {{A constant bound for fixed-order prefix discrepancy}},
  howpublished = {AIM --- Open Applied Problems, GitHub repository},
  year         = {2026},
  url          = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/325-strong-komlos-prefix-discrepancy.md},
  note         = {Entry 325 at commit a153f46, 2026-10-13},
}

Status history

When	Change	By	Reason
2026-10-14	Needs verification → Open	—	Listed open with a note on a claim the registry cannot record.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00323, "A constant bound for fixed-order prefix discrepancy", clopen.solutions.