Pith. sign in

REVIEW 3 major objections 4 minor 5 cited by

Solving Ax=b requires Ω(κ log(1/ε)) matrix–vector products in the worst case, and one-sided solvers need n even when κ=1.

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-03 04:25 UTC pith:6Q37JG3H

load-bearing objection Strong paper with two serious gaps: Theorem 1.1 overclaims without a dimension condition, and the proof of the one-sided n-bound has a flawed probability step; worth refereeing after fixes. the 3 major comments →

arxiv 2602.04842 v4 pith:6Q37JG3H submitted 2026-02-04 cs.DS cs.NAmath.NAmath.OC

The matrix-vector complexity of Ax=b

Micha{\l} Derezi\'nski , Ethan N. Epperly , Raphael A. Meyer This is my paper
classification cs.DS cs.NAmath.NAmath.OC MSC 65F1068Q1768Q25
keywords matrix-vector complexitylinear systemsKrylov subspace methodslower boundscondition numberconjugate gradientGMRESrandomized algorithms
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 establishes worst-case lower bounds on the number of matrix–vector products needed to approximately solve a general linear system Ax=b. It shows that any randomized two-sided algorithm — one that can multiply by both A and its transpose — must use at least Ω(κ log(1/ε)) products for a system of condition number κ and target relative residual ε, matching the count used by conjugate gradient on the normal equations to within a factor of four. It further shows that one-sided algorithms, which can only multiply by A, must use n products even for an orthogonal matrix, matching GMRES's worst-case behavior. A third result sharpens the lower bound for symmetric positive-definite systems to Ω(√κ log(1/ε)). Together these results confirm that the classical Krylov methods are optimal within the much larger class of randomized matrix–vector algorithms.

Core claim

The paper's central claim is that the matrix–vector complexity of solving linear systems is now understood up to small constants. For two-sided algorithms, the hard case is a symmetric matrix whose eigenvalues lie on the split interval [−κ,−1]∪[1,κ]; the function f(x)=1/x cannot be approximated there by polynomials of degree less than Ω(κ log(1/ε)), and the paper proves that this polynomial inapproximability forces any randomized algorithm to use that many matvecs. For one-sided algorithms, the hard case is a Haar-random orthogonal matrix Q: a new hidden Haar theorem shows that after fewer than n matvecs, the algorithm cannot learn enough about Q's rows to distinguish the solution from other

What carries the argument

Two load-bearing tools. For the two-sided bound: the reduction of linear-system solving to estimating the trace of A^{-1}, combined with a theorem that matrix–vector algorithms for spectral sums need at least as many matvecs as the degree of the best polynomial approximation to the function (here 1/x on a split interval). For the one-sided bound: the hidden Haar theorem, which states that when a Haar-random orthogonal matrix is queried by a one-sided algorithm, the unobserved part of the matrix remains uniformly random conditioned on the transcript, so the queries cannot reveal the rows of Q needed to solve Qx=b.

Load-bearing premise

The two-sided bound rests on an imported reduction theorem asserting that any adaptive sequence of matrix–vector products against a rotationally invariant matrix is distributionally equivalent to a triangular block Krylov sequence, and the proof only goes through when the dimension n is large compared with κ; if either premise fails, the stated Ω(κ log(1/ε)) bound for all κ is not established.

What would settle it

Run a two-sided randomized solver on a large symmetric matrix whose eigenvalues cover the split interval [−κ,−1]∪[1,κ] at a large condition number κ and small target residual ε, and observe whether it beats roughly (1/4)κ log(1/ε) matvecs; doing so by a constant factor for all κ and ε would refute Theorem 1.1. Alternatively, exhibit an adaptive query strategy whose transcript against a Haar-random orthogonal matrix is not equivalent to any triangular block Krylov sequence, which would invalidate the imported reduction behind the proof.

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

