Pith. sign in

REVIEW 6 minor 35 references

The paper proves that the original online leverage-score sampling algorithm survives adaptive adversaries: every prefix stays a (1±ε) spectral approximation with high probability, using O(d ε^{-2} log n log κ_OL) rows.

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-01 03:40 UTC pith:ROXBODP2

load-bearing objection The core adaptive robustness proof for online leverage-score sampling is solid and genuinely new; the near-linear graph implementation rests on an external APSP data structure, but that dependency is reasonable.

arxiv 2607.23098 v1 pith:ROXBODP2 submitted 2026-07-25 cs.DS

An Online Sparsification Algorithm from the Book

Gramoz Goranci , Rasmus Kyng , Maximilian Probst Gutenberg , Yibin Zhao , Gernot Z\"ocklein This is my paper
classification cs.DS MSC 68W2768W2060B2005C85
keywords online spectral sparsificationadaptive adversaryleverage score samplingmatrix martingale concentrationFreedman inequalityevolving isotropic mapgraph sparsificationnear-linear time
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.

This paper asks whether the simplest online spectral sparsification heuristic—when a row arrives, compute its current leverage score and keep it with probability proportional to that score—still works when an adaptive adversary chooses each row after seeing the algorithm's previous random decisions. The answer is yes. The paper proves that the unmodified algorithm maintains a (1±ε)-spectral approximation of every prefix of the stream with high probability, at the price of O(d ε^{-2} log n log κ_OL) rows (O(d ε^{-2} log^2 d) for polynomially bounded integer data). The proof rests on a new matrix martingale inequality that allows the isotropic normalization to evolve with the stream. If true, this gives the first adaptive-stream online sparsifier whose working memory is proportional to the sparsifier itself, and, for graph Laplacians, an implementation running in near-linear time.

Core claim

On the paper's own terms, the central discovery is that the natural online row-sampling rule needs no modification to defeat adaptivity. The error process E_i = K_i^{†/2}(K̃_i - K_i)K_i^{†/2} is a martingale with increments whose variance is bounded by (1/ρ)v_i v_i^T, even though the normalization K_i^{†/2} changes at every step. The paper proves a contractive Freedman inequality: with C_i = K_i^{†/2} K_{i-1}^{1/2}, the trace-exponential potential obeys E[Ψ_i | F_{i-1}] ≤ Ψ_{i-1} + d, so the drift is only the dimension d, and optional stopping yields the desired high-probability bound. This establishes that the matrices produced by online leverage-score sampling are (1±ε)-spectral approximat

What carries the argument

The evolving isotropic map C_i = K_i^{†/2} K_{i-1}^{1/2}, together with the contractive Freedman inequality that accompanies it. The map re-normalizes the error martingale from the previous prefix into the current one while satisfying C_i C_i^T ⪯ I; the inequality shows that the trace-exponential potential Ψ_i = Tr exp(θY_i - g_R(θ)V_i) is almost a supermartingale, with only an additive d of drift per step, via the trace lemma Tr exp(CHC^T) ≤ d + Tr exp(H). This mechanism is what lets the concentration argument follow a randomly changing normalization instead of requiring the final matrix to be fixed in advance.

Load-bearing premise

The main theorem hangs on the stopping-time assumption that the current sparsifier remains a (1−ε)-approximation until the first moment it fails, so the estimated sampling probabilities over-sample the true online leverage scores; the graph near-linear-time claim additionally rests on the assumed deterministic online spanner with stretch Õ(1), size O(n log W), and near-linear total update time.

What would settle it

Simulate the algorithm on an adversarial stream that at each step feeds the unit vector maximizing the current estimated leverage score a_i^T (K̃_{i-1} + a_i a_i^T)^† a_i; the theorem predicts the normalized error ‖K_i^{†/2}(K̃_i - K_i)K_i^{†/2}‖_op stays below ε for every prefix with high probability. If, for n = 1000, d = 5, ε = 0.1, the maximum error exceeds ε in even a few percent of trials, the central claim is false.

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

If this is right

  • The original online leverage-score sampling algorithm is valid against adaptive adversaries with no change to its sampling rule.
  • The sparsifier size is near-optimal: O(d ε^{-2} log n log κ_OL) rows, improving to O(d ε^{-2} log^2 d) for polynomially bounded integer entries.
  • Working memory is proportional to the sparsifier, not to the input size or d², so sparse rows such as graph edges can be processed with O(k d ε^{-2} log^2 d) memory.
  • For graph Laplacians, the same algorithm can be implemented in near-linear total time and near-linear memory while maintaining the spectral guarantee for every prefix.
  • The contractive Freedman inequality is a reusable concentration tool for martingales whose normalization changes over time.

