Pith. sign in

REVIEW 4 major objections 4 minor 52 references

Online Discrepancy Minimization for Sub-Gaussian Inputs via Regularization and Restriction

T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read This paper proves a polynomial-time online algorithm that keeps terminal discrepancy at $O(\sigma^8\sqrt{n})$ for i.i.d. sub-Gaussian inputs, with failure probability $\exp(-\Omega(\sigma^3\sqrt{n}))$, for every finite horizon $T$.

desk verdict A plausible and genuinely new potential-based online discrepancy algorithm for sub-Gaussian inputs, but the central proof currently rests on three explicitly omitted technical estimates. read the letter →

arxiv 2608.10040 v1 pith:5ABKVID7 submitted 2026-08-10 cs.DS cs.DMmath.COmath.PR

Nicola Wengiel This is my paper · ORCID
classification cs.DScs.DMmath.COmath.PR
keywords onlinediscrepancyminimizationsub-GaussianrandomvectorsregularizedinfinitynormpotentialfunctionBernoullimaskingsymmetricbinaryperceptronexponentialmomentmethodhorizon-independentbounds
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 establishes a polynomial-time online algorithm for discrepancy minimization: when the arriving vectors have independent, symmetric, centered, unit-variance sub-Gaussian coordinates with norm at most $\sigma$, the terminal discrepancy is $O(\sigma^8\sqrt{n})$ with probability at least $1-\exp(-\Omega(\sigma^3\sqrt{n}))$, for every prescribed finite horizon $T$. This extends a guarantee previously known only for Rademacher entries to Gaussian, bounded, and other sub-Gaussian inputs, and supplies the efficient $O(\sqrt{n})$ bound that had been conjectured for Gaussian inputs. In the Bernoulli-masked sparse model with expected support $k \gtrsim (\log n)^2$, the same algorithm achieves $O(\sigma^8\sqrt{k})$ with failure probability $\exp(-\Omega(\sigma^3\sqrt{k}))$, replacing ambient dimension by expected support. The proof works by regularizing the $\ell_\infty$-norm with a concave square-root term, restricting it to an adaptively chosen active coordinate set, and paying for set changes through a capped accounting balance, then converting a one-step negative drift into horizon-independent exponential-moment bounds.

What carries the argument

The central object is the $\ell_{1/2}$-regularization of the $\ell_\infty$-norm: $\Phi(y)=\max_{(p,q)\in S_n}\{\langle p-q,y\rangle + (2/\eta)\sum_i(p_i^{1/2}+q_i^{1/2})\}$, a twice-differentiable function that stays within $O(\sqrt{n}/\eta)$ of $\|y\|_\infty$, with its optimizer encoded by a one-dimensional Lagrange multiplier $\lambda(y)$. The algorithm restricts this potential to an adaptively chosen active set $I_t$ containing all leading coordinates, using a pre-leading zone with hysteresis so that unbounded sub-Gaussian entries never push the Taylor analysis outside a controlled neighborhood of the maximum. Active-set changes are financed by a variable-cost accounting balance with ordered levels, exchange pairs, and a cap at $4\sqrt{n}/\eta$, giving an amortized process $\Psi_t=\Phi|_{I_t}(d_t)+\beta_t$ that dominates the discrepancy. A one-step drift estimate is converted into the contraction $\mathbb{E}\exp(\lambda\Psi_{t+1})\le A+\exp(-\delta)\mathbb{E}\exp(\lambda\Psi_t)$, which iterates to horizon-independent exponential moments and Chernoff tail bounds.

What would settle it

Simulate the restriction procedure on Rademacher or Gaussian inputs at dimension $n=10^4$ and record the exchange count $r$ and active-set size $m$ at each step; if $\log \mathbb{E}\exp(\theta r/m)$ grows faster than the claimed $\theta/(C\sigma^7\sqrt{n})$ scale for admissible $\theta$, Lemma 24 is false and with it the contraction argument. Separately, a direct disproof of the main theorem would exhibit unit-variance sub-Gaussian inputs for which the algorithm's terminal discrepancy exceeds $C\sigma^8\sqrt{n}$ with probability larger than $\exp(-\Omega(\sigma^3\sqrt{n}))$.

Watch

Extended reading notes