If this is right

  • CG on the normal equations is worst-case optimal for general linear systems up to a factor of about 4; no randomized algorithm can asymptotically beat it in the matvec model.
  • GMRES's need for n matvecs on some perfectly conditioned systems is unavoidable; transpose access is necessary to escape the n-matvec barrier.
  • The SPD lower bound Ω(√κ log(1/ε)) matches the convergence rate of conjugate gradient, so the ε-dependence in the standard upper bound is tight.
  • The fine-grained lower bound Ω(k + κ_k log(1/ε)) shows that exploiting a few outlying singular values cannot beat the reduced condition number bound, and it separates matvec-access algorithms from direct-entry access for dense matrices.

Where Pith is reading between the lines

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

  • The polynomial-inapproximability route is general: any function f that is hard to approximate by low-degree polynomials on a symmetric spectrum should force Ω(t) matvecs to compute f(A)b or tr(f(A)), so the two-sided result likely extends well beyond solving linear systems.
  • The dimension threshold n ≳ κ^{(6+δ)/η} leaves open a regime n ≤ κ^6 where the techniques give no lower bound; a natural next question is whether the complexity genuinely drops there or whether a better proof can close the gap.
  • The relative-error trace estimation problem is left open; if the authors' conjectured Ω(t/ε) lower bound holds, it would strengthen the trace-inverse results and, by reduction, the linear-systems lower bound in the low-accuracy regime.
  • The one-sided lower bound is distributional rather than worst-case over fixed instances; translating it into a deterministic family of hard instances with explicit constants would make the bound more directly usable for benchmarking solvers.

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

3 major / 4 minor

Summary. The paper studies the worst-case matrix-vector query complexity of approximately solving general linear systems Ax=b. The two main claims are: (1) any randomized two-sided matrix-vector algorithm needs Ω(κ log(1/ε)) matvecs to achieve relative residual ε for matrices of condition number at most κ, matching CGNE up to a factor of about 4; and (2) any one-sided algorithm needs n matvecs for perfectly conditioned problems, matching GMRES's worst-case behavior, with a weaker Ω(n/2) bound for constant accuracy. The two-sided lower bound is obtained through a polynomial-inapproximability argument for tr(A^{-1}), a reduction from linear-system solvers to trace-inverse estimators, and a reduction to randomized block Krylov methods. The one-sided lower bound is obtained from a new 'hidden Haar theorem' showing that after t one-sided queries, the unobserved part of a Haar-random orthogonal matrix remains hidden. The paper also states SPD and fine-grained variants. The proof architecture is coherent and the explicit constants are a strength, but two load-bearing gaps appear: the headline two-sided theorem is stated without the dimension condition used in its proof, and the modest-accuracy one-sided proof contains an invalid probability step. The one-sided constant-accuracy proof also appears to misapply a concentration proposition.

Significance. If the stated results can be made fully rigorous, the paper would resolve the worst-case matrix-vector complexity of general linear system solving up to small constant factors, confirming the optimality of CGNE for two-sided algorithms and of GMRES for one-sided algorithms. The explicit constants and the clean reduction to polynomial inapproximability are valuable. The hidden Haar theorem is a new technical tool with likely applications to transpose-free linear algebra lower bounds. However, the current version overclaims: Theorem 1.1 is not established as stated, and Theorem 1.2(b) is not proven as written. These are not mere presentation issues; they affect the central theorems. The results are plausible and the gaps appear repairable, so the paper merits major revision rather than rejection.

