About

Raghu Meka is a Professor of Computer Science at UCLA Samueli School of Engineering. His research interests include complexity theory, learning theory, algorithms, and probability theory. He has been recognized with awards such as the FOCS Best Paper Award in 2023 and the NSF CAREER Award in 2016. Dr. Meka earned his PhD from the University of Texas at Austin in 2011. His work explores the elegance and applications of complexity and learning in computer science, and he has been featured in publications such as IEEE Computer Society and Quanta Magazine for his contributions to the field.

Research topics

• Computer Science
• Computer Security
• Mathematics
• Combinatorics
• Economics
• Pure mathematics
• Theoretical computer science
• Discrete mathematics
• Physics
• Computer network
• Arithmetic
• Microeconomics

Selected publications

• Sparsifying Sums of Positive Semidefinite Matrices

  Society for Industrial and Applied Mathematics eBooks · 2026-01-01

  book-chapterSenior author

  In this paper, we revisit spectral sparsification for sums of arbitrary positive semidefinite (PSD) matrices. Concretely, for any collection of PSD matrices \(\mathcal{A}=\{A_1,A_2,\ldots,A_r\}\subseteq \mathbb{R}^{n\times n}\), given any subset \(T\subseteq [r]\), our goal is to find sparse weights \(\mu_i\in\mathbb{R}_{\ge 0}\) such that \((1-\varepsilon)\sum_{i\in T} A_i \;\preceq\; \sum_{i\in T} \mu_i A_i \;\preceq\; (1+\varepsilon)\sum_{i\in T} A_i\). This generalizes spectral sparsification of graphs which corresponds to \(\mathcal{A}\) being the set of Laplacians of edges. It also captures sparsifying Cayley graphs by choosing a subset of generators. The former has been extensively studied with optimal sparsifiers known. The latter has received attention recently and was solved for a few special groups (e.g., \(\mathbb{F}_2^n\)). Prior work shows any sum of PSD matrices can be sparsified down to \(O(n)\) elements. This bound however turns out to be too coarse and in particular yields no non-trivial bound for building Cayley sparsifiers for Cayley graphs. In this work, we develop a new, instance-specific (i.e., specific to a given collection \(\mathcal{A}\)) theory of PSD matrix sparsification based on a new parameter \(N^*(\mathcal{A})\) which we call connectivity threshold that generalizes the threshold of the number of edges required to make a graph connected. Our main result gives a sparsifier that uses at most \(O(\varepsilon^{-2} N^*(\mathcal{A}) (\log n) (\log r))\) matrices and is constructible in randomized polynomial time. We also show that we need \(N^*(\mathcal{A})\) elements to sparsify for any \(\varepsilon \lt 0.99\). As the main application of our framework, we prove that any Cayley graph can be sparsified to \(O(\varepsilon^{-2}\log^4 N)\) generators. Previously, a non-trivial bound on Cayley sparsifiers was known only in the case when the group is \(\mathbb{F}_2^n\).

  PublisherDOI

• Tight Lower Bound for Multicolor Discrepancy

  Society for Industrial and Applied Mathematics eBooks · 2026-01-01

  book-chapterSenior author

  We prove the following asymptotically tight lower bound for \(k\)-color discrepancy: For any \(k \ge 2\), there exists a hypergraph with \(n\) hyperedges such that its \(k\)-color discrepancy is at least \(\Omega (\sqrt n)\). This improves on the previously known lower bound of \(\Omega (\sqrt {n/\log k})\) due to Caragiannis et al. (2025). As an application, we show that our result implies improved lower bounds for group fair division.

  PublisherDOI

• Moonflowers and efficient code sparsification

  ArXiv.org · 2026-05-09

  articleOpen access

  We introduce \emph{moonflowers}, a weaker analogue of sunflowers. A family of sets $S_1,\ldots,S_k$ is a $k$-moonflower if each set $S_i$ contains at least one element that is absent from all the others. We study the extremal problem of determining the largest possible size of a family of sets of size at most $w$ that avoids a $k$-moonflower, and obtain near-optimal bounds. As an application, we revisit the code sparsification problem studied by Brakensiek and Guruswami (STOC 2025) and improve the bounds to near optimal. Concretely, we improve the dependence on the block length from poly-logarithmic to logarithmic, and show that such a dependence is necessary.

  PublisherOA PDF

