15 citations · 51 across the 40 of their papers we have counts for
10 papers · 1 filter
Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks
Anders Aamand, Justin Y. Chen, Piotr Indyk +5
Recent work shows that the expressive power of Graph Neural Networks (GNNs) in distinguishing non-isomorphic graphs is exactly the same as that of the Weisfeiler-Lehman (WL) graph…
Sub-quadratic Algorithms for Kernel Matrices via Kernel Density Estimation
Ainesh Bakshi, Piotr Indyk, Praneeth Kacham +2
Kernel matrices, as well as weighted graphs represented by them, are ubiquitous objects in machine learning, statistics and other related fields. The main drawback of using kernel…
Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time
Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff +1
We study fundamental problems in linear algebra, such as finding a maximal linearly independent subset of rows or columns (a basis), solving linear regression, or computing a subsp…
Faster Linear Algebra for Distance Matrices
Piotr Indyk, Sandeep Silwal
The distance matrix of a dataset of points with respect to a distance function represents all pairwise distances between points in induced by . Due to their wide…
Learning-Augmented Algorithms for Online Linear and Semidefinite Programming
Elena Grigorescu, Young-San Lin, Sandeep Silwal +2
Semidefinite programming (SDP) is a unifying framework that generalizes both linear programming and quadratically-constrained quadratic programming, while also yielding efficient s…
Hardness and Algorithms for Robust and Sparse Optimization
Eric Price, Sandeep Silwal, Samson Zhou
We explore algorithms and limitations for sparse optimization problems such as sparse linear regression and robust linear regression. The goal of the sparse linear regression probl…