Pith. sign in

REVIEW 3 major objections 4 minor 58 references

John Ellipsoids via Lazy Updates

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

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

Pith's one-line read The authors show that approximate John ellipsoids of n dense points in d dimensions can be computed in nearly O(ε^{-1}nd) time, removing the matrix-multiplication exponent from the dominant term of the best prior algorithm, and give a…

desk verdict The lazy-update scheduler is worth reading, but the O(nd) leverage-score claim rests on a false premise and the main proof has a bug. read the letter →

arxiv 2501.01801 v1 pith:OITLSMIM submitted 2025-01-03 cs.DS cs.LG

David P. Woodruff , Taisuke Yasuda This is my paper · ORCID
classification cs.DScs.LG MSC 68W2068Q2590C25
keywords JohnellipsoidleveragescoreslazyupdatesfastrectangularmatrixmultiplicationstreamingalgorithmsrandomizednumericallinearalgebraD-optimaldesignconvexhullapproximation
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 claims that the classic fixed-point iteration for computing an approximate John ellipsoid—repeatedly reweighting points by their leverage scores—can be simulated in nearly O($ε^{{-1}}$nd) time for dense inputs, improving on the previous best of O($ε^{{-1}}$$nd^{{ω-1}}$) log(n/d) with ω the matrix multiplication exponent. The key is to defer high-accuracy leverage score computations, using low-accuracy scores for all rows to sample a small set, and then to compute batches of high-accuracy weights at once via fast rectangular matrix multiplication. The paper also gives a multi-pass streaming algorithm with O($d^{2}$/ε) space using the same lazy-update idea. If correct, this removes the superlinear dependence on the matrix multiplication exponent from the dominant term and makes John ellipsoid computation nearly input-sparsity time for dense matrices.

What carries the argument

The central object is the leverage score fixed-point iteration: $w^{{(t)}}$_i = τ_i(√$W^{{(t-1)}}$ A), where the John ellipsoid is given by the quadratic form A^T W A. The acceleration mechanism is 'lazy updates': the algorithm maintains only approximate quadratics Q̃(t), computes low-accuracy leverage scores for all rows in O(nd) time to drive a row sample, evaluates exact-weight products only on the sampled rows, and periodically batches the full weight update into a single product of A with a d×m Gaussian-sketch matrix, exploiting the fast rectangular matrix multiplication bound that an n×d by d×m product costs O(nd + n $m^{{1/α}}$) poly-log time for a constant α≥0.1.

What would settle it

Take A = diag(1, 100, 1, ..., 1) in d dimensions with n−d zero rows appended, so the true leverage score of every nonzero row is 1. For any random d×t matrix R with t independent of d, the squared row norms of A R for the first two rows will be proportional to 1 and 10000 (after scaling), differing by a factor of $10^{4}$; observing this ratio for d ≥ 2 and t = O($ε^{{-2}}$ log n) would directly contradict the claimed representation of leverage scores as row norms of A R, which is the stated basis for Theorem 1.3.

Watch

Extended reading notes

Core claim

The authors establish that the iterative John ellipsoid algorithm of [CCLY19]—which alternates between computing leverage scores of the reweighted matrix and reweighting rows—can be accelerated by a 'lazy update' scheme. Instead of computing all n high-accuracy leverage scores in every one of the T=O($ε^{{-1}}$ log(n/d)) iterations, the algorithm computes only low-accuracy leverage scores for all rows in O(nd) time, samples a small subset of rows using those scores, evaluates high-accuracy weights on just the sampled rows, and accumulates approximate quadratics. After O(log n) rounds, it resets the weights by a single multiplication of A by a d×m Gaussian-sketched matrix, using fast rectangular matrix multiplication to do this in O(nd) poly-log time. The resulting Algorithm 3 returns an ellipsoid Q with 1/√(1+ε) Q ⊆ P ⊆ √d Q in time O($ε^{{-1}}$nd)(log(n/d)+poly log($ε^{{-1}}$log n)) + O(n) poly($ε^{{-1}}$log n) + O($n^{{0.1}}$) $d^{{ω+1}}$ $ε^{{-3}}$ (log n)^2, and the same machinery yields a streaming algorithm with O($d^{2}$T) space that passes over the data T times.