major comments (3)
  1. [§1.2 and §2.5 (Theorem 1.1 vs Theorem 2.8)] Theorem 1.1 is stated as a universal lower bound over all ε>0, κ≥1, and matrices A with cond(A)≤κ, with no restriction on the dimension n. The proof, however, goes through Theorem 2.8, which assumes n≳κ^{(6+δ)/η} and directly proves the lower bound only for ε=1/n (Eq. (2.2)). The text in §2.5 says this 'recovers Theorem 1.1', but that is not a proof for all ε: for a fixed n below the threshold, or for ε≪1/n, the claimed (1−η)/4·κ log(1/ε) bound does not follow. In fact, for n=1 the claimed statement is false for sufficiently small ε, since one matvec with A determines A and hence the solution. The theorem must either be restricted with an explicit n≥n0(κ,ε,η,δ) condition and a matching ε range, or an additional argument must be supplied to cover all ε and n.
  2. [§3.3(b), proof of Theorem 3.3(b)] The probability step in part (b) is invalid. With t=n−1, W^T e1 is a scalar uniformly distributed on [−r,r], where r=sqrt(1−∥V^T e1∥²). For any fixed x~2, the conditional success probability is at most min(ε/r,1) with ε=0.2/√n. Proposition 3.2(a) gives r≥ε with probability >4/5, but this only yields ε/r ≤ 1, not ε/r ≤ 1/2. The sentence 'The component x~2 can be < (1−∥V^T e1∥²) with probability at most 1/2' does not bound the conditional success event, and the product (1/2)(4/5)=2/5 does not imply failure with probability ≥2/3. Thus Theorem 1.2(b) is not established as written. A stronger lower-tail bound on r—for example r≥Cε with C>1 with high probability—would likely repair the argument, but this is not present.
  3. [§3.3(a), proof of Theorem 3.3(a)] The proof of part (a) appears to misapply Proposition 3.2(b). The proposition lower-bounds the sum of the first ⌊n/2⌋ coordinates of a random unit vector by 0.49. The quantity here is r²=1−∥V^T e1∥², which is the sum of the last n−t coordinates. For t<⌈n/2⌉ these are different sets, and the event that the first half has large mass is compatible with the tail after t having small mass. A tail version of the concentration bound is needed; it is plausible and likely true for n sufficiently large, but it is not what Proposition 3.2(b) states. Since part (a) is one of the paper's two one-sided lower bounds, this proof gap should be fixed.
minor comments (4)
  1. [Throughout] There are several typographical confusions between propositions and theorems: §2.1 refers to 'Theorem 2.1' when it means Proposition 2.1; §2.2 refers to 'Theorem 2.2' for Proposition 2.2; §2.6 says 'Proof of Theorem 2.5' and later 'Theorem 2.9' for what is imported Lemma 2.9; the proof of Theorem E.2 references 'Theorem 2.9' instead of Lemma 2.9. These should be corrected.
  2. [Construction A.11] In the definition of the two diagonal matrices, the second matrix is written as 'D := diag(...)' again; it should be Silde{D} := diag(...). Also, just above Lemma A.18, 'Chew et al.' should be 'Chewi et al.'.
  3. [Lemma A.18 and Theorem A.1] The proof of Theorem A.1 sets η=ct^{-3} and uses 'n≳t^6' to bound the bilinear-power TV distance, but the hypothesis of Theorem A.1 also requires n≳t^4/α for the trace separation. This is stated later, but the transition is slightly tangled; please make the role of each hypothesis explicit in one place.
  4. [§2.4] In Theorem 2.6, the condition n≳κ^{(6+δ)/η} is stated with a 'fix any δ,η∈(0,1)' quantifier. The theorem would be clearer if it stated explicitly that the hidden constant in ≳ is universal and independent of κ, n, δ, η, as is standard for this notation, since the proof relies on it.

Circularity Check

0 steps flagged

No significant circularity: the lower bounds are derived from external polynomial-inapproximability, block-Krylov simulation, and hidden-Haar arguments; self-citations are not load-bearing.

full rationale

The derivation chain does not reduce to its own inputs. The two-sided lower bound (Theorem 1.1) proceeds from a linear-system-to-trace-inverse reduction (Proposition 2.2, Theorem 2.8) and the polynomial inapproximability of 1/x on the split interval, which is proved in Section 2.6 from the imported Kraus et al. bound (Lemma 2.9). The general spectral-sum lower bound (Theorem 2.4) is proved in Appendix A using LP duality, Wishart/GOE total-variation bounds, and Chewi et al.'s reduction to block Krylov (Imported Theorem A.5); none of these assume the target lower bound. The one-sided lower bound rests on the hidden Haar theorem, which is proved in Appendix B from rotational invariance rather than assumed. The only significant self-citation is in Theorem 1.4, where the paper says 'This corollary follows immediately by combining our results with a reduction from Derezi´nski et al. [DLNR25, Lem. 27 & Rem. 8]'; this is a fine-grained corollary, not the main result, and the reduction is imported published work rather than an assumption of the target. No fitted parameter is relabeled as a prediction, and no quantity is defined in terms of the quantity being bounded. The manuscript openly notes limitations, e.g. that the techniques provide no lower bound when n ≲ κ^6, and the proof of Theorem 3.3(b) contains a questionable probability step; these are correctness risks, not circularity.

