Pith. sign in

REVIEW 2 major objections 3 minor 3 cited by

Decoupling via Affine Spectral-Independence: Beck-Fiala and Koml\'os Bounds Beyond Banaszczyk

T0 review · 2 major / 3 minor · reviewed 2026-08-06 · deepseek-v4-flash

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

Pith's one-line read Resolves the Beck-Fiala conjecture for degree $k \ge \log^2 n$, gives an $\widetilde{O}(\sqrt{k}+\sqrt{\log n})$ bound for smaller degree, and improves the Komlós discrepancy bound to $\widetilde{O}(\log^{1/4} n)$, all with polynomial-time

desk verdict Major claimed improvements on Beck-Fiala and Komlós from a new decoupling technique, but the provided text is corrupted so the load-bearing feasibility lemmas cannot be checked. read the letter →

arxiv 2508.03961 v2 pith:LPYTOKDB submitted 2025-08-05 math.CO cs.DMcs.DSmath.PR

Nikhil Bansal , Haotian Jiang This is my paper · ORCID
classification math.COcs.DMcs.DSmath.PR MSC 05D4068W20
keywords discrepancyBeck-FialaconjectureKomlóssemidefiniteprogrammingroundingalgorithmsaffinespectralindependencediscreteBrownianmotionsetsystems
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

This paper claims to settle the Beck-Fiala conjecture whenever the degree satisfies $k \ge \log^2 n$: every set system on $n$ elements, with each element in at most $k$ sets, has a ±1 coloring whose largest set imbalance is $O(\sqrt{k})$, and such a coloring can be found in polynomial time. For smaller degree it claims $\widetilde{O}(\sqrt{k}+\sqrt{\log n})$, improving the previous $O(\sqrt{k\log n})$ for every $k$. For the Komlós problem it claims that every $m\times n$ matrix with unit-length columns has discrepancy $\widetilde{O}(\log^{1/4} n)$, improving the previous $O(\sqrt{\log n})$. The unifying idea is a rounding scheme: a discrete Brownian motion guided by a semidefinite program, enriched with affine spectral-independence constraints that decouple the evolution of discrepancies across rows. If correct, these results replace two long-standing benchmarks and add a general rounding technique to discrepancy theory.

What carries the argument

The load-bearing mechanism is the set of affine spectral-independence constraints imposed on the SDP that steers the rounding. For a distribution over ±1 colorings, spectral independence means that no coordinate has a large influence on the others; the affine version enforces this on the distribution restricted to colorings consistent with the current partial rounding. During the discrete Brownian motion the algorithm re-solves the SDP and maintains these constraints, which decouples the discrepancy evolution of different rows. This decoupling is what produces the sharp count of rows exceeding a threshold, and it is the single new tool from which all three discrepancy bounds follow.

What would settle it

Exhibit one set system with degree $k \ge \log^2 n$ and discrepancy $\omega(\sqrt{k})$, or one unit-length-column matrix with discrepancy $\omega(\log^{1/4} n)$; the theorems assert no such instance exists. A computational check is to implement the SDP-guided discrete Brownian motion with the affine spectral-independence constraints and run it on random matrices and set systems—the paper promises polynomial-time colorings at the stated rates, so a single violating instance would disprove the claim.

Watch

Extended reading notes

Core claim

The paper's central claim is that the Beck-Fiala conjecture is true for large degree: for every set system on $n$ elements where each element lies in at most $k$ sets and $k \ge \log^2 n$, there is a $\pm1$ coloring with discrepancy $O(\sqrt{k})$, found in polynomial time. In the remaining degree range $k \le \log^2 n$, the claimed bound is $\widetilde{O}(\sqrt{k}+\sqrt{\log n})$, which is no worse than the previous $O(\sqrt{k\log n})$ and matches $O(\sqrt{k})$ up to a $\sqrt{\log n}$ additive term. For Komlós, every matrix with unit-length columns is claimed to admit a $\pm1$ signing with row sums bounded by $\widetilde{O}(\log^{1/4} n)$, improving $O(\sqrt{\log n})$. The proof runs a discr

Load-bearing premise

