Greedy Vector Balancing

Arka Ghosh; Daniel Dadush; Ekin Ergen; {\L}ukasz Orlikowski; S{\l}awomir Lasota; Wojciech Czerwi\'nski

Greedy Vector Balancing

T0 review · 0 major / 3 minor · reviewed 2026-06-26 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The greedy algorithm for online vector balancing keeps Euclidean prefix-sum norms at most (2/δ_T)^{d-1} for any finite set T of unit vectors in R^d.

desk verdict The paper gives the first n-independent bound for Euclidean-greedy on finite T by building an explicit absorbing body from subspace chains. read the letter →

arxiv 2606.17991 v1 pith:VBKZVLX2 submitted 2026-06-16 cs.CG

Wojciech Czerwiński , Daniel Dadush , Ekin Ergen , Arka Ghosh , S{l}awomir Lasota , {L}ukasz Orlikowski This is my paper · ORCID

classification cs.CG

keywords vectorbalancinggreedyalgorithmonlinediscrepancyconvexabsorbingsetssubspacechainsschedulingapplication

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves that the greedy algorithm for online vector balancing achieves a performance bound independent of the number of input vectors when those vectors come from a finite set. Specifically, for unit vectors in d-dimensional space, the maximum Euclidean norm of any signed prefix sum is at most (2/δ_T)^{d-1}, where δ_T is the minimum nonzero distance between a vector and the subspaces spanned by other vectors in the set. This result follows from the construction of a T-absorbing convex body that remains bounded and contains all the greedy partial sums. The bound also applies to scaled versions of the vectors and extends to an online partitioning problem, yielding a polynomial-time algorithm for a fixed-scenario scheduling task.

What carries the argument

The T-absorbing convex body K_T, defined so that for x in K_T and t in ±T, if the inner product is non-positive then x + t stays in K_T; built from subspace chains to lie inside a ball of radius (2/δ_T)^{d-1}.

What would settle it

A finite T with δ_T > 0 together with an explicit sequence from T on which greedy produces some prefix sum whose Euclidean norm exceeds (2/δ_T)^{d-1}.

Watch

Extended reading notes

Core claim

When T ⊂ R^d is finite and consists of unit vectors, the greedy algorithm—which at each step picks the sign so that the new vector has non-positive inner product with the current sum—ensures that every prefix sum has Euclidean norm at most (2/δ_T)^{d-1}. This holds because there exists a bounded convex set K_T that is T-absorbing: whenever a point x in K_T has non-positive inner product with a vector t from ±T, then x + t remains in K_T. The set K_T is constructed explicitly using chains of subspaces spanned by vectors from T and is contained in a ball of the stated radius.

Load-bearing premise

T must be finite with δ_T positive, so the subspace-chain construction of the absorbing body stays bounded rather than extending indefinitely in degenerate directions.

Editorial extensions

If this is right

The same bound holds when every vector in the sequence is a positive scalar multiple of some vector from T.
The greedy method extends to online partitioning of the sequence into p subsequences while preserving an analogous n-independent guarantee.
A lexicographic version of total completion time scheduling under a fixed number of scenarios is polynomial-time solvable.
There exist sets T for which Ω(√d / δ_T) is a matching lower bound on the worst-case norm produced by greedy.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The explicit subspace-chain construction of the absorbing body supplies a potential-function template that could be reused for other online linear-decision problems.
When the input set is known in advance, the bound gives a concrete guarantee even against adversarial arrival order without solving an offline optimization.
If δ_T shrinks only polynomially with d the exponential dependence on d limits practical use to well-separated vector collections.
The result cleanly separates the finite-support case from the general infinite-T regime where n-dependent growth may still be required.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The main point is that this paper proves the first bound on the natural Euclidean-greedy algorithm for online vector balancing that stays finite as n grows, when the input set T is finite. For unit vectors in R^d the signed sums stay inside a ball of radius (2/δ_T)^{d-1}, where δ_T is the min nonzero distance from vectors in T to subspaces spanned by other vectors in T. The same bound holds for scaled-down versions of T.

They obtain this by exhibiting a convex T-absorbing body K_T contained in that ball. The construction uses chains of subspaces spanned by subsets of T; because T is finite the collection of subspaces is finite and every chain has length at most d, so the radius stays bounded independently of n. The absorbing property then forces every greedy prefix sum to remain inside K_T. They also supply a simple T where the norm can reach Ω(√d / δ_T), and they use the same technique to settle a special case of the Bosman scheduling conjecture when the number of scenarios is fixed.

The geometric argument looks clean on the abstract and the stress-test note finds no internal inconsistency. The bound is new relative to earlier log-n or infinite-T results. The explicit subspace-chain construction is the clearest contribution.

The obvious limitation is the d-1 exponent and the dependence on 1/δ_T; both can be large, and the gap to the lower bound is still wide. That is normal for a first finite guarantee. The result is stated only for finite T with δ_T > 0, which is the natural setting for the claim.

Readers working on discrepancy or online vector problems will find the absorbing-body technique useful. The paper is worth a serious referee because the claim is new, the construction is explicit, and the scheduling application is concrete.

Referee Report

0 major / 3 minor