Axiom & Free-Parameter Ledger

0 free parameters · 7 axioms · 0 invented entities

No free parameters; all constants are proof variables. The central claims rest on imported theorems about polynomial approximation, block-Krylov simulation, Wishart/GOE TV bounds, and standard probabilistic tools; none are fitted to data. Self-citations appear only in the fine-grained reduction via DLNR25, which is a prior-work reduction rather than the target result.

axioms (7)
  • standard math Polynomial inapproximability of 1/x on interval [1,b] (Kraus et al., Imported Lemma 2.9)
    Used in Theorem 2.5 to derive inapproximability on the split interval, key to the trace-inverse lower bound.
  • domain assumption Reduction of arbitrary matrix-vector algorithms to randomized block Krylov (Chewi et al., Imported Theorem A.5)
    Load-bearing for the two-sided lower bound; assumes any adaptive matvec sequence against a rotationally invariant matrix is distributionally captured by block Krylov.
  • standard math Neyman-Pearson and coupling lemmas for total variation distance (Imported Theorems A.3 and A.4)
    Used to convert TV closeness of transcripts into a failure probability for distinguishing hard instances.
  • standard math Wishart-to-GOE and Gaussian total variation bounds (Imported Theorems A.15-A.17)
    Used to bound the TV distance between bilinear power sequences of the two constructed hard matrices.
  • domain assumption Matrix-vector algorithm model: access only via z → Az and z → Aᵀz
    Defines the complexity measure; the results are about this query model, not entry-access algorithms.
  • standard math Haar measure on O(n) and rotational invariance
    Basis of the one-sided lower bound; the hidden Haar theorem is proved in Section B using rotational invariance.
  • standard math Yao's minimax principle
    Used to pass from randomized to deterministic algorithms in both lower-bound proofs.

pith-pipeline@v1.3.0-alltime-deepseek · 27705 in / 21786 out tokens · 206675 ms · 2026-08-03T04:25:56.433888+00:00 · methodology

0 comments
read the original abstract

Matrix--vector algorithms, particularly Krylov subspace methods, are widely viewed as the most effective algorithms for solving large systems of linear equations. This paper establishes lower bounds on the worst-case number of matrix--vector products needed by such an algorithm to approximately solve a general linear system. The first main result is that, for any matrix--vector algorithm which is allowed the use of randomization and can perform products with both a matrix and its transpose, $\Omega(\kappa \log(1/\varepsilon))$ matrix--vector products are necessary to solve a linear system with condition number $\kappa$ to accuracy $\varepsilon$, matching an upper bound for conjugate gradient on the normal equations. The second main result is that one-sided algorithms, which lack access to the transpose, must use $n$ matrix--vector products to solve an $n \times n$ linear system, even when the problem is perfectly conditioned. Both main results include explicit constants that match known upper bounds up to a factor of four. These results rigorously demonstrate the limitations of matrix--vector algorithms and confirm the optimality of widely used Krylov subspace algorithms.

discussion (0)

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

Forward citations

Cited by 5 Pith papers

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

  1. Well-Conditioned Oblivious Perturbations in Linear Space

    cs.DS 2026-04 unverdicted novelty 8.0

    An O(n)-randomness perturbation combining a dense deterministic pattern matrix with a non-uniform sparse dependent perturbation reduces condition numbers to O(n) for any input matrix.

  2. Towards Universal Convergence of Backward Error in Linear System Solvers

    math.NA 2026-04 unverdicted novelty 8.0

    Richardson iteration achieves universal 1/k backward error on PSD systems, enabling O(n²/ε) solvers; MINBERR reaches O(1/k²) rate and O(n²/√ε) complexity, with empirical O(1/k) extension to general systems.

  3. Towards Universal Convergence of Backward Error in Linear System Solvers

    math.NA 2026-04 accept novelty 8.0

    Richardson and a new Krylov method MINBERR achieve universal (condition-free) backward-error rates 1/k and O(1/k^{2}) for PSD linear systems, with a near-universal O(log n / k) extension to general systems.

  4. Transpose-free linear algebra

    math.NA 2026-05 unverdicted novelty 7.0

    Establishes non-identifiability results and query lower bounds showing transpose-free matvec access provides limited information for core linear algebra tasks.

  5. Spectral density estimation for normal matrices

    math.NA 2026-05 unverdicted novelty 7.0

    Algorithm approximates spectral density of normal matrices to EMD O(1/m + log m/sqrt(n)) with m matvec queries and proves Omega(1/epsilon) lower bound even for symmetric case.