Core claim

The central claim is that a simple potential-driven rule—choose the sign minimizing a restricted smooth $\ell_\infty$ proxy, then update the active set by hysteresis and exchange—has negative drift above a threshold of order $\sigma^7\sqrt{n}$, with increments whose tails are controlled well enough that exponential moments stay bounded uniformly in time. Theorem 1 states that for i.i.d. inputs with independent, symmetric, centered, unit-variance sub-Gaussian coordinates, the algorithm outputs signs with terminal discrepancy at most $C\sigma^8\sqrt{n}$ with probability at least $1-\exp(-c\sigma^3\sqrt{n})$. Theorem 2 states that if each coordinate is independently masked by a Bernoulli variable of mean $k/n$ and $k \gtrsim (\log n)^2$, the bound improves to $O(\sigma^8\sqrt{k})$ with failure probability $\exp(-\Omega(\sigma^3\sqrt{k}))$. The paper also argues that the $\sqrt{n}$ scale is essentially unavoidable online and, under worst-case lattice-hardness assumptions, cannot be improved offline by a fixed polynomial factor in $T/n$ when $T$ is polynomially larger than $n$.

Load-bearing premise

The load-bearing premise is that three technical estimates in the contraction step hold—the exponential bound on the number of exchange pairs, the weighted interface-count estimate for exchange displacements, and the sub-Gaussian concentration of the adjusted account increment—and each is currently justified only by a heuristic argument or an omitted technical proof; if any fails, the high-probability $O(\sigma^8\sqrt{n})$ guarantee is not established.

Editorial extensions

If this is right

  • For Gaussian inputs in the proportional regime $T=\Theta(n)$, the online algorithm achieves terminal discrepancy $O(\sigma^8\sqrt{n})$, matching the optimal offline order up to constants.
  • For the symmetric binary perceptron, the algorithm finds a signing whenever the inverse aspect ratio satisfies $\alpha \gtrsim \kappa^{-2}$, determining the online threshold up to constants together with the known online lower bound.
  • Both the discrepancy bound and the failure probability are independent of the prescribed finite horizon $T$.
  • In the Bernoulli-masked sparse model with expected support $k \gtrsim (\log n)^2$, the bound becomes $O(\sigma^8\sqrt{k})$ with failure probability $\exp(-\Omega(\sigma^3\sqrt{k}))$, and the same holds for uniform exact-support masks.
  • Under standard worst-case lattice-hardness assumptions, no polynomial-time offline algorithm can improve the $\sqrt{n}$ scale by a fixed polynomial factor in $T/n$, so the online guarantee is conditionally near-optimal in superlinear regimes.

Reading between the lines

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

  • The paper's own remark that symmetry is used only in the comparison-walk argument suggests a testable extension: the same algorithm should keep centered non-symmetric sub-Gaussian coordinates within the same discrepancy scale.
  • The gap between the $k=o(\log n)$ lower-bound example and the assumed $k \gtrsim (\log n)^2$ suggests the accounting-rescaling analysis might be refined to close the logarithmic threshold gap.
  • The same combination of a smooth restricted $\ell_\infty$ proxy, hysteresis, and capped accounting could transfer to prefix-discrepancy objectives or to oblivious online settings where coordinate independence is replaced by other assumptions.
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

4 major / 4 minor

Summary. The paper claims a polynomial-time online algorithm for terminal discrepancy minimization on i.i.d. random vectors whose coordinates are independent, symmetric, centered, unit-variance sub-Gaussian with sub-Gaussian norm at most sigma. Theorem 1 asserts terminal discrepancy O(sigma^8 sqrt(n)) with failure probability exp(-Omega(sigma^3 sqrt(n))) for every prescribed finite horizon T. Theorem 2 extends the bound to O(sigma^8 sqrt(k)) for Bernoulli-masked inputs with expected support size k >= (log n)^2. The algorithm is a potential-based method combining an ell_{1/2}-regularized ell_infty potential restricted to an adaptively chosen active coordinate set, with an amortized account that pays for switching costs. The proof proceeds through one-step drift estimates, sub-Gaussian/sub-exponential concentration of proxy increments, and an exponential-moment contraction that is uniform in t.