Where Pith is reading between the lines

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

  • The technique likely transfers to other adaptive streaming problems where the natural concentration argument normalizes by a random final matrix, such as online covariance estimation, ridge regression, or kernel sketch maintenance, though the paper does not state this.
  • The graph implementation's efficiency is bottlenecked by the assumed deterministic online spanner; any faster or smaller online spanner would immediately improve the near-linear time and memory bounds.
  • An empirical test could check whether the algorithm's sparsifier size tracks the predicted O(d ε^{-2} log n log κ_OL) bound on deliberately adversarial streams; the theory predicts it does, and any systematic violation would pinpoint a gap in the stopping-time argument.

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

0 major / 6 minor

Summary. This paper studies online spectral sparsification of a matrix whose rows arrive one by one, possibly chosen adaptively based on the algorithm's previous random choices. The algorithm considered is the natural online leverage-score sampling rule of Cohen, Musco, and Pachocki (CMP16): upon receiving row a_i, it computes an estimate of the current leverage score τ^{OL}(a_i) = a_i^T(A_i^T A_i)^+ a_i using the sparsifier maintained so far, and keeps the row (reweighted) with proportional probability. The main theorem (Theorem 3.2) states that, with high probability, the resulting sparsifier is a (1±ε)-spectral approximation of every prefix A_i, even under an adaptive adversary. The proof centers on a new matrix concentration inequality (Theorem 3.5), a Freedman-type bound for processes with an evolving contraction C_i, together with a trace lemma (Lemma 4.3) controlling the contraction step and a stopping-time argument for the estimated leverage scores. The sample-size bound is O(d ε^{-2} log n log κ_OL), improving to O(d ε^{-2} log^2 n) for polynomially bounded integer entries (Theorem 3.4). For graph Laplacians, the paper gives a near-linear-time implementation using online spanners and an incremental APSP data structure, yielding a sparsifier with \tilde O(n ε^{-2} log W) edges in \tilde O(m ε^{-2} log W) total time and memory (Theorem 5.1).

Significance. The result resolves a natural open question left by CMP16: whether the same online sampling algorithm that works for oblivious streams also works for adaptive streams. The technical contribution — a Freedman-type inequality with an evolving isotropic map — is elegant and appears correct; it is likely to be useful beyond this specific application. The paper also gives the first implementation that is simultaneously adaptive-robust, near-linear in time, and near-linear in memory for spectral graph sparsification. The proof is largely self-contained, with the main external dependency being the published incremental APSP data structure of FNP23 used in the graph spanner construction. I found no circularity or fitted parameters; the constants are explicit and the bounds are parameter-free. The acknowledgment that an initial version of the concentration proof was generated with ChatGPT is unusual but does not affect the mathematics, as the authors state they verified and rewrote the proof. Overall, if the minor issues below are fixed, the paper is a strong contribution to the algorithmic spectral sparsification literature.

minor comments (6)
  1. [Section 4.2, Lemma 4.3] In the proof of Lemma 4.3, the displayed chain "x^T C H C^T x > a||x||^2 ≥ ||C^T x||^2" is missing a factor a; it should read "a||x||^2 ≥ a||C^T x||^2". The intended argument is otherwise clear and the lemma is correct.
  2. [Section 3.2, proof of Theorem 3.2] After Eq. (13), plugging ρ=8ε^{-2}log n into 2d(n+1)exp(-3/8 ε^2 ρ) gives at most 4n^{-1} (using d≤n and n+1≤2n), not 2n^{-1} as claimed. Please adjust ρ to, say, 16ε^{-2}log n, or restate the failure probability as O(n^{-1}) with the explicit constant.
  3. [Section 3.2, proof of Theorem 3.4] The expression for p_i in the proof is written as min{1, ρ(1+ε) a_i^T(\tilde A_{i-1}^T \tilde A_{i-1})^† a_i}, omitting the "+ a_i a_i^T" term in the middle of the pseudo-inverse. This should match Algorithm 1 line 6; otherwise the subsequent bound \tilde τ_i ≤ (1/(1-ε))τ^{OL}(a_i) does not follow from the given definitions.
  4. [Section 4.3, proof of Theorem 3.5] The process Q_i = Ψ_i + d(T-i) is introduced before the stopping time T is defined, and for a random stopping time T the variable Q_i is not F_i-measurable in general. The standard repair is to note that M_i = Ψ_i - d i is a nonnegative supermartingale and apply optional stopping to M_T; this yields the same bound E[Ψ_T] ≤ d(n+1). Please clarify this step.
  5. [Appendix A, proof of Theorem 5.5] The proof of Theorem 5.5 is a sketch. In particular, the girth argument ("it must be that H has girth at least 2 log n + 1") is not fully spelled out. Since the time/memory guarantees of Theorem 5.1 depend on this spanner, please expand the argument and explicitly state that the result relies on the incremental APSP data structure of FNP23 (Theorem A.2). The dependency is acceptable because FNP23 is a published result, but the exposition should be precise.
  6. [Various] Minor typos and presentation issues: "runing" in the proof of Theorem 3.4; "and and" in Theorem 5.5; "at most at most" in Theorem 1.2; inconsistent use of \tilde A vs eA in the abstract and introduction. These do not affect the mathematical content.

