--- 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 - [**Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank**](https://arxiv.org/abs/2208.11286) ArXiv Nikhil Bansal, Haotian Jiang, Raghu Meka --- - **Efficient Resilient Functions** 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 --- - [**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.***