Cameron Musco

Mohammadreza Daneshvaramoli

Algorithmica, June, 2024

Efficient and Private Marginal Reconstruction with Local Non-Negativity.

[BibT_eX]

[DOI]

CoRR, 2024

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

[BibT_eX]

[DOI]

CoRR, 2024

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

[BibT_eX]

[DOI]

CoRR, 2024

Competitive Algorithms for Online Knapsack with Succinct Predictions.

[BibT_eX]

[DOI]

CoRR, 2024

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

[BibT_eX]

[DOI]

CoRR, 2024

Fixed-sparsity matrix approximation from matrix-vector products.

[BibT_eX]

[DOI]

CoRR, 2024

Sublinear Time Low-Rank Approximation of Toeplitz Matrices.

[BibT_eX]

[DOI]

Kshiteej Sheth

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

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

[BibT_eX]

[DOI]

Raphael A. Meyer

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

Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra.

[BibT_eX]

[DOI]

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

On the Role of Edge Dependency in Graph Generative Models.

[BibT_eX]

[DOI]

Proceedings of the Forty-first International Conference on Machine Learning, 2024

2023

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

[BibT_eX]

[DOI]

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

Latent Random Steps as Relaxations of Max-Cut, Min-Cut, and More.

[BibT_eX]

[DOI]

CoRR, 2023

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

[BibT_eX]

[DOI]

CoRR, 2023

Local Edge Dynamics and Opinion Polarization.

[BibT_eX]

[DOI]

Nikita Bhalla

Adam Lechowicz

Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, 2023

Near-Linear Sample Complexity for Lp Polynomial Regression.

[BibT_eX]

[DOI]

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

Toeplitz Low-Rank Approximation with Sublinear Query Complexity.

[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

No-regret Algorithms for Fair Resource Allocation.

[BibT_eX]

[DOI]

Abhishek Sinha

Ativ Joshi

Mohammad Hajiesmaili

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

Finite Population Regression Adjustment and Non-asymptotic Guarantees for Treatment Effect Estimation.

[BibT_eX]

[DOI]

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

Exact Representation of Sparse Networks with Symmetric Nonnegative Embeddings.

[BibT_eX]

[DOI]

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

Direct Embedding of Temporal Network Edges via Time-Decayed Line Graphs.

[BibT_eX]

[DOI]

Proceedings of the Eleventh International Conference on Learning Representations, 2023

Optimal Sketching Bounds for Sparse Linear Regression.

[BibT_eX]

[DOI]

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

Modeling Transitivity and Cyclicity in Directed Graphs via Binary Code Box Embeddings.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Kernel Interpolation with Sparse Grids.

[BibT_eX]

[DOI]

Mohit Yadav

Daniel R. Sheldon

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Simplified Graph Convolution with Heterophily.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Sample Constrained Treatment Effect Estimation.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Fast Regression for Structured Inputs.

[BibT_eX]

[DOI]

Proceedings of the Tenth International Conference on Learning Representations, 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

Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries.

[BibT_eX]

[DOI]

Raghavendra Addanki

Andrew McGregor

Proceedings of the 30th Annual European Symposium on Algorithms, 2022

A Basic Compositional Model for Spiking Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the A Journey from Process Algebra via Timed Automata to Model Learning, 2022

Sublinear Time Approximation of Text Similarity Matrices.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Sixth AAAI Conference on Artificial Intelligence, 2022

2021

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

[BibT_eX]

[DOI]

CoRR, 2021

An Interpretable Graph Generative Model with Heterophily.

[BibT_eX]

[DOI]

CoRR, 2021

Sublinear Time Eigenvalue Approximation via Random Sampling.

[BibT_eX]

[DOI]

Archan Ray

CoRR, 2021

Hutch++: Optimal Stochastic Trace Estimation.

[BibT_eX]

[DOI]

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

Coresets for Classification - Simplified and Strengthened.

[BibT_eX]

[DOI]

Tung Mai

Anup Rao

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

On the Power of Edge Independent Graph Models.

[BibT_eX]

[DOI]

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]

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

DeepWalking Backwards: From Embeddings Back to Graphs.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

Faster Kernel Matrix Algebra via Density Estimation.

[BibT_eX]

[DOI]

