Christopher Musco

R. Teal Witter

CoRR, 2024

Benchmarking Estimators for Natural Experiments: A Novel Dataset and a Doubly Robust Algorithm.

[BibT_eX]

[DOI]

R. Teal Witter

CoRR, 2024

Sharper Bounds for Chebyshev Moment Matching with Applications to Differential Privacy and Beyond.

[BibT_eX]

[DOI]

CoRR, 2024

Coupling without Communication and Drafter-Invariant Speculative Decoding.

[BibT_eX]

[DOI]

Majid Daliri

Ananda Theertha Suresh

CoRR, 2024

Near-optimal hierarchical matrix approximation from matrix-vector products.

[BibT_eX]

[DOI]

CoRR, 2024

Faster Spectral Density Estimation and Sparsification in the Nuclear Norm.

[BibT_eX]

[DOI]

CoRR, 2024

Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits.

[BibT_eX]

[DOI]

CoRR, 2024

Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning.

[BibT_eX]

[DOI]

Michal Derezinski

Jiaming Yang

CoRR, 2024

Fixed-sparsity matrix approximation from matrix-vector products.

[BibT_eX]

[DOI]

CoRR, 2024

Simple Analysis of Priority Sampling.

[BibT_eX]

[DOI]

Proceedings of the 2024 Symposium on Simplicity in Algorithms, 2024

On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation.

[BibT_eX]

[DOI]

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Improved Active Learning via Dependent Leverage Score Sampling.

[BibT_eX]

[DOI]

Proceedings of the Twelfth International Conference on Learning Representations, 2024

