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

Learning Graphical Models using Multiplicative Weights
To appear in FOCS 2017. Adam Klivans, Raghu Meka
ABSTRACT arXiv
Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs
STOC 2017. Pravesh Kothari, Prasad Raghavendra, Raghu Meka
Invited to SICOMP Special Issue on STOC 2017
ABSTRACT arXiv
Explicit resilient functions matching Ajtai-Linial
SODA 2017. Raghu Meka
ABSTRACT arXiv
Anti-concentration for polynomials of independent random variables
Theory of Computing, Volume 12. Raghu Meka, Oanh Nguyen, Van Vu.
ABSTRACT TOC
Pseudorandomness via the discrete Fourier transform
FOCS 2015. Parikshit Gopalan, Daniel Kane, Raghu Meka.
Invited to SICOMP Special Issue on FOCS 2015
ABSTRACT arXiv
Sum-of-squares lower bounds for planted clique
STOC 2015. Raghu Meka, Aaron Potechin, Avi Wigderson.
Invited to SICOMP Special Issue on STOC 2015
ABSTRACT arXiv
Almost Optimal Pseudorandom Generators for Spherical Caps
STOC 2015. Pravesh Kothari, Raghu Meka.
ABSTRACT arXiv
Rectangles are Nonnegative Juntas
STOC 2015. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman.
ABSTRACT ECCC
Communication with Imperfectly Shared Randomness
ITCS 2015. Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan.
ABSTRACT arXiv MIT-NEWS
Fast Pseudorandomness for Independence and Load Balancing
ICALP 2014. Raghu Meka, Omer Reingold, Guy Rothblum, Ron Rothblum.
ABSTRACT PDF
Volumetric Spanners an Exploration Basis for Learning
COLT 2014. Elad Hazan, Zohar Karnin, Raghu Meka.
ABSTRACT JMLR
Computational Limits for Matrix Completion
COLT 2014. Moritz Hardt, Raghu Meka, Prasad Raghavendra, Benjamin Weitz.
ABSTRACT JMLR
Deterministic Coupon Collection and Better Strong Dispersers
RANDOM 2014. Raghu Meka, Omer Reingold, Yuan Zhou.
ABSTRACT PDF
Learning Halfspaces under Log-Concave Distributions
COLT 2013. Daniel Kane, Adam Klivans and Raghu Meka.
ABSTRACT JMLR
A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut
STOC 2013. Daniel Kane and Raghu Meka.
ABSTRACT arXiv
Better Pseudorandom Generators from Milder Pseudorandom Restrictions
FOCS 2012. Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan.
ABSTRACT arXiv
Pseudorandomness from Shrinkage
FOCS 2012. Russell Impagliazzo, Raghu Meka, David Zuckerman
ABSTRACT ECCC
Constructive Discrepancy Minimization by Walking on The Edges
FOCS 2012. Shachar Lovett, Raghu Meka
Invited to SICOMP Special Issue on FOCS 2012
ABSTRACT arXiv
A PTAS for Computing the Supremum of Gaussian Processes
FOCS 2012. Raghu Meka
Annals of Applied Probability, Volume 25, Issue 2
ABSTRACT arXiv
Making the long code shorter, with applications to the Unique Games Conjecture
FOCS 2012. Boaz Barak, Parikshit Gopalan, Johan Hastad, Raghu Meka, Prasad Raghavendra, David Steurer
Invited to SICOMP Special Issue on FOCS 2012
ABSTRACT ECCC
Learning Functions of Halfspaces using Prefix Covers
COLT 2012. Parikshit Gopalan, Adam Klivans, Raghu Meka
DNF Sparsification and Faster Deterministic Counting
CCC 2012. Parikshit Gopalan, Raghu Meka, Omer Reingold
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
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
Almost Optimal Explicit Johnson-Lindenstrauss Transformations
Random 2011. Daniel Kane, Raghu Meka and Jelani Nelson
Pseudorandom Generators for Combinatorial Shapes
STOC 2011. Parikshit Gopalan, Raghu Meka, Omer Reingold and David Zuckerman
To appear in SICOMP
ABSTRACT ECCC
An Invariance Principle for Polytopes
STOC 2010. Prahladh Harsha, Adam Klivans and Raghu Meka
Journal of the ACM (JACM), Volume 59, Issue 6
ABSTRACT arXiv ECCC
Pseudorandom Generators for Polynomial Threshold Functions
STOC 2010. Raghu Meka and David Zuckerman
Invited to SICOMP Special Issue on STOC 2010
ABSTRACT arXiv
Bounding the Sensitivity of Polynomial Threshold Functions
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.
ABSTRACT arXiv
Small-Bias Spaces for Group Products
Random 2009. Raghu Meka and David Zuckerman
ABSTRACT PDF

Guaranteed Rank Minimization via Singular Value Projection
NIPS 2010. Prateek Jain, Raghu Meka and Inderjit Dhillon.
ABSTRACT arXiv Code
Matrix Completion from Power-Law Distributed Samples
NIPS 2009. Raghu Meka, Prateek Jain and Inderjit Dhillon.
ABSTRACT PDF
Rank Minimization via Online Learning
ICML 2008. Raghu Meka, Prateek Jain, Constantine Caramanis and Inderjit Dhillon
ABSTRACT BibTex PDF
Simultaneous Unsupervised Learning of Disparate Clusterings
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