Load-bearing premise

The near-linear running time depends on the premise that all leverage scores can be approximated to a (1±ε) factor as the squared row norms of A times a random d×t matrix with t = O($ε^{{-2}}$ log(n/δ)) independent of d.

Editorial extensions

If this is right

  • If correct, the algorithm gives the first nearly O(ε^{-1} n d) algorithm for approximating John ellipsoids of dense matrices, removing the superlinear d^{ω-1} factor from prior bounds.
  • The lazy-update scheme is a general template: any iterative reweighting algorithm whose bottleneck is repeated full-matrix leverage-score computations could be accelerated by batching the precise computations and using fast rectangular matrix multiplication, as the paper notes for parallelization in Remark 1.7.
  • The streaming algorithm yields a multi-pass algorithm using O(d^2/ε) space, improving on prior streaming ellipsoid algorithms that either used more passes or allowed only O(√log n) approximation.
  • The approximate leverage score result (Theorem 1.3), if established, gives a near-linear time algorithm for (1+ε)-approximate leverage scores of dense matrices, a central primitive in randomized numerical linear algebra.
  • For n≫ d, the running time bound implies that even constant-factor volume-optimal ellipsoids (approximating the maximal volume up to (1+ε)) can be computed in O(ε^{-1} n d^2 log(n/d)) time.

Reading between the lines

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

  • The technique of 'delaying large matrix multiplications to exploit economies of scale' could apply to other iterative algorithms that repeatedly compute leverage scores, such as ℓ_p Lewis weight algorithms, where the bottleneck is similar; the paper raises this as a future question but the transfer may be direct.
  • The practical speedup over prior work depends on the hidden constants in the fast rectangular matrix multiplication (currently α≥0.1) and the poly(ε^{-1}) factors; at moderate d and n, the O(nd^{ω-1}) baseline may still win on real hardware until ε is quite small.
  • A testable extension is to implement the streaming algorithm and verify the O(d^2T)-word space bound in the real-number model, while acknowledging the paper leaves the bit-complexity version open.
  • The near-linear per-iteration cost suggests John ellipsoid computation could become practical for massive online learning and D-optimal design instances where prior dense-matrix algorithms were infeasible.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper proposes faster algorithms for computing approximate John ellipsoids for a set of n points in d dimensions. The main contribution is a claimed O(ε^{-1}nd) log(n/d)-time algorithm, improving on the O(ε^{-1}nd^{ω-1}) log(n/d) iterative-leverage-score algorithm of CCLY19. The technical strategy is to (i) compute approximate leverage scores in O(nd) time via fast rectangular matrix multiplication, (ii) use a 'lazy update' scheme to avoid high-accuracy leverage score computations at every iteration, and (iii) periodically recompute the weights using fast rectangular matrix multiplication. A streaming variant is also stated. The central claims rest on Theorem 1.3 (linear-time leverage scores) and Theorem 1.6 (the final running-time bound), with correctness argued through a sequence of lemmas on products of χ² variables and leverage-score sampling.

Significance. If the main results were correct, they would represent a significant improvement for dense John ellipsoid computation: the O(ε^{-1}nd) log(n/d) running time would be nearly linear in the input size for n≫d, and the streaming result would be a useful low-space multi-pass algorithm. The paper is clearly written and the high-level idea (delaying high-accuracy leverage-score computations, then batching them via rectangular matrix multiplication) is attractive. However, the main theorem is not established in the submitted version: the leverage-score time claim rests on a misstatement of the DMMW12 result, the proof of a key concentration lemma is invalid, and the running-time statement omits important matrix-multiplication costs. These are load-bearing issues, not presentation details.