The load-bearing premise is that the extra constraints added to the rounding program can be maintained at every step of the discrete Brownian motion and that they really do separate the growth of different rows' discrepancies as tightly as the proof needs; if either part fails, the stated Beck-Fiala and Komlós bounds collapse.

Editorial extensions

If this is right

  • Any set system with degree $k \ge \log^2 n$ has discrepancy $O(\sqrt{k})$, so the Beck-Fiala conjecture is settled in the entire large-degree regime.
  • For $k \le \log^2 n$, the discrepancy is $\widetilde{O}(\sqrt{k}+\sqrt{\log n})$, which is never worse than the prior $O(\sqrt{k\log n})$ and is within an additive $\widetilde{O}(\sqrt{\log n})$ of the conjectured $O(\sqrt{k})$.
  • The Komlós bound for unit-length-column matrices drops to $\widetilde{O}(\log^{1/4} n)$, the first improvement over $O(\sqrt{\log n})$.
  • All of these colorings are produced by polynomial-time algorithms, making the existential bounds effective.
  • The affine spectral-independence decoupling is offered as a reusable rounding primitive, so the method can be carried to other SDP-based rounding problems.

Reading between the lines

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

  • Going beyond the paper: the remaining Beck-Fiala gap is only the additive $\widetilde{O}(\sqrt{\log n})$ for $k \le \log^2 n$, so a sharper small-degree argument could close the conjecture entirely.
  • Going beyond the paper: the $1/4$ exponent in the Komlós bound may reflect a counting tradeoff rather than a barrier; pushing the same constraints is a plausible route toward $\mathrm{poly}(\log\log n)$ or $O(1)$.
  • Going beyond the paper: the SDP-plus-spectral-independence template should transfer to other balancing problems where cross-row correlation is the obstacle, such as vector balancing in $\ell_p$ norms or hereditary discrepancy.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 3 minor

Summary. The paper claims three discrepancy bounds: (1) for any set system on n elements with degree k >= log^2 n, a polynomial-time algorithm achieves discrepancy O(sqrt(k)), resolving the Beck-Fiala conjecture in that regime; (2) for k <= log^2 n, the bound is O~(sqrt(k) + sqrt(log n)); (3) for the Komlos problem, every m x n matrix with unit-length columns admits discrepancy O~(log^{1/4} n). These improve on Banaszczyk's O(sqrt(k log n)) and O(sqrt(log n)) bounds. The method is a discrete Brownian-motion rounding guided by an SDP augmented with 'affine spectral-independence' constraints that allegedly decouple the discrepancy evolution of different rows. The supplied full text, however, is corrupted mojibake; only the abstract and fragments are readable, so I cannot check any lemma, proof, or theorem statement beyond the abstract.

Significance. If the claims are correct, this is a major advance: it resolves the Beck-Fiala conjecture for all k >= log^2 n, removing a log factor from the previous best bound in that regime, and it gives the first improvement over Banaszczyk's O(sqrt(log n)) Komlos bound. The polynomial-time algorithms add further value, and the proposed 'decoupling via affine spectral-independence' technique could be of independent interest. The abstract is internally consistent and does not show circularity: the final discrepancy bounds are compared against external benchmarks, not fitted to them. However, the significance is entirely conditional: none of the proof ingredients can be audited from the submitted text, and the corrupted full text prevents any verification of the central technical claims.

major comments (2)
  1. [Abstract] The central claim rests on a load-bearing technical premise that is not verifiable from the supplied text. Specifically, the abstract says the algorithms 'add some extra affine spectral-independence constraints, which effectively decouple the evolution of discrepancies across different rows.' To prove the stated bounds, one must establish at least three things: (i) at every step of the discrete Brownian motion, the SDP with these added constraints remains feasible; (ii) the constraints yield a quantitative bound on the number of rows accumulating large discrepancy; and (iii) this bound has the correct exponent so that the final discrepancy is O(sqrt(k)) and O(log^{1/4} n), respectively. The full text is corrupted mojibake, so none of these lemmas or their proofs can be checked. This is not an accusation of error, but the absence of auditable evidence is decisive for my recommendation.
  2. [Full text (all sections)] The supplied full text is unreadable: it consists almost entirely of mojibake characters. I cannot locate the main theorems, definitions of affine spectral independence, SDP formulations, or the analysis of the Brownian-motion process. In a normal review I would cite specific sections and equations; here no section number can be trusted because the text cannot be parsed. The manuscript therefore does not currently provide the evidence needed to support its abstract-level claims.