Summary. The manuscript analyzes the Euclidean greedy algorithm for the online vector balancing problem where vectors arrive from a finite set T ⊂ R^d of unit vectors. It proves that signed prefix sums have Euclidean norm at most (2/δ_T)^{d-1}, with δ_T the minimum non-zero distance from any vector in T to a subspace spanned by other vectors in T. The proof proceeds by explicitly constructing a bounded T-absorbing convex body K_T contained in a ball of the stated radius, using chains of subspaces spanned by subsets of T; the absorbing property ensures all greedy prefix sums remain inside K_T independently of n. The same bound holds for scaled vectors from T. A matching Ω(√d / δ_T) lower bound example is given for some T, the result is extended to online vector partitioning into p parts, and an application shows a special case of the Bosman et al. conjecture on lexicographic total completion time scheduling is polynomial-time solvable for fixed number of scenarios.

Significance. If the construction is correct, the result is significant: it supplies the first n-independent guarantee for the natural greedy algorithm in this online discrepancy setting when T is finite, resolving an open question about whether greedy can diverge. The explicit geometric construction of K_T via finite subspace chains is a clean, parameter-free approach that may be reusable in other discrepancy or online-algorithm contexts. The lower-bound example and the scheduling application (a partial resolution of an existing conjecture) strengthen the contribution.

minor comments (3)

[Abstract] Abstract and §1: the precise definition of δ_T (including the metric used for distance to a subspace and the exact quantification over all proper subspaces) should be stated formally before the main theorem, as the exponent d-1 depends directly on it.
The lower-bound construction (mentioned after the main theorem) would benefit from an explicit small example in low dimension (e.g., d=2 or d=3) showing how the Ω(√d / δ_T) dependence is realized.
Notation: the paper introduces K_T as a T-absorbing body but does not always distinguish between the specific constructed body and any absorbing body; a short remark clarifying that the radius bound applies to the explicit construction would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review and for recommending minor revision. The referee's summary accurately reflects the manuscript's contributions, including the bound on the greedy algorithm, the geometric construction of K_T, the lower bound, the extension to partitioning, and the scheduling application. No specific major comments appear in the report.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity identified

full rationale

The derivation relies on an explicit, self-contained geometric construction of the T-absorbing convex body K_T from chains of subspaces spanned by the finite set T. The radius bound (2/δ_T)^{d-1} is obtained directly from the maximum chain length d and the definition of δ_T as the minimum positive distance to subspaces; no parameters are fitted, no equations are defined in terms of their own outputs, and no load-bearing self-citations are invoked for the core bound. The absorbing property then implies the greedy invariant without circular reduction. This is a standard first-principles proof whose central claim has independent mathematical content.

Assumptions & free parameters 0 free parameters · 2 assumptions · 1 invented entities

The central claim rests on the existence of a bounded T-absorbing convex body K_T constructed from chains of subspaces spanned by T; δ_T is taken as given from the input set and is not a fitted parameter. No new physical entities are postulated.

assumptions (2)

domain assumption Existence of a bounded convex T-absorbing set K_T whose radius is controlled by subspace chains
Invoked in the proof sketch to obtain the n-independent bound; location: main result paragraph.
standard math Standard facts about convex bodies and inner-product sign conditions in Euclidean space
Used to define the absorbing property; no section citation given in abstract.

invented entities (1)

K_T (T-absorbing convex body)
purpose: Witness set that remains bounded under the greedy sign rule
Constructed explicitly from subspace chains; independent_evidence false because no external verification is supplied in the abstract.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Greedy Vector Balancing." pith.science (2026). https://pith.science/paper/VBKZVLX2

@misc{pith2026260617991,
  author       = {Pith},
  title        = {Pith review of: Greedy Vector Balancing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VBKZVLX2}},
  note         = {Machine review of arXiv:2606.17991}
}

abstract

In online vector balancing, vectors $t_1,\dots,t_n$ arrive one by one from a given set $T$ and the goal is to assign signs $s_1,\dots,s_n\in\{\pm1\}$ in an online manner so as to minimize the largest norm of any signed prefix sum $\sum_{i=1}^ks_i t_i$, $k \in [n]$. In this paper, we analyze the natural Euclidean greedy vector balancing algorithm for this problem: at each step $k$, the sign $s_k\in\{\pm1\}$ is chosen so that $s_k t_k$ has non-positive inner product with $\sum_{i=1}^{k-1} s_i\cdot t_i$. Our main result is the first finite bound, independent of the sequence length $n$, on the performance of greedy whenever $T$ is finite. When $T \subset \mathbb{R}^d$ consists of unit vectors, we prove that the signed sums produced by greedy have Euclidean norm at most $(2/\delta_T)^{d-1}$, where $\delta_T$ is the minimum non-zero distance between vectors in $T$ and subspaces spanned by vectors in $T$. The same upper bound holds when the sequences are composed of scaled down vectors in $T$. We also provide a simple set $T$ for which $\Omega(\sqrt{d}/\delta_T)$ is a lower bound. We analyze the greedy algorithm by proving the existence of a bounded convex $K_T$ that is $T$-absorbing: $\forall x\in K_T$ and $t \in\pm T$, $\langle x,t\rangle\leq0\Rightarrow x+t\in K_T$. We give an explicit construction of a set $K_T$ contained in a ball of radius $(2/\delta_T)^{d-1}$, based on chains of subspaces spanned by vectors in $T$, which may be of independent interest. We generalize our greedy vector balancing bound to online vector partitioning, where the sequence $t_1,\dots,t_n$ must be partitioned in an online manner into $p$ subsequences. As an application, we prove a special case of a conjecture of Bosman et al. (arxiv:2402.19259), showing that a lexicographic version of total completion time scheduling under scenarios is polynomial time solvable when the number of scenarios is fixed.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

