John Peebles

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Singular value approximation and sparsifying random walks on directed graphs	2025-08-15	Paper
High-precision estimation of random walks in small space	2025-08-12	Paper
Solving directed Laplacian systems in nearly-linear time through sparse LU factorizations	2025-08-12	Paper
Determinant-preserving sparsification of SDDM matrices with applications to counting and sampling spanning trees	2025-08-06	Paper
Faster algorithms for computing the stationary distribution, simulating random walks, and more	2025-08-06	Paper
Optimal testing of discrete distributions with high probability Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing	2023-11-14	Paper
Sample-optimal identity testing with high probability (available as arXiv preprint)	2021-07-28	Paper
Determinant-preserving sparsification of SDDM matrices SIAM Journal on Computing	2020-08-25	Paper
Collision-based Testers are Optimal for Uniformity and Closeness Chicago Journal of Theoretical Computer Science	2019-09-12	Paper
Sublinear-time algorithms for counting star subgraphs via edge sampling Algorithmica	2018-04-06	Paper
Sublinear-time algorithms for counting star subgraphs via edge sampling Algorithmica	2018-04-06	Paper
Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing	2017-08-17	Paper
Sampling random spanning trees faster than matrix multiplication Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing	2017-08-17	Paper
Replacing mark bits with randomness in Fibonacci heaps Automata, Languages, and Programming	2015-10-27	Paper

Research outcomes over time

This page was built for person: John Peebles