• Moonflowers and efficient code sparsification

  arXiv (Cornell University) · 2026-05-09

  preprintOpen access

  We introduce \emph{moonflowers}, a weaker analogue of sunflowers. A family of sets $S_1,\ldots,S_k$ is a $k$-moonflower if each set $S_i$ contains at least one element that is absent from all the others. We study the extremal problem of determining the largest possible size of a family of sets of size at most $w$ that avoids a $k$-moonflower, and obtain near-optimal bounds. As an application, we revisit the code sparsification problem studied by Brakensiek and Guruswami (STOC 2025) and improve the bounds to near optimal. Concretely, we improve the dependence on the block length from poly-logarithmic to logarithmic, and show that such a dependence is necessary.

  PublisherDOI

• Discrepancy Beyond Additive Functions with Applications to Fair Division (Extended Abstract)

  Leibniz-Zentrum für Informatik (Schloss Dagstuhl) · 2026-01-01

  articleOpen access

  We consider a setting where we have a ground set ℳ together with real-valued set functions f₁, … , f_n, and the goal is to partition ℳ into two sets S₁,S₂ such that |f_i(S₁) - f_i(S₂)| is small for every i. Many results in discrepancy theory can be stated in this form with the functions f_i being additive. In this work, we initiate the study of the unstructured case where f_i is not assumed to be additive. We show that even without the additivity assumption, the upper bound remains at most O(√{n log n}). Our result has implications on the fair allocation of indivisible goods. In particular, we show that a consensus halving up to O(√{n log n}) goods always exists for n agents with monotone utilities. Previously, only an O(n) bound was known for this setting.

  PublisherDOI

• Tight Lower Bound for Multicolor Discrepancy

  ArXiv.org · 2025-04-25

  preprintOpen accessSenior author

  We prove the following asymptotically tight lower bound for $k$-color discrepancy: For any $k \geq 2$, there exists a hypergraph with $n$ hyperedges such that its $k$-color discrepancy is at least $Ω(\sqrt{n})$. This improves on the previously known lower bound of $Ω(\sqrt{n/\log k})$ due to Caragiannis et al. (arXiv:2502.10516). As an application, we show that our result implies improved lower bounds for group fair division.

  PublisherOA PDFDOI

• Sparsifying Sums of Positive Semidefinite Matrices

  ArXiv.org · 2025-08-11

  preprintOpen accessSenior author

  In this paper, we revisit spectral sparsification for sums of arbitrary positive semidefinite (PSD) matrices. Concretely, for any collection of PSD matrices $\mathcal{A} = \{A_1, A_2, \ldots, A_r\} \subset \mathbb{R}^{n \times n}$, given any subset $T \subseteq [r]$, our goal is to find sparse weights $μ\in \mathbb{R}_{\geq 0}^r$ such that $(1 - ε) \sum_{i \in T} A_i \preceq \sum_{i \in T} μ_i A_i \preceq (1 + ε) \sum_{i \in T} A_i.$ This generalizes spectral sparsification of graphs which corresponds to $\mathcal{A}$ being the set of Laplacians of edges. It also captures sparsifying Cayley graphs by choosing a subset of generators. The former has been extensively studied with optimal sparsifiers known. The latter has received attention recently and was solved for a few special groups (e.g., $\mathbb{F}_2^n$). Prior work shows any sum of PSD matrices can be sparsified down to $O(n)$ elements. This bound however turns out to be too coarse and in particular yields no non-trivial bound for building Cayley sparsifiers for Cayley graphs. In this work, we develop a new, instance-specific (i.e., specific to a given collection $\mathcal{A}$) theory of PSD matrix sparsification based on a new parameter $N^*(\mathcal{A})$ which we call connectivity threshold that generalizes the threshold of the number of edges required to make a graph connected. Our main result gives a sparsifier that uses at most $O(ε^{-2}N^*(\mathcal{A}) (\log n)(\log r))$ matrices and is constructible in randomized polynomial time. We also show that we need $N^*(\mathcal{A})$ elements to sparsify for any $ε< 0.99$. As the main application of our framework, we prove that any Cayley graph can be sparsified to $O(ε^{-2}\log^4 N)$ generators. Previously, a non-trivial bound on Cayley sparsifiers was known only in the case when the group is $\mathbb{F}_2^n$.

  PublisherOA PDFDOI