major comments (3)
  1. [Section 1.2.1, Theorem 1.3] The claim that 'the leverage scores of A can be written as the row norms of AR for a d×t matrix with t=O(ε^{-2}log(n/δ))' is false. Leverage scores of A are the squared row norms of U = A(A^T A)^{-1/2}, not of A R; they are invariant under right-multiplication of A by any invertible matrix, whereas row norms of A R are not. For A=[I_d; (1/√d)1^T] and R=I, the last row has row norm 1 but leverage score 1/2. Approximating leverage scores by row norms of U R requires forming or implicitly multiplying by the whitening matrix (A^T A)^{-1/2}; the paper provides no O(nd)-time procedure for this step, and the cited DMMW12 result (which computes an orthonormal basis first) does not establish it. Consequently, Theorem 1.3's O(nd) leverage-score bound is unsupported, and the dominant O(ε^{-1}nd) log(n/d) term in Theorem 1.6 and the abstract is not justified.
  2. [Lemma 2.2] The proof of Lemma 2.2 sets s=k/2 in the lower-tail bound of Lemma 2.1. For this value, C_{-s,k}=2^{-k/2} Γ(0)/Γ(k/2) is infinite, so the bound Pr{∏X_i ≤ 1/R} ≤ C_{-s,k}^T R^{-s} is vacuous. The high-probability event on products of χ² variables, which Lemma 2.4 and the proof of Theorem 1.6 condition on, is therefore not established. A different proof (e.g., tail bounds for sums of log-χ² variables) might salvage the lemma, but the submitted argument is invalid as written.
  3. [Theorem 1.6, Table 1] The running time stated in Theorem 1.6 contains the term O(n^{0.1})d^{ω+1}ε^{-3}(log n)^2, but the abstract and Table 1 advertise only O(ε^{-1}nd) log(n/d). These are not equivalent in the stated regime n≫d≫poly(ε^{-1}log n): for d=n^{0.8}, the extra term is n^{0.1}·(n^{0.8})^{ω+1} ≈ n^{0.1+0.8×3.37} = n^{2.8}, whereas ε^{-1}nd ≈ n^{1.8}, so the omitted term dominates. Moreover, the algorithm does not account for the cost of forming Q(0)=A^T W(0)A in Algorithm 2, Line 2, or the final product A^T \tildeWA in Algorithm 3, Line 11; each of these products costs O(nd^{ω-1}) with fast matrix multiplication and can dominate the claimed bound. The running-time statement is therefore incomplete.
minor comments (4)
  1. [Lemma 2.4, Algorithm 2] The definition of v_i^{(t)} in Lemma 2.4 uses a product up to t−1, while Algorithm 2, Line 7 sets v_i^{(t)} as a product up to t; these should be reconciled to avoid an off-by-one error in the correctness argument.
  2. [Theorem 2.6, Algorithm 3] Theorem 2.6 states the JL lemma for an m×d Gaussian matrix G, while Algorithm 3, Line 6 uses a d×m Gaussian; the transpose convention should be fixed for clarity.
  3. [Theorem 1.8] The proof of the streaming result is only a sketch; the claim that Sherman-Morrison updates lead to O(d^2T) update time per row should be made explicit, since the pseudocode in Algorithm 1 does not show the pseudoinverse update.
  4. [Remark 1.7] There is a minor typo in Remark 1.7 ('can be be viewed'), and the paper contains a few other small typographical errors (e.g., inconsistent use of t vs. T in the proof of Lemma 2.2).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation rests on external fixed-point, sketching, and JL theorems and is self-contained.

full rationale

The paper's derivation chain is not circular. The central algorithmic claim (Theorem 1.6) is built on the CCLY19 fixed-point characterization (Theorem 2.5, cited externally), the DMMW12 leverage-score sketching theorem (Section 1.2.1), the Johnson–Lindenstrauss lemma (Theorem 2.6), and standard leverage-score sampling (Theorem 2.3). None of these is defined in terms of the John ellipsoid conclusion, and no parameter is fitted to the output ellipsoid: the algorithm's weights are produced by the fixed-point iteration and then bounded by direct probabilistic analysis of products of chi-squared variables and JL errors. The only self-citations are WY22 and WY23, used as contextual references for streaming work and an application, not as load-bearing premises. The citation to DMMW12, though co-authored by one of the present authors, is a published external theorem with its own proof and does not assume the John ellipsoid result; under the rules, this is independent support, not circularity. The reviewer's concern about whether DMMW12's sketch width can be independent of d is a correctness or assumption issue, not a circularity issue, and accordingly does not affect the circularity score. The paper is self-contained against external benchmarks, so the honest finding is no significant circularity.

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

