---
title: Research
---
# Raghu Meka

| [HOME](http://www.raghumeka.org) | [RESEARCH](https://raghumeka.github.io/research.html) | [TEACHING](https://raghumeka.github.io/courses.html) |
| -------- | -------- | -------- |
---

My main interests are in complexity theory, learning theory, algorithm design. More generally, I like probability and combinatorics related things. The best resource for up to date publications really is to look up my [**profile on Google scholar**](https://scholar.google.com/citations?hl=en&user=xuDZ9-sAAAAJ&view_op=list_works&sortby=pubdate).

You can find a description of some of my recent research work in [**Quanta article**](https://www.quantamagazine.org/surprise-computer-science-proof-stuns-mathematicians-20230321/), [**Science News**](https://www.sciencenews.org/article/arithmetic-progressions-math-order-combinatorics) and in this
[**video highlight**](https://www.youtube.com/watch?v=4HHUGnHcDQw).

---
## Publications
- [**Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension**](https://arxiv.org/abs/2407.00966)
COLT 2024 (**Best Paper Award**)
Gautam Chandrasekaran, Adam Klivans, Vasilis Kontonis, Raghu Meka, Konstantinos Stavropoulos
---
- **Learning Neural Networks with Sparse Activations**
COLT 2024
Pranjal Awasthi, Nishant Dikkala, Pritish Kamath, Raghu Meka
---
- **On Convex Optimization with Semi-Sensitive Features**
COLT 2024
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
---
- [**Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps**](https://arxiv.org/abs/2402.15409)
COLT 2024
Jonathan Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
---
- [**New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms**](https://arxiv.org/abs/2311.09095)
STOC 2024
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka
---
- [**Explicit separations between randomized and deterministic Number-on-Forehead communication**](https://eccc.weizmann.ac.il/report/2023/124/)
STOC 2024
Zander Kelley, Shachar Lovett, Raghu Meka
---
---
- [**User-Level Differential Privacy With Few Examples Per User**](https://arxiv.org/abs/2309.12500)
Neurips 2023 (**Oral Presentation**)
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
---
- [**Feature Adaptation for Sparse Linear Regression**](https://arxiv.org/abs/2305.16892)
Neurips 2023 (**Spotlight**)
Jonathan Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
---
- [**On User-Level Private Convex Optimization**](https://arxiv.org/abs/2305.04912)
ICML 2023
Badih Ghazi, Pritish Kamath, Ravi Kumar, Raghu Meka, Pasin Manurangsi, Chiyuan Zhang
---
- [**Learning Narrow One-Hidden-Layer ReLU Networks**](https://arxiv.org/abs/2304.10524)
COLT 2023
Sitan Chen, Zehao Dou, Surbhi Goel, Adam R Klivans, Raghu Meka
---
- [**Strong Bounds for 3-Progressions**](https://arxiv.org/abs/2302.05537)
FOCS 2023 (**Best Paper Award**)
Zander Kelley, Raghu Meka
[**Quanta article on the work**](https://www.quantamagazine.org/surprise-computer-science-proof-stuns-mathematicians-20230321/)
[**Video highlight**](https://www.youtube.com/watch?v=4HHUGnHcDQw)
---
- [**Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank**](https://arxiv.org/abs/2208.11286)
STOC 2023 (**Invited to SICOMP Special Issue**)
Nikhil Bansal, Haotian Jiang, Raghu Meka
---
- [**Efficient Resilient Functions**](https://epubs.siam.org/doi/abs/10.1137/1.9781611977554.ch108)
SODA 2023
Peter Ivanov, Raghu Meka, Emanuele Viola
---
---
- [**Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs**](https://arxiv.org/abs/2203.02824)
Neurips 2022
Jonathan Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
---
- [**Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks**](https://arxiv.org/abs/2202.05258)
Neurips 2022 (**Oral Presentation**)
Sitan Chen, Aravind Gollakota, Adam Klivans, Raghu Meka
---
- [**Sketching based Representations for Robust Image Classification with Provable Guarantees**](https://openreview.net/forum?id=fDWNnSiHeka)
Neurips 2022
Nishanth Dikkala, Sankeerth Rao Karingula, Raghu Meka, Jelani Nelson, Rina Panigrahy, Xin Wang
---
- [**Random restrictions and PRGs for PTFs in Gaussian Space**](https://arxiv.org/abs/2103.14134)
CCC 2022
Zander Kelley, Raghu Meka
---
- [**Smoothed Analysis of the Komlós Conjecture**](https://arxiv.org/abs/2204.11427)
ICALP 2022
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
---
- [**Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs**](https://arxiv.org/abs/2201.07206)
ICLR 2022
Sitan Chen, Jerry Li, Yuanzhi Li, Raghu Meka
---

- [**Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing**](https://arxiv.org/abs/2111.07049)
ITCS 2022
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
---
- [**Lifting with Sunflowers**](https://eccc.weizmann.ac.il/report/2020/111/)
ITCS 2022
Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, Jiapeng Zhang
---
---
- [**Efficiently Learning One Hidden Layer Neural Networks From Queries**](https://arxiv.org/abs/2111.04727)
Neurips 2021
Sitan Chen, Adam Klivans, Raghu Meka
---
- [**On the Power of Preconditioning in Sparse Linear Regression**](https://arxiv.org/abs/2106.09207)
FOCS 2021
Jonathan Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
---
- [**Learning Deep ReLU Networks is Fixed-Parameter Tractacble**](https://arxiv.org/abs/2009.13512)
FOCS 2021
Sitan Chen, Adam Klivans, Raghu Meka
---
- [**Pseudorandom Generators for Read-Once Monotone Branching Programs**](https://eccc.weizmann.ac.il/report/2021/018/)
RANDOM 2021
Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil Vadhan
---
- [**Online Discrepancy Minimization for Stochastic Arrivals**](https://arxiv.org/abs/2007.10622)
SODA 2021
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
---
---
- **Extractors and Secret Sharing Against Bounded Collusion Protocols**
FOCS 2020. (Merger of [these](https://eprint.iacr.org/2020/473) [two](https://eprint.iacr.org/2020/478))
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, David Zuckerman

---
- [**Learning Polynomials in Few Relevant Dimensions**](https://arxiv.org/abs/1905.01282)
COLT 2020
Sitan Chen, Raghu Meka
---
- [**Balancing Gaussian vectors in high dimension**](https://arxiv.org/abs/1910.13972)
COLT 2020
Paxton Turner, Raghu Meka, Philippe Rigollet
---
- [**Learning Some Popular Gaussian Graphical Models without Condition Number Bounds**](https://arxiv.org/abs/2004.13748)
NeurIPS 2020, **Spotlight**
Jonathan Kelner, Frederic Koehler, Raghu Meka, Ankur Moitra
---
---
- [**Leakage-Resilient Secret Sharing**](https://eprint.iacr.org/2018/1138)
FOCS 2019
Ashutosh Kumar, Raghu Meka, Amit Sahai
---
- [**On the Discrepancy of Random Low-Degree Set Systems**](https://arxiv.org/abs/1810.03374)
SODA 2019
Nikhil Bansal, Raghu Meka
---
- [**Pseudorandom Generators for Width-3 Branching Programs**](https://arxiv.org/abs/1806.04256)
STOC 2019
Raghu Meka, Omer Reingold, Avishay Tal
---
---
- [**Efficient Algorithms for Outlier-Robust Regression**](https://arxiv.org/abs/1803.03241)
COLT 2018
Adam Klivans, Pravesh Kothari, Raghu Meka
---
- [**Learning One Convolutional Layer with Overlapping Patches**](https://arxiv.org/abs/1802.02547)
ICML 2018
Surbhi Goel, Adam Klivans, Raghu Meka
---
- [**Learning Graphical Models using Multiplicative Weights**](https://arxiv.org/abs/1706.06274)
FOCS 2017
Adam Klivans, Raghu Meka
---
- [**Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs**](https://arxiv.org/abs/1610.02704)
STOC 2017
Pravesh Kothari, Prasad Raghavendra, Raghu Meka
***Invited to SICOMP Special Issue on STOC 2017***
---
- [**Explicit resilient functions matching Ajtai-Linial**](http://arxiv.org/abs/1509.00092)
SODA 2017
Raghu Meka
---
- [**Anti-concentration for polynomials of independent random variables**](http://theoryofcomputing.org/articles/v012a011/)
Theory of Computing, Volume 12.
Raghu Meka, Oanh Nguyen, Van Vu.
---
- [**Pseudorandomness via the discrete Fourier transform**](http://arxiv.org/abs/1506.04350)
FOCS 2015
Parikshit Gopalan, Daniel Kane, Raghu Meka.
***Invited to SICOMP Special Issue on FOCS 2015***
---
- [**Sum-of-squares lower bounds for planted clique**](http://arxiv.org/abs/1503.06447)
STOC 2015
Raghu Meka, Aaron Potechin, Avi Wigderson.
***Invited to SICOMP Special Issue on STOC 2015***
---
- [**Almost Optimal Pseudorandom Generators for Spherical Caps**](http://arxiv.org/abs/1411.6299)
STOC 2015
Pravesh Kothari, Raghu Meka.
---
- [**Rectangles are Nonnegative Juntas**](http://eccc.hpi-web.de/report/2014/147/)
STOC 2015. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman.
***SICOMP***
---
- [**Communication with Imperfectly Shared Randomness**](http://arxiv.org/abs/1411.3603)
ITCS 2015
Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan.
[***MIT-NEWS Blurb***](http://news.mit.edu/2014/more-reliable-communication-protocols-1212)
---
- [**Fast Pseudorandomness for Independence and Load Balancing**](https://raghumeka.github.io/pubs/eps_bias.pdf)
ICALP 2014
Raghu Meka, Omer Reingold, Guy Rothblum, Ron Rothblum.
---
- [**Volumetric Spanners an Exploration Basis for Learning**](http://proceedings.mlr.press/v35/hazan14b.html)
COLT 2014
Elad Hazan, Zohar Karnin, Raghu Meka.
---
- [**Computational Limits for Matrix Completion**
COLT 2014](http://jmlr.org/proceedings/papers/v35/hardt14b.html)
Moritz Hardt, Raghu Meka, Prasad Raghavendra, Benjamin Weitz.
---
- [**Deterministic Coupon Collection and Better Strong Dispersers**](https://raghumeka.github.io/pubs/dispersers.pdf)
RANDOM 2014
Raghu Meka, Omer Reingold, Yuan Zhou.
---
- [**Learning Halfspaces under Log-Concave Distributions**
COLT 2013](http://jmlr.org/proceedings/papers/v30/Kane13.html)
Daniel Kane, Adam Klivans and Raghu Meka.
Earlier version: [Moment Matching Polynomials](https://arxiv.org/abs/1301.0820)
---
- [**A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut**](http://arxiv.org/abs/1211.1109)
STOC 2013
Daniel Kane and Raghu Meka.
---
- [**Better Pseudorandom Generators from Milder Pseudorandom Restrictions**](https://arxiv.org/abs/1210.0049)
FOCS 2012
Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan.
---
- [**Pseudorandomness from Shrinkage**](http://eccc.hpi-web.de/report/2012/057/)
FOCS 2012
Russell Impagliazzo, Raghu Meka, David Zuckerman
***Journal of the ACM 66(2): 11:1-11:16 (2019)***
---
- [**Constructive Discrepancy Minimization by Walking on The Edges**](http://arxiv.org/abs/1203.5747)
FOCS 2012
Shachar Lovett, Raghu Meka
***Invited to SICOMP Special Issue on FOCS 2012***
---
- [**A PTAS for Computing the Supremum of Gaussian Processes**](http://arxiv.org/abs/1202.4970)
FOCS 2012. Raghu Meka
***Annals of Applied Probability, Volume 25, Issue 2***
---
- [**Making the long code shorter, with applications to the Unique Games Conjecture**](http://eccc.uni-trier.de/report/2011/142)
FOCS 2012
Boaz Barak, Parikshit Gopalan, Johan Hastad, Raghu Meka, Prasad Raghavendra, David Steurer
***Invited to SICOMP Special Issue on FOCS 2012***
---
- **Learning Functions of Halfspaces using Prefix Covers**
COLT 2012
Parikshit Gopalan, Adam Klivans, Raghu Meka
---
- [**DNF Sparsification and Faster Deterministic Counting**](http://eccc.hpi-web.de/report/2012/060)
CCC 2012
Parikshit Gopalan, Raghu Meka, Omer Reingold
***Invited to Computational Complexity Special Issue on CCC 2012***
---
- [**Computational Applications of Invariance Principles**](https://raghumeka.github.io/pubs/thesisf.pdf)
Dissertation.
***Bert Kay Best Dissertation Award in Computer Science***
---
- [**PTAS for Knapsack and Related Problems using Branching Programs**](http://eccc.uni-trier.de/report/2010/133)
FOCS 2011
Parikshit Gopalan, Adam Klivans and Raghu Meka
[Conference version merged with this paper by Daniel Stefankovich, Santhosh Vempala and Eric Vigoda.]
---
- **Almost Optimal Explicit Johnson-Lindenstrauss Transformations**
Random 2011
Daniel Kane, Raghu Meka and Jelani Nelson
---
- [**Pseudorandom Generators for Combinatorial Shapes](http://eccc.uni-trier.de/report/2010/176)
STOC 2011**
Parikshit Gopalan, Raghu Meka, Omer Reingold and David Zuckerman
***SICOMP***
---
- [**An Invariance Principle for Polytopes**](http://eccc.uni-trier.de/report/2009/144)
STOC 2010
Prahladh Harsha, Adam Klivans and Raghu Meka
***Journal of the ACM (JACM), Volume 59, Issue 6***
---
- [**Pseudorandom Generators for Polynomial Threshold Functions**](http://arxiv.org/abs/0910.4122)
STOC 2010
Raghu Meka and David Zuckerman
***Invited to SICOMP Special Issue on STOC 2010***
---
- [**Bounding the Sensitivity of Polynomial Threshold Functions**](https://arxiv.org/abs/0909.5175)
STOC 2010
Prahladh Harsha, Adam Klivans and Raghu Meka
[Conference version to be merged with this paper by Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan]
***Invited to a Special Issue of Theory of Computing***
---
- [**Guaranteed Rank Minimization via Singular Value Projection**](http://arxiv.org/abs/0909.5457)
NIPS 2010. [Code](http://www.cs.utexas.edu/~pjain/svp) (Not maintained ...)
Prateek Jain, Raghu Meka and Inderjit Dhillon.
---
- [**Small-Bias Spaces for Group Products**](https://raghumeka.github.io/pubs/genepsilon.pdf)
Random 2009
Raghu Meka and David Zuckerman
---
- [**Matrix Completion from Power-Law Distributed Samples**](https://raghumeka.github.io/pubs/powerlawmc.pdf)
NIPS 2009
Raghu Meka, Prateek Jain and Inderjit Dhillon.
---
- [**Rank Minimization via Online Learning**](https://raghumeka.github.io/pubs/icml08.pdf)
ICML 2008. Raghu Meka, Prateek Jain, Constantine Caramanis and Inderjit Dhillon
---
- [**Simultaneous Unsupervised Learning of Disparate Clusterings**](https://raghumeka.github.io/pubs/sdm08.pdf)
SDM 2008. ***Best Paper Runner-Up***
Prateek Jain, Raghu Meka and Inderjit Dhillon.
***Statistical Analysis and Data Mining, Volume 1, Issue 3.***