We study a model of a random centrally symmetric polytope and ask about the existence of points in the polytope with non-zero, integer coordinates. Our main results are the location of a sharp threshold for the existence of these integer points, a characterization of the typical empirical distribution of their coordina...
Dylan J. Altschuler, Ruben Ascoli, Will Perkins· 0 citations
This paper identifies the threshold at which sparsity begins to govern the online discrepancy of the random Beck--Fiala model, where the independent uniformly random vectors are independent of the sparsity up to constant factors.
We give an efficient algorithm with improved algorithmic guarantees for the (offline) Beck--Fiala problem when the sets have bounded size. Let $A$ be an arbitrary matrix $A\in\{0,1\}^{m\times n}$ with at most $d$ ones per column and at most $s$ ones per row. Let $\log^*$ denote the iterated logarithm and $\ell_j$ denot...
The main thrust of the result is that it is actually obtained by an efficient \textit{online} algorithm that minimizes prefix discrepancy, and is also essentially optimal, since online prefix discrepancy is known to scale as $\omega(\sqrt{d})$ for $d =o(\log T)$.
Dylan J. Altschuler, Konstantin E. Tikhomirov· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
