b'Cameron Musco'

research

∙ 08/12/2023

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

Algorithms for node clustering typically focus on finding homophilous st...

0 Sudhanshu Chanpuriya, et al. ∙

research

∙ 05/23/2023

Kernel Interpolation with Sparse Grids

Structured kernel interpolation (SKI) accelerates Gaussian process (GP) ...

0 Mohit Yadav, et al. ∙

research

∙ 05/10/2023

Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra

Given 𝐀∈ℝ^n × n with entries bounded in magnitude by 1, it is well-known...

0 Rajarshi Bhattacharjee, et al. ∙

research

∙ 05/04/2023

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

Krylov subspace methods are a ubiquitous tool for computing near-optimal...

0 Raphael A. Meyer, et al. ∙

research

∙ 04/05/2023

Optimal Sketching Bounds for Sparse Linear Regression

We study oblivious sketching for k-sparse linear regression under variou...

0 Tung Mai, et al. ∙

research

∙ 03/11/2023

No-regret Algorithms for Fair Resource Allocation

We consider a fair resource allocation problem in the no-regret setting ...

0 Abhishek Sinha, et al. ∙

research

∙ 03/06/2023

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

We study the Lanczos method for approximating the action of a symmetric ...

0 Noah Amsel, et al. ∙

research

∙ 01/14/2023

Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation

We present a new approach for computing compact sketches that can be use...

0 Aline Bessa, et al. ∙

research

∙ 11/21/2022

Toeplitz Low-Rank Approximation with Sublinear Query Complexity

We present a sublinear query algorithm for outputting a near-optimal low...

0 Michael Kapralov, et al. ∙

research

∙ 11/13/2022

Near-Linear Sample Complexity for L_p Polynomial Regression