Reference graph

Works this paper leans on

51 extracted references · 13 canonical work pages · cited by 4 Pith papers

  1. [1]

    Fixed-sparsity matrix approximation from matrix-vector products

    Noah Amsel, Tyler Chen, Feyza Duman Keles, Diana Halikias, Cameron Musco, and Christopher Musco. Fixed-sparsity matrix approximation from matrix-vector products. SIAM Journal on Matrix Analysis and Applications , 2026. To appear. Preprint available at http://arxiv.org/abs/2402.09379v3

    Pith/arXiv arXiv 2026

  2. [2]

    On the rate of convergence of the preconditioned conjugate gradient method

    Owe Axelsson and Gunhild Lindskog. On the rate of convergence of the preconditioned conjugate gradient method. Numerische Mathematik , 48:499--523, 1986. doi:10.1007/BF01389448

    work page doi:10.1007/bf01389448 1986

  3. [3]

    Clarkson, and David P

    Ainesh Bakshi, Kenneth L. Clarkson, and David P. Woodruff. Low-rank approximation with ^ 1/3 matrix-vector products. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 1130--1143, June 2022. doi:10.1145/3519935.3519988

    arXiv 2022

  4. [4]

    Otto, and Alex Townsend

    Nicolas Boullé, Diana Halikias, Samuel E. Otto, and Alex Townsend. Operator learning without the adjoint. Journal of Machine Learning Research , 25(364):1--54, 2024. ://jmlr.org/papers/v25/24-0162.html

    2024

  5. [5]

    The gradient complexity of linear regression

    Mark Braverman, Elad Hazan, Max Simchowitz, and Blake Woodworth. The gradient complexity of linear regression. In Conference on Learning Theory , pages 627--647, 2020. ://proceedings.mlr.press/v125/braverman20a.html

    2020

  6. [6]

    Krylov methods are (nearly) optimal for low-rank approximation

    Ainesh Bakshi and Shyam Narayanan. Krylov methods are (nearly) optimal for low-rank approximation. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science , pages 2093--2101, 2023. doi:10.1109/FOCS57990.2023.00128

    arXiv 2023

  7. [7]

    Convex Optimization

    Stephen Boyd and Lieven Vandenberghe. Convex Optimization . Cambridge University Press, 2004. doi:10.1017/CBO9780511804441

    doi:10.1017/cbo9780511804441 2004

  8. [8]

    Clément L. Canonne. Topics and Techniques in Distribution Testing . Now Publishers, 2022. doi:10.1561/9781638281016

    work page doi:10.1561/9781638281016 2022

  9. [9]

    Query lower bounds for log-concave sampling

    Sinho Chewi, Jaume de Dios Pont, Jerry Li, Chen Lu, and Shyam Narayanan. Query lower bounds for log-concave sampling. Journal of the ACM , 71(4):1--42, 2024. doi:10.1145/3673651

    doi:10.1145/3673651 2024

  10. [10]

    Clarkson and David P

    Kenneth L. Clarkson and David P. Woodruff. Numerical linear algebra in the streaming model. In Proceedings of the forty-first annual ACM Symposium on Theory of Computing , pages 205--214, May 2009. doi:10.1145/1536414.1536445

    arXiv 2009

  11. [11]

    Clarkson and David P

    Kenneth L. Clarkson and David P. Woodruff. Low-rank approximation and regression in input sparsity time. Journal of the ACM , 63(6):1--45, February 2017. doi:10.1145/3019134

    work page doi:10.1145/3019134 2017

  12. [12]

    DeVore and George G

    Ronald A. DeVore and George G. Lorentz. Constructive Approximation , volume 303. Springer Science & Business Media, 1993

    1993

  13. [13]

    Fine-grained analysis and faster algorithms for iteratively solving linear systems

    Michal Derezi \'n ski, Daniel LeJeune, Deanna Needell, and Elizaveta Rebrova. Fine-grained analysis and faster algorithms for iteratively solving linear systems. Journal of Machine Learning Research , 26(144):1--49, 2025. ://www.jmlr.org/papers/v26/24-1906.html

    2025

  14. [14]

    Recent and upcoming developments in randomized numerical linear algebra for machine learning

    Micha Derezi \'n ski and Michael W Mahoney. Recent and upcoming developments in randomized numerical linear algebra for machine learning. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining , pages 6470--6479, 2024. doi:10.1145/3637528.3671461

    arXiv 2024

  15. [15]

    The total variation distance between high-dimensional Gaussians with the same mean

    Luc Devroye, Abbas Mehrabian, and Tommy Reddad. The total variation distance between high-dimensional Gaussians with the same mean. arXiv preprint arXiv:1810.08693v7 http://arxiv.org/abs/1810.08693v7 , February 2022

    Pith/arXiv arXiv 2022

  16. [16]

    Faster linear systems and matrix norm approximation via multi-level sketched preconditioning

    Micha Derezi\'nski, Christopher Musco, and Jiaming Yang. Faster linear systems and matrix norm approximation via multi-level sketched preconditioning. In Proceedings of the 2025 Annual ACM - SIAM Symposium on Discrete Algorithms , pages 1972--2004. January 2025. doi:10.1137/1.9781611978322.62

    work page doi:10.1137/1.9781611978322.62 2025

  17. [17]

    Approaching optimality for solving dense linear systems with low-rank structure

    Micha Derezi\'nski and Aaron Sidford. Approaching optimality for solving dense linear systems with low-rank structure. In Proceedings of the 37th Annual ACM-SIAM Symposium on Discrete Algorithms , 2026. doi:10.1137/1.9781611978971.37

    work page doi:10.1137/1.9781611978971.37 2026

  18. [18]

    Driscoll, Kim-Chuan Toh, and Lloyd N

    Tobin A. Driscoll, Kim-Chuan Toh, and Lloyd N. Trefethen. From potential theory to matrix iterations in six steps. SIAM Review , 40(3):547--578, January 1998. doi:10.1137/S0036144596305582

    doi:10.1137/s0036144596305582 1998

  19. [19]

    Solving dense linear systems faster than via preconditioning

    Micha Derezi \'n ski and Jiaming Yang. Solving dense linear systems faster than via preconditioning. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 1118--1129, 2024. doi:10.1145/3618260.3649694

    arXiv 2024

  20. [20]

    Ethan N. Epperly. Make the most of what you have: Resource-efficient randomized algorithms for matrix computations . PhD thesis, California Institute of Technology, 2025. Available online at https://arxiv.org/abs/2512.15929v1

    arXiv 2025

  21. [21]

    Un algorithme simple et rapide pour la validation croisée généralisée sur des problèmes de grande taille

    Didier Girard. Un algorithme simple et rapide pour la validation croisée généralisée sur des problèmes de grande taille . 1987. ://membres-ljk.imag.fr/Didier.Girard/TR-665-M-IMAG.pdf

    1987

  22. [22]

    Iterative Methods for Solving Linear Systems

    Anne Greenbaum. Iterative Methods for Solving Linear Systems . Number 17 in Frontiers in Applied Mathematics. Society for Industrial and Applied Mathematics, 1997. doi:10.1137/1.9781611970937

    doi:10.1137/1.9781611970937 1997

  23. [23]

    Structured Matrix Recovery and Approximation from Matrix-Vector Products

    Diana Halikias. Structured Matrix Recovery and Approximation from Matrix-Vector Products . PhD , Cornell University, 2025

    2025

  24. [24]

    Harrow, Avinatan Hassidim, and Seth Lloyd

    Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for solving linear systems of equations. Physical Review Letters , 103(15):150502, October 2009. doi:10.1103/PhysRevLett.103.150502

    doi:10.1103/physrevlett.103.150502 2009

  25. [25]

    Optimal sketching for trace estimation

    Shuli Jiang, Hai Pham, David Woodruff, and Richard Zhang. Optimal sketching for trace estimation. Advances in Neural Information Processing Systems , 34:23741--23753, 2021. ://dl.acm.org/doi/10.5555/3540261.3542079

    arXiv 2021

  26. [26]

    Kraus, Panayot S

    Johannes K. Kraus, Panayot S. Vassilevski, and Ludmil T. Zikatanov. Polynomial of best uniform approximation to x^ -1 and smoothing in two-level methods. arXiv preprint arXiv:1002.1859v3 https://arxiv.org/abs/1002.1859v3 , 2010

    Pith/arXiv arXiv 2010

  27. [27]

    Markov Chains and Mixing Times , volume 107

    David A Levin and Yuval Peres. Markov Chains and Mixing Times , volume 107. American Mathematical Society, 2017

    2017

  28. [28]

    Meyer and Haim Avron

    Raphael A. Meyer and Haim Avron. Hutchinson's estimator is bad at Kronecker-Trace-Estimation . SIAM Journal on Matrix Analysis and Applications , 47(1):1--32, 2026. doi:10.1137/23M1595180

    work page doi:10.1137/23m1595180 2026

  29. [29]

    Randomized numerical linear algebra: A perspective on the field with an eye to software

    Riley Murray, James Demmel, Michael W Mahoney, N Benjamin Erichson, Maksim Melnichenko, Osman Asif Malik, Laura Grigori, Piotr Luszczek, Micha Derezi \'n ski, Miles E Lopes, Tianyu Liang, Hengrui Luo, and Jack Dongarra. Randomized numerical linear algebra: A perspective on the field with an eye to software. arXiv preprint arXiv:2302.11474v2 https://arxiv....

    Pith/arXiv arXiv 2023

  30. [30]

    Towards Optimal Matrix-Vector Complexity in Numerical Linear Algebra

    Raphael Arkady Meyer. Towards Optimal Matrix-Vector Complexity in Numerical Linear Algebra . PhD thesis, New York University Tandon School of Engineering, 2024

    2024

  31. [31]

    Geometric median and robust estimation in Banach spaces

    Stanislav Minsker. Geometric median and robust estimation in Banach spaces. Bernoulli , pages 2308--2335, 2015. doi:10.3150/14-BEJ645

    doi:10.3150/14-bej645 2015

  32. [32]

    Meyer, Cameron Musco, Christoper Musco, and David P

    Raphael A. Meyer, Cameron Musco, Christoper Musco, and David P. Woodruff. Hutch++ : Optimal stochastic trace estimation. January 2021. doi:10.1137/1.9781611976496

    work page doi:10.1137/1.9781611976496 2021

  33. [33]

    Randomized Algorithms

    Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms . Cambridge University Press, 1st edition, August 1995. doi:10.1017/CBO9780511814075

    doi:10.1017/cbo9780511814075 1995

  34. [34]

    Foundations of Machine Learning

    Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning . 2018

    2018

  35. [35]

    Per-Gunnar Martinsson and Joel A. Tropp. Randomized numerical linear algebra: Foundations and algorithms. Acta Numerica , 29:403--572, 2020. doi:10.1017/S0962492920000021

    doi:10.1017/s0962492920000021 2020

  36. [36]

    Musco and D

    C. Musco and D. P. Woodruff. Sublinear time low-rank approximation of positive semidefinite matrices. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science , pages 672--683, October 2017. doi:10.1109/FOCS.2017.68

    work page doi:10.1109/focs.2017.68 2017

  37. [37]

    Nachtigal, Satish C

    Noël M. Nachtigal, Satish C. Reddy, and Lloyd N. Trefethen. How fast are nonsymmetric matrix iterations? SIAM Journal on Matrix Analysis and Applications , 13(3):778--795, July 1992. doi:10.1137/0613049

    work page doi:10.1137/0613049 1992

  38. [38]

    Problem Complexity and Method Efficiency in Optimization

    Arkadij Semenovi c Nemirovsky and David Borisovich Yudin. Problem Complexity and Method Efficiency in Optimization . Wiley-Interscience, 1983. ://www2.isye.gatech.edu/ nemirovs/Nemirovskii_Yudin_1983.pdf

    1983

  39. [39]

    Paige and Michael A

    Christopher C. Paige and Michael A. Saunders. LSQR : An algorithm for sparse linear equations and sparse least squares. ACM Transactions on Mathematical Software , 8(1):43--71, March 1982. doi:10.1145/355984.355989

    arXiv 1982

  40. [40]

    Richard Peng and Santosh S. Vempala. Solving sparse linear systems faster than matrix multiplication. Communications of the ACM , 67(7):79--86, July 2024. doi:10.1145/3615679

    work page doi:10.1145/3615679 2024

  41. [41]

    Theodore J. Rivlin. An Introduction to the Approximation of Functions . Dover Books on Advanced Mathematics. Dover, 1981

    1981

  42. [42]

    Rácz and Jacob Richey

    Miklós Z. Rácz and Jacob Richey. A smooth transition from Wishart to GOE . Journal of Theoretical Probability , 32(2):898--906, 2019. doi:10.1007/s10959-018-0808-2

    work page doi:10.1007/s10959-018-0808-2 2019

  43. [43]

    A fast randomized algorithm for overdetermined linear least-squares regression

    Vladimir Rokhlin and Mark Tygert. A fast randomized algorithm for overdetermined linear least-squares regression. Proceedings of the National Academy of Sciences , 105(36):13212--13217, September 2008. doi:10.1073/pnas.0804869105

    work page doi:10.1073/pnas.0804869105 2008

  44. [44]

    Tight query complexity lower bounds for PCA via finite sample deformed Wigner law

    Max Simchowitz, Ahmed El Alaoui, and Benjamin Recht. Tight query complexity lower bounds for PCA via finite sample deformed Wigner law. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing , pages 1249--1259, 2018. doi:10.1145/3188745.3188796

    arXiv 2018

  45. [45]

    Solve for x: Technical perspective

    Daniel Spielman. Solve for x: Technical perspective. Communications of the ACM , 67(7):78, July 2024. doi:10.1145/3643835

    work page doi:10.1145/3643835 2024

  46. [46]

    Youcef Saad and Martin H. Schultz. GMRES : A generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM Journal on Scientific and Statistical Computing , 7(3):856--869, July 1986. doi:10.1137/0907058

    doi:10.1137/0907058 1986

  47. [47]

    Spielman and Shang-Hua Teng

    Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis: An attempt to explain the behavior of algorithms in practice. Communications of the ACM , 52(10):76--84, 2009. doi:10.1145/1562764.1562785

    arXiv 2009

  48. [48]

    J. F. Traub, G. W. Wasilkowski, and H. Wo\' z niakowski. Information-Based Complexity . Academic Press Professional, Inc., 1988

    1988

  49. [49]

    Optimal query complexities for dynamic trace estimation

    David Woodruff, Fred Zhang, and Richard Zhang. Optimal query complexities for dynamic trace estimation. Advances in Neural Information Processing Systems , 35:35049--35060, 2022. ://dl.acm.org/doi/10.5555/3600270.3602810

    arXiv 2022

  50. [50]

    Divide and conquer kernel ridge regression

    Yuchen Zhang, John Duchi, and Martin Wainwright. Divide and conquer kernel ridge regression. In Conference on Learning Theory , pages 592--617. PMLR, 2013. ://proceedings.mlr.press/v30/Zhang13.html

    2013

  51. [51]

    write newline

    " write newline "" before.all 'output.state := FUNCTION fin.entry add.period write newline FUNCTION new.block output.state before.all = 'skip after.block 'output.state := if FUNCTION new.sentence output.state after.block = 'skip output.state before.all = 'skip after.sentence 'output.state := if if FUNCTION not #0 #1 if FUNCTION and 'skip pop #0 if FUNCTIO...