My main interests are in complexity theory, learning theory, algorithm design.
More generally, I like probability and combinatorics related things.

**STOC 2019.**Raghu Meka, Omer Reingold, Avishay Tal
**COLT 2018.** Adam Klivans, Pravesh Kothari, Raghu Meka
**ICML 2018.** Surbhi Goel, Adam Klivans, Raghu Meka
**FOCS 2017.** Adam Klivans, Raghu Meka
ABSTRACT arXiv
**STOC 2017.** Pravesh Kothari, Prasad
Raghavendra, Raghu Meka
**Theory of Computing, Volume 12.** Raghu Meka, Oanh
Nguyen, Van Vu.
ABSTRACT TOC
**FOCS 2015**. Parikshit Gopalan,
Daniel Kane, Raghu Meka.
**STOC 2015**. Raghu Meka, Aaron
Potechin, Avi Wigderson.
**STOC 2015**. Pravesh Kothari, Raghu Meka.
ABSTRACT arXiv
**STOC 2015**. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman.
ABSTRACT ECCC
**ITCS 2015**. Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan.
ABSTRACT
arXiv MIT-NEWS
**ICALP 2014**. Raghu Meka, Omer Reingold, Guy Rothblum, Ron Rothblum.
ABSTRACT PDF
**COLT 2014**. Elad Hazan, Zohar Karnin, Raghu Meka.
ABSTRACT JMLR
**COLT 2014**. Moritz Hardt, Raghu Meka, Prasad Raghavendra, Benjamin Weitz.
ABSTRACT JMLR
**RANDOM 2014**. Raghu Meka, Omer Reingold, Yuan Zhou.
ABSTRACT PDF
**COLT 2013**. Daniel Kane, Adam Klivans and Raghu Meka.
ABSTRACT JMLR
**STOC 2013**. Daniel Kane and Raghu Meka.
ABSTRACT arXiv
**FOCS 2012**. Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan.
ABSTRACT arXiv
**FOCS 2012**. Russell Impagliazzo, Raghu Meka, David Zuckerman
ABSTRACT ECCC
**FOCS 2012**. Shachar Lovett, Raghu Meka
**FOCS 2012**. Raghu Meka
**FOCS 2012**. Boaz Barak, Parikshit Gopalan, Johan Hastad, Raghu Meka, Prasad Raghavendra, David Steurer
**COLT 2012**. Parikshit Gopalan, Adam Klivans, Raghu Meka
**CCC 2012**. Parikshit Gopalan, Raghu Meka, Omer Reingold
**FOCS 2011**. Parikshit Gopalan, Adam Klivans and Raghu Meka

Conference version to be merged with this paper by Daniel Stefankovich, Santhosh Vempala and Eric Vigoda.
ABSTRACT ECCC
**Random 2011**. Daniel Kane, Raghu Meka and Jelani Nelson
**STOC 2011**. Parikshit Gopalan, Raghu Meka, Omer Reingold and David Zuckerman
**STOC 2010**. Prahladh Harsha, Adam Klivans and Raghu Meka
**STOC 2010**. Raghu Meka and David Zuckerman
**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.

**NIPS 2010**. Prateek Jain, Raghu Meka and Inderjit Dhillon.
ABSTRACT arXiv Code
**NIPS 2009**. Raghu Meka, Prateek Jain and Inderjit Dhillon.
ABSTRACT PDF
**ICML 2008**. Raghu Meka, Prateek Jain, Constantine Caramanis and Inderjit Dhillon
ABSTRACT BibTex PDF
**SDM 2008**. Prateek Jain, Raghu Meka and Inderjit Dhillon.

Journal Version: Statistical Analysis and Data Mining, Volume 1, Issue 3.
ABSTRACT BibTex PDF Best Paper Runner-up

Learning Some Popular Gaussian Graphical Models without Condition Number Bounds

Jonathan Kelner, Frederic Koehler, Raghu Meka, Ankur Moitra

Pseudorandom Generators for Width-3 Branching Programs

Efficient Algorithms for Outlier-Robust Regression

Learning One Convolutional Layer with Overlapping Patches

Learning Graphical Models using Multiplicative Weights

Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs

Invited to SICOMP **Special Issue** on STOC 2017

ABSTRACT arXiv
Anti-concentration for polynomials of independent random variables

Pseudorandomness via the discrete Fourier transform

Invited to SICOMP **Special Issue** on FOCS 2015

ABSTRACT arXiv
Sum-of-squares lower bounds for planted clique

Invited to SICOMP **Special Issue** on STOC 2015

ABSTRACT arXiv
Almost Optimal Pseudorandom Generators for Spherical Caps

Rectangles are Nonnegative Juntas

Communication with Imperfectly Shared Randomness

Fast Pseudorandomness for Independence and Load Balancing

Volumetric Spanners an Exploration Basis for Learning

Computational Limits for Matrix Completion

Deterministic Coupon Collection and Better Strong Dispersers

Learning Halfspaces under Log-Concave Distributions

A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut

Better Pseudorandom Generators from Milder Pseudorandom Restrictions

Pseudorandomness from Shrinkage

Constructive Discrepancy Minimization by Walking on The Edges

Invited to SICOMP **Special Issue** on FOCS 2012

ABSTRACT arXiv
A PTAS for Computing the Supremum of Gaussian Processes

Annals of Applied Probability, Volume 25, Issue 2

ABSTRACT arXiv
Making the long code shorter, with applications to the Unique Games Conjecture

Invited to SICOMP **Special Issue** on FOCS 2012

ABSTRACT ECCC
Learning Functions of Halfspaces using Prefix Covers

DNF Sparsification and Faster Deterministic Counting

Invited to Computational Complexity **Special Issue** on CCC 2012

ABSTRACT ECCC
Computational Applications of Invariance Principles

Dissertation.
PDF

Bert Kay **Best Dissertation Award** in Computer Science

PTAS for Knapsack and Related Problems using Branching Programs

Conference version to be merged with this paper by Daniel Stefankovich, Santhosh Vempala and Eric Vigoda.

Almost Optimal Explicit Johnson-Lindenstrauss Transformations

Pseudorandom Generators for Combinatorial Shapes

To appear in **SICOMP**

ABSTRACT ECCC
An Invariance Principle for Polytopes

Journal of the ACM **(JACM)**, Volume 59, Issue 6

ABSTRACT arXiv ECCC
Pseudorandom Generators for Polynomial Threshold Functions

Invited to SICOMP **Special Issue** on STOC 2010

ABSTRACT arXiv
Bounding the Sensitivity of Polynomial Threshold Functions

Invited to a **Special Issue** of Theory of Computing.

ABSTRACT arXiv
Guaranteed Rank Minimization via Singular Value Projection

Matrix Completion from Power-Law Distributed Samples

Rank Minimization via Online Learning

Simultaneous Unsupervised Learning of Disparate Clusterings

Journal Version: Statistical Analysis and Data Mining, Volume 1, Issue 3.