Significance. If the theorems are correct, this is a substantial generalization of the Bansal-Spencer Rademacher result, gives an efficient O(sqrt(n)) Gaussian guarantee as conjectured by Gamarnik et al., and determines the Gaussian online threshold for the symmetric binary perceptron up to constant factors. The regularized-and-restricted potential framework and the account-based amortization are interesting technical contributions, and many supporting lemmas are proved in detail. However, the central exponential-moment contraction is not currently complete: several key estimates are explicitly asserted with only heuristic or omitted proofs. The result is therefore conditional on the completion of those estimates.

major comments (4)
  1. [§5.2, Lemma 16(iii) and the footnote following it] The proof of Lemma 16 stops at the exact point where the sub-Gaussian concentration of the adjusted account-balance proxy is needed. After conditioning on (Psi_t, |I_t|), the ordering hat(pi)_{t+1} and the exchange pairs depend on the fresh vector v_{t+1}, so the summands of eDelta beta_t are not independent. The text states that a joint weighted-rank concentration estimate is required and then says "We omit this technical argument." This estimate is directly used in Corollary 8 and in the Holder-step of Lemma 26; without it, the negative drift in the exponential-moment recursion is not established.
  2. [§5.3, Lemma 24] The exponential bound on the number of exchange pairs r is justified only by a chip-game heuristic. The lemma itself says that a complete proof requires a technical coupling argument and that these details are omitted. Lemma 24 is used in the proof of Lemma 25, and Lemma 25 controls the residual moving-level error R_t that appears in the main contraction Lemma 26. Thus this is a load-bearing gap in the central proof chain.
  3. [§5.3, Lemma 25] The weighted interface-count estimate used to bound E_t^ex is stated without proof: the text says it "does not follow immediately from Lemma 24" because the layer counts are dependent and then says "we omit the resulting technical details." This estimate is not a formal consequence of the preceding lemmas, and it is necessary for the exponential moment bound on R_t. Since Lemma 26 relies on this bound, the high-probability statement in Theorem 1 is currently unsupported at this step.
  4. [§5.2, comparison-walk argument before Lemma 23] The proof of Lemma 23 uses the assertion that the auxiliary random walk (X_t) has stronger concentration around R/4 than the actual relative-position process (Y_t). This stochastic domination is asserted rather than proved; Appendix B analyzes the stationary measure of (X_t) but does not establish the needed comparison with (Y_t). Lemma 23 supplies the expectation bound on eDelta rho_t(j) that feeds into Lemma 16(ii), so this is another load-bearing point in the dense-regime proof.
minor comments (4)
  1. [Theorem 1 and §5, proof of Lemma 17] The theorem states n ≳ sigma^24, but the proof repeatedly uses n ≫ sigma^24 to absorb prefactors such as log(sigma^8 sqrt(n)) into the exponential tail. The intended asymptotic regime (n -> infinity with sigma fixed or growing slowly) should be stated explicitly.
  2. [§5.3, Lemma 26 and proof of Lemma 17] The constants c and C are used both as absolute constants and as the large constant appearing in the definition of R and eta. The presentation would be clearer if all dependencies on the large absolute constant C were tracked explicitly, or if the proof stated that C is chosen sufficiently large after all other absolute constants.
  3. [§5.2, proof of Lemma 16] The footnote containing the omitted weighted-rank estimate is a central technical step, not a side remark. It would be better placed as a separate lemma with a full proof in an appendix.
  4. [Appendix B, Lemma 37] The proof of Lemma 37 uses the condition R ≳ sigma^2 in the displayed inequality after (47). This condition follows from the standing assumption n ≳ sigma^24 and R = C sigma^7 sqrt(n), but the implication is not stated; adding one sentence would avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the discrepancy bound is derived from a self-contained potential/amortization analysis whose target scale is not assumed.

full rationale