Proceedings of the 38th International Conference on Machine Learning, 2021

Subspace Embeddings under Nonlinear Transformations.

[BibT_eX]

[DOI]

Aarshvi Gajjar

Proceedings of the Algorithmic Learning Theory, 2021

Intervention Efficient Algorithms for Approximate Learning of Causal Graphs.

[BibT_eX]

[DOI]

Raghavendra Addanki

Andrew McGregor

Proceedings of the Algorithmic Learning Theory, 2021

Faster Kernel Interpolation for Gaussian Processes.

[BibT_eX]

[DOI]

Mohit Yadav

Daniel Sheldon

Proceedings of the 24th International Conference on Artificial Intelligence and Statistics, 2021

2020

Online Row Sampling.

[BibT_eX]

[DOI]

Michael B. Cohen

Jakub Pachocki

Theory Comput., 2020

Estimation of Shortest Path Covariance Matrices.

[BibT_eX]

[DOI]

Raj Kumar Maity

CoRR, 2020

Model-specific Data Subsampling with Influence Functions.

[BibT_eX]

[DOI]

CoRR, 2020

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

[BibT_eX]

[DOI]

CoRR, 2020

Spiking Neural Networks Through the Lens of Streaming Algorithms.

[BibT_eX]

[DOI]

Yael Hitron

Proceedings of the 34th International Symposium on Distributed Computing, 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

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

Node Embeddings and Exact Low-Rank Representations of Complex Networks.

[BibT_eX]

[DOI]

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

InfiniteWalk: Deep Network Embeddings as Laplacian Embeddings with a Nonlinearity.

[BibT_eX]

[DOI]

Shiva Prasad Kasiviswanathan

Proceedings of the KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2020

Random Sketching, Clustering, and Short-Term Memory in Spiking Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Efficient Intervention Design for Causal Discovery with Latents.

[BibT_eX]

[DOI]

Raghavendra Addanki

Andrew McGregor

Proceedings of the 37th International Conference on Machine Learning, 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

Importance Sampling via Local Sensitivity.

[BibT_eX]

[DOI]

Anant Raj

Lester Mackey

Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019

Winner-Take-All Computation in Spiking Neural Networks.

[BibT_eX]

[DOI]

CoRR, 2019

Low-Rank Approximation from Communication Complexity.

[BibT_eX]

[DOI]

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

Toward a Characterization of Loss Functions for Distribution Learning.

[BibT_eX]

[DOI]

Nika Haghtalab

Bo Waggoner

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Learning to Prune: Speeding up Repeated Computations.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

2018

The power of randomized algorithms: from numerical linear algebra to biological systems.

[BibT_eX]

[DOI]

PhD thesis, 2018

Learning Networks from Random Walk-Based Node Similarities.

[BibT_eX]

[DOI]

Jeremy G. Hoskins

CoRR, 2018

Minimizing Polarization and Disagreement in Social Networks.

[BibT_eX]

[DOI]

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

Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 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

Ant-inspired density estimation via random walks.

[BibT_eX]

[DOI]

Hsin-Hao Su

Proc. Natl. Acad. Sci. USA, 2017

Neuro-RAM Unit with Applications to Similarity Testing and Compression in Spiking Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Distributed Computing, 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

Is Input Sparsity Time Possible for Kernel Low-Rank Approximation?

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, 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

Computational Tradeoffs in Biological Neural Networks: Self-Stabilizing Winner-Take-All Networks.

[BibT_eX]

[DOI]

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 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

Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices.

[BibT_eX]

[DOI]

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Provably Useful Kernel Matrix Approximation in Linear Time.

[BibT_eX]

[DOI]

CoRR, 2016

Ant-Inspired Density Estimation via Random Walks: Extended Abstract.

[BibT_eX]

[DOI]

Hsin-Hao Su

Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Faster Eigenvector Computation via Shift-and-Invert Preconditioning.

[BibT_eX]

[DOI]

Proceedings of the 33nd International Conference on Machine Learning, 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

Robust Shift-and-Invert Preconditioning: Faster and More Sample Efficient Algorithms for Eigenvector Computation.

[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

Distributed House-Hunting in Ant Colonies.

[BibT_eX]

[DOI]

Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, 2015

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

[BibT_eX]

[DOI]