Pith. sign in

REVIEW 4 major objections 5 minor 126 references

This monograph argues that modern discrepancy theory can be unified through Banaszczyk's theorem and its algorithmic conversions, and provides a self-contained proof of that theorem.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · deepseek-v4-flash

2026-08-04 01:10 UTC pith:K7CNOXC6

load-bearing objection A useful, well-attributed monograph of known discrepancy results; the new proof in Chapter 6 has a repairable gap in exposition and the ChatGPT claim in §1.8 should go. the 4 major comments →

arxiv 2608.00140 v1 pith:K7CNOXC6 submitted 2026-07-31 math.HO cs.DMcs.DSmath.COmath.MG

Discrepancy Theory: An Algorithmic and Geometric Perspective

Nikhil Bansal , Aleksandar Nikolov This is my paper
classification math.HO cs.DMcs.DSmath.COmath.MG MSC 05D4052A4011K3868W20
keywords discrepancy theoryBanaszczyk's theoremGaussian measureconvex geometryvector balancingpartial coloringhereditary discrepancyalgorithmic rounding
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

The book is trying to establish that the modern transformation of discrepancy theory—Spencer's six deviations, the Komlós bound, partial colorings, and efficient rounding algorithms—can be told as one connected story whose pivot is Banaszczyk's theorem: any closed convex set of Gaussian measure at least 1/2 is hit by a signed sum of vectors of length at most 1/5. A sympathetic reader should care because, if true, a single geometric result yields the best known bounds for vector balancing, axis-parallel boxes, prefix discrepancy, Steinitz constants, and hereditary discrepancy approximation, and it points to the algorithmic ideas needed to compute such colorings. The book also supplies new analyses and presents several results as consequences of a few convex-geometric lemmas.

Core claim

The central claim is that Banaszczyk's theorem is the right organizing principle for discrepancy theory. On the book's own terms: for any closed convex set K in R^m with Gaussian measure at least 1/2 and any vectors of Euclidean length at most 1/5, there exist signs whose signed sum lies in K. From this theorem the book derives the O(√log m) Komlós bound, the γ2-norm discrepancy bound disc(M) ≤ γ2(M)√log(2m), the best known upper bound for axis-parallel boxes, and prefix/Steinitz consequences; it then shows that algorithmic variants—Lovett-Meka's Brownian walk, Rothvoss's projection, the Gram-Schmidt Walk, and SDP vector discrepancy—convert the nonconstructive geometry into polynomial-time c

What carries the argument

Banaszczyk's theorem (Theorem 5.1) is the load-bearing object: a Gaussian-measure condition on a convex body guarantees a low-discrepancy signed sum. The proof's engine is the construction, for each direction u with ||u||≤1/5, of a convex body K*u contained in (K−u)∪(K+u) whose Gaussian measure is at least that of K; the body is built via Ehrhard symmetrization and a pairing argument that reduces the higher-dimensional comparison to Gaussian measures of one-dimensional intervals. The algorithmic chapters supply the mechanism that turns this existence theorem into computation: a Gaussian walk in a shrinking subspace, projection onto K∩[−1,1]^n, the Gram-Schmidt Walk for sub-Gaussian discrepan

Load-bearing premise

The load-bearing premise is that the self-contained proof of Banaszczyk's theorem—through the Ehrhard-Borell inequality and the one-dimensional interval comparison—is correct; if that chain breaks, the book's advertised unified treatment collapses, and the peripheral Section 1.8 claim that a ChatGPT-discovered algorithm resolves open problems is not proven in the text.

What would settle it

Recompute the key numeric and monotonic checks in Section 6.4: the ratio f(d) = (Φ(d)−Φ(d+r))/Φ(p+d) must be non-decreasing in d, with f(p) ≥ 1 for p ≥ 1 and r ≤ 1/5. A counterexample at p=1, r=0.2, d=0 would falsify the book's proof of Theorem 6.1.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • Banaszczyk's theorem yields the best known O(√log m) bound for the Komlós vector-balancing problem, improving on the O(log n) given by partial coloring alone.
  • The same theorem gives disc(M) ≤ γ2(M)√log(2m), which yields polylogarithmic approximations of hereditary discrepancy and the best known upper bound for the discrepancy of axis-parallel boxes.
  • The proof framework implies prefix-discrepancy and Steinitz bounds, including a √log n prefix Komlós bound and near-Euclidean Steinitz estimates.
  • The algorithmic chapters claim polynomial-time colorings matching several nonconstructive bounds, including Spencer-type O(√n) results via Lovett-Meka and Rothvoss algorithms.
  • The Gram-Schmidt Walk provides an efficient way to sample a near-sub-Gaussian discrepancy distribution, making the Komlós bound constructive; the Self-Balancing Walk extends near-optimal bounds to the online setting.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The book leaves implicit that the 1/5 length bound and the 1/2 Gaussian threshold are the true bottlenecks: improving either constant in Theorem 5.1 would immediately improve every application it feeds, so the constants are a natural focus for future work.
  • Because the proof rests on Ehrhard-Borell, a sharper one-dimensional comparison could plausibly remove the additive √log n term in prefix discrepancy and settle the Euclidean Steinitz conjecture; this is an inference, not a result in the book.
  • A testable extension of the book's approach would be to run the Gram-Schmidt Walk on the prefix problem (Theorem 5.15); the book states that no efficient algorithm is known, so a concrete open route is to adapt the sub-Gaussian sampling to the prefix setting.
  • The Section 1.8 claim that a ChatGPT-discovered algorithm resolves open problems is an unverified aside, separate from the core derivation; it should be treated as a pointer to external work rather than part of the book's contribution.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. This is an expository monograph on combinatorial discrepancy theory, aiming to present modern algorithmic and convex-geometric techniques through a unified set of ideas. The visible portion covers Chapters 1-6: classical linear-algebraic methods (Beck-Fiala, permutations, boxes, vector balancing), partial-coloring methods and Spencer's theorem, the Lovett-Meka and Rothvoss algorithms, and a substantial presentation of Banaszczyk's theorem with Chapter 6 devoted to the geometric proof of the key measure-increase lemma. The table of contents advertises further chapters on hereditary discrepancy, algorithmic Banaszczyk bounds, the Gram-Schmidt walk, and online discrepancy, but those chapters are not present in the submitted text. The visible proofs of Beck-Fiala and Spencer follow standard arguments, and the general structure of the Banaszczyk proof is recognizable, but the submitted manuscript is incomplete and the central proof contains local gaps that need repair.