The paper's central claim is proved from a potential-function construction: it introduces a restricted regularized l_infinity potential, an accounting mechanism for active-set changes, and an exponential-moment contraction argument (Lemmas 14-17). The target bound O(sigma^8 sqrt n) is never used as an input: the parameters eta, R, and lambda are chosen to make the drift and concentration estimates go through, not fitted to the desired bound. The failure probability exp(-Omega(sigma^3 sqrt n)) is obtained by Chernoff from the exponential-moment bound, and the final rescaling by sigma is a fixed normalization, not an assumption of the conclusion. There is no fitted-input-called-prediction step, no self-citation that carries a load-bearing premise, and no renamed known result. The proof does contain acknowledged gaps: Lemma 16(iii) requires a 'joint weighted-rank concentration estimate' whose proof is omitted, and Lemmas 24/25 rely on a chip-game heuristic and an omitted weighted interface-count estimate. These are missing proofs within the derivation chain and create correctness risk, but they are not circular: the missing estimates are independent probabilistic facts, not restatements of the theorem being proven. Consequently, the derivation chain is self-contained in structure, and the score is 0.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

The central claim rests on the stated random-input model and on several analytical estimates that are asserted rather than fully proved. The algorithm's design parameters eta, R, and lambda are chosen for the proof; they are not fitted to data and do not by themselves bias the result.

free parameters (3)
  • eta (regularizer strength) = 1/(C sigma^7)
    Introduced in Section 3; controls the tradeoff between l_infinity approximation and smoothness. Chosen to make Lemmas 4, 5, and the drift estimates work.
  • R (leading zone radius) = C sigma^7 sqrt(n)
    Definition 5; sets the width of the leading and pre-leading zones used by the restriction procedure. Chosen sufficiently large for the analysis.
  • lambda (exponential moment parameter) = 1/(C sigma^4)
    Section 5.3; scaling for the exponential-moment recursion. Chosen to satisfy the smallness condition in Lemma 32(iii).
assumptions (5)
  • domain assumption Input coordinates are independent, symmetric, centered, unit-variance sub-Gaussian with sub-Gaussian norm at most sigma
    This is the hypothesis of Theorems 1 and 2; the entire probabilistic analysis depends on it.
  • standard math Standard properties of sub-Gaussian and sub-exponential random variables, Khintchine inequality, Berry-Esseen, Paley-Zygmund, and Markov chain regeneration
    Used throughout Appendices A and B and in Lemmas 18-21 and 26; assumed without proof.
  • ad hoc to paper The comparison walk (X_t) has stronger concentration around R/4 than the actual relative-position process (Y_t)
    Asserted in Section 5.2, paragraph 'We can therefore interpret (Y_t)...'; no proof is given, and this comparison is essential for Lemmas 21-23.
  • ad hoc to paper The exchange-pair exponential bound (Lemma 24) and weighted interface-count estimate (Lemma 25) hold as stated
    Both lemmas are stated in Section 5.3 but their proofs are omitted or replaced by chat-based reasoning; they are load-bearing for the contraction in Lemma 26.
  • ad hoc to paper The psi_2 concentration estimate for the adjusted account-balance increment in Lemma 16 holds
    The proof notes that 'a joint weighted-rank concentration estimate ... is required' (footnote 12) but the argument is not supplied.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Online Discrepancy Minimization for Sub-Gaussian Inputs via Regularization and Restriction." pith.science (2026). https://pith.science/paper/5ABKVID7

@misc{pith2026260810040,
  author       = {Pith},
  title        = {Pith review of: Online Discrepancy Minimization for Sub-Gaussian Inputs via Regularization and Restriction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5ABKVID7}},
  note         = {Machine review of arXiv:2608.10040}
}
abstract

We study online discrepancy minimization: vectors $v_1,\ldots,v_T\in\mathbb{R}^n$ arrive sequentially, and each must immediately be assigned a sign $x_t\in\{\pm1\}$, with the aim of minimizing $\|\sum_{t=1}^T x_t v_t\|_\infty$. We give a polynomial-time potential-based algorithm combining a regularization of the $\ell_\infty$-norm with restriction to an adaptively chosen coordinate set. For i.i.d. inputs with independent, symmetric, centered, unit-variance sub-Gaussian coordinates of sub-Gaussian norm at most $\sigma$, the algorithm achieves terminal discrepancy $O(\sigma^8\sqrt{n})$ with probability at least $1-\exp(-\Omega(\sigma^3\sqrt{n}))$. If the coordinates are independently masked by Bernoulli variables with mean $k/n$, where $k\gtrsim(\log n)^2$, the bound improves to $O(\sigma^8\sqrt{k})$, with failure probability $\exp(-\Omega(\sigma^3\sqrt{k}))$. Both guarantees hold for every prescribed finite horizon $T$, with no dependence on $T$. The dense result substantially generalizes a theorem of Bansal and Spencer (2020) for Rademacher inputs and gives an efficient $O(\sqrt{n})$ bound for Gaussian inputs, as conjectured by Gamarnik et al. (2022). When $T$ is polynomially larger than $n$, this is conditionally close to optimal: under worst-case hardness assumptions for standard approximate lattice problems, Vafa and Vaikuntanathan (2025) showed that no polynomial-time algorithm, even offline, can improve the $\sqrt{n}$ scale by a fixed polynomial factor in $T/n$.