We study L_p polynomial regression. Given query access to a function f:[...

0 Raphael A. Meyer, et al. ∙

research

∙ 10/12/2022

Sample Constrained Treatment Effect Estimation

Treatment effect estimation is a fundamental problem in causal inference...

0 Raghavendra Addanki, et al. ∙

research

∙ 09/30/2022

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

Temporal networks model a variety of important phenomena involving timed...

0 Sudhanshu Chanpuriya, et al. ∙

research

∙ 07/06/2022

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

We study the problem of estimating the number of edges in an n-vertex gr...

0 Raghavendra Addanki, et al. ∙

research

∙ 03/14/2022

Fast Regression for Structured Inputs

We study the ℓ_p regression problem, which requires finding 𝐱∈ℝ^d that m...

0 Raphael A. Meyer, et al. ∙

research

∙ 02/23/2022

Low-memory Krylov subspace methods for optimal rational matrix function approximation

We describe a Lanczos-based algorithm for approximating the product of a...

0 Tyler Chen, et al. ∙

research

∙ 02/08/2022

Simplified Graph Convolution with Heterophily

Graph convolutional networks (GCNs) (Kipf Welling, 2017) attempt to ...

0 Sudhanshu Chanpuriya, et al. ∙

research

∙ 12/17/2021

Sublinear Time Approximation of Text Similarity Matrices

We study algorithms for approximating pairwise similarity matrices that ...

8 Archan Ray, et al. ∙

research

∙ 11/28/2021

Local Edge Dynamics and Opinion Polarization

The proliferation of social media platforms, recommender systems, and th...

0 Nikita Bhalla, et al. ∙

research

∙ 11/09/2021

Active Sampling for Linear Regression Beyond the ℓ_2 Norm

We study active sampling algorithms for linear regression, which aim to ...

0 Cameron Musco, et al. ∙

research

∙ 11/04/2021

An Interpretable Graph Generative Model with Heterophily

Many models for graphs fall under the framework of edge-independent dot ...

0 Sudhanshu Chanpuriya, et al. ∙

research

∙ 10/29/2021

On the Power of Edge Independent Graph Models

Why do many modern neural-network-based graph generative models fail to ...

0 Sudhanshu Chanpuriya, et al. ∙

research

∙ 09/16/2021

Sublinear Time Eigenvalue Approximation via Random Sampling

We study the problem of approximating the eigenspectrum of a symmetric m...

0 Rajarshi Bhattacharjee, et al. ∙

research

∙ 06/17/2021

Error bounds for Lanczos-based matrix function approximation

We analyze the Lanczos method for matrix function approximation (Lanczos...

0 Tyler Chen, et al. ∙

research

∙ 06/08/2021

Coresets for Classification – Simplified and Strengthened

We give relative error coresets for training linear classifiers with a b...

0 Tung Mai, et al. ∙

research

∙ 02/17/2021

DeepWalking Backwards: From Embeddings Back to Graphs

Low-dimensional node embeddings play a key role in analyzing graph datas...

0 Sudhanshu Chanpuriya, et al. ∙

research

∙ 02/16/2021

Faster Kernel Matrix Algebra via Density Estimation

We study fast algorithms for computing fundamental properties of a posit...

25 Arturs Backurs, et al. ∙

research

∙ 01/28/2021

Faster Kernel Interpolation for Gaussian Processes

A key challenge in scaling Gaussian Process (GP) regression to massive d...

7 Mohit Yadav, et al. ∙

research

∙ 12/27/2020

Intervention Efficient Algorithms for Approximate Learning of Causal Graphs

We study the problem of learning the causal relationships between a set ...

0 Raghavendra Addanki, et al. ∙

research

∙ 11/19/2020

Estimation of Shortest Path Covariance Matrices

We study the sample complexity of estimating the covariance matrix Σ∈ℝ^d...

0 Raj Kumar Maity, et al. ∙

research

∙ 10/20/2020

Model-specific Data Subsampling with Influence Functions

Model selection requires repeatedly evaluating models on a given dataset...

0 Anant Raj, et al. ∙

research

∙ 10/19/2020

Hutch++: Optimal Stochastic Trace Estimation

We study the problem of estimating the trace of a matrix A that can only...

0 Raphael A. Meyer, et al. ∙

research

∙ 10/05/2020

Subspace Embeddings Under Nonlinear Transformations

We consider low-distortion embeddings for subspaces under entrywise nonl...

17 Aarshvi Gajjar, et al. ∙

research

∙ 10/03/2020

Spiking Neural Networks Through the Lens of Streaming Algorithms

We initiate the study of biological neural networks from the perspective...

0 Yael Hitron, et al. ∙

research

∙ 06/12/2020

Fourier Sparse Leverage Scores and Approximate Kernel Learning

We prove new explicit upper bounds on the leverage scores of Fourier spa...

0 Tamás Erdélyi, et al. ∙

research

∙ 06/10/2020

Node Embeddings and Exact Low-Rank Representations of Complex Networks

Low-dimensional embeddings, from classical spectral embeddings to modern...

0 Sudhanshu Chanpuriya, et al. ∙

research

∙ 05/29/2020

InfiniteWalk: Deep Network Embeddings as Laplacian Embeddings with a Nonlinearity

The skip-gram model for learning word embeddings (Mikolov et al. 2013) h...

0 Sudhanshu Chanpuriya, et al. ∙

research

∙ 05/24/2020

Efficient Intervention Design for Causal Discovery with Latents

We consider recovering a causal graph in presence of latent variables, w...

0 Raghavendra Addanki, et al. ∙

research

∙ 04/17/2020

Projection-Cost-Preserving Sketches: Proof Strategies and Constructions

In this note we illustrate how common matrix approximation methods, such...

0 Cameron Musco, et al. ∙

research

∙ 11/19/2019

Low-Rank Toeplitz Matrix Estimation via Random Ultra-Sparse Rulers

We study how to estimate a nearly low-rank Toeplitz covariance matrix T ...

0 Hannah Lawrence, et al. ∙

research

∙ 11/04/2019

Importance Sampling via Local Sensitivity

Given a loss function F:X→R^+ that can be written as the sum of losses o...

0 Anant Raj, et al. ∙

research

∙ 06/06/2019

Toward a Characterization of Loss Functions for Distribution Learning

In this work we study loss functions for learning and evaluating probabi...

0 Nika Haghtalab, et al. ∙

research

∙ 05/14/2019

Sample Efficient Toeplitz Covariance Estimation

We study the query complexity of estimating the covariance matrix T of a...

0 Yonina C. Eldar, et al. ∙

research

∙ 04/26/2019

Learning to Prune: Speeding up Repeated Computations

It is common to encounter situations where one must solve a sequence of ...

12 Daniel Alabi, et al. ∙

research

∙ 04/25/2019

Winner-Take-All Computation in Spiking Neural Networks

In this work we study biological neural networks from an algorithmic per...

0 Nancy Lynch, et al. ∙

research

∙ 04/22/2019

Low-Rank Approximation from Communication Complexity

In low-rank approximation with missing entries, given A∈R^n× n and binar...

0 Cameron Musco, et al. ∙

research

∙ 03/28/2019

Faster Spectral Sparsification in Dynamic Streams

Graph sketching has emerged as a powerful technique for processing massi...

0 Michael Kapralov, et al. ∙

research

∙ 12/20/2018

A Universal Sampling Method for Reconstructing Signals with Simple Fourier Transforms

Reconstructing continuous signals from a small number of discrete sample...

0 Haim Avron, et al. ∙

research

∙ 08/12/2018

A Basic Compositional Model for Spiking Neural Networks

This paper is part of a project on developing an algorithmic theory of b...

0 Nancy Lynch, et al. ∙

research

∙ 04/26/2018

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

Random Fourier features is one of the most popular techniques for scalin...

0 Haim Avron, et al. ∙

research

∙ 04/23/2018

Eigenvector Computation and Community Detection in Asynchronous Gossip Models

We give a simple distributed algorithm for computing adjacency matrix ei...

0 Frederik Mallmann-Trenn, et al. ∙

Cameron Musco

Featured Co-authors