Significance. If completed, the monograph would be a useful modern reference: it explains several important techniques in one place, including Giannopoulos's geometric partial-coloring lemma, Royen's correlation inequality, the Lovett-Meka edge walk, and Rothvoss's convex-programming algorithm. The visible mathematical content is broadly coherent and accurately attributed to the existing literature. However, the submitted version cannot be accepted as a finished work: its advertised scope is not present, and the proof of Banaszczyk's theorem — the main geometric contribution of the book — has steps that are not written correctly. The manuscript does not contain machine-checked proofs or reproducible code, so the assessment rests entirely on the written arguments. The central claims are standard and likely correct, but the presentation is not yet refereable in its current form.

major comments (4)
  1. [Overall submission, Chapters 7-10] The table of contents lists Chapters 7-10, including hereditary discrepancy, algorithmic Banaszczyk bounds, the Gram-Schmidt walk, and online discrepancy, but these chapters are absent from the submitted text. Consequently, several advertised contributions — for example the algorithmic proof of Banaszczyk's bound, the self-balancing walk, and the claimed constant vector-discrepancy proof in Chapter 10 — cannot be checked. This is an incomplete submission and blocks acceptance.
  2. [Section 6.4, Lemma 6.5] The chord-replacement argument is written incorrectly. For a concave decreasing h_K, the chord L through P=(-p,h_K(-p)) and Q=(-r/2,h_K(-r/2)) lies below h_K on [-p,-r/2] and above h_K outside this interval, including on (-∞,-p] and [-r/2,∞). The displayed statement 'L(x)≤h_K(x) for x≤−p−d' is undefined and generally false. More importantly, the blue-region case analysis treats x∈[-p,-r/2) and then 'x > r/2', omitting the whole range [-r/2,r/2]. The conclusion is salvageable by changing the second condition to x≥−r/2, because γ1([a,a+r]) decreases under a right shift for a≥−r/2, but as written the proof of γ2(C)≤γ2(D) is incomplete. Since Theorem 6.6 and Theorem 6.1 depend on this step, this must be fixed.
  3. [Section 6.5, Proposition 6.4] Proposition 6.4 asserts that the Ehrhard symmetrization used to reduce to two dimensions preserves convexity of K and K'. The section states the Ehrhard-Borell inequality but the proof of log-concavity of the slice functions h_K and h_{K'} and the resulting convexity is not included in the submitted text; more generally, Section 6.5 ends before the argument is completed. This is a load-bearing step in the reduction to two dimensions, and it needs a full proof or a precise, self-contained reference.
  4. [Section 1.8 and later cross-references] Section 1.8 states that a ChatGPT-discovered algorithm 'gives a new constructive proof of Theorem 5.15, and resolves several open problems in this book.' This is inconsistent with later statements: for example, Section 5.6 still describes an efficient version of Theorem 5.15 as open, and several open problems in earlier chapters are not updated. No bibliography entries or verification details are supplied. This is not load-bearing for the core mathematics, but the unsupported and internally inconsistent claim should be removed or substantiated, and all open-problem statements cross-referenced consistently.
minor comments (5)
  1. [Lemma 3.14] In the displayed consequence of Sidak's lemma, the product should run over i=1,...,m, not i=1,...,n, and the factors should be γ1([-t_i,t_i]), not γ_n(S_i). The current indexing is confusing.
  2. [Section 6.4.1] The numerical values γ1([-1/5,1/5])≈0.1585 and γ1((-∞,-1])≈0.1586 are correct, but the surrounding comparison of these values is written loosely; the condition should be stated as γ1([-r,r])≤γ1((-∞,-1]) for r≤1/5.
  3. [Theorem 2.8] The proof concludes with a bound of O(k log n) for the discrepancy, while the theorem statement promises O(k log^2 n). The dependence on n should be stated consistently.
  4. [Section 5.3] The convexity of K*u is asserted in one sentence. A short verification using the affine variation of the endpoints of the slices would improve readability.
  5. [Bibliography] The text cites references such as [2], [5], [17], and [44] but no reference list appears in the submitted version. A complete bibliography is required for any publication.

Circularity Check

0 steps flagged

No significant circularity: the book's central derivation (proof of Banaszczyk's Theorem 5.1) proceeds from external theorems and contains no fitted parameters; self-citations are ordinary attributions.

full rationale