166 extracted references · 62 canonical work pages

[1]

Discrete balancing games , author=. Bull. Inst. Math. Acad. Sinica , volume=
[2]

Journal of Combinatorial Theory, Series B , volume=

Balancing games , author=. Journal of Combinatorial Theory, Series B , volume=. 1977 , publisher=

1977
[3]

Journal of Combinatorial Theory, Series A , volume=

On a class of balancing games , author=. Journal of Combinatorial Theory, Series A , volume=. 1979 , publisher=

1979
[4]

Combinatorica , volume=

Balancing vectors in the max norm , author=. Combinatorica , volume=. 1986 , publisher=

1986
[5]

Journal of Combinatorial Theory, Series A , volume=

Vector balancing games with aging , author=. Journal of Combinatorial Theory, Series A , volume=. 2001 , publisher=

2001
[6]

arXiv preprint arXiv:2512.03273 , year=

Balancing games on unbounded sets , author=. arXiv preprint arXiv:2512.03273 , year=

work page arXiv
[7]

Discrete Analysis , volume=

Balancing sums of random vectors , author=. Discrete Analysis , volume=. 2018 , publisher=

2018
[8]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages=

Online vector balancing and geometric discrepancy , author=. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages=

Show all 166 references

[9]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

Online discrepancy minimization for stochastic arrivals , author=. Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2021 , organization=

2021
[10]

Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=

Discrepancy minimization via a self-balancing walk , author=. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing , pages=
[11]

13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , volume=

A Gaussian Fixed Point Random Walk , author=. 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) , volume=. 2022 , organization=

2022
[12]

Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=

Optimal online discrepancy minimization , author=. Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages=
[13]

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

Quasi-Monte Carlo Beyond Hardy-Krause , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

2025
[14]

Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences , volume=

A deterministic-control-based approach motion by curvature , author=. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences , volume=. 2006 , publisher=

2006
[15]

Proceedings of the 2018 ACM Conference on Economics and Computation , pages=

How to make envy vanish over time , author=. Proceedings of the 2018 ACM Conference on Economics and Computation , pages=

2018
[16]

Advances in Neural Information Processing Systems , volume=

Grab: Finding provably better data permutations than random reshuffling , author=. Advances in Neural Information Processing Systems , volume=
[17]

Journal of Machine Learning Research , volume=

Kernel thinning , author=. Journal of Machine Learning Research , volume=
[18]

Theory of Computing Systems , volume=

Total completion time scheduling under scenarios , author=. Theory of Computing Systems , volume=. 2025 , publisher=

2025
[19]

1997 , issn =

Anti-Hadamard Matrices, Coin Weighing, Threshold Gates, and Indecomposable Hypergraphs , journal =. 1997 , issn =. doi:https://doi.org/10.1006/jcta.1997.2780 , url =

1997 doi
[20]

Proceedings of the twenty-eighth annual symposium on Computational geometry , pages=

On sub-determinants and the diameter of polyhedra , author=. Proceedings of the twenty-eighth annual symposium on Computational geometry , pages=
[21]

International Colloquium on Automata, Languages, and Programming , pages=

Finding short paths on polytopes by the shadow vertex algorithm , author=. International Colloquium on Automata, Languages, and Programming , pages=. 2013 , organization=

2013
[22]

arXiv preprint arXiv:1412.5381 , year=

Solving totally unimodular LPs with the shadow vertex algorithm , author=. arXiv preprint arXiv:1412.5381 , year=

arXiv
[23]

Discrete & Computational Geometry , volume=

On the shadow simplex method for curved polyhedra , author=. Discrete & Computational Geometry , volume=. 2016 , publisher=

2016
[24]

Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

On finding exact solutions of linear programs in the oracle model , author=. Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2022 , organization=

2022
[25]

Surveys in combinatorics , pages=

Circuit imbalance measures and linear programming , author=. Surveys in combinatorics , pages=
[26]

Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

Excluding a Line Minor via Design Matrices and Column Number Bounds for the Circuit Imbalance Measure , author=. Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2026 , organization=

2026
[27]

Approximate solution of some problems of scheduling theory , JOURNAL =

Sevast. Approximate solution of some problems of scheduling theory , JOURNAL =. 1978 , PAGES =

1978
[28]

and Fiala, T

Beck, J. and Fiala, T. , Date-Added =. Integer-making theorems , Volume =. Discrete Applied Mathematics , Number =
[29]

Linear Algebra and its Applications , volume=

On some combinatorial questions in finite-dimensional spaces , author=. Linear Algebra and its Applications , volume=. 1981 , publisher=

1981
[30]

Six standard deviations suffice , Volume =

Joel Spencer , Date-Added =. Six standard deviations suffice , Volume =. Trans. Amer. Math. Soc. , Pages =
[31]