Faster Spectral Density Estimation and Sparsification in the Nuclear Norm (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Agnostic Active Learning of Single Index Models with Linear Sample Complexity.

[BibT_eX]

[DOI]

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

A Simple and Practical Method for Reducing the Disparate Impact of Differential Privacy.

[BibT_eX]

[DOI]

Lucas Rosenblatt

Julia Stoyanovich

Proceedings of the Thirty-Eighth AAAI Conference on Artificial Intelligence, 2024

2023

Low-Memory Krylov Subspace Methods for Optimal Rational Matrix Function Approximation.

[BibT_eX]

[DOI]

SIAM J. Matrix Anal. Appl., June, 2023

Algorithm-agnostic low-rank approximation of operator monotone matrix functions.

[BibT_eX]

[DOI]

David Persson

CoRR, 2023

Near-Optimality Guarantees for Approximating Rational Matrix Functions by the Lanczos Method.

[BibT_eX]

[DOI]

CoRR, 2023

A Tight Analysis of Hutchinson's Diagonal Estimator.

[BibT_eX]

[DOI]

Prathamesh Dharangutte

Proceedings of the 2023 Symposium on Simplicity in Algorithms, 2023

Near-Linear Sample Complexity for Lp Polynomial Regression.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation.

[BibT_eX]

[DOI]

Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2023

Structured Semidefinite Programming for Recovering Structured Preconditioners.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

Dimensionality Reduction for General KDE Mode Finding.

[BibT_eX]

[DOI]

Xinyu Luo

Cas Widdershoven

Proceedings of the International Conference on Machine Learning, 2023

Efficient Block Approximate Matrix Multiplication.

[BibT_eX]

[DOI]

Chuhan Yang

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

Moments, Random Walks, and Limits for Spectrum Approximation.

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

Active Learning for Single Neuron Models with Lipschitz Non-Linearities.

[BibT_eX]

[DOI]

Aarshvi Gajjar

Chinmay Hegde

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2023

2022

Error Bounds for Lanczos-Based Matrix Function Approximation.

[BibT_eX]

[DOI]

SIAM J. Matrix Anal. Appl., 2022

Near-Linear Sample Complexity for Lp Polynomial Regression.

[BibT_eX]

[DOI]

CoRR, 2022

Streaming Approach to In Situ Selection of Key Time Steps for Time-Varying Volume Data.

[BibT_eX]

[DOI]

Mengxi Wu

Yi-Jen Chiang

Comput. Graph. Forum, 2022

Sublinear time spectral density estimation.

[BibT_eX]

[DOI]

Vladimir Braverman

Aditya Krishnan

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Fast Regression for Structured Inputs.

[BibT_eX]

[DOI]

Proceedings of the Tenth International Conference on Learning Representations, 2022

A Sketch-based Index for Correlated Dataset Search.

[BibT_eX]

[DOI]

Proceedings of the 38th IEEE International Conference on Data Engineering, 2022

Active Linear Regression for ℓp Norms and Beyond.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Active Sampling for Linear Regression Beyond the $\ell_2$ Norm.

[BibT_eX]

[DOI]

CoRR, 2021

How to Quantify Polarization in Models of Opinion Dynamics.

[BibT_eX]

[DOI]

CoRR, 2021

Linear and Sublinear Time Spectral Density Estimation.

[BibT_eX]

[DOI]

Vladimir Braverman

Aditya Krishnan

CoRR, 2021

Hutch++: Optimal Stochastic Trace Estimation.

[BibT_eX]

[DOI]

Proceedings of the 4th Symposium on Simplicity in Algorithms, 2021

Public Transport Planning: When Transit Network Connectivity Meets Commuting Demand.

[BibT_eX]

[DOI]

Proceedings of the SIGMOD '21: International Conference on Management of Data, 2021

Correlation Sketches for Approximate Join-Correlation Queries.

[BibT_eX]

[DOI]

Proceedings of the SIGMOD '21: International Conference on Management of Data, 2021

Dynamic Trace Estimation.

[BibT_eX]

[DOI]

Prathamesh Dharangutte

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation.

[BibT_eX]

[DOI]

David P. Woodruff

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

Finding an Approximate Mode of a Kernel Density Estimate.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

Graph Learning for Inverse Landscape Genetics.

[BibT_eX]

[DOI]

Prathamesh Dharangutte

Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020

The Statistical Cost of Robust Kernel Hyperparameter Tuning.

[BibT_eX]

[DOI]

CoRR, 2020

Projection-Cost-Preserving Sketches: Proof Strategies and Constructions.

[BibT_eX]

[DOI]

CoRR, 2020

Analyzing the Impact of Filter Bubbles on Social Network Polarization.

[BibT_eX]

[DOI]

Uthsav Chitra

Proceedings of the WSDM '20: The Thirteenth ACM International Conference on Web Search and Data Mining, 2020

Fast and Space Efficient Spectral Sparsification in Dynamic Streams.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Sample Efficient Toeplitz Covariance Estimation.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

The Statistical Cost of Robust Kernel Hyperparameter Turning.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Fourier Sparse Leverage Scores and Approximate Kernel Learning.

[BibT_eX]

[DOI]

Tamás Erdélyi

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Low-Rank Toeplitz Matrix Estimation Via Random Ultra-Sparse Rulers.

[BibT_eX]

[DOI]

Proceedings of the 2020 IEEE International Conference on Acoustics, 2020

Near Optimal Linear Algebra in the Online and Sliding Window Models.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Finding the Mode of a Kernel Density Estimate.

[BibT_eX]

[DOI]

CoRR, 2019

Understanding Filter Bubbles and Polarization in Social Networks.

[BibT_eX]

[DOI]

Uthsav Chitra

CoRR, 2019

Low-Rank Approximation from Communication Complexity.

[BibT_eX]

[DOI]

David P. Woodruff

CoRR, 2019

Faster Spectral Sparsification in Dynamic Streams.

[BibT_eX]

[DOI]

CoRR, 2019

A universal sampling method for reconstructing signals with simple Fourier transforms.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018

Faster linear algebra for data analysis and machine learning.

[BibT_eX]

[DOI]

PhD thesis, 2018

Learning Networks from Random Walk-Based Node Similarities.

[BibT_eX]

[DOI]

Jeremy G. Hoskins

Charalampos E. Tsourakakis

CoRR, 2018

Minimizing Polarization and Disagreement in Social Networks.

[BibT_eX]

[DOI]

Charalampos E. Tsourakakis

Proceedings of the 2018 World Wide Web Conference on World Wide Web, 2018

Stability of the Lanczos Method for Matrix Function Approximation.

[BibT_eX]

[DOI]

Aaron Sidford

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Inferring Networks From Random Walk-Based Node Similarities.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

Eigenvector Computation and Community Detection in Asynchronous Gossip Models.

[BibT_eX]

[DOI]

Frederik Mallmann-Trenn

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

Single Pass Spectral Sparsification in Dynamic Streams.

[BibT_eX]

[DOI]

SIAM J. Comput., 2017

Input Sparsity Time Low-rank Approximation via Ridge Leverage Score Sampling.

[BibT_eX]

[DOI]

Michael B. Cohen

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

Recursive Sampling for the Nystrom Method.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 2017

Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees.

[BibT_eX]

[DOI]

Proceedings of the 34th International Conference on Machine Learning, 2017

Determining Tournament Payout Structures for Daily Fantasy Sports.

[BibT_eX]

[DOI]

Maxim Sviridenko

Justin Thaler

Proceedings of the Ninteenth Workshop on Algorithm Engineering and Experiments, 2017

2016

Provably Useful Kernel Matrix Approximation in Linear Time.

[BibT_eX]

[DOI]

CoRR, 2016

Principal Component Projection Without Principal Component Analysis.

[BibT_eX]

[DOI]

Proceedings of the 33nd International Conference on Machine Learning, 2016

2015

Stronger Approximate Singular Value Decomposition via the Block Lanczos and Power Methods.

[BibT_eX]

[DOI]

CoRR, 2015

Ridge Leverage Scores for Low-Rank Approximation.

[BibT_eX]

[DOI]

Michael B. Cohen

CoRR, 2015

Dimensionality Reduction for k-Means Clustering and Low Rank Approximation.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, 2015

Principled Sampling for Anomaly Detection.

[BibT_eX]

[DOI]

Brendan Juba