73 citations · 347 across the 51 of their papers we have counts for
8 papers · 1 filter
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
Amir Abboud, Nick Fischer, Zander Kelley +2
We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With the invention of algebraic fast matrix multiplication over 50 years ago, it also became known that BMM…
Simple Mechanisms for Representing, Indexing and Manipulating Concepts
Yuanzhi Li, Raghu Meka, Rina Panigrahy +1
Supervised and unsupervised learning using deep neural networks typically aims to exploit the underlying structure in the training data; this structure is often explained using a l…
User-Level Differential Privacy With Few Examples Per User
Badih Ghazi, Pritish Kamath, Ravi Kumar +3
Previous work on user-level differential privacy (DP) [Ghazi et al. NeurIPS 2021, Bun et al. STOC 2023] obtained generic algorithms that work for various learning tasks. However, t…
Explicit separations between randomized and deterministic Number-on-Forehead communication
Zander Kelley, Shachar Lovett, Raghu Meka
We study the power of randomness in the Number-on-Forehead (NOF) model in communication complexity. We construct an explicit 3-player function , such that: (i)…
Feature Adaptation for Sparse Linear Regression
Jonathan Kelner, Frederic Koehler, Raghu Meka +1
Sparse linear regression is a central problem in high-dimensional statistics. We study the correlated random design setting, where the covariates are drawn from a multivariate Gaus…
On User-Level Private Convex Optimization
Badih Ghazi, Pritish Kamath, Ravi Kumar +3
We introduce a new mechanism for stochastic convex optimization (SCO) with user-level differential privacy guarantees. The convergence rates of this mechanism are similar to those…