I walked the derivation chain of the central claim, Theorem 5.1 (Banaszczyk). The theorem is not defined in terms of its own conclusion: the body K*u in (6.1) is constructed from K and u, and Theorem 5.8's inequality γ_m(K*u) ≥ γ_m(K) is argued via symmetrization, reduction to two dimensions, the chord replacement in Lemma 6.5, and the 1-D interval comparisons of §6.4, all resting on external ingredients (Gaussian isoperimetric/Ehrhard–Borell inequality, cited [47,36]; Sidak's Lemma 3.14; Royen's correlation inequality Theorem 3.19; Talagrand's comparison Theorem 5.12). There are no fitted parameters, no predictions from data, and no quantity is set up so that the claimed conclusion holds by construction. The abundant self-citations (e.g., Nikolov [98], Matoušek–Nikolov–Talwar [91], Dadush–Nikolov–Talwar–Tomczak-Jaegermann [45], Bansal–Jiang [17]) attribute independently published, externally falsifiable results; none is invoked as an unverified uniqueness theorem or as a load-bearing ansatz. The skeptic-flagged issue in Lemma 6.5 (the case analysis over a∈[−r/2,r/2] in the chord-replacement argument) and the omitted proofs of Ehrhard–Borell and Royen are correctness/completeness concerns, not definitional circularity, and per the operating rules proof gaps do not by themselves raise the circularity score. The unusual §1.8 passage claiming that an external ChatGPT-discovered algorithm 'resolves several open problems' is flagged as a reliability/citation concern, but it plays no role in the core derivation of Chapters 5–6, so it is not load-bearing. Verdict: the monograph is self-contained against external benchmarks; no circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 8 axioms · 0 invented entities

No free parameters are fitted to data, and the book introduces no new entities. The listed axioms are background theorems and modeling assumptions; this is consistent with a survey/expository monograph.

axioms (8)
  • standard math Prekopa-Leindler inequality (Lemma 3.16).
    Used to prove the Gaussian Brunn-Minkowski inequality (Lemma 3.17), which underlies Sidak's lemma and log-concavity of slice measures in Chapter 3. Cited without proof.
  • standard math Sidak's lemma (Lemma 3.14).
    Gives a product lower bound on Gaussian measure of intersections of symmetric slabs; central to proving the stronger partial coloring lemma (Lemma 3.4).
  • standard math Royen's Gaussian correlation inequality (Theorem 3.19).
    Used in Section 3.4 to lower-bound Gaussian measure of intersections of bodies K_i for k permutations; cited without proof.
  • standard math Gaussian isoperimetric inequality (Sudakov-Tsirelson / Borell, Theorem 4.8).
    Used in the analysis of Rothvoss' convex-programming algorithm, specifically in Lemma 4.9.
  • standard math Ehrhard-Borell inequality (Theorem 6.13).
    Main black box in Chapter 6's proof of Banaszczyk's theorem; used to justify Gaussian symmetrization and convexity. Not proved in the book.
  • standard math Talagrand's comparison theorem (Theorem 5.12).
    Used in Section 5.4 to convert sub-Gaussianity of the discrepancy vector into containment in a scaled body K; cited as a deep external theorem.
  • standard math Small-ball inequality for Brownian motion (Eq. 3.17).
    Used in Lemma 3.21 to estimate the Gaussian measure of tK_i for permutation discrepancy.
  • domain assumption Membership oracle and polynomial-time SDP solvability for Rothvoss' algorithm.
    The algorithmic claims assume a membership oracle for K and that the convex program (4.2) can be solved efficiently. Standard in algorithmic geometry, but still a modeling assumption.

pith-pipeline@v1.3.0-alltime-deepseek · 69633 in / 13144 out tokens · 139466 ms · 2026-08-04T01:10:08.275577+00:00 · methodology

0 comments
read the original abstract

Combinatorial discrepancy theory is a subject with roots in combinatorics, geometry, and number theory, and with numerous applications to mathematics and computer science. At its core, discrepancy theory is about dividing a collection of objects into two parts that are as balanced as possible. For example, given a collection of subsets of a finite universe, we may wish to color the elements with two colors so that each set is approximately evenly split. Other problems in discrepancy are more geometric in flavor, and ask for example, to assign signs to a collection of vectors, so that the sum of the signed vectors is as small as possible. Classical results, such as the Beck-Fiala theorem and Spencer's "six deviations" result, show that it is often possible to attain remarkably small discrepancy, often far smaller than what naive random colorings achieve. In recent years, discrepancy theory has undergone a transformation, driven by new algorithmic techniques and a rich interplay between probability, optimization, and convex geometry. These developments have led not only to new constructive proofs of foundational theorems, but also to several new results and research directions. This monograph aims to provide an accessible and unified introduction to these modern developments, with a focus on the core algorithmic and convex geometric ideas that have driven them. For several results, we provide new simpler analyses, while highlighting the intuition behind the proofs.

Figures

Figures reproduced from arXiv: 2608.00140 by Aleksandar Nikolov, Nikhil Bansal.