Discrepancy of set-systems and matrices , Volume =

Lov. Discrepancy of set-systems and matrices , Volume =. European Journal of Combinatorics , Number =
[32]

Mathematics of the USSR-Sbornik , volume=

Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces , author=. Mathematics of the USSR-Sbornik , volume=. 1989 , publisher=

1989
[33]

Studia Math

Banaszczyk, Wojciech , TITLE =. Studia Math. , FJOURNAL =. 1993 , NUMBER =

1993
[34]

Probability in

Chobanyan, Sergej , TITLE =. Probability in. 1994 , MRCLASS =

1994
[35]

The Discrepancy Method , Year =

Bernard Chazelle , Date-Added =. The Discrepancy Method , Year =
[36]

Beck, J. and S. Discrepancy theory , Year =. Handbook of combinatorics (vol. 2) , Date-Added =
[37]

Studia Mathematica , volume=

On some vector balancing problems , author=. Studia Mathematica , volume=. 1997 , publisher=

1997
[38]

, Date-Added =

Banaszczyk, W. , Date-Added =. Balancing vectors and Gaussian measures of n-dimensional convex bodies , Volume =. Random Structures & Algorithms , Number =
[39]

Geometric Discrepancy (An Illustrated Guide) , Year =

Ji. Geometric Discrepancy (An Illustrated Guide) , Year =
[40]

Linear algebra and its applications , volume=

Balanced partitions of vector sequences , author=. Linear algebra and its applications , volume=. 2006 , publisher=

2006
[41]

Building Bridges: Between Mathematics and Computer Science , pages=

On the power of linear dependencies , author=. Building Bridges: Between Mathematics and Computer Science , pages=. 2008 , publisher=

2008
[42]

Constructive algorithms for discrepancy minimization , Year =

Bansal, Nikhil , Booktitle =. Constructive algorithms for discrepancy minimization , Year =
[43]

Newman, Alantha and Neiman, Ofer and Nikolov, Aleksandar , TITLE =. 2012. 2012 , MRCLASS =

2012
[44]

and Meka, R

Lovett, S. and Meka, R. , Date-Added =. Arxiv preprint arXiv:1203.5747 , Title =

arXiv
[45]

Proceedings of the American Mathematical Society , volume=

The determinant bound for discrepancy is almost tight , author=. Proceedings of the American Mathematical Society , volume=
[46]

Algorithmica , volume =

Nikhil Bansal and Joel Spencer , title =. Algorithmica , volume =. 2013 , pages =

2013
[47]

Random Structures Algorithms , FJOURNAL =

Banaszczyk, Wojciech , TITLE =. Random Structures Algorithms , FJOURNAL =. 2012 , NUMBER =. doi:10.1002/rsa.20373 , URL =

2012 doi
[48]

Constructive Discrepancy Minimization for Convex Sets , booktitle =

Thomas Rothvo. Constructive Discrepancy Minimization for Convex Sets , booktitle =. 2014 , url =. doi:10.1109/FOCS.2014.23 , timestamp =

2014 doi
[49]

Proceedings of the 20th International Workshop on Randomization and Computation ---

Dadush, Daniel and Garg, Shashwat and Lovett, Shachar and Nikolov, Aleksandar , TITLE =. Proceedings of the 20th International Workshop on Randomization and Computation ---. 2016 , MRCLASS =

2016
[50]

An algorithm for

Bansal, Nikhil and Dadush, Daniel and Garg, Shashwat , booktitle=. An algorithm for. 2016 , organization=

2016
[51]

SIAM Journal on Computing , volume=

Constructive discrepancy minimization for convex sets , author=. SIAM Journal on Computing , volume=. 2017 , publisher=

2017
[52]

Random Structures & Algorithms , volume=

Efficient algorithms for discrepancy minimization in convex sets , author=. Random Structures & Algorithms , volume=. 2018 , publisher=

2018
[53]

Theory OF Computing , volume=

The Gram--Schmidt Walk: A Cure for the Banaszczyk Blues , author=. Theory OF Computing , volume=
[54]

Journal of the American Statistical Association , volume=

Balancing covariates in randomized experiments with the gram--schmidt walk design , author=. Journal of the American Statistical Association , volume=. 2024 , publisher=

2024
[55]

arXiv preprint arXiv:2508.03961 , year=

Decoupling via Affine Spectral-Independence: Beck-Fiala and Koml 'os Bounds Beyond Banaszczyk , author=. arXiv preprint arXiv:2508.03961 , year=
[56]

SODA , pages =

Moses Charikar and Alantha Newman and Aleksandar Nikolov , title =. SODA , pages =
[57]

, Date-Added =

Guruswami, V. , Date-Added =. Inapproximability results for set splitting and satisfiability problems with no mixed clauses , Year =. Approximation Algorithms for Combinatorial Optimization , Pages =
[58]

CoRR , Title =

Karthekeyan Chandrasekaran and Santosh Vempala , Bibsource =. CoRR , Title =
[59]

The entropy rounding method in approximation algorithms , Url =

Rothvo , Thomas , Booktitle =. The entropy rounding method in approximation algorithms , Url =. 2012 , Bdsk-Url-1 =

2012
[60]

Bin Packing via Discrepancy of Permutations , journal =

