--- 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). --- ## Publications - [**Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps**](https://arxiv.org/abs/2402.15409) ArXiv 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 (To appear) 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 (To appear) 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.***
Last changed by  
 
Raghu Meka
12638

Read more

Algorithmic Machine Learning

In this course we will look at a handful of ubiquitous algorithms in machine learning. We will cover several classical tools in machine learning but more emphasis will be given to recent advances and developing efficient and provable algorithms for learning tasks. A tentative syllabus/schedule can be found below; the topics may change based on student interests as well. You can also check last year's course notes for a more details about what's to come.

4/5/2024
Algorithmic Machine Learning

In this course we will look at a handful of ubiquitous algorithms in machine learning. We will cover several classical tools in machine learning but more emphasis will be given to recent advances and developing efficient and provable algorithms for learning tasks. A tentative syllabus/schedule can be found below; the topics may change based on student interests as well. You can also check last year's course notes for a more details about what's to come.

2/23/2024
Teaching

Here are the courses I have taught or will in the future.

2/23/2024
CS181: Introduction to Theory of Computing Fall 2023

The official title for the course is Formal Languages and Automata Theory. This offering will be geared towards introducing you to the beautiful and profundly impactful world of Theoretical Computer Science (TOC). The following three questions encompass our main learning goals:

12/4/2023
Read more from Raghu Meka
Published on HackMD