The paper introduces no new entities or fitted constants. It relies on standard randomized linear algebra tools and one external convergence theorem. The most fragile axiom is the DMMW12 leverage score premise, which is load-bearing for the near-linear time claim and appears to require sketch width scaling with d.

assumptions (5)
  • standard math Fast rectangular matrix multiplication with exponent α ≥ 0.1 (Theorem 1.4)
    Cited from Coppersmith 1982 and Williams 2011/2024; used to derive Corollary 1.5 and the O(nd) multiplication bounds.
  • standard math Johnson-Lindenstrauss lemma for embedding n points in O(ε^{-2} log n) dimensions
    Used in Theorem 2.6 and in Algorithm 3 to approximate leverage scores via Gaussian sketches.
  • domain assumption CCLY19 fixed-point iteration guarantee (Theorem 2.5)
    The entire correctness reduction to (1±ε) leverage scores relies on this external theorem from Cohen, Cousins, Lee, and Yang 2019.
  • domain assumption DMMW12 sketching-based leverage score approximation
    Used to assert leverage scores can be read off row norms of A times a d×t matrix with t=O(ε^{-2} log(n/δ)); questionable for t independent of d.
  • standard math Leverage score sampling theorem (DMM06, SS11)
    Used in Theorem 2.3 to guarantee a spectral approximation from sampled rows.

how reviews work

0 comments
Cite this review

Pith. "Pith review of John Ellipsoids via Lazy Updates." pith.science (2026). https://pith.science/paper/OITLSMIM

@misc{pith2026250101801,
  author       = {Pith},
  title        = {Pith review of: John Ellipsoids via Lazy Updates},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OITLSMIM}},
  note         = {Machine review of arXiv:2501.01801}
}
abstract

We give a faster algorithm for computing an approximate John ellipsoid around $n$ points in $d$ dimensions. The best known prior algorithms are based on repeatedly computing the leverage scores of the points and reweighting them by these scores [CCLY19]. We show that this algorithm can be substantially sped up by delaying the computation of high accuracy leverage scores by using sampling, and then later computing multiple batches of high accuracy leverage scores via fast rectangular matrix multiplication. We also give low-space streaming algorithms for John ellipsoids using similar ideas.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

58 extracted references · 55 canonical work pages

  1. [1]

    On computing approximate Lewis weights

    Simon Apers, Sander Gribling, and Aaron Sidford. On computing approximate L ewis weights. CoRR , abs/2404.02881, 2024

    work page Pith review arXiv 2024

  2. [2]

    Agarwal and R

    Pankaj K. Agarwal and R. Sharathkumar. Streaming algorithms for extent problems in high dimensions. Algorithmica , 72(1):83--98, 2015

    2015

  3. [3]

    Selin Damla Ahipasaoglu, Peng Sun, and Michael J. Todd. Linear convergence of a modified F rank- W olfe algorithm for computing minimum-volume enclosing ellipsoids. Optim. Methods Softw. , 23(1):5--19, 2008

    work page 2008

  4. [4]

    Corwin L. Atwood. Optimal and efficient designs of experiments. Ann. Math. Statist. , 40:1570--1602, 1969

    work page 1969

  5. [5]

    Corwin L. Atwood. Sequences converging to D -optimal designs of experiments. Ann. Statist. , 1:342--352, 1973

    work page 1973

  6. [6]

    S \' e bastien Bubeck, Nicol \` o Cesa - Bianchi, and Sham M. Kakade. Towards minimax policies for online linear optimization with bandit feedback. In Shie Mannor, Nathan Srebro, and Robert C. Williamson, editors, COLT 2012 - The 25th Annual Conference on Learning Theory, June 25-27, 2012, Edinburgh, Scotland , volume 23 of JMLR Proceedings , pages 41.1--...

    work page 2012

  7. [7]

    Tight bounds for volumetric spanners and applications

    Aditya Bhaskara, Sepideh Mahabadi, and Ali Vakilian. Tight bounds for volumetric spanners and applications. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA...

    work page 2023

  8. [8]

    Cohen, Ben Cousins, Yin Tat Lee, and Xin Yang

    Michael B. Cohen, Ben Cousins, Yin Tat Lee, and Xin Yang. A near-optimal algorithm for approximating the J ohn ellipsoid. In Alina Beygelzimer and Daniel Hsu, editors, Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA , volume 99 of Proceedings of Machine Learning Research , pages 849--873. PMLR , 2019

    work page 2019

