Skip to content
Preprint

Vector Balancing via Directional Total Variation

Sep 2026 · 10 citations · ⚡ 2 influential · 20 references
Mathematics

TL;DR

Every finite family of real vectors of Euclidean norm at most one admits a signed sum of $\ell_\infty$-norm less than this constant, independently of the dimension and the family size.

Abstract

Our main result is a $3\sqrt{2\pi}$ bound for the Koml\'os signing problem: every finite family of real vectors of Euclidean norm at most one admits a signed sum of $\ell_\infty$-norm less than this constant, independently of the dimension and the family size. For any $\kappa\ge0$, if a bounded open convex set supports a probability density with directional total variation at most $\kappa$ in every unit direction, then its open-set Banaszczyk transform supports another such density with the same $\kappa$, provided the translation vector $v$ satisfies $\kappa\|v\|_2\le1/3$. As a consequence, every finite set system in which each element belongs to at most $t$ sets, where $t\ge1$ is an integer, admits a two-coloring whose imbalance in each set is less than $3\sqrt{2\pi t}$. This gives the square-root dependence predicted by the Beck-Fiala conjecture. The proof was discovered by the Odin Automatic AI Research Agent.

View source

Similar papers

Preprint Aug 2026

Discrepancy of geometric incidences

We study the combinatorial (red-blue) discrepancy of finite point sets with respect to hyperplanes and, more generally, bounded-complexity affine algebraic sets. We prove that every $n$-point set in a real Euclidean space admits a red-blue coloring for which every affine algebraic set of dimension at most $D$ and degre...

A. Adıbelli, István Tomon · 1 citation
Preprint Sep 2026

Vector balancing in convex order

It is proved that Covariance-matched analytic uniformly log-concave sources can have a greatest useful-data-only private release with infinite information, while no greatest full-data release exists.

E. Ercan · 0 citations
Preprint Sep 2026

Exact Universality of Online Discrepancy

We study online vector balancing with $N$ random vectors in $\mathbb{R}^M$ revealed sequentially, where each vector must be assigned an irrevocable sign upon arrival. The goal is to minimize the expected $\ell^\infty$ norm of the final signed sum. For i.i.d. entries with mean zero, variance one, and a finite fourth mom...

Sunghyeon Jo, Taekyun Lee · 0 citations
Preprint Oct 2026

The Koml\'os Problem in Matrix-Multiplication Time

We give a randomized algorithm that, for an $m\times n$ matrix whose columns have Euclidean norm at most one, finds a signing with discrepancy below $99$ in expected $\widetilde O(L_{\mathrm{in}}+n^\omega)$ bit operations, where $L_{\mathrm{in}}$ is the input encoding length and $\omega$ is the exponent of matrix multi...

E. Anand, Peter Chen · 1 citation
Sep 2026

Fast Spectral Signing for Vector Balancing

A deterministic algorithm that finds signs with $\|A\varepsilon\|_\infty<99$ using $O(mn+n^{\omega+2}\log^3 n)$ arithmetic operations, where $\omega>2$ is any fixed attainable matrix-multiplication exponent; with the current bounds on $\omega$ this is $\widetilde O(mn+n^{4.372})$.

Xiao-Yu Li · 3 citations · ⚡1
Preprint Sep 2026

Joint Lower Bounds for Zeroth-Order Nonconvex Optimization on Euclidean Balls

We prove a joint stochastic zeroth-order lower bound for Goldstein stationarity on a Euclidean query ball, even when the ball is guaranteed to contain a stationary point. In dimension $d$, let $f=\mathbb{E}[F(\cdot;\xi)]$, assume $\mathbb{E}[\operatorname{Lip}(F(\cdot;\xi))^2]\le L_0^2$, and bound the initial objective...

Hai-Han Zhang, Wen-Dao Wu, Chen-Heng Zhang et al. · 3 citations · ⚡1

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.