Circularity Check

0 steps flagged

No material circularity; core adaptive row-sampling proof is self-contained, and the graph-specific dependencies are external prior results.

full rationale

The central claim (Theorem 3.2) is derived rather than assumed: Algorithm 1's sampling probabilities use the current sparsifier, and the proof employs a stopping-time argument together with the custom contractive Freedman inequality (Theorem 3.5), which is proved in Section 4 from standard matrix concentration tools (matrix MGF bound, Lieb's inequality, and a trace lemma). The only external result entering the row-sampling analysis is Theorem 3.1, the online-leverage-score sum bound cited from CMP16 and WY22; these are independent prior works and do not assume the target spectral approximation. No parameter is fitted to data and then renamed as a prediction. The graph implementation (Theorem 5.1) does rest on the deterministic online spanner of Theorem 5.5, whose Appendix A proof invokes the incremental APSP data structure of FNP23, a published STOC paper co-authored by one of the current authors. That is an external, independently stated theorem and is not used to assume the paper's spectral-sparsification result, so it is not circular; it is however the least secure external dependency, since if the APSP guarantees were incorrect the near-linear graph time/memory claims would not follow. Minor technical issues (e.g., a typo in the proof of Lemma 4.3 and a slightly compressed probability estimate) are repairable and do not constitute input-output equivalence or otherwise force the conclusions by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 0 invented entities

No numbers are fitted to data and no new entities are postulated. The paper's contribution is a proof, and its load-bearing inputs are standard concentration inequalities, two cited leverage-score bounds, and a cited dynamic-algorithms data structure.

axioms (6)
  • standard math Matrix MGF bound and Lieb's theorem (Lemma 4.1, Theorem 4.2 from [Tro15])
    Used in the proof of the contractive Freedman inequality (Theorem 3.5), the paper's main technical tool.
  • standard math Scalar Freedman inequality (Lemma 2.1)
    Used in Theorem 3.4 and Lemma 5.9 to bound the number of sampled rows; the proof is only sketched.
  • domain assumption Online leverage score sum bound (Theorem 3.1 from [CMP16,WY22])
    Gives \sum τ^OL(a_i)=O(d log κ_OL); controls the final sparsifier size and is not proved in this paper.
  • domain assumption t-bundle spanner leverage bound (Lemma 5.3 from [KX16])
    Certifies that edges outside the spanner bundle have small leverage scores; essential for the graph algorithm.
  • domain assumption Incremental APSP data structure of [FNP23] (Theorem A.2)
    The deterministic online spanner uses this external data structure for near-linear update time and bounded memory.
  • standard math Girth-size bound for sparse graphs (Observation A.3)
    Folklore bound used to show the online spanner has O(n) edges.

pith-pipeline@v1.3.0-alltime-deepseek · 2986 in / 3102 out tokens · 421948 ms · 2026-08-01T03:40:09.134459+00:00 · methodology

0 comments
read the original abstract

In their seminal paper [Cohen et al., 2016], Cohen, Musco, and Pachocki proposed a natural and simple online spectral sparsification algorithm: rows $a_1, a_2, \ldots \in \mathbb{R}^d$ of a matrix $A$ arrive one-by-one, and when row $a_i$ arrives, it is appended to sparsifier $\tilde{A}$ (after appropriately reweighting it) with probability proportional to its current leverage score $$ \tau^{\mathrm{OL}}(a_i)=a_i^\top(A_i^\top A_i)^\dagger a_i, \text{ where }A_i = [a_1, a_2, \ldots, a_i]^\top $$ or otherwise discarded forever. For oblivious streams, they showed that this maintains a $(1\pm\epsilon)$-spectral approximation $\tilde{A}$ of every $A$ with $O(d\epsilon^{-2}\log^2 d)$ many rows. A natural question is whether the same algorithm works for adaptive streams, where each row may depend on the algorithm's previous random choices. The original proof does not extend directly: it analyzes the process in isotropic position with respect to the final matrix $A$, which is not fixed in advance under adaptivity. As an extension of this proof framework remained elusive, various algorithmic variants have since been suggested. In this paper, we show that the original online leverage-score sampling algorithm is indeed robust to adaptive adversaries. Our main technical contribution is a Freedman-type matrix martingale inequality with an evolving isotropic map, allowing the isotropic map used in the concentration argument to change with the stream. As a consequence, this gives the first online sparsification algorithm for adaptive streams that yields a sparsifier of near-optimal size $O(d \varepsilon^{-2}\log^2 d)$ whose working memory is proportional to the size of the sparsifier. For the special case of spectral graph sparsification, we provide an implementation that additionally runs in time near-linear in the stream size.

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