Friedrich Eisenbrand and D. Bin Packing via Discrepancy of Permutations , journal =. 2013 , volume =. doi:10.1145/2483699.2483704 , timestamp =

2013 doi
[61]

2014 , volume =

Kasper Green Larsen , title =. 2014 , volume =. doi:10.1137/120865240 , timestamp =

2014 doi
[62]

Approximating Bin Packing within O(log

Thomas Rothvo. Approximating Bin Packing within O(log. 54th Annual. 2013 , pages =. doi:10.1109/FOCS.2013.11 , timestamp =

2013 doi
[63]

Conference on Learning Theory , pages=

Near-optimal herding , author=. Conference on Learning Theory , pages=. 2014 , organization=

2014
[64]

Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach , Year =

Nikhil Bansal and Moses Charikar and Ravishankar Krishnaswamy and Shi Li , Bibsource =. Better Algorithms and Hardness for Broadcast Scheduling via a Discrepancy Approach , Year =. SODA , Date-Added =
[65]

IPCO , pages =

Nikhil Bansal and Viswanath Nagarajan , title =. IPCO , pages =
[66]

SIAM Journal on Computing , volume=

Better bin packing approximations via discrepancy theory , author=. SIAM Journal on Computing , volume=. 2016 , publisher=

2016
[67]

Proceedings of the

Hoberg, Rebecca and Rothvoss, Thomas , TITLE =. Proceedings of the. 2017 , MRCLASS =. doi:10.1137/1.9781611974782.172 , URL =

2017 doi
[68]

ACM Transactions on Algorithms (TALG) , volume=

Proximity results and faster algorithms for integer programming using the Steinitz lemma , author=. ACM Transactions on Algorithms (TALG) , volume=. 2019 , publisher=

2019
[69]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=

Linear size sparsifier and the geometry of the operator norm ball , author=. Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms , pages=. 2020 , organization=

2020
[70]

Mathematics of Operations Research , volume=

On integer programming, discrepancy, and convolution , author=. Mathematics of Operations Research , volume=. 2023 , publisher=

2023
[71]

Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=

Flow time scheduling and prefix beck-fiala , author=. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages=
[72]

Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

Linear-sized sparsifiers via near-linear time discrepancy theory , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

2024
[73]

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

Eulerian Graph Sparsification by Effective Resistance Decomposition , author=. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2025 , organization=

2025
[74]

Geometric Algorithms and Combinatorial Optimization , publisher =

Gr. Geometric Algorithms and Combinatorial Optimization , publisher =
[75]

and Lvov, A

Chazelle, B. and Lvov, A. The discrepancy of boxes in higher dimension. Discrete Comput. Geom. 2001

2001
[76]

The ellipsoid method and its consequences in combinatorial optimization , JOURNAL =

Gr. The ellipsoid method and its consequences in combinatorial optimization , JOURNAL =. 1981 , NUMBER =. doi:10.1007/BF02579273 , URL =

1981 doi
[77]

Approximation algorithms and semidefinite programming , PUBLISHER =

G. Approximation algorithms and semidefinite programming , PUBLISHER =. 2012 , PAGES =. doi:10.1007/978-3-642-22015-9 , URL =

2012 doi
[78]

2004 , PAGES =

Boyd, Stephen and Vandenberghe, Lieven , TITLE =. 2004 , PAGES =. doi:10.1017/CBO9780511804441 , URL =

2004 doi
[79]

Per Austrin and Venkatesan Guruswami and Johan H. (2+ ) -. 2013 , booktitle=

2013
[80]

Seymour, P. D. , TITLE =. J. Combin. Theory Ser. B , FJOURNAL =. 1980 , NUMBER =. doi:10.1016/0095-8956(80)90075-1 , URL =

1980 doi
[81]

Ghouila-Houri, Alain , TITLE =. C. R. Acad. Sci. Paris , VOLUME =. 1962 , PAGES =

1962
[82]

Matou. An. European J. Combin. , FJOURNAL =. 1998 , NUMBER =. doi:10.1006/eujc.1997.0162 , URL =

1998 doi
[83]

1997 , PAGES =

Bhatia, Rajendra , TITLE =. 1997 , PAGES =. doi:10.1007/978-1-4612-0653-8 , URL =

1997 doi
[84]

and Olkin, Ingram and Arnold, Barry C

Marshall, Albert W. and Olkin, Ingram and Arnold, Barry C. , TITLE =. 2011 , PAGES =. doi:10.1007/978-0-387-68276-1 , URL =

2011 doi
[85]

On some combinatorial questions in finite-dimensional spaces , Volume =

B\'. On some combinatorial questions in finite-dimensional spaces , Volume =. Linear Algebra and its Applications , Pages =
[86]

and Srivastav, A

Doerr, B. and Srivastav, A. and Wehr, P. , TITLE =. Electron. J. Combin. , VOLUME =. 2004 , PAGES =

2004
[87]

Proceedings of the

Srinivasan, Aravind , TITLE =. Proceedings of the. 1997 , MRCLASS =

1997
[88]

On the discrepancy for boxes and polytopes , JOURNAL =

Matou. On the discrepancy for boxes and polytopes , JOURNAL =. 1999 , NUMBER =. doi:10.1007/s006050050044 , URL =

1999 doi
[89]

and Lvov, A

Chazelle, B. and Lvov, A. , TITLE =. Discrete Comput. Geom. , FJOURNAL =. 2001 , NUMBER =. doi:10.1145/336154.336179 , URL =

2001 doi
[90]

and Lvov, A

Chazelle, B. and Lvov, A. , TITLE =. Discrete Comput. Geom. , FJOURNAL =. 2001 , NUMBER =. doi:10.1007/s00454-001-0014-2 , URL =

2001 doi
[91]

CoRR , volume =

Boris Konev and Alexei Lisitsa , title =. CoRR , volume =
[92]

Tyrrell , TITLE =

Rockafellar, R. Tyrrell , TITLE =. 1970 , PAGES =

1970
[93]

1992 , PAGES =

Niederreiter, Harald , TITLE =. 1992 , PAGES =. doi:10.1137/1.9781611970081 , URL =

1992 doi
[94]

In Eurographics '91 , year =

Peter Shirley , title =. In Eurographics '91 , year =
[95]

2004 , PAGES =

Glasserman, Paul , TITLE =. 2004 , PAGES =

2004
[96]

Derandomization in computational geometry , JOURNAL =

Matou. Derandomization in computational geometry , JOURNAL =. 1996 , NUMBER =. doi:10.1006/jagm.1996.0027 , URL =

1996 doi
[97]

Alon, Noga and Mansour, Yishay , TITLE =. Inform. Process. Lett. , FJOURNAL =. 1995 , NUMBER =. doi:10.1016/0020-0190(95)00032-8 , URL =

1995 doi
[98]

1993 , volume =

Joseph Naor and Moni Naor , title =. 1993 , volume =. doi:10.1137/0222053 , timestamp =

1993 doi
[99]

Simple Construction of Almost k-wise Independent Random Variables

Noga Alon and Oded Goldreich and Johan H. Simple Construction of Almost k-wise Independent Random Variables. , journal =. 1992 , volume =. doi:10.1002/rsa.3240030308 , timestamp =

1992 doi
[100]

Goldreich, Oded and Goldwasser, Shari and Ron, Dana , title =. J. ACM , issue_date =. 1998 , issn =. doi:10.1145/285055.285060 , acmid =

1998 doi
[101]

Alon, Noga and Yuster, Raphael and Zwick, Uri , title =. J. ACM , issue_date =. 1995 , issn =. doi:10.1145/210332.210337 , acmid =

1995 doi
[102]

Broder and Moses Charikar and Alan M

Andrei Z. Broder and Moses Charikar and Alan M. Frieze and Michael Mitzenmacher , title =. J. Comput. Syst. Sci. , year =. doi:10.1006/jcss.1999.1690 , timestamp =

1999 doi
[103]

and Floyd, Robert W

Blum, Manuel and Pratt, Vaughan and Tarjan, Robert E. and Floyd, Robert W. and Rivest, Ronald L. , TITLE =. J. Comput. System Sci. , FJOURNAL =. 1973 , PAGES =

1973
[104]

1997 , PAGES =

Kushilevitz, Eyal and Nisan, Noam , TITLE =. 1997 , PAGES =

1997
[105]

Chung, Fan R. K. , TITLE =. 1997 , PAGES =

1997
[106]

Combinatorica , FJOURNAL =

Bilu, Yonatan and Linial, Nathan , TITLE =. Combinatorica , FJOURNAL =. 2006 , NUMBER =. doi:10.1007/s00493-006-0029-7 , URL =

2006 doi
[107]

2006 , Publisher =

Shlomo. 2006 , Publisher =. doi:10.1090/S0273-0979-06-01126-8 , MSC2010 =

2006 doi
[108]

On the discrepancy of

Bohus, G. On the discrepancy of. Random Structures Algorithms , FJOURNAL =. 1990 , NUMBER =. doi:10.1002/rsa.3240010208 , URL =

1990 doi
[109]

Discrepancy theory , BOOKTITLE =

Beck, J. Discrepancy theory , BOOKTITLE =. 1995 , MRCLASS =

1995
[110]

Coverings and coloring of hypergraphs , BOOKTITLE =

Lov. Coverings and coloring of hypergraphs , BOOKTITLE =. 1973 , MRCLASS =

1973
[111]

Vadhan , title =

Salil P. Vadhan , title =. Foundations and Trends in Theoretical Computer Science , year =. doi:10.1561/0400000010 , timestamp =

doi
[112]

2007 , school=

Efficient and private distance approximation in the communication and streaming models , author=. 2007 , school=

2007
[113]

Kane and Jelani Nelson and David P

Daniel M. Kane and Jelani Nelson and David P. Woodruff , title =. Proceedings of the Twenty-Ninth. 2010 , pages =. doi:10.1145/1807085.1807094 , timestamp =

2010 doi
[114]

T. S. Jayram and David P. Woodruff , title =. 2013 , volume =. doi:10.1145/2483699.2483706 , timestamp =

2013 doi
[115]

Woodruff , title =

David P. Woodruff , title =. Proceedings of the Fifteenth Annual. 2004 , pages =

2004
[116]

Some Complexity Questions Related to Distributive Computing (Preliminary Report) , booktitle =

Andrew Chi. Some Complexity Questions Related to Distributive Computing (Preliminary Report) , booktitle =. 1979 , pages =. doi:10.1145/800135.804414 , timestamp =

1979 doi
[117]

Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract) , booktitle =

Andrew Chi. Probabilistic Computations: Toward a Unified Measure of Complexity (Extended Abstract) , booktitle =. 1977 , pages =. doi:10.1109/SFCS.1977.24 , timestamp =

1977 doi
[118]

Information Theory Methods in Communication Complexity , booktitle =

Ziv Bar. Information Theory Methods in Communication Complexity , booktitle =. 2002 , pages =. doi:10.1109/CCC.2002.1004344 , timestamp =

2002 doi
[119]

and Thomas, Joy A

Cover, Thomas M. and Thomas, Joy A. , TITLE =. 2006 , PAGES =

2006
[120]

Muthukrishnan , title =

S. Muthukrishnan , title =. Foundations and Trends in Theoretical Computer Science , year =. doi:10.1561/0400000002 , timestamp =

doi
[121]

2014 , url =

Huang, Zengfeng and Yi, Ke , title =. 2014 , url =

2014
[122]

Deterministic Simulation in

Mikl. Deterministic Simulation in. Proceedings of the 19th Annual. 1987 , pages =. doi:10.1145/28395.28410 , timestamp =

1987 doi
[123]

30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989 , year =

Aviad Cohen and Avi Wigderson , title =. 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989 , year =. doi:10.1109/SFCS.1989.63449 , timestamp =

1989 doi
[124]

30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989 , year =

Russell Impagliazzo and David Zuckerman , title =. 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989 , year =. doi:10.1109/SFCS.1989.63486 , timestamp =

1989 doi
[125]

Computational Complexity , year =

Noga Alon and Uriel Feige and Avi Wigderson and David Zuckerman , title =. Computational Complexity , year =. doi:10.1007/BF01277956 , timestamp =

doi
[126]

, TITLE =

Nilli, A. , TITLE =. Discrete Math. , FJOURNAL =. 1991 , NUMBER =. doi:10.1016/0012-365X(91)90112-F , URL =

1991 doi
[127]

Friedman, Joel , TITLE =. Mem. Amer. Math. Soc. , FJOURNAL =. 2008 , NUMBER =. doi:10.1090/memo/0910 , URL =

2008 doi
[128]

Spielman and Nikhil Srivastava , title =

Adam Marcus and Daniel A. Spielman and Nikhil Srivastava , title =. 54th Annual. 2013 , pages =. doi:10.1109/FOCS.2013.63 , timestamp =

2013 doi
[129]

arXiv preprint arXiv:1306.3969 , year=

Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem , author=. arXiv preprint arXiv:1306.3969 , year=

arXiv
[130]

Nikhil Srivastava , Note =. Erd
[131]

Batson and Daniel A

Joshua D. Batson and Daniel A. Spielman and Nikhil Srivastava , title =. 2014 , volume =. doi:10.1137/130949117 , timestamp =

2014 doi
[132]

Cutting a graph into two dissimilar halves , JOURNAL =

Erd. Cutting a graph into two dissimilar halves , JOURNAL =. 1988 , NUMBER =. doi:10.1002/jgt.3190120113 , URL =

1988 doi
[133]

Imbalances in

Erd. Imbalances in. Networks , FJOURNAL =. 1971/72 , PAGES =

1971
[134]

Intersections of graphs , JOURNAL =

Bollob. Intersections of graphs , JOURNAL =. 2011 , NUMBER =. doi:10.1002/jgt.20489 , URL =

2011 doi
[135]

Approximating

Andr. Approximating. Proceedings of the Twenty-Eighth Annual. 1996 , pages =. doi:10.1145/237814.237827 , timestamp =

1996 doi
[136]

2012 , PAGES =

Compressed sensing , EDITOR =. 2012 , PAGES =. doi:10.1017/CBO9780511794308 , URL =

2012 doi
[137]

and Cevher, Volkan and Duarte, Marco F

Baraniuk, Richard G. and Cevher, Volkan and Duarte, Marco F. and Hegde, Chinmay , TITLE =. IEEE Trans. Inform. Theory , FJOURNAL =. 2010 , NUMBER =. doi:10.1109/TIT.2010.2040894 , URL =

2010 doi
[138]

Highly robust error correction by convex programming , JOURNAL =

Cand. Highly robust error correction by convex programming , JOURNAL =. 2008 , NUMBER =. doi:10.1109/TIT.2008.924688 , URL =

2008 doi
[139]

Williamson and David B

David P. Williamson and David B. Shmoys , title =. 2011 , publisher =

2011
[140]

Vazirani , title =

Vijay V. Vazirani , title =. 2001 , publisher =

2001
[141]

1961 , Publisher =

P.C. 1961 , Publisher =. doi:10.1287/opre.9.6.849 , Zbl =

1961 doi
[142]

Karp , title =

Narendra Karmarkar and Richard M. Karp , title =. 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982 , year =. doi:10.1109/SFCS.1982.61 , timestamp =

1982 doi
[143]

Thompson , title =

Prabhakar Raghavan and Clark D. Thompson , title =. Combinatorica , year =. doi:10.1007/BF02579324 , timestamp =

doi
[144]

Proceedings of the

Nikolov, Aleksandar and Talwar, Kunal , TITLE =. Proceedings of the. 2015 , MRCLASS =. doi:10.1137/1.9781611973730.24 , URL =

2015 doi
[145]

Combinatorial Discrepancy for Boxes via the Ellipsoid-Infinity Norm , Eprint =

Matou. Combinatorial Discrepancy for Boxes via the Ellipsoid-Infinity Norm , Eprint =
[146]

Random Structures Algorithms , FJOURNAL =

Linial, Nati and Shraibman, Adi , TITLE =. Random Structures Algorithms , FJOURNAL =. 2009 , NUMBER =. doi:10.1002/rsa.20232 , URL =

2009 doi
[147]

Combinatorica , FJOURNAL =

Linial, Nati and Mendelson, Shahar and Schechtman, Gideon and Shraibman, Adi , TITLE =. Combinatorica , FJOURNAL =. 2007 , NUMBER =. doi:10.1007/s00493-007-2160-5 , URL =

2007 doi
[148]

Factorization Norms and Hereditary Discrepancy , journal =

Matou. Factorization Norms and Hereditary Discrepancy , journal =. 2018 , doi =

2018
[149]

Management science , volume=

Bounds for the optimal scheduling of n jobs on m processors , author=. Management science , volume=. 1964 , publisher=

1964
[150]

Mathematische Annalen , Number =

Weyl, Hermann , Date-Added =. Mathematische Annalen , Number =
[151]

, TITLE =

Schmidt, Wolfgang M. , TITLE =. Acta Arith. , FJOURNAL =. 1972 , PAGES =

1972
[152]

1935 , Publisher =

J.G. 1935 , Publisher =

1935
[153]

, TITLE =

van Aardenne-Ehrenfest, T. , TITLE =. Nederl. Akad. Wetensch., Proc. , VOLUME =. 1945 , PAGES =

1945
[154]

, TITLE =

van Aardenne-Ehrenfest, T. , TITLE =. Nederl. Akad. Wetensch., Proc. , VOLUME =. 1949 , PAGES =

1949
[155]

Roth, K. F. , TITLE =. Mathematika , FJOURNAL =. 1954 , PAGES =

1954
[156]

Remark concerning integer sequences , Volume =

Roth, Klaus F , Date-Added =. Remark concerning integer sequences , Volume =. Acta Arithmetica , Pages =
[157]

Balanced two-colorings of finite sets in the square I , Volume =

Beck, J. Balanced two-colorings of finite sets in the square I , Volume =. Combinatorica , Number =
[158]

Roth's estimate of the discrepancy of integer sequences is nearly sharp , JOURNAL =

Beck, J. Roth's estimate of the discrepancy of integer sequences is nearly sharp , JOURNAL =. 1981 , NUMBER =. doi:10.1007/BF02579452 , URL =

1981 doi
[159]

, Date-Added =

Alexander, R. , Date-Added =. Geometric methods in the study of irregularities of distribution , Volume =. Combinatorica , Number =
[160]

and Matou

Chazelle, B. and Matou. An Elementary Approach to Lower Bounds in Geometric Discrepancy , Volume =. Discrete and Computational Geometry , Number =
[161]

Discrete and Computational Geometry , Number =

Matou. Discrete and Computational Geometry , Number =
[162]

Discrepancy in arithmetic progressions , JOURNAL =

Matou. Discrepancy in arithmetic progressions , JOURNAL =. 1996 , NUMBER =. doi:10.1090/S0894-0347-96-00175-0 , URL =

1996 doi
[163]

Integer sequences and semidefinite programming , NOTE =

Lov. Integer sequences and semidefinite programming , NOTE =. Publ. Math. Debrecen , FJOURNAL =. 2000 , NUMBER =

2000
[164]

Gil Kalai , Date-Added =. Erd
[165]

Multiple Authors , Date-Added =. Erd
[166]

Steven Finch , Date-Added =

Pith tools

Reviewed June 26, 2026 · model on record in the stance chip above.

[1] [1]

Discrete balancing games , author=. Bull. Inst. Math. Acad. Sinica , volume=

[2] [2]

Journal of Combinatorial Theory, Series B , volume=

Balancing games , author=. Journal of Combinatorial Theory, Series B , volume=. 1977 , publisher=

1977

[3] [3]

Journal of Combinatorial Theory, Series A , volume=

On a class of balancing games , author=. Journal of Combinatorial Theory, Series A , volume=. 1979 , publisher=

1979

[4] [4]

Combinatorica , volume=

Balancing vectors in the max norm , author=. Combinatorica , volume=. 1986 , publisher=

1986

[5] [5]

Journal of Combinatorial Theory, Series A , volume=

Vector balancing games with aging , author=. Journal of Combinatorial Theory, Series A , volume=. 2001 , publisher=

2001

[6] [6]

arXiv preprint arXiv:2512.03273 , year=

Balancing games on unbounded sets , author=. arXiv preprint arXiv:2512.03273 , year=

work page arXiv

[7] [7]

Discrete Analysis , volume=

Balancing sums of random vectors , author=. Discrete Analysis , volume=. 2018 , publisher=

2018

[8] [8]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages=

Online vector balancing and geometric discrepancy , author=. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages=