Raphael Arkady Meyer

I am a Postdoc at UC Berkeley, hosted by Michael Mahoney in the Stats Department and ICSI. Before that, I was a Postdoc at Caltech working with Joel Tropp. Before that, I finished my Ph.D. at NYU advised by Christopher Musco.

I research problems in mathematical computing from the perspective of theoretical computer science.

In the summer of 2022, I visited Michael Kapralov's group at EPFL and Haim Avron's group at TAU.

Links: Google Scholar, dblp, Github

My recent publications have looked at:

Fast Numerical Linear Algebra (preprint, COLT2026, SODA2026)
Tensor-based Sketching Methods (preprint, SIMAX, ICML2025)
Robust Active Learning for Regression Problems (SOSA26, SODA2023)

Of course, I am interested in problems beyond these areas, and if you want to work with me on a problem, send me an email: $ram900@berkeley.edu$

News

I'm giving at talk at the ETH Mittagsseminar, covering some recent work on sketching methods (link1, link2). You can find the abstract here. My co-author Chris Camaño will be talking about related joint work later that afternoon! Thanks to everyone who helped organize this!
New paper on arXiv: Linear algebra at exponential scale via tensor network dimension reduction! Tensor-structured sketching with nice theoretical guarantees! Pretty pictures!
I gave at talk at the RandNLA workshop at EPFL about recent and upcomming work on matrix-vector complexity. Thanks to the organizers for inviting me!

\phantom{.}

June 2026:

Technical note on arXiv: A non-asymptotic bound on the TV distance between a Wishart matrix and an appropriately scaled GOE matrix. This proves a non-asymptotic version of a result of Bubeck, Ding, Eldan, and Rácz, as needed for the Ax=b paper.

May 2026:

I went to ILAS to give a talk about my work on the matrix-vector complexity of solving $Ax=b$ (link) at the minisymposium Polynomials, Krylov Methods and Applications. Thanks to Cade, Ethan, and Alex for inviting me!

I went to the Inaugural Midwest Randomized Linear Algebra Workshop, and will be facilitating some of the breakout room discussions there. Thanks to Vivak and Daniel for organizing!

Paper accepted to COLT: The matrix-vector complexity of $Ax=b$ !

March 2026:

I gave a talk at the Joint Math/CS Seminar at UC Davis. Slides are here. Thanks to Jasper and Greg for organizing!

Feburary 2026:

New paper on arXiv, and accepted to AISTATS: Quantifying Epistemic Uncertainty in Diffusion Models!
In Fall 2025, the Simons Institue worked on a list of open problems, which I helped work on and is now released for the public! Read the list of problems here. Check it out – I helped write about sketching!
New paper on arXiv: The matrix-vector complexity of $Ax=b$ !

October 2025:

Hutchinson’s Estimator is Bad at Kronecker-Trace-Estimation was accepted to SIMAX!
I wrote a short article on trace estimation lower bounds. Read it here!
I'll be giving a talk on Low-Rank Approximation at the WSU Graduate Research Seminar. Thanks to Akash Rao for inviting me out!
Debiasing Polynomial and Fourier Regression was accepted to SOSA 2026! I presented a poster about it at the Simons Workshop on Linear Systems and Eigenvalue Problems.
Does block size matter in randomized block Krylov low-rank approximation? was accepted to SODA 2026!

September 2025:

I gave a talk about Kronecker Matrix-Vector complexity at the Simon's Institute Recent Progress and Open Directions in Matrix Computations seminar.
I joined Michael Mahoney's group as a postdoc at UC Berkeley (officially in the Statistics department and at ICSI).

August 2025

New paper on arXiv: Faster Linear Algebra Algorithms with Structured Random Matrices. Introducing the oblivious subspace injection!
New paper on arXiv: Does block size matter in randomized block Krylov low-rank approximation?. Punchline: Block Krylov finds a rank- $k$ approximation with $O(k)$ matrix-vector products, regardless of the block size!
New paper on arXiv: Debiasing Polynomial and Fourier Regression. Chris Camaño wrote beautiful code for it, available on github! Punchline: you can do DPP sampling for polynomial regression by computing the eigenvalues of random complex matrices!

July 2025

I presented a poster for my paper accepted to ICML: Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra.

June 2025

I gave a talk on Kronecker Matrix-Vector Complexity at Tom Trogdon's RMT + NLA II workshop this past June!

April 2025

I gave a talk at the UCSD MINDS Seminar on April 18th – thanks to Rob Webber for inviting me out!

March 2025

I recently gave a guest lecture in Laura Balzano's Randomized Numerical Linear Algebra class at UMich! It was great fun, and many great questions were asked. Thanks for having me! You can find my slides here.
I made a website to contain the cleanest known proofs for foundational concepts in RandNLA: link. I actually made it a while ago and don't update it often.
New preprint on arXiv: Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra. Punchline: there's too much orthogonality!
I'm talking about low-rank approximation (this paper and this paper) at Caltech on Friday Feb 14th. Come on out!

January 2025

Updated version of the Kronecker Trace Estimation paper (link). New strengthened results on random rank-one matrices, Rademacher test vectors, and random unit vector test vectors!

October 2024

I'm at SIAM MDS giving a talk on recent and upcoming results on Kronecker Matrix-Vector Complexity. Come say hi! Thanks to Ethan and Rob for organizing the minisymposium!
Paper accepted at SIMAX: Algorithm-Agnostic Low-Rank Approximation of Operator Monotone Matrix Functions. My first paper in a math journal!

May 2024

I'll be joining Caltech as a postdoc in Joel Tropp's group this fall!
I've been awarded the Pearl Brownstein Doctoral Research Award (i.e. best dissertation award) for my research! Big thanks to the Tandon CSE department for awarding this to me, and congrats to the other awardees, Aecios and Mengwei!
I gave a talk at the Center for Communications Research on Trace Estimation and Kronecker-Trace Estimation.

April 2024

I just successfully defended my thesis, on April 16th 2024! See details about my talk here: link.

March 2024

The Responsible AI Lab at NYU Tandon (who I have been a part of for the past two years) wrote a spotlight on me! Thanks to Caterina and the R/AI team for writing this up. See the short interview here: link.

January 2024

I presented my work on Trace Estimation and $f(A)$ Low-Rank Approximation at the Mahoney Group at UC Berkeley.
I presented my work on Krylov methods at SODA 2024.

November 2023

New preprint on arXiv: Algorithm-Agnostic Low-Rank Approximation of Operator Monotone Matrix Functions.
I gave a talk on Krylov methods at the Conference on Fast Direct Solvers at Purdue University in November.
I gave a talk at UChicago on Trace Estimation and Kronecker-Trace Estimation on November 1st.

October 2023

Paper accepted at SODA 2024: On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation!
I organized a minisymposium on The Matrix-Vector Complexity of Linear Algebra at the first ever SIAM-NNP conference!

Shyam Narayanan, Diana Halikias, William Swartworth, Tyler Chen, and myself were presenting at 8:30am on Sunday. What a stacked lineup! See the details here: link.

September 2023

New preprint on arXiv: Hutchinson’s Estimator is Bad at Kronecker-Trace-Estimation.

May 2023

New preprint on arXiv: On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation.

March 2023

I gave two talks at the NYU / UMass Quantum Linear Algebra reading group.
I gave a talk at the BIRS Perspectives on Matrix Computations about my new work on Krylov methods.

January 2023

I presented Near-Linear Sample Complexity for $L_p$ Polynomial Regression at SODA 2023.

November 2022

I gave a talk at the TCS Seminar at Purdue in early November to present my new research on the role of block size in Krylov Methods.

October 2022

New paper accepted at SODA 2023: Near-Linear Sample Complexity for $L_p$ Polynomial Regression! I just gave a talk on it last week Friday at the Grad Student Seminar at CDS (at NYU).

September 2022

I gave a talk at GAMM ANLA on the role of block size in Krylov Methods for low-rank approximation. A preprint will be available very soon, but until then you can check out my slides for a preview! Slides

July 2022

I gave a talk at the SIAM Annual Meeting Minisymposium on Matrix Functions, Operator Functions, and Related Approximation Methods. Thanks to Heather, Andrew, and Ke for organizing!

June 2022

I'm going be presenting Hutch++ this summer at HALG2022, with both a short talk and a poster.
I'm traveling this summer! I'm first in London for HALG2022. Then I'm spending June visiting Haim Avron at TAU, and July visiting Michael Kapralov at EPFL. If you're in the same place at the same time, drop me a line!

May 2022

I recently organized a mini-conference for NYU CS Theory researchers to present their "Pandemic Papers" in-person. Thanks to everyone who showed up and made it a success! More details here
I'm honored to be awarded the Deborah Rosenthal, MD Award for Best Quals Examination in 2022, for my presentation Towards Optimal Spectral Sum Estimation in the Matrix-Vector Oracle Model.

April 2022

I'm honored to be a ICLR 2022 Highlighted Reviewer.

Publications

Linear algebra at exponential scale via tensor network dimension reduction
in submission with Chris Camaño, Ethan N. Epperly, and Joel A. Tropp
A non-asymptotic bound on the TV distance between a Wishart matrix and an appropriately scaled GOE matrix
unpublished technical note
The matrix-vector complexity of $Ax=b$ ^[1]
at COLT 2026 with Michał Dereziński and Ethan N. Epperly
Faster Linear Algebra Algorithms with Structured Random Matrices^[2]
in submission with Chris Camaño, Ethan N. Epperly, and Joel A. Tropp
Quantifying Epistemic Uncertainty in Diffusion Models
at AISTATS 2026 with Aditi Gupta, Yotam Yaniv, Elynn Chen, and N. Benjamin Erichson
Does block size matter in randomized block Krylov low-rank approximation?^[3]
at SODA 2026 with Tyler Chen, Ethan N. Epperly, Christopher Musco, and Akash Rao
Debiasing Polynomial and Fourier Regression^[4]
at SOSA 2026 with Chris Camaño and Kevin Shu
Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra^[5]
at ICML 2025 with William Swartworth and David P. Woodruff
Hutchinson's Estimator is Bad at Kronecker-Trace-Estimation^[6]
in SIMAX with Haim Avron
Algorithm-Agnostic Low-Rank Approximation of Operator Monotone Matrix Functions
in SIMAX with David Persson and Christopher Musco
On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation^[7]
at SODA 2024 with Cameron Musco and Christopher Musco
Near-Linear Sample Complexity for $L_p$ Polynomial Regression^[8]
at SODA 2023 with Cameron Musco, Christopher Musco, David P. Woodruff, and Samson Zhou
Fast Regression for Structured Inputs^[9]
at ICLR 2022 with Cameron Musco, Christopher Musco, David P. Woodruff, and Samson Zhou
Hutch++: Optimal Stochastic Trace Estimation^[10]
at SOSA 2021 with Cameron Musco, Christopher Musco, and David P. Woodruff
The Statistical Cost of Robust Kernel Hyperparameter Tuning^[11]
at NeurIPS 2020 with Christopher Musco
Optimality Implies Kernel Sum Classifiers are Statistically Efficient^[12]
at ICML 2019 with Jean Honorio
Characterizing Optimal Security and Round-Complexity for Secure OR Evaluation
at ISIT 2017 with Amisha Jhanji and Hemanta K. Maji

\phantom{.}

[1]

Slides

[2]	Talk by Joel $\cdot$ Code available on github

[3]	Slides $\cdot$ Talk by Ethan

[4]	Poster $\cdot$ Code available on github

[5]

Poster

[6]

Slides

[7]	Code available on github $\cdot$ Slides using TCS language $\cdot$ Slides using Applied Math language

[8]

Slides

[9]

Poster

[10]	Code available on github $\cdot$ Landscape Poster $\cdot$ Portrait Poster $\cdot$ 4min Slides $\cdot$ 12min Slides $\cdot$ 25min Slides $\cdot$ 35min Slides $\cdot$ 1hr Slides

[11]

Slides

[12]	Poster $\cdot$ Slides.

Talks & Presentations

To date, I have presented every paper I published at the associated conference. This is a list of other talks or presentations I have given.

The matrix-vector complexity of $Ax=b$
at Randomized Linear Algebra, a workshop at the EPFL Bernoulli Center for Fundamental Studies
The matrix-vector complexity of $Ax=b$
at Polynomials, Krylov Methods and Applications, a minisymposium at Conference of the International Linear Algebra Society (ILAS 2026)
Overwhelming Orthogonality and the Mysteries of Tensor-Structured Sketching

at UC Davis Joint Math/CS Seminar.^[13]
Randomized Methods for Low-Rank Approximation
at WSU Graduate Research Seminar.
Kronecker Matrix-Vector Complexity is Strange
at Simons Institute Recent Progress and Open Directions in Matrix Computations Seminar.
Guest Lecture on Trace Estimation^[14]
at Laura Balzano's Randomized NLA course at the University of Michigan.
On the Unreasonable Effectiveness of Single Vector Krylov for Low-Rank Approximation
at Caltech SIAM Student/Postoc Seminar.
Kronecker Matrix-Vector Complexity is Strange^[15]
at Randomized Matrix Computations for Large-scale Scientific and Machine Learning Problems, a minisymposium at SIAM Conference on Mathematics of Data Science (MDS24)
Optimal Trace Estimation and Sub-Optimal Kronecker-Trace Estimation
at Center for Communications Research.
Optimal Trace Estimation and Algorithm-Agnostic funNystrom Guarantees
at UC Berkeley Mahoney Group Meeting.
Optimal Trace Estimation and Sub-Optimal Kronecker-Trace Estimation
at U Chicago Theory Lunch.
On the Unreasonable Effectiveness of Single Vector Krylov for Low-Rank Approximation
at BIRS workshop on Perspectives on Matrix Computations.
On the Unreasonable Effectiveness of Single Vector Krylov for Low-Rank Approximation
at Purdue University TCS Seminar
Near-Linear Sample Complexity for $L_p$ Polynomial Regression
at NYU CDS Student Seminar
Hutch++ and More: Towards Optimal Spectral Sum Estimation
at Matrix Functions, Operator Functions, and Related Approximation Methods, a minisymposium at SIAM Annual Meeting (AN22)
Hutch++: Optimal Stochastic Trace Estimation
at John Hopkins University Theory Seminar
Lessons from Trace Estimation Lower Bounds: Testing, Communication, and Anti-Concentration^[16]
at Computational Lower Bounds in Numerical Linear Algebra, a minisymposium at SIAM Annual Meeting (AN21)

[13]	Slides available here

[14]	Slides available here

[15]	Slides available here

[16]	Slides available here. Video starts at 1:04:55 here.

Kronecker Matrix-Vector Complexity is Strange
Short Talk at the RMN + NLA II Conference
On the Unreasonable Effectiveness of Single Vector Krylov for Low-Rank Approximation^[17]
Short Talk at Conference on Fast Direct Solvers
Hutchinson's Estimator is Bad at Kronecker-Trace-Estimation^[17]
Short Talk at SIAM-NNP 2022
On the Unreasonable Effectiveness of Single Vector Krylov for Low-Rank Approximation^[17]
Short Talk at GAMM ANLA 2022.
Hutch++: Optimal Stochastic Trace Estimation^[17]
Poster and Short Talk at HALG 2022.
Chebyshev Sampling is Optimal for Lp Polynomial Regression^[17]
Talk at NYU "Pandemic Presentations" 2022
Hutch++: Optimal Stochastic Trace Estimation^[17]
Poster at Wald(O) 2021.
Optimality Implies Kernel Sum Classifiers are Statistically Efficient^[17]
Poster at Midwest Theory Day 2019

[17]	Assets available in the Publications section.

This list is no longer updated. The existing slides are useful though, so I'm keeping this around.

Feature Importance Impossibility Theorems^[18]
45-min-long talk at NYU RAI Reading Group
Fairwashing SHAP (aka Interventional and Observational Shapley Values)^[19]
45-min-long talk at NYU RAI Reading Group
The Equivalence of Matrix-Vector Complexity in Quantum Computing, Part 2
1-hour-long talk at NYU/UMass Quantum Linear Algebra Reading Group
The Equivalence of Matrix-Vector Complexity in Quantum Computing, Part 1
1-hour-long talk at NYU/UMass Quantum Linear Algebra Reading Group
Hutch++: Optimal Stochastic Trace Estimation
1-hour-long talk at NYU VIDA RG Reading Group
Introduction to Leverage Scores
1.5-hour-long talk at NYU Tandon Theory Reading Group
Strategies for Episodic Tabular & Linear MDPs
Two 1.5-hour-long talks at NYU Tandon Reinforcement Learning Reading Group
Lagrangian Duality
Three 1.5-hour-long talks at NYU Tandon Theory Reading Group
Introduction to Differential Entropy
1-hour-long talk at NYU CDS Reading Group on Information Theory
Lower bounds on the complexity of stochastic convex optimization^[20]
1-hour-long presentation of the paper Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization by Agarwal et. al.