minor comments (3)
  1. [Full text header] The full text contains an inserted header 'arXiv:2508.03963v4 [cs.AI] 24 Apr 2026', which is inconsistent with the claimed paper identifier (arXiv:2508.03961) and subject classification (math.CO). This metadata mismatch should be corrected; more importantly, it underscores that the submitted file is not in a reliable state.
  2. [Abstract] The phrase 'resolve the Beck-Fiala Conjecture for k >= log^2 n' is potentially misleading if read in isolation. The conjecture is about all k; the paper resolves it only in the high-degree regime. The sentence is already qualified, but explicit wording such as 'resolve the conjecture in this regime' would be clearer.
  3. [Abstract] The notation O~(.) is defined as hiding poly(log log n) factors. This is nonstandard, since O~ typically hides powers of log n. I recommend adding a sentence explaining why the definition is restricted to poly(log log n), especially because the small-k bound and the Komlos bound may have very different logarithmic dependencies.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity identified; the claimed bounds are compared against external Banaszczyk benchmarks, and the new affine spectral-independence constraints are proof ingredients rather than fitted targets.

full rationale

The derivation chain, as far as the abstract and the legible fragments of the corrupted full text allow auditing, does not reduce any claimed bound to its own assumptions. The target results are stated as inequalities against Banaszczyk's external O(sqrt(k log n)) and O(sqrt(log n)) bounds, not as outputs of parameters fitted to those targets. The affine spectral-independence constraints are introduced as additional feasibility constraints in the SDP-guided Brownian motion; nothing visible defines them in terms of the final discrepancy bound, and no uniqueness theorem imported from the authors' prior work is invoked to forbid alternative approaches. The fact that the feasibility of these constraints is a load-bearing technical premise is a correctness risk, especially since the corrupted text prevents full verification, but it is not circularity. No self-citation that carries the argument can be identified, and the curious inserted line 'arXiv:2508.03963v4 [cs.AI] 24 Apr 2026' is a textual artifact without bearing on circularity. The honest finding is therefore no significant circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No fitted numbers appear: this is a theorem-proving paper, so the free-parameter list is empty. The 'affine spectral-independence constraints' are a new proof ingredient, a family of constraints added to an SDP, not a postulated physical or combinatorial entity of the kind the ledger tracks. The axioms listed are the natural background assumptions of SDP-rounding proofs; exact section-level citations are impossible because the supplied body text is corrupted.

assumptions (4)
  • domain assumption The rounding SDP, including the affine spectral-independence constraints, has a feasible solution at every step of the discrete Brownian motion.
    This is the load-bearing precondition of the new technique. If the constraints cannot be maintained during the walk, the decoupling argument fails. Location: the algorithmic description summarized in the abstract; the body is unreadable in the supplied copy.
  • domain assumption The spectral-independence bounds implied by the affine constraints are strong enough to control the number of rows whose discrepancy exceeds thresholds.
    The paper's stated goal is to 'control how many rows accumulate large discrepancies at any point during the process.' The decoupling estimate is the quantitative engine behind both new bounds. Exact lemma unverifiable from the abstract.
  • standard math Standard martingale and concentration inequalities hold for the discrete Brownian motion used in the rounding.
    Any SDP-guided random-walk rounding needs tail bounds on the accumulated discrepancy vector. These are standard tools in the discrepancy literature (Banaszczyk-type arguments), but the specific lemma cannot be checked in the corrupted body.
  • domain assumption Inputs can be normalized as stated: degree-k set systems and matrices with unit-length columns.
    The problem setup from the abstract: set systems with degree k and m×n matrices with unit-length columns. Standard normalization in this literature; the claim being generalized is exactly the Komlós and Beck-Fiala conjectures.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Decoupling via Affine Spectral-Independence: Beck-Fiala and Koml\'os Bounds Beyond Banaszczyk." pith.science (2026). https://pith.science/paper/LPYTOKDB