35 extracted references · 4 canonical work pages

  1. [1]

    and Musco, Cameron and Pachocki, Jakub , title =

    Cohen, Michael B. and Musco, Cameron and Pachocki, Jakub , title =. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016) , pages =. 2016 , volume =. doi:10.4230/LIPIcs.APPROX-RANDOM.2016.7 , annote =

    doi:10.4230/lipics.approx-random.2016.7 2016

  2. [2]

    and Yasuda, Taisuke , booktitle=

    Woodruff, David P. and Yasuda, Taisuke , booktitle=. High-Dimensional Geometric Streaming in Polynomial Space , year=

  3. [3]

    All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time , year=

    Abboud, Amir and Li, Jason and Panigrahi, Debmalya and Saranurak, Thatchaphol , booktitle=. All-Pairs Max-Flow is no Harder than Single-Pair Max-Flow: Gomory-Hu Trees in Almost-Linear Time , year=

  4. [4]

    arXiv preprint arXiv:2507.20354 , year=

    Deterministic Almost-Linear-Time Gomory-Hu Trees , author=. arXiv preprint arXiv:2507.20354 , year=

    Pith/arXiv arXiv

  5. [5]

    Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =

    Amir Abboud and Robert Krauthgamer and Ohad Trabelsi , title =. Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =. 2021 , publisher =. doi:10.1137/1.9781611975994.4 , URL =

    work page doi:10.1137/1.9781611975994.4 2020

  6. [6]

    Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time , year=

    Abboud, Amir and Krauthgamer, Robert and Li, Jason and Panigrahi, Debmalya and Saranurak, Thatchaphol and Trabelsi, Ohad , booktitle=. Breaking the Cubic Barrier for All-Pairs Max-Flow: Gomory-Hu Tree in Nearly Quadratic Time , year=

  7. [7]

    Journal of the Society for Industrial and Applied Mathematics , volume=

    Multi-terminal network flows , author=. Journal of the Society for Industrial and Applied Mathematics , volume=. 1961 , publisher=

    1961

  8. [8]

    On Fully Dynamic Graph Sparsifiers , year=

    Abraham, Ittai and Durfee, David and Koutis, Ioannis and Krinninger, Sebastian and Peng, Richard , booktitle=. On Fully Dynamic Graph Sparsifiers , year=

  9. [9]

    49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) , pages =

    Bernstein, Aaron and van den Brand, Jan and Probst Gutenberg, Maximilian and Nanongkai, Danupon and Saranurak, Thatchaphol and Sidford, Aaron and Sun, He , title =. 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) , pages =. 2022 , volume =. doi:10.4230/LIPIcs.ICALP.2022.20 , annote =

    doi:10.4230/lipics.icalp.2022.20 2022

  10. [10]

    2019 , isbn =

    Durfee, David and Gao, Yu and Goranci, Gramoz and Peng, Richard , title =. 2019 , isbn =. doi:10.1145/3313276.3316379 , booktitle =

    arXiv 2019

  11. [11]

    Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers , year=

    Chen, Li and Goranci, Gramoz and Henzinger, Monika and Peng, Richard and Saranurak, Thatchaphol , booktitle=. Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers , year=

  12. [12]

    and Peng, Richard and Sidford, Aaron , title =

    van den Brand, Jan and Gao, Yu and Jambulapati, Arun and Lee, Yin Tat and Liu, Yang P. and Peng, Richard and Sidford, Aaron , title =. 2022 , isbn =. doi:10.1145/3519935.3520068 , booktitle =

    arXiv 2022

  13. [13]

    SIAM Journal on Computing , pages =

    Gao, Yu and Liu, Yang and Peng, Richard , title =. SIAM Journal on Computing , pages =. 2023 , doi =

    2023

  14. [14]

    arXiv preprint arXiv:2507.19632 , year=

    Fully Dynamic Spectral and Cut Sparsifiers for Directed Graphs , author=. arXiv preprint arXiv:2507.19632 , year=

    Pith/arXiv arXiv

  15. [15]

    SIAM Journal on Computing , volume =

    Spielman, Daniel and Srivastava, Nikhil , title =. SIAM Journal on Computing , volume =. 2011 , doi =

    2011

  16. [16]

    2015 , issue_date =

    Koutis, Ioannis and Levin, Alex and Peng, Richard , title =. 2015 , issue_date =. doi:10.1145/2743021 , journal =

    work page doi:10.1145/2743021 2015

  17. [17]

    Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions , year=

    Chu, Timothy and Gao, Yu and Peng, Richard and Sachdeva, Sushant and Sawlani, Saurabh and Wang, Junxing , booktitle=. Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions , year=

  18. [18]

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

    Lawrence Li and Sushant Sachdeva , title =. Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , chapter =. 2023 , pages =. doi:10.1137/1.9781611977554.ch102 , URL =

    work page doi:10.1137/1.9781611977554.ch102 2023

  19. [19]

    Towards Optimal Effective Resistance Estimation , url =

    Dwaraknath, Rajat Vadiraj and Karmarkar, Ishani and Sidford, Aaron , booktitle =. Towards Optimal Effective Resistance Estimation , url =

  20. [20]

    Proceedings of the 35th International Conference on Neural Information Processing Systems , articleno =

    Braverman, Vladimir and Hassidim, Avinatan and Matias, Yossi and Schain, Mariano and Silwal, Sandeep and Zhou, Samson , title =. Proceedings of the 35th International Conference on Neural Information Processing Systems , articleno =. 2021 , isbn =

    2021

  21. [21]

    The Complexity of Dynamic Least-Squares Regression , year=

    Jiang, Shunhua and Peng, Binghui and Weinstein, Omri , booktitle=. The Complexity of Dynamic Least-Squares Regression , year=

  22. [22]

    2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=

    Near optimal linear algebra in the online and sliding window models , author=. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS) , pages=. 2020 , organization=

    2020

  23. [23]

    2025 , eprint=

    On the Adversarial Robustness of Online Importance Sampling , author=. 2025 , eprint=

    2025

  24. [24]

    Foundations and trends

    An introduction to matrix concentration inequalities , author=. Foundations and trends. 2015 , publisher=

    2015

  25. [25]

    Freedman , title =

    David A. Freedman , title =. The Annals of Probability , number =. 1975 , doi =

    1975

  26. [26]

    Peng, Binghui , title =

  27. [27]

    2016 , issue_date =

    Koutis, Ioannis and Xu, Shen Chen , title =. 2016 , issue_date =. doi:10.1145/2948062 , journal =

    work page doi:10.1145/2948062 2016

  28. [28]

    Discrete & Computational Geometry , volume=

    On sparse spanners of weighted graphs , author=. Discrete & Computational Geometry , volume=. 1993 , publisher=

    1993

  29. [29]

    30th Annual European Symposium on Algorithms (ESA 2022) , pages =

    Bhattacharya, Sayan and Saranurak, Thatchaphol and Sukprasert, Pattara , title =. 30th Annual European Symposium on Algorithms (ESA 2022) , pages =. 2022 , volume =. doi:10.4230/LIPIcs.ESA.2022.17 , annote =

    doi:10.4230/lipics.esa.2022.17 2022

  30. [30]

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

    Forster, Sebastian and Nazari, Yasamin and Probst Gutenberg, Maximilian , title =. Proceedings of the 55th Annual ACM Symposium on Theory of Computing , pages =. 2023 , isbn =. doi:10.1145/3564246.3585213 , abstract =

    arXiv 2023

  31. [31]

    52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , pages=

    A Simple Dynamic Spanner via APSP , author=. 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) , pages=. 2025 , organization=

    2025

  32. [32]

    arXiv preprint arXiv:2004.08432 , year=

    Fully-dynamic graph sparsifiers against an adaptive adversary , author=. arXiv preprint arXiv:2004.08432 , year=

    Pith/arXiv arXiv 2004

  33. [33]

    Howard and Aaditya Ramdas and Jon McAuliffe and Jasjeet Sekhon , title =

    Steven R. Howard and Aaditya Ramdas and Jon McAuliffe and Jasjeet Sekhon , title =. Probability Surveys , number =. 2020 , doi =

    2020

  34. [34]

    2025 , eprint=

    Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams , author=. 2025 , eprint=

    2025

  35. [35]

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

    Kyng, Rasmus and Pachocki, Jakub and Peng, Richard and Sachdeva, Sushant , title =. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , pages =. 2017 , publisher =

    2017