• The communication complexity of distributed estimation

  ArXiv.org · 2025-11-26

  preprintOpen access

  We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions $p$ and $q$ over domains $X$ and $Y$, respectively. Their goal is to estimate \[ \mathbb{E}_{x \sim p,\, y \sim q}[f(x, y)] \] to within additive error $\varepsilon$ for a bounded function $f$, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the communication complexity of $f$ and the error parameter $\varepsilon$. The random sampling approach -- estimating the mean by averaging $f$ over $O(1/\varepsilon^2)$ random samples -- requires $O(R(f)/\varepsilon^2)$ total communication, where $R(f)$ is the randomized communication complexity of $f$. We design a new debiasing protocol which improves the dependence on $1/\varepsilon$ to be linear instead of quadratic. Additionally we show better upper bounds for several special classes of functions, including the Equality and Greater-than functions. We introduce lower bound techniques based on spectral methods and discrepancy, and show the optimality of many of our protocols: the debiasing protocol is tight for general functions, and that our protocols for the equality and greater-than functions are also optimal. Furthermore, we show that among full-rank Boolean functions, Equality is essentially the easiest.

  PublisherOA PDFDOI

• Sparse Linear Regression is Easy on Random Supports

  ArXiv.org · 2025-11-09

  preprintOpen access

  Sparse linear regression is one of the most basic questions in machine learning and statistics. Here, we are given as input a design matrix $X \in \mathbb{R}^{N \times d}$ and measurements or labels ${y} \in \mathbb{R}^N$ where ${y} = {X} {w}^* + ξ$, and $ξ$ is the noise in the measurements. Importantly, we have the additional constraint that the unknown signal vector ${w}^*$ is sparse: it has $k$ non-zero entries where $k$ is much smaller than the ambient dimension. Our goal is to output a prediction vector $\widehat{w}$ that has small prediction error: $\frac{1}{N}\cdot \|{X} {w}^* - {X} \widehat{w}\|^2_2$. Information-theoretically, we know what is best possible in terms of measurements: under most natural noise distributions, we can get prediction error at most $ε$ with roughly $N = O(k \log d/ε)$ samples. Computationally, this currently needs $d^{Ω(k)}$ run-time. Alternately, with $N = O(d)$, we can get polynomial-time. Thus, there is an exponential gap (in the dependence on $d$) between the two and we do not know if it is possible to get $d^{o(k)}$ run-time and $o(d)$ samples. We give the first generic positive result for worst-case design matrices ${X}$: For any ${X}$, we show that if the support of ${w}^*$ is chosen at random, we can get prediction error $ε$ with $N = \text{poly}(k, \log d, 1/ε)$ samples and run-time $\text{poly}(d,N)$. This run-time holds for any design matrix ${X}$ with condition number up to $2^{\text{poly}(d)}$. Previously, such results were known for worst-case ${w}^*$, but only for random design matrices from well-behaved families, matrices that have a very low condition number ($\text{poly}(\log d)$; e.g., as studied in compressed sensing), or those with special structural properties.

  PublisherOA PDFDOI

• Learning Neural Networks with Sparse Activations

  arXiv (Cornell University) · 2024-06-26

  preprintOpen accessSenior author

  A core component present in many successful neural network architectures, is an MLP block of two fully connected layers with a non-linear activation in between. An intriguing phenomenon observed empirically, including in transformer architectures, is that, after training, the activations in the hidden layer of this MLP block tend to be extremely sparse on any given input. Unlike traditional forms of sparsity, where there are neurons/weights which can be deleted from the network, this form of {\em dynamic} activation sparsity appears to be harder to exploit to get more efficient networks. Motivated by this we initiate a formal study of PAC learnability of MLP layers that exhibit activation sparsity. We present a variety of results showing that such classes of functions do lead to provable computational and statistical advantages over their non-sparse counterparts. Our hope is that a better theoretical understanding of {\em sparsely activated} networks would lead to methods that can exploit activation sparsity in practice.

  PublisherOA PDFDOI

Recent grants

• Collaborative Research: EnCORE: Institute for Emerging CORE Methods in Data Science

  NSF · $853k · 2022–2027

• CAREER: The power and limitations of randomness

  NSF · $500k · 2016–2022

• AF: Small: Challenges in Communication Complexity and Pseudorandomness

  NSF · $400k · 2020–2024

Frequent coauthors

• Parikshit Gopalan

  27 shared

• Adam R. Klivans

  26 shared

• Omer Reingold

  Stanford University

  24 shared

• Prasad Raghavendra

  20 shared

• Pravesh K. Kothari

  Carnegie Mellon University

  20 shared

• David Zuckerman

  The University of Texas at Austin

  18 shared

• Nikhil Bansal

  University of Michigan–Ann Arbor

  17 shared

• Shachar Lovett

  14 shared

Education

• Ph.D., Electrical Engineering

  University of California, Los Angeles

  2003

• M.S., Electrical Engineering

  University of California, Los Angeles

  1999

• B.S., Electrical Engineering

  University of California, Los Angeles

  1997

Awards & honors

• FOCS Best Paper Award, 2023
• NSF CAREER Award, 2016