Show all 58 references
  1. [9]

    Wainwright, and Bin Yu

    Yuansi Chen, Raaz Dwivedi, Martin J. Wainwright, and Bin Yu. Fast MCMC sampling algorithms on polytopes. J. Mach. Learn. Res. , 19:55:1--55:86, 2018

    2018

  2. [10]

    Clarkson

    Kenneth L. Clarkson. Subgradient and sampling algorithms for _1 regression. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '05, pages 257--266, USA, 2005. Society for Industrial and Applied Mathematics

    2005

  3. [11]

    Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford

    Michael B. Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford. Uniform sampling for matrix approximation. In Tim Roughgarden, editor, Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israe...

    2015

  4. [12]

    Rapid multiplication of rectangular matrices

    Don Coppersmith. Rapid multiplication of rectangular matrices. SIAM J. Comput. , 11(3):467--471, 1982

    1982

  5. [13]

    Clarkson and David P

    Kenneth L. Clarkson and David P. Woodruff. Low rank approximation and regression in input sparsity time. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013 , pages 81--90. ACM , 2013

    2013

  6. [14]

    Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, and Michael W. Mahoney. Sampling algorithms and coresets for _p regression. SIAM J. Comput. , 38(5):2060--2078, 2009

    2009

  7. [15]

    An elementary proof of a theorem of J ohnson and L indenstrauss

    Sanjoy Dasgupta and Anupam Gupta. An elementary proof of a theorem of J ohnson and L indenstrauss. Random Struct. Algorithms , 22(1):60--65, 2003

    2003

  8. [16]

    Mahoney, and S

    Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. Sampling algorithms for _2 regression and applications. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006 , pages 1127--1136. ACM Press, 2006

    2006

  9. [17]

    Mahoney, and David P

    Petros Drineas, Malik Magdon - Ismail, Michael W. Mahoney, and David P. Woodruff. Fast approximation of matrix coherence and statistical leverage. J. Mach. Learn. Res. , 13:3475--3506, 2012

    2012

  10. [18]

    Faster matrix multiplication via asymmetric hashing

    Ran Duan, Hongxun Wu, and Renfei Zhou. Faster matrix multiplication via asymmetric hashing. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023 , pages 2129--2138. IEEE , 2023

    2023

  11. [19]

    Computing L ewis weights to high precision

    Maryam Fazel, Yin Tat Lee, Swati Padmanabhan, and Aaron Sidford. Computing L ewis weights to high precision. In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, U...

    2022

  12. [20]

    Pattern separation via ellipsoids and conic programming

    Fran c ois Glineur. Pattern separation via ellipsoids and conic programming. M \'e moire de DEA, Facult \'e Polytechnique de Mons, Mons, Belgium , 1998

    1998

  13. [21]

    John's walk

    Adam Gustafson and Hariharan Narayanan. John's walk. Adv. in Appl. Probab. , 55(2):473--491, 2023

    2023

  14. [22]

    A randomized exchange algorithm for computing optimal approximate designs of experiments

    Radoslav Harman, Lenka Filov\' a , and Peter Richt\' a rik. A randomized exchange algorithm for computing optimal approximate designs of experiments. J. Amer. Statist. Assoc. , 115(529):348--361, 2020

    2020

  15. [23]

    Elad Hazan and Zohar S. Karnin. Volumetric spanners: An efficient exploration basis for learning. J. Mach. Learn. Res. , 17:119:1--119:34, 2016

    2016

  16. [24]

    Johnson and Joram Lindenstrauss

    William B. Johnson and Joram Lindenstrauss. Extensions of L ipschitz mappings into a H ilbert space. In Conference in modern analysis and probability ( N ew H aven, C onn., 1982) , volume 26 of Contemp. Math. , pages 189--206. Amer. Math. Soc., Providence, RI, 1984

    1982

  17. [25]

    Extremum problems with inequalities as subsidiary conditions

    Fritz John. Extremum problems with inequalities as subsidiary conditions. In Studies and E ssays P resented to R . C ourant on his 60th B irthday, J anuary 8, 1948 , pages 187--204. Interscience Publishers, Inc., New York, N. Y., 1948

    1948

  18. [26]

    Khachiyan

    Leonid G. Khachiyan. A polynomial algorithm in linear programming. Dokl. Akad. Nauk SSSR , 244(5):1093--1096, 1979

    1979

  19. [27]

    Khachiyan

    Leonid G. Khachiyan. Rounding of polytopes in the real number model of computation. Math. Oper. Res. , 21(2):307--320, 1996

    1996

  20. [28]

    Khachiyan and Michael J

    Leonid G. Khachiyan and Michael J. Todd. On the complexity of approximating the maximal inscribed ellipsoid for a polytope. Math. Programming , 61(2, Ser. A):137--159, 1993

    1993

  21. [29]

    Alper Yildirim

    Piyush Kumar and E. Alper Yildirim. Minimum-volume enclosing ellipsoids and core sets. J. Optim. Theory Appl. , 126(1):1--21, 2005

    2005

  22. [30]

    Miller, and Richard Peng

    Mu Li, Gary L. Miller, and Richard Peng. Iterative row sampling. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA , pages 127--136. IEEE Computer Society, 2013

    2013

  23. [31]

    Streaming algorithms for ellipsoidal approximation of convex polytopes

    Yury Makarychev, Naren Sarayu Manoj, and Max Ovsiankin. Streaming algorithms for ellipsoidal approximation of convex polytopes. In Po - Ling Loh and Maxim Raginsky, editors, Conference on Learning Theory, 2-5 July 2022, London, UK , volume 178 of Proceedings of Machine Learnin...

    2022

  24. [32]

    Near-optimal streaming ellipsoidal rounding for general convex polytopes

    Yury Makarychev, Naren Sarayu Manoj, and Max Ovsiankin. Near-optimal streaming ellipsoidal rounding for general convex polytopes. CoRR , abs/2311.09460, 2023

    2023 arXiv

  25. [33]

    Approximate ellipsoid in the streaming model

    Asish Mukhopadhyay, Animesh Sarker, and Tom Switzer. Approximate ellipsoid in the streaming model. In Weili Wu and Ovidiu Daescu, editors, Combinatorial Optimization and Applications - 4th International Conference, COCOA 2010, Kailua-Kona, HI, USA, December 18-20, 2010, Procee...

    2010

  26. [34]

    Interior-point polynomial algorithms in convex programming , volume 13 of SIAM Studies in Applied Mathematics

    Yurii Nesterov and Arkadii Nemirovskii. Interior-point polynomial algorithms in convex programming , volume 13 of SIAM Studies in Applied Mathematics . Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1994

    1994

  27. [35]

    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 Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013 , pages...

    2013

  28. [36]

    Pattern separation by convex programming

    Judah Ben Rosen. Pattern separation by convex programming. Journal of Mathematical Analysis and Applications , 10(1):123--134, 1965

    1965

  29. [37]

    Peng Sun and Robert M. Freund. Computation of minimum-volume covering ellipsoids. Oper. Res. , 52(5):690--706, 2004

    2004

  30. [38]

    Cut-off method with space extension in convex programming problems

    Naum Z Shor. Cut-off method with space extension in convex programming problems. Cybernetics , 13(1):94--96, 1977

    1977

  31. [39]

    Optimal design: an introduction to the theory for parameter estimation , volume 1

    Samuel Silvey. Optimal design: an introduction to the theory for parameter estimation , volume 1. Springer Science & Business Media, 2013

    2013

  32. [40]

    Spielman and Nikhil Srivastava

    Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J. Comput. , 40(6):1913--1926, 2011

    1913

  33. [41]

    On products of gaussian random variables

    Z eljka Stojanac, Daniel Suess, and Martin Kliesch. On products of gaussian random variables. arXiv preprint arXiv:1711.10516 , 2017

    2017 arXiv

  34. [42]

    Minimum covering ellipses

    BW Silverman and DM Titterington. Minimum covering ellipses. SIAM Journal on Scientific and Statistical Computing , 1(4):401--409, 1980

    1980

  35. [43]

    An algorithm for optimal designs on a design space

    Samuel D Silvey, DH Titterington, and Ben Torsney. An algorithm for optimal designs on a design space. Communications in Statistics-Theory and Methods , 7(14):1379--1389, 1978

    1978

  36. [44]

    Faster algorithm for structured J ohn ellipsoid computation

    Zhao Song, Xin Yang, Yuanyuan Yang, and Tianyi Zhou. Faster algorithm for structured J ohn ellipsoid computation. CoRR , abs/2211.14407, 2022

    2022

  37. [45]

    S. P. Tarasov, L. G. Khachiyan, and I. I. \`Erlikh. The method of inscribed ellipsoids. Dokl. Akad. Nauk SSSR , 298(5):1081--1085, 1988

    1988

  38. [46]

    Coresets for near-convex functions

    Murad Tukan, Alaa Maalouf, and Dan Feldman. Coresets for near-convex functions. In Hugo Larochelle, Marc'Aurelio Ranzato, Raia Hadsell, Maria - Florina Balcan, and Hsuan - Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Info...

    2020

  39. [47]

    Michael J. Todd. Minimum volume ellipsoids - theory and algorithms , volume 23 of MOS-SIAM Series on Optimization . SIAM , 2016

    2016

  40. [48]

    New coresets for projective clustering and applications

    Murad Tukan, Xuan Wu, Samson Zhou, Vladimir Braverman, and Dan Feldman. New coresets for projective clustering and applications. In Gustau Camps - Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTA...

    2022

  41. [49]

    Todd and E

    Michael J. Todd and E. Alper Yildirim. On K hachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids. Discrete Appl. Math. , 155(13):1731--1744, 2007

    2007

  42. [50]

    Pravin M. Vaidya. A new algorithm for minimizing convex functions over convex sets. Math. Programming , 73(3, Ser. A):291--341, 1996

    1996

  43. [51]

    Geometric random walks: a survey

    Santosh Vempala. Geometric random walks: a survey. Combinatorial and computational geometry , 52(573-612):2, 2005

    2005

  44. [52]

    Non-uniform ACC circuit lower bounds

    Ryan Williams. Non-uniform ACC circuit lower bounds. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011 , pages 115--125. IEEE Computer Society, 2011

    2011

  45. [53]

    Personal communication, 2024

    Ryan Williams. Personal communication, 2024

    2024

  46. [54]

    P. Wolfe. Convergence theory in nonlinear programming. In Integer and nonlinear programming , pages 1--36. North-Holland, Amsterdam-London, 1970

    1970

  47. [55]

    New bounds for matrix multiplication: from alpha to omega

    Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New bounds for matrix multiplication: from alpha to omega. In David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024...

    2024

  48. [56]

    Woodruff and Taisuke Yasuda

    David P. Woodruff and Taisuke Yasuda. High-dimensional geometric streaming in polynomial space. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022 , pages 732--743. IEEE , 2022

    2022

  49. [57]

    Woodruff and Taisuke Yasuda

    David P. Woodruff and Taisuke Yasuda. New subset selection algorithms for low rank approximation: Offline and online. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20-23, 202...

    2023

  50. [58]

    D-optimal designs via a cocktail algorithm

    Yaming Yu. D-optimal designs via a cocktail algorithm. Stat. Comput. , 21(4):475--481, 2011

    2011

Pith tools

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