Figures

Figures reproduced from arXiv: 2608.10040 by the authors.

Figure 1
Figure 1. Schematic small-margin phase diagram for the Gaussian symmetric binary perceptron [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Basic restriction rule at a fixed level Mt . Green and red denote inactive and active states, respectively. A coordinate moving toward the leading zone is activated at Mt − R/4, whereas a coordinate moving away remains active until it crosses Mt−R/2. Exchanges within the pre-leading zone are omitted. We apply the regularized potential only to the resulting set of active coordinates. For a non-empty set I ⊆ [n], defi… view at source ↗
Figure 3
Figure 3. Fixed-cost accounting at a fixed level Mt . The local credit of an inactive coordinate varies linearly across the pre-leading zone. Upon activation, the entry-cost portion is spent and the exit reserve remains. Variable costs and exchanges are omitted. Let βt denote the resulting account balance and define the amortized process by Ψt := Φ|It (dt)+βt . We initialize the account with β0 = 0 and maintain βt ≥ 0. Since … view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

52 extracted references · 37 canonical work pages

  1. [1]

    Abbe, Emmanuel and Li, Shuangping and Sly, Allan , TITLE =. 2021. 2022 , ISBN =

    work page 2021

  2. [2]

    Abbe, Emmanuel and Li, Shuangping and Sly, Allan , TITLE =. S. 2022 , ISBN =

    work page 2022

  3. [3]

    , TITLE =

    Abramowitz, Milton and Stegun, Irene A. , TITLE =. 1964 , PAGES =

    1964

  4. [4]

    2026 , eprint=

    Optimal Online Discrepancy Minimization in Linear Time , author=. 2026 , eprint=

    work page 2026

  5. [5]

    Allen-Zhu, Zeyuan and Liao, Zhenyu and Orecchia, Lorenzo , TITLE =. S. 2015 , ISBN =

    work page 2015

  6. [6]

    and Niles-Weed, Jonathan , TITLE =

    Altschuler, Dylan J. and Niles-Weed, Jonathan , TITLE =. Random Structures Algorithms , FJOURNAL =. 2022 , NUMBER =. doi:10.1002/rsa.21054 , URL =

    work page doi:10.1002/rsa.21054 2022

  7. [7]

    vectors , author=

    A threshold for online balancing of sparse i.i.d. vectors , author=. 2025 , eprint=

    work page 2025

  8. [8]

    Online Beck--Fiala Down to Logarithmic Sparsity

    Dylan J. Altschuler and Konstantin Tikhomirov , year=. Online. 2607.14238 , archivePrefix=

    work page Pith review arXiv

Show all 52 references
  1. [9]

    and Sawhney, Mehtaab , TITLE =

    Alweiss, Ryan and Liu, Yang P. and Sawhney, Mehtaab , TITLE =. S. 2021 , ISBN =. doi:10.1145/3406325.3450994 , URL =

    2021

  2. [10]

    Aubin, Benjamin and Perkins, Will and Zdeborov\'a, Lenka , TITLE =. J. Phys. A , FJOURNAL =. 2019 , NUMBER =. doi:10.1088/1751-8121/ab227a , URL =

    2019 doi

  3. [11]

    Bansal, Nikhil , TITLE =. 2010. 2010 , ISBN =

    2010

  4. [12]

    , TITLE =

    Bansal, Nikhil and Spencer, Joel H. , TITLE =. Random Structures Algorithms , FJOURNAL =. 2020 , NUMBER =. doi:10.1002/rsa.20955 , URL =

    2020 doi

  5. [13]

    Bansal, Nikhil and Jiang, Haotian and Singla, Sahil and Sinha, Makrand , TITLE =. S. 2020 , ISBN =

    2020

  6. [14]

    Proceedings of the 2021

    Bansal, Nikhil and Jiang, Haotian and Meka, Raghu and Singla, Sahil and Sinha, Makrand , TITLE =. Proceedings of the 2021. 2021 , ISBN =. doi:10.1137/1.9781611976465.169 , URL =

    2021 doi

  7. [15]

    Bansal, Nikhil , TITLE =. I. 2023 , ISBN =

    2023

  8. [16]

    Beck--Fiala conjecture , volume =

    Bansal and Jiang , journal =. Beck--Fiala conjecture , volume =

  9. [17]

    Bansal, Nikhil and Jiang, Haotian , TITLE =. S. 2026 , ISBN =. doi:10.1145/3798129.3800762 , URL =

    2026

  10. [18]

    On a Class of Balancing Games , journal =

    Imre B. On a Class of Balancing Games , journal =. 1979 , doi =

    1979

  11. [19]

    and Spielman, Daniel A

    Batson, Joshua D. and Spielman, Daniel A. and Srivastava, Nikhil , TITLE =. S. 2009 , ISBN =

    2009

  12. [20]

    , TITLE =

    Bertsekas, Dimitri P. , TITLE =. 1999 , PAGES =

    1999

  13. [21]

    2004 , PAGES =

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

    2004 doi

  14. [22]

    2000 , PAGES =

    Chazelle, Bernard , TITLE =. 2000 , PAGES =. doi:10.1017/CBO9780511626371 , URL =

    2000 doi

  15. [23]

    , TITLE =

    Costello, Kevin P. , TITLE =. Israel J. Math. , FJOURNAL =. 2009 , PAGES =. doi:10.1007/s11856-009-0068-z , URL =

    2009 doi

  16. [24]

    Random Structures Algorithms , FJOURNAL =

    Eldan, Ronen and Singh, Mohit , TITLE =. Random Structures Algorithms , FJOURNAL =. 2018 , NUMBER =. doi:10.1002/rsa.20763 , URL =

    2018 doi

  17. [25]

    2026 , eprint=

    The Mean-Field Limit of Online Stochastic Vector Balancing , author=. 2026 , eprint=

    2026

  18. [26]

    Random Structures Algorithms , FJOURNAL =

    Franks, Cole and Saks, Michael , TITLE =. Random Structures Algorithms , FJOURNAL =. 2020 , NUMBER =. doi:10.1002/rsa.20909 , URL =

    2020 doi

  19. [27]

    Algorithms and barriers in the symmetric binary perceptron model , BOOKTITLE =

    Gamarnik, David and K. Algorithms and barriers in the symmetric binary perceptron model , BOOKTITLE =. 2022 , ISBN =

    2022

  20. [28]

    The Thirty Sixth Annual Conference on Learning Theory , pages=

    Geometric barriers for stable and online algorithms for discrepancy minimization , author=. The Thirty Sixth Annual Conference on Learning Theory , pages=. 2023 , organization=

    2023

  21. [29]

    Hajek, Bruce , TITLE =. Adv. in Appl. Probab. , FJOURNAL =. 1982 , NUMBER =. doi:10.2307/1426671 , URL =

    1982 doi

  22. [30]

    Proceedings of the

    Hoberg, Rebecca and Rothvoss, Thomas , TITLE =. Proceedings of the. 2019 , ISBN =. doi:10.1137/1.9781611975482.156 , URL =

    2019 doi

  23. [31]

    , institution =

    Karmarkar, Narendra and Karp, Richard M. , institution =. The differencing method of set partitioning , year =

  24. [32]

    , TITLE =

    Kim, Jeong Han and Roche, James R. , TITLE =. J. Comput. System Sci. , FJOURNAL =. 1998 , NUMBER =. doi:10.1006/jcss.1997.1560 , URL =

    1998

  25. [33]

    Kulkarni, Janardhan and Reis, Victor and Rothvoss, Thomas , TITLE =. S. 2024 , ISBN =. doi:10.1145/3618260.3649720 , URL =

    2024

  26. [34]

    Lau, Lap Chi and Wang, Robert and Zhou, Hong , TITLE =. 2025. 2025 , ISBN =. doi:10.1137/1.9781611978315.24 , URL =

    2025 doi

  27. [35]

    Theory of evolutionary computation---recent developments in discrete optimization , SERIES =

    Lengler, Johannes , TITLE =. Theory of evolutionary computation---recent developments in discrete optimization , SERIES =. 2020 , ISBN =. doi:10.1007/978-3-030-29414-4\_2 , URL =

    2020 doi

  28. [36]

    Integer programming and combinatorial optimization , SERIES =

    Levy, Avi and Ramadas, Harishchandra and Rothvoss, Thomas , TITLE =. Integer programming and combinatorial optimization , SERIES =. 2017 , ISBN =. doi:10.1007/978-3-319-59250-3\_31 , URL =

    2017 doi

  29. [37]

    Liu and Ashwin Sah and Mehtaab Sawhney , title =

    Yang P. Liu and Ashwin Sah and Mehtaab Sawhney , title =. 13th Innovations in Theoretical Computer Science Conference (. 2022 , doi =

    2022

  30. [38]

    Lovett, Shachar and Meka, Raghu , TITLE =. SIAM J. Comput. , FJOURNAL =. 2015 , NUMBER =. doi:10.1137/130929400 , URL =

    2015 doi

  31. [39]

    Exact value of sub-gaussian norm , volume =

    Ostrovsky and Sirota , journal =. Exact value of sub-gaussian norm , volume =

  32. [40]

    , TITLE =

    Pemantle, Robin and Rosenthal, Jeffrey S. , TITLE =. Stochastic Process. Appl. , FJOURNAL =. 1999 , NUMBER =. doi:10.1016/S0304-4149(99)00012-5 , URL =

    1999 doi

  33. [41]

    Perkins, Will and Xu, Changji , TITLE =. S. 2021 , ISBN =. doi:10.1145/3406325.3451119 , URL =

    2021

  34. [42]

    Proceedings of the 2023

    Pesenti, Lucas and Vladu, Adrian , TITLE =. Proceedings of the 2023. 2023 , ISBN =. doi:10.1137/1.9781611977554.ch66 , URL =

    2023 doi

  35. [43]

    2018 , eprint=

    Discrepancy in random hypergraph models , author=. 2018 , eprint=

    2018

  36. [44]

    Rothvoss, Thomas , TITLE =. SIAM J. Comput. , FJOURNAL =. 2017 , NUMBER =. doi:10.1137/141000282 , URL =

    2017 doi

  37. [45]

    Spencer, Joel , TITLE =. J. Combinatorial Theory Ser. B , FJOURNAL =. 1977 , NUMBER =. doi:10.1016/0095-8956(77)90057-0 , URL =

    1977 doi

  38. [46]

    Spencer, Joel , TITLE =. Trans. Amer. Math. Soc. , FJOURNAL =. 1985 , NUMBER =. doi:10.2307/2000258 , URL =

    1985 doi

  39. [47]

    , TITLE =

    Spencer, J. , TITLE =. Combinatorica , FJOURNAL =. 1986 , NUMBER =. doi:10.1007/BF02579409 , URL =

    1986 doi

  40. [48]

    1994 , PAGES =

    Spencer, Joel , TITLE =. 1994 , PAGES =. doi:10.1137/1.9781611970074 , URL =

    1994 doi

  41. [49]

    Balancing

    Turner, Paxton and Meka, Raghu and Rigollet, Philippe , booktitle =. Balancing. 2020 , editor =

    2020

  42. [50]

    and Casella, George , TITLE =

    Robert, Christian P. and Casella, George , TITLE =. 2004 , PAGES =. doi:10.1007/978-1-4757-4145-2 , URL =

    2004 doi

  43. [51]

    Vafa, Neekon and Vaikuntanathan, Vinod , TITLE =. S. 2025 , ISBN =. doi:10.1145/3717823.3718263 , URL =

    2025

  44. [52]

    2018 , PAGES =

    Vershynin, Roman , TITLE =. 2018 , PAGES =. doi:10.1017/9781108231596 , URL =

    2018 doi

Pith tools

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