Figure 1.1
Figure 1.1. Figure 1.1: A path of short steps returning to the origin, and a rearrange [PITH_FULL_IMAGE:figures/full_fig_p017_1_1.png] view at source ↗
Figure 2.1
Figure 2.1. Figure 2.1: We find xt by starting from xt−1 and going in the direction of ∆xt until we hit a boundary of the cube [−1, +1]U . Analysis. Let us use the notation At := U \ Ft for the “active” elements, i.e., the ones not yet fixed. First we verify that, as long as Ft ̸= U (equiva￾lently At ̸= ∅), there exists a ∆xt ̸= 0 satisfying 1. and 2. The two conditions form a system of linear equations, and to show that the sy… view at source ↗
Figure 2.2
Figure 2.2. Figure 2.2: The permutation π2 for a pointset in [8]2 , listing the points with y-coordinate in {1, 2, 3, 4} first, in increasing order of their x-coordinate, and then listing the points with y-coordinate in {5, 6, 7, 8}. The bottom-left corner is (1, 1). If S is the set system induced by π1, . . . , πm on P, then, by Theorem 2.8, disc(S) ≲ m log(2n) ≲ log(2n) 2 . The theorem is now implied by the bound disc(Ad|P , … view at source ↗
Figure 3.1
Figure 3.1. Figure 3.1: The set K0 where K is a three-dimensional Euclidean ball cen￾tered at the origin. K0 is a slice of the ball given by intersecting it with a horizontal plane through the origin [PITH_FULL_IMAGE:figures/full_fig_p056_3_1.png] view at source ↗
Figure 3.2
Figure 3.2. Figure 3.2: The Gaussian measure of Kt as a function of t, where K is a three-dimensional Euclidean ball of radius 5. Here Kt is a two-dimensional circle of radius √ 25 − t 2. Notice the measure is quasiconcave, i.e., the set {t : γ 3 (Kt) ≥ α} is an interval for any α [PITH_FULL_IMAGE:figures/full_fig_p056_3_2.png] view at source ↗
Figure 4.1
Figure 4.1. Figure 4.1: Lovett-Meka Algorithm. The random walk starting from [PITH_FULL_IMAGE:figures/full_fig_p066_4_1.png] view at source ↗
Figure 4.2
Figure 4.2. Figure 4.2: Rothvoss’ Algorithm. The shaded area indicates [PITH_FULL_IMAGE:figures/full_fig_p071_4_2.png] view at source ↗
Figure 4.3
Figure 4.3. Figure 4.3: The unit vectors wj ∈ R n in the SDP solution. Clearly 4.4 implies vdisc(M) ≤ disc(M). However, at first glance, vector colorings do not seem to give useful information. E.g., for any matrix M with entries in [−1, 1] (as in Spencer’s theorem 3.5), the solution wi = ei , the i-th standard basis vector, is always feasible with λ = n 1/2 . Interestingly however, this SDP becomes quite useful when λ ≪ n 1/2 … view at source ↗
Figure 5.1
Figure 5.1. Figure 5.1: The block structure of (vℓ,j )ℓ,j for d = 3. All unshaded entries are 0’s. is the i-th coordinate in the ℓ-th block. We claim that K has large Gaussian measure. Claim 5.7. For d ≲ log(2m) large enough, γ dm(K) ≥ 1/2. Proof. As K = ∩ m i=1Ki , by the union bound it suffices to show that γ dm(R dm\ Ki) = P[ Pd ℓ=1 g(ℓ, i) 2 > 2d] ≤ 1/2m, where the g(ℓ, i) are independent stan￾dard Gaussian random variables… view at source ↗
Figure 5.2
Figure 5.2. Figure 5.2: The body K ∗ u obtained from K. 0 and K, i.e., there is some y ∈ R m and α < 0 such that ⟨x, y⟩ ≤ α for all x ∈ K (this is the hyperplane separator theorem, see [105, Corollary 11.4.2]). However, γ m(K) ≤ γ m({x ∈ R m : ⟨x, y⟩ ≤ α}) = P[⟨g, y⟩ ≤ α] < 1 2 , for a standard Gaussian random vector g ∈ R m, contradicting the assump￾tion γ m(K) ≥ 1/2. Suppose the result holds for n − 1. Consider the convex bod… view at source ↗
Figure 6.1
Figure 6.1. Figure 6.1: The convex body K ∗ u obtained from K and u. we gain by extending the intervals Ky to Ky + [−r, r] whenever |Ky| ≥ 2r [PITH_FULL_IMAGE:figures/full_fig_p099_6_1.png] view at source ↗
Figure 6.2
Figure 6.2. Figure 6.2: The region gained (blue) and lost (red) in [PITH_FULL_IMAGE:figures/full_fig_p099_6_2.png] view at source ↗
Figure 6.3
Figure 6.3. Figure 6.3: The symmetrization of K along u. The interval Ky of K is transformed to the interval (−∞, fK(y). The body Iu(K) extends infinitely to the left. where we denote fK(y) = Φ−1 (γ 1 (Ky)) for ease of notation. Similarly, Iu(K ∗ u) = {(t, y) : y ∈ R m−1 , t ≤ fK∗u(y)}, where fK∗u(y) = Φ−1 (γ 1 ((K ∗u)y)). See [PITH_FULL_IMAGE:figures/full_fig_p101_6_3.png] view at source ↗
Figure 6.4
Figure 6.4. Figure 6.4: The body Iu(K ∗ u) obtained by symmetrizating K∗ along u, and described by the function fK∗u(y). The blue and red regions depict the volume gained and lost by Iu(K ∗ u) over Iu(K). The body K′ . We now shrink the body Iu(K ∗u) and replace it a simpler body K′ that is more closely related to Iu(K). This is depicted in Figure [PITH_FULL_IMAGE:figures/full_fig_p101_6_4.png] view at source ↗
Figure 6.5
Figure 6.5. Figure 6.5: The body K′ obtained by shrinking Iu(K ∗ u). The blue region only decreases and the red region only increases. Notice that K′ only depends on fK(y) and is more closely related to Iu(K). K′ is also convex, as K′ + (r, 0) is the intersection of the translated convex set Iu(K) + (r, 0) with the convex superlevel set {(t, y) : fK(y) ≥ −p}. We now show that K′ ⊂ Iu(K ∗ u). Lemma 6.3. For all y, gK(y) ≤ fK∗u(y… view at source ↗
Figure 6.6
Figure 6.6. Figure 6.6: The two-dimensional bodies KW and K′ W given by hK(x) and hK′(x). The bodies extend infinitely to the left and to the bottom The bodies KW and K′ W have the following properties. First, it is easily checked that γ 2 (KW ) = γ m(K) and γ 2 (K′ W ) = γ m(K′ ) as symmetrization is measure-preserving. The second remarkable property which will follow from Ehrhard’s inequality in Section 6.5 is that this symme… view at source ↗
Figure 6.7
Figure 6.7. Figure 6.7: Replacing the curve hK(x) by the line L(x). On the right the red and blue regions are defined according to L(x). Lemma 6.5. Replacing hK(x) by L(x) only increases γ 2 (A) and only de￾creases γ 2 (B). More precisely, γ 2 (C) ≥ γ 2 (A) and γ 2 (D) ≤ γ 2 (B). Proof. We show that the measure of each horizontal segment in B only decreases and for those in A it only increases. Recall that hK is concave and dec… view at source ↗
Figure 6
Figure 6. Figure 6: showing this pairing [PITH_FULL_IMAGE:figures/full_fig_p106_6.png] view at source ↗
Figure 6.8
Figure 6.8. Figure 6.8: On the left is a type 1 pairing between the red interval [PITH_FULL_IMAGE:figures/full_fig_p107_6_8.png] view at source ↗
Figure 9.1
Figure 9.1. Figure 9.1: The left shows the pivot and discrepancy update direction. The [PITH_FULL_IMAGE:figures/full_fig_p149_9_1.png] view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

126 extracted references · 1 linked inside Pith

  1. [2]

    Optimal online discrepancy minimization in linear time, 2026

    Ishaq Aden-Ali. Optimal online discrepancy minimization in linear time, 2026

    2026

  2. [3]

    Schulman, and Orli Waarts

    Miklós Ajtai, James Aspnes, Moni Naor, Yuval Rabani, Leonard J. Schulman, and Orli Waarts. Fairness in scheduling.J. Algorithms, 29(2):306–357, 1998

    1998

  3. [4]

    Alon and J.H

    N. Alon and J.H. Spencer.The probabilistic method. Wiley- Interscience series in discrete mathematics and optimization. Wiley, 2000

    2000

  4. [5]

    Altschuler and Konstantin Tikhomirov

    Dylan J. Altschuler and Konstantin Tikhomirov. Online beck–fiala down to logarithmic sparsity, 2026

    2026

  5. [6]

    Liu, and Mehtaab Sawhney

    Ryan Alweiss, Yang P. Liu, and Mehtaab Sawhney. Discrepancy min- imization via a self-balancing walk. InSymposium on Theory of Com- puting, STOC, pages 14–20, 2021

    2021

  6. [7]

    Comput., 46(5):1554–1573, 2017

    Per Austrin, Venkatesan Guruswami, and Johan Håstad.(2 +ε)-Sat is NP-hard.SIAM J. Comput., 46(5):1554–1573, 2017

    2017

  7. [8]

    An elementary introduction to modern convex geometry

    Keith Ball. An elementary introduction to modern convex geometry. InFlavors of geometry, pages 1–58. Cambridge Univ. Press, 1997

    1997

  8. [9]

    Balancing vectors and convex bodies.Studia Math., 106(1):93–100, 1993

    Wojciech Banaszczyk. Balancing vectors and convex bodies.Studia Math., 106(1):93–100, 1993

    1993

  9. [10]

    Balancing vectors and Gaussian measures of n-dimensional convex bodies.Random Structures and Algorithms, 12(4):351–360, 1998

    Wojciech Banaszczyk. Balancing vectors and Gaussian measures of n-dimensional convex bodies.Random Structures and Algorithms, 12(4):351–360, 1998. 165 BIBLIOGRAPHY166

    1998

  10. [11]

    On series of signed vectors and their rearrange- ments.Random Structures & Algorithms, 40(3):301–316, 2012

    Wojciech Banaszczyk. On series of signed vectors and their rearrange- ments.Random Structures & Algorithms, 40(3):301–316, 2012

    2012

  11. [12]

    Constructive algorithms for discrepancy minimization

    Nikhil Bansal. Constructive algorithms for discrepancy minimization. InSymposium on Foundations of Computer Science, FOCS, pages 3– 10, 2010

    2010

  12. [13]

    On a generalization of iterated and randomized round- ing

    Nikhil Bansal. On a generalization of iterated and randomized round- ing. InSymposium on Theory of Computing, STOC, pages 1125–1135. ACM, 2019

    2019

  13. [14]

    An algorithm for Komlós conjecture matching Banaszczyk’s bound

    Nikhil Bansal, Daniel Dadush, and Shashwat Garg. An algorithm for Komlós conjecture matching Banaszczyk’s bound. InSymposium on Foundations of Computer Science, FOCS, pages 788–799, 2016

    2016

  14. [15]

    The Gram-Schmidt walk: A cure for the Banaszczyk blues.Theory Comput., 15:1–27, 2019

    Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett. The Gram-Schmidt walk: A cure for the Banaszczyk blues.Theory Comput., 15:1–27, 2019

    2019

  15. [16]

    Algorithmic discrepancy beyond partial coloring

    Nikhil Bansal and Shashwat Garg. Algorithmic discrepancy beyond partial coloring. InSymposium on Theory of Computing, STOC, pages 914–926. ACM, 2017

    2017

  16. [17]

    Decoupling via affine spectral- independence: Beck-Fiala and Komlós bounds beyond banaszczyk, 2025

    Nikhil Bansal and Haotian Jiang. Decoupling via affine spectral- independence: Beck-Fiala and Komlós bounds beyond banaszczyk, 2025

    2025

  17. [18]

    Nikhil Bansal, Aditi Laddha, and Santosh S. Vempala. A unified ap- proach to discrepancy minimization. InAPPROX/RANDOM, volume 245 ofLIPIcs, pages 1:1–1:22, 2022

    2022

  18. [19]

    Flow time schedul- ing and prefix Beck-Fiala

    Nikhil Bansal, Lars Rohwedder, and Ola Svensson. Flow time schedul- ing and prefix Beck-Fiala. InSymposium on Theory of Computing, STOC, pages 331–342. ACM, 2022

    2022

  19. [20]

    Nikhil Bansal and Joel H. Spencer. On-line balancing of random in- puts.Random Struct. Algorithms, 57(4):879–891, 2020

    2020

  20. [21]

    Bárány and VS Grinberg

    I. Bárány and VS Grinberg. On some combinatorial questions in finite- dimensional spaces.Linear Algebra and its Applications, 41:1–9, 1981

    1981

  21. [22]

    On a class of balancing games.J

    Imre Bárány. On a class of balancing games.J. Comb. Theory, Ser. A, 26(2):115–126, 1979

    1979

  22. [23]

    On the power of linear dependencies

    Imre Bárány. On the power of linear dependencies. InBuilding bridges, pages 31–45. Springer, 2008. BIBLIOGRAPHY167

    2008

  23. [24]

    The Brunn-Minkowski theorem and related geometric and functional inequalities

    Franck Barthe. The Brunn-Minkowski theorem and related geometric and functional inequalities. InInternational Congress of Mathemati- cians. Vol. II, pages 1529–1546. Eur. Math. Soc., Zürich, 2006

    2006

  24. [25]

    A convexity condition in Banach spaces and the strong law of large numbers.Proc

    Anatole Beck. A convexity condition in Banach spaces and the strong law of large numbers.Proc. Amer. Math. Soc., 13:329–334, 1962

    1962

  25. [26]

    Beck and W

    J. Beck and W. W. L. Chen. Note on irregularities of distribution. II. Proc. London Math. Soc. (3), 61(2):251–272, 1990

    1990

  26. [27]

    Balanced two-colorings of finite sets in the square i

    József Beck. Balanced two-colorings of finite sets in the square i. Combinatorica, 1(4):327–335, 1981

    1981

  27. [28]

    Roth’s estimate of the discrepancy of integer sequences is nearly sharp.Combinatorica, 1(4):319–325, 1981

    József Beck. Roth’s estimate of the discrepancy of integer sequences is nearly sharp.Combinatorica, 1(4):319–325, 1981

    1981

  28. [29]

    Irregularities of distribution

    József Beck. Irregularities of distribution. II.Proc. London Math. Soc. (3), 56(1):1–50, 1988

    1988

  29. [30]

    József Beck and William W. L. Chen.Irregularities of distribution, volume 89 ofCambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 1987

    1987

  30. [31]

    Integer-making theorems.Discrete Ap- plied Mathematics, 3(1):1–8, 1981

    József Beck and Tibor Fiala. Integer-making theorems.Discrete Ap- plied Mathematics, 3(1):1–8, 1981

    1981

  31. [32]

    A note on the Beck-Fiala theo- rem.Combinatorica, 17(1):147–149, 1997

    Debe Bednarchak and Martin Helm. A note on the Beck-Fiala theo- rem.Combinatorica, 17(1):147–149, 1997

    1997

  32. [33]

    Lacey, and Armen Vagharshakyan

    Dmitriy Bilyk, Michael T. Lacey, and Armen Vagharshakyan. On the small ball inequality in all dimensions.J. Funct. Anal., 254(9):2470– 2502, 2008

    2008

  33. [34]

    On the discrepancy of3permutations.Random Struc- tures Algorithms, 1(2):215–220, 1990

    Géza Bohus. On the discrepancy of3permutations.Random Struc- tures Algorithms, 1(2):215–220, 1990

    1990

  34. [35]

    The Brunn-Minkowski inequality in Gauss space.In- ventiones Mathematicae, 30:207, 1975

    Christer Borell. The Brunn-Minkowski inequality in Gauss space.In- ventiones Mathematicae, 30:207, 1975

    1975

  35. [36]

    The Ehrhard inequality.Acad

    Christer Borell. The Ehrhard inequality.Acad. Sci. Paris, 337(10):663–666, 2003

    2003

  36. [37]

    An improvement of the Beck-Fiala theorem.Combin

    Boris Bukh. An improvement of the Beck-Fiala theorem.Combin. Probab. Comput., 25(3):380–398, 2016

    2016

  37. [38]

    Tight hardness results for minimizing discrepancy

    Moses Charikar, Alantha Newman, and Aleksandar Nikolov. Tight hardness results for minimizing discrepancy. InACM-SIAM Sympo- sium on Discrete Algorithms, SODA, pages 1607–1614, 2011. BIBLIOGRAPHY168

    2011

  38. [39]

    Chazelle.The discrepancy method: randomness and complexity

    B. Chazelle.The discrepancy method: randomness and complexity. Cambridge University Press, 2001

    2001

  39. [40]

    Gaussian discrepancy: A probabilistic relaxation of vector balancing

    Sinho Chewi, Patrik Gerber, Philippe Rigollet, and Paxton Turner. Gaussian discrepancy: A probabilistic relaxation of vector balancing. Discret. Appl. Math., 322:123–141, 2022

    2022

  40. [41]

    Convergence a.s

    Sergej Chobanyan. Convergence a.s. of rearranged random series in Banach space and associated inequalities. InProbability in Banach spaces, pages 3–29. Birkhäuser Boston, MA, 1994

    1994

  41. [42]

    Combettes and Sebastian Pokutta

    Cyrille W. Combettes and Sebastian Pokutta. Revisiting the approx- imate Carathéodory problem via the Frank-Wolfe algorithm.Math. Program., 197(1):191–214, 2023

    2023

  42. [43]

    Towards a constructive version of Banaszczyk’s vector bal- ancing theorem

    Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov. Towards a constructive version of Banaszczyk’s vector bal- ancing theorem. InAPPROX/RANDOM, volume 60, 2016

    2016

  43. [44]

    Towards a constructive version of Banaszczyk’s vector bal- ancing theorem.Theory Comput., 15:Paper No

    Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov. Towards a constructive version of Banaszczyk’s vector bal- ancing theorem.Theory Comput., 15:Paper No. 15, 58, 2019

    2019

  44. [45]

    Balancing vectors in any norm

    Daniel Dadush, Aleksandar Nikolov, Kunal Talwar, and Nicole Tomczak-Jaegermann. Balancing vectors in any norm. InSymposium on Foundations of Computer Science, FOCS, pages 1–10. 2018

    2018

  45. [46]

    Tichy.Sequences, discrepancies and applications, volume 1651 ofLecture Notes in Mathematics

    Michael Drmota and Robert F. Tichy.Sequences, discrepancies and applications, volume 1651 ofLecture Notes in Mathematics. Springer- Verlag, Berlin, 1997

    1997

  46. [47]

    Symétrisation dans l’espace de Gauss.Mathematica Scandinavica, 53:281–301, 1983

    Antoine Ehrhard. Symétrisation dans l’espace de Gauss.Mathematica Scandinavica, 53:281–301, 1983

    1983

  47. [48]

    Proximity results and faster algorithms for integer programming using the Steinitz lemma

    Friedrich Eisenbrand and Robert Weismantel. Proximity results and faster algorithms for integer programming using the Steinitz lemma. ACM Trans. Algorithms, 16(1):5:1–5:14, 2020

    2020

  48. [49]

    Efficient algorithms for discrepancy minimization in convex sets.Random Struct

    Ronen Eldan and Mohit Singh. Efficient algorithms for discrepancy minimization in convex sets.Random Struct. Algorithms, 53(2):289– 307, 2018

    2018

  49. [50]

    A simplified disproof of Beck’s three permutations con- jecture and an application to root-mean-squared discrepancy.Combin

    Cole Franks. A simplified disproof of Beck’s three permutations con- jecture and an application to root-mean-squared discrepancy.Combin. Probab. Comput., 30(3):398–411, 2021. BIBLIOGRAPHY169

    2021

  50. [51]

    On some vector balancing problems.Studia Mathematica, 122(3):225–234, 1997

    Apostolos Giannopoulos. On some vector balancing problems.Studia Mathematica, 122(3):225–234, 1997

    1997

  51. [52]

    E. D. Gluskin. Extremal properties of orthogonal parallelepipeds and their applications to the geometry of Banach spaces.Mat. Sb. (N.S.), 136(178)(1):85–96, 1988

    1988

  52. [53]

    V. S. Grinberg and S. V. Sevastjanov. Value of the Steinitz constant. Funktsional. Anal. i Prilozhen., 14(2):56–57, 1980

    1980

  53. [54]

    Grothendieck

    A. Grothendieck. Résumé de la théorie métrique des produits ten- soriels topologiques.Bol. Soc. Mat. São Paulo, 8:1–79, 1953

    1953

  54. [55]

    Inapproximability results for set splitting and satisfiability problems with no mixed clauses.Algorithmica, 38(3):451– 469, 2004

    Venkatesan Guruswami. Inapproximability results for set splitting and satisfiability problems with no mixed clauses.Algorithmica, 38(3):451– 469, 2004

    2004

  55. [56]

    Es- sential coding theory, 2012

    Venkatesan Guruswami, Atri Rudra, and Madhu Sudan. Es- sential coding theory, 2012. Draft available athttps: //cse.buffalo.edu/faculty/atri/courses/coding-theory/ book/web-coding-book.pdf

    2012

  56. [57]

    Spielman, and Peng Zhang

    Christopher Harshaw, Fredrik Sävje, Daniel A. Spielman, and Peng Zhang. Balancing covariates in randomized experiments with the Gram–Schmidt walk design.Journal of the American Statistical As- sociation, 119(548):2934–2946, 2024

    2024

  57. [58]

    Nicholas J. A. Harvey, Roy Schwartz, and Mohit Singh. Discrepancy without partial colorings. InAPPROX/RANDOM, volume 28, pages 258–273, 2014

    2014

  58. [59]

    Near-optimal herding

    Nick Harvey and Samira Samadi. Near-optimal herding. InConference on Learning Theory, COLT, pages 1165–1182, 2014

    2014

  59. [60]

    A Fourier-analytic approach for the discrepancy of random set systems

    Rebecca Hoberg and Thomas Rothvoss. A Fourier-analytic approach for the discrepancy of random set systems. InACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2547–2556, 2019

    2019

  60. [61]

    Spencer’s theorem in nearly input-sparsity time

    Vishesh Jain, Ashwin Sah, and Mehtaab Sawhney. Spencer’s theorem in nearly input-sparsity time. InACM-SIAM Symposium on Discrete Algorithms, SODA, pages 3946–3958, 2023

    2023

  61. [62]

    Linear-sized sparsi- fiers via near-linear time discrepancy theory

    Arun Jambulapati, Victor Reis, and Kevin Tian. Linear-sized sparsi- fiers via near-linear time discrepancy theory. InACM-SIAM Sympo- sium on Discrete Algorithms, SODA, pages 5169–5208, 2024. BIBLIOGRAPHY170

    2024

  62. [63]

    A tighter relation between hereditary discrepancy and determinant lower bound

    Haotian Jiang and Victor Reis. A tighter relation between hereditary discrepancy and determinant lower bound. InSymposium on Simplic- ity in Algorithms (SOSA), pages 308–313. 2022

    2022

  63. [64]

    M. I. Kadec. On a property of broken lines inn-dimensional space. Uspehi Matem. Nauk (N.S.), 8(1(53)):139–143, 1953

    1953

  64. [65]

    Practical and private (deep) learning without sampling or shuffling

    Peter Kairouz, Brendan McMahan, Shuang Song, Om Thakkar, Abhradeep Thakurta, and Zheng Xu. Practical and private (deep) learning without sampling or shuffling. InInternational Conference on Machine Learning, ICML, pages 5213–5225, 2021

    2021

  65. [66]

    Narendra Karmarkar and Richard M. Karp. An efficient approxima- tion scheme for the one-dimensional bin-packing problem. InSympo- sium on Foundations of Computer Science, pages 312–320, 1982

    1982

  66. [67]

    Optimal online discrepancy minimization

    Janardhan Kulkarni, Victor Reis, and Thomas Rothvoss. Optimal online discrepancy minimization. InSymposium on Theory of Com- puting, STOC, pages 1832–1840. ACM, 2024

    2024

  67. [68]

    On operators factorizable throughLp space

    Stanislaw Kwapień. On operators factorizable throughLp space. In Actes du Colloque d’Analyse Fonctionnelle, volume 100 ofSupplément au Bull. Soc. Math. France, pages 215–225. 1972

    1972

  68. [69]

    On range searching in the group model and combinatorial discrepancy.SIAM J

    Kasper Green Larsen. On range searching in the group model and combinatorial discrepancy.SIAM J. Comput., 43(2):673–686, 2014

    2014

  69. [70]

    Royen’s proof of the Gaussian corre- lation inequality

    RafałLatał a and Dariusz Matlak. Royen’s proof of the Gaussian corre- lation inequality. InGeometric aspects of functional analysis, volume 2169 ofLecture Notes in Math., pages 265–275. Springer, 2017

    2017

  70. [71]

    R. Latala. On some inequalities for Gaussian measures.Proc. ICM, 2:813–822, 2002

    2002

  71. [72]

    Ravi, and Mohit Singh.Iterative methods in combi- natorial optimization

    Lap Chi Lau, R. Ravi, and Mohit Singh.Iterative methods in combi- natorial optimization. Cambridge University Press, New York, 2011

    2011

  72. [73]

    Proofs of the Gaussian isoperimetric inequal- ity.https://perso.math.univ-toulouse.fr/ledoux/files/2024/ 01/Gaussian-isoperimetry.pdf

    Michel Ledoux. Proofs of the Gaussian isoperimetric inequal- ity.https://perso.math.univ-toulouse.fr/ledoux/files/2024/ 01/Gaussian-isoperimetry.pdf

    2024

  73. [74]

    Isoperimetry and Gaussian analysis

    Michel Ledoux. Isoperimetry and Gaussian analysis. InLectures on probability theory and statistics (Saint-Flour, 1994), volume 1648 of Lecture Notes in Math., pages 165–294. Springer, Berlin, 1996

    1994

  74. [75]

    Springer-Verlag, Berlin, 1991

    Michel Ledoux and Michel Talagrand.Probability in Banach spaces, volume 23. Springer-Verlag, Berlin, 1991. BIBLIOGRAPHY171

    1991

  75. [76]

    Lower bounds in communication com- plexity.Found

    Troy Lee and Adi Shraibman. Lower bounds in communication com- plexity.Found. Trends Theor. Comput. Sci., 3(4):263–398, 2009

    2009

  76. [77]

    A direct product the- orem for discrepancy

    Troy Lee, Adi Shraibman, and Robert Špalek. A direct product the- orem for discrepancy. InConference on Computational Complexity, CCC, pages 71–80, 2008

    2008

  77. [78]

    Determin- istic discrepancy minimization via the multiplicative weight update method

    Avi Levy, Harishchandra Ramadas, and Thomas Rothvoss. Determin- istic discrepancy minimization via the multiplicative weight update method. InInteger Programming and Combinatorial Optimization, IPCO, pages 380–391, 2017

    2017

  78. [79]

    On the gap between hereditary dis- crepancy and the determinant lower bound.SIAM J

    Lily Li and Aleksandar Nikolov. On the gap between hereditary dis- crepancy and the determinant lower bound.SIAM J. Discrete Math., 38(2):1222–1238, 2024

    2024

  79. [80]

    Complexity measures of sign matrices.Combinatorica, 27(4):439–463, 2007

    Nati Linial, Shahar Mendelson, Gideon Schechtman, and Adi Shraib- man. Complexity measures of sign matrices.Combinatorica, 27(4):439–463, 2007

    2007

  80. [81]

    Liu, Ashwin Sah, and Mehtaab Sawhney

    Yang P. Liu, Ashwin Sah, and Mehtaab Sawhney. A Gaussian fixed point random walk. InInnovations in Theoretical Computer Science Conference, ITCS, pages 101:1–101:10, 2022

    2022

Showing first 80 references.