@misc{pith2026250803961,
  author       = {Pith},
  title        = {Pith review of: Decoupling via Affine Spectral-Independence: Beck-Fiala and Koml\'os Bounds Beyond Banaszczyk},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LPYTOKDB}},
  note         = {Machine review of arXiv:2508.03961}
}
abstract

The Beck-Fiala Conjecture [Discrete Appl. Math, 1981] asserts that any set system of $n$ elements with degree $k$ has combinatorial discrepancy $O(\sqrt{k})$. A substantial generalization is the Koml\'os Conjecture, which states that any $m \times n$ matrix with unit length columns has discrepancy $O(1)$. In this work, we resolve the Beck-Fiala Conjecture for $k \geq \log^2 n$. We also give an $\widetilde{O}(\sqrt{k} + \sqrt{\log n})$ bound for $k \leq \log^2 n$, where $\widetilde{O}(\cdot)$ hides $\mathsf{poly}(\log \log n)$ factors. These bounds improve upon the $O(\sqrt{k \log n})$ bound due to Banaszczyk [Random Struct. Algor., 1998]. For the Komlos problem, we give an $\widetilde{O}(\log^{1/4} n)$ bound, improving upon the previous $O(\sqrt{\log n})$ bound [Random Struct. Algor., 1998]. All of our results also admit efficient polynomial-time algorithms. To obtain these results, we exploit a new technique of ``decoupling via affine spectral-independence'' in designing rounding algorithms. In particular, our algorithms obtain the desired colorings via a discrete Brownian motion, guided by a semidefinite program (SDP). Besides standard constraints used in prior works, we add some extra affine spectral-independence constraints, which effectively decouple the evolution of discrepancies across different rows, and allow us to better control how many rows accumulate large discrepancies at any point during the process. This new technique is quite general and may be of independent interest.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Algorithms for Standard-form ILP Problems via Koml\'os' Discrepancy Setting

    cs.DS 2026-04 unverdicted novelty 8.0 of 10

    Standard-form ILP can be solved in O(κ_k)^{2k} Δ² log Δ arithmetic operations and feasibility in O(κ_k)^k Δ bit operations, where κ_k is the Komlós discrepancy constant.

  2. Online Beck--Fiala Down to Logarithmic Sparsity

    math.CO 2026-07 conditional novelty 7.0 of 10

    A new online random-walk algorithm achieves O(√d) prefix discrepancy for d-sparse vectors whenever d ≥ log(T)(log log T)^{2+η}, proving Beck–Fiala in that regime and resolving the online Spencer conjecture.

  3. Online balancing of vectors with small coordinates

    math.CO 2026-08 accept novelty 6.0 of 10

    This paper achieves constant prefix discrepancy for online signed balancing of small-coordinate vectors with failure probability about T exp(-c d / ln^2(ed)), and proves the ln^2 scale is a barrier for the compact-pot...

Reference graph

Works this paper leans on

59 extracted references · 55 canonical work pages · cited by 3 Pith papers

  1. [1]

    Spectral independence in high-dimensional expanders and applications to the hardcore model

    Nima Anari, Kuikui Liu, and Shayan Oveis Gharan. Spectral independence in high-dimensional expanders and applications to the hardcore model. In Symposium on Foundations of Computer Science, FOCS , pages 1319--1330, 2020

    work page 2020

  2. [2]

    Liu, and Mehtaab Sawhney

    Ryan Alweiss, Yang P. Liu, and Mehtaab Sawhney. Discrepancy minimization via a self-balancing walk. In Symposium on Theory of Computing, STOC , pages 14--20, 2021

    work page 2021

  3. [3]

    The discrepancy of random rectangular matrices

    Dylan J Altschuler and Jonathan Niles-Weed. The discrepancy of random rectangular matrices. Random Structures & Algorithms , 60(4):551--593, 2022

    work page 2022

  4. [4]

    Balancing vectors and G aussian measures of n-dimensional convex bodies

    Wojciech Banaszczyk. Balancing vectors and G aussian measures of n-dimensional convex bodies. Random Structures & Algorithms , 12(4):351--360, 1998

    work page 1998

  5. [5]

    Constructive algorithms for discrepancy minimization

    Nikhil Bansal. Constructive algorithms for discrepancy minimization. In Symposium on Foundations of Computer Science , pages 3--10, 2010

    work page 2010

  6. [6]

    On series of signed vectors and their rearrangements

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

    work page 2012

  7. [7]

    Discrepancy theory and related algorithms

    Nikhil Bansal. Discrepancy theory and related algorithms. In Proc. Int. Cong. Math , volume 7, pages 5178--5210, 2022

    work page 2022

  8. [8]

    On a generalization of iterated and randomized rounding

    Nikhil Bansal. On a generalization of iterated and randomized rounding. Theory of Computing , 20(1):1--23, 2024

    work page 2024

Show all 59 references
  1. [9]

    An algorithm for K oml \'o s conjecture matching banaszczyk's bound

    Nikhil Bansal, Daniel Dadush, and Shashwat Garg. An algorithm for K oml \'o s conjecture matching banaszczyk's bound. SIAM Journal on Computing , 48(2):534--553, 2019

    2019

  2. [10]

    The Gram-Schmidt walk: a cure for the Banaszczyk blues

    Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett. The Gram-Schmidt walk: a cure for the Banaszczyk blues. In Symposium on Theory of Computing, STOC , pages 587--597, 2018

    2018

  3. [11]

    Roth’s estimate of the discrepancy of integer sequences is nearly sharp

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

    1981

  4. [12]

    I nteger-making

    J \'o zsef Beck and Tibor Fiala. “ I nteger-making” theorems. Discrete Applied Mathematics , 3(1):1--8, 1981

    1981

  5. [13]

    Algorithmic discrepancy beyond partial coloring

    Nikhil Bansal and Shashwat Garg. Algorithmic discrepancy beyond partial coloring. In Symposium on Theory of Computing, STOC , pages 914--926, 2017

    2017

  6. [14]

    A note on the beck-fiala theorem

    Debe Bednarchak and Martin Helm. A note on the beck-fiala theorem. Combinatorica , 17(1):147--149, 1997

    1997

  7. [15]

    An improved bound for the Beck-Fiala conjecture

    Nikhil Bansal and Haotian Jiang. An improved bound for the Beck-Fiala conjecture. In 66th IEEE Symposium on Foundations of Computer Science (FOCS) . IEEE, 2025

    2025

  8. [16]

    Quasi-Monte Carlo Beyond Hardy-Krause

    Nikhil Bansal and Haotian Jiang. Quasi-Monte Carlo Beyond Hardy-Krause . In Symposium on Discrete Algorithms (SODA) , pages 2051--2075. SIAM, 2025

  9. [17]

    Smoothed analysis of the Koml \'o s conjecture

    Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, and Makrand Sinha. Smoothed analysis of the Koml \'o s conjecture . In Intl. Colloquium on Automata, Languages, and Programming (ICALP) , pages 14--1, 2022

    2022

  10. [18]

    A unified approach to discrepancy minimization

    Nikhil Bansal, Aditi Laddha, and Santosh Vempala. A unified approach to discrepancy minimization. In APPROX/RANDOM , pages 1--1, 2022

    2022

  11. [19]

    On the discrepancy of random low degree set systems

    Nikhil Bansal and Raghu Meka. On the discrepancy of random low degree set systems. Random Structures & Algorithms , 57(3):695--705, 2020

    2020

  12. [20]

    Cover-decomposition and polychromatic numbers

    B \'e la Bollob \'a s, David Pritchard, Thomas Rothvo , and Alex Scott. Cover-decomposition and polychromatic numbers. SIAM Journal on Discrete Mathematics , 27(1):240--256, 2013

    2013

  13. [21]

    Flow time scheduling and prefix Beck-Fiala

    Nikhil Bansal, Lars Rohwedder, and Ola Svensson. Flow time scheduling and prefix Beck-Fiala . In Symposium on Theory of Computing, STOC , pages 331--342, 2022

    2022

  14. [22]

    Deterministic discrepancy minimization

    Nikhil Bansal and Joel Spencer. Deterministic discrepancy minimization. Algorithmica , 67:451--471, 2013

    2013

  15. [23]

    An improvement of the beck--fiala theorem

    Boris Bukh. An improvement of the beck--fiala theorem. Combinatorics, Probability and Computing , 25(3):380--398, 2016

    2016

  16. [24]

    The Discrepancy Method: Randomness and Complexity

    Bernard Chazelle. The Discrepancy Method: Randomness and Complexity . Cambridge University Press, 2000

    2000

  17. [25]

    A quasi-monte carlo data structure for smooth kernel evaluations

    Moses Charikar, Michael Kapralov, and Erik Waingarten. A quasi-monte carlo data structure for smooth kernel evaluations. In Symposium on Discrete Algorithms (SODA) , pages 5118--5144, 2024

    2024

  18. [26]

    A note on norms of signed sums of vectors

    Giorgos Chasapis and Nikos Skarmogiannis. A note on norms of signed sums of vectors. Advances in Geometry , 21(1):5--14, 2021

    2021

  19. [27]

    A panorama of discrepancy theory , volume 2107

    William Chen, Anand Srivastav, and Giancarlo Travaglini. A panorama of discrepancy theory , volume 2107. Springer, 2014

    2014

  20. [28]

    Towards a constructive version of B anaszczyk's vector balancing theorem

    Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov. Towards a constructive version of B anaszczyk's vector balancing theorem. In APPROX/RANDOM 2016 , pages 28:1--28:12, 2016

    2016

  21. [29]

    On the beck-fiala conjecture for random set systems

    Esther Ezra and Shachar Lovett. On the beck-fiala conjecture for random set systems. Random Structures & Algorithms , 54(4):665--675, 2019

    2019

  22. [30]

    Efficient algorithms for discrepancy minimization in convex sets

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

    2018

  23. [31]

    On the discrepancy of random matrices with many columns

    Cole Franks and Michael Saks. On the discrepancy of random matrices with many columns. Random Structures & Algorithms , 57(1):64--96, 2020

    2020

  24. [32]

    Extremal properties of orthogonal parallelepipeds and their applications to the geometry of banach spaces

    Efim Davydovich Gluskin. Extremal properties of orthogonal parallelepipeds and their applications to the geometry of banach spaces. Mathematics of the USSR-Sbornik , 64(1):85, 1989

    1989

  25. [33]

    On a conjecture of k \"o mlos about signed sums of vectors inside the sphere

    D Hajela. On a conjecture of k \"o mlos about signed sums of vectors inside the sphere. European Journal of Combinatorics , 9(1):33--37, 1988

    1988

  26. [34]

    A note on the discrepancy of matrices with bounded row and column sums

    Nicholas JA Harvey. A note on the discrepancy of matrices with bounded row and column sums. Discrete Mathematics , 338(4):517--521, 2015

    2015

  27. [35]

    On the beck-fiala theorem

    Martin Helm. On the beck-fiala theorem. Discrete mathematics , 207(1-3):73--87, 1999

    1999

  28. [36]

    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. In Symposium on Discrete Algorithms (SODA) , pages 2547--2556, 2019

    2019

  29. [37]

    Discrepancy without partial colorings

    Nicholas Harvey, Roy Schwartz, and Mohit Singh. Discrepancy without partial colorings. In APPROX/RANDOM , 2014

    2014

  30. [38]

    Balancing covariates in randomized experiments with the G ram-- S chmidt walk design

    Christopher Harshaw, Fredrik S \"a vje, Daniel A Spielman, and Peng Zhang. Balancing covariates in randomized experiments with the G ram-- S chmidt walk design. Journal of the American Statistical Association , 119(548):2934--2946, 2024

    2024

  31. [39]

    Spencer's theorem in nearly input-sparsity time

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

    2023

  32. [40]

    Personal Communication

    Jeff Kahn. Personal Communication

  33. [41]

    The discrepancy of unsatisfiable matrices and a lower bound for the koml \'o s conjecture constant

    Dmitriy Kunisky. The discrepancy of unsatisfiable matrices and a lower bound for the koml \'o s conjecture constant. SIAM Journal on Discrete Mathematics , 37(2):586--603, 2023

    2023

  34. [42]

    Constructive discrepancy minimization by walking on the edges

    Shachar Lovett and Raghu Meka. Constructive discrepancy minimization by walking on the edges. SIAM Journal on Computing , 44(5):1573--1582, 2015

    2015

  35. [43]

    Deterministic discrepancy minimization via the multiplicative weight update method

    Avi Levy, Harishchandra Ramadas, and Thomas Rothvoss. Deterministic discrepancy minimization via the multiplicative weight update method. In Integer Programming and Combinatorial Optimization (IPCO) , pages 380--391, 2017

    2017

  36. [44]

    Geometric discrepancy: An illustrated guide , volume 18

    Jiri Matousek. Geometric discrepancy: An illustrated guide , volume 18. Springer Science & Business Media, 2009

    2009

  37. [45]

    Combinatorial discrepancy for boxes via the _2 norm

    Jir \' Matousek and Aleksandar Nikolov. Combinatorial discrepancy for boxes via the _2 norm. In Symposium on Computational Geometry, SoCG , pages 1--15, 2015

    2015

  38. [46]

    The koml \'o s conjecture holds for vector colorings

    Aleksandar Nikolov. The koml \'o s conjecture holds for vector colorings. arXiv preprint arXiv:1301.4039 , 2013

    2013 arXiv

  39. [47]

    Tighter bounds for the discrepancy of boxes and polytopes

    Aleksandar Nikolov. Tighter bounds for the discrepancy of boxes and polytopes. Mathematika , 63(3):1091--1113, 2017

    2017

  40. [48]

    Beck's three permutations conjecture: A counterexample and some consequences

    Alantha Newman, Ofer Neiman, and Aleksandar Nikolov. Beck's three permutations conjecture: A counterexample and some consequences. In Symposium on Foundations of Computer Science, FOCS , pages 253--262, 2012

    2012

  41. [49]

    The geometry of differential privacy: the sparse and approximate cases

    Aleksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In Symposium on Theory of Computing, STOC , pages 351--360, 2013

    2013

  42. [50]

    A spectral bound on hypergraph discrepancy

    Aditya Potukuchi. A spectral bound on hypergraph discrepancy. In International Colloquium on Automata, Languages, and Programming (ICALP) , pages 93:1--93:14, 2020

    2020

  43. [51]

    Near-optimal coresets of kernel density estimates

    Jeff M Phillips and Wai Ming Tai. Near-optimal coresets of kernel density estimates. Discrete & Computational Geometry , 63:867--887, 2020

    2020

  44. [52]

    Discrepancy minimization via regularization

    Lucas Pesenti and Adrian Vladu. Discrepancy minimization via regularization. In Symposium on Discrete Algorithms, SODA , pages 1734--1758, 2023

    2023

  45. [53]

    Better bin packing approximations via discrepancy theory

    Thomas Rothvoss. Better bin packing approximations via discrepancy theory. SIAM Journal on Computing , 45(3):930--946, 2016

    2016

  46. [54]

    Constructive discrepancy minimization for convex sets

    Thomas Rothvoss. Constructive discrepancy minimization for convex sets. SIAM Journal on Computing , 46(1):224--234, 2017

    2017

  47. [55]

    Linear size sparsifier and the geometry of the operator norm ball

    Victor Reis and Thomas Rothvoss. Linear size sparsifier and the geometry of the operator norm ball. In Symposium on Discrete Algorithms, SODA , 2020

    2020

  48. [56]

    Six standard deviations suffice

    Joel Spencer. Six standard deviations suffice. Transactions of the American mathematical society , 289(2):679--706, 1985

    1985

  49. [57]

    Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems

    Aravind Srinivasan. Improving the discrepancy bound for sparse matrices: Better approximations for sparse lattice approximation problems. In Symposium on Discrete algorithms (SODA) , pages 692--701, 1997

    1997

  50. [58]

    The E rd\"os discrepancy problem

    Terence Tao. The E rd\"os discrepancy problem. Discrete Analysis , feb 28 2016

    2016

  51. [59]

    Balancing gaussian vectors in high dimension

    Paxton Turner, Raghu Meka, and Philippe Rigollet. Balancing gaussian vectors in high dimension. In Conference on Learning Theory , pages 3455--3486. PMLR, 2020

    2020

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.