My main interests are in complexity theory, learning theory, algorithm design.
More generally, I like probability and combinatorics related things.
Pseudorandom Generators for Width-3 Branching Programs
Raghu Meka, Omer Reingold, Avishay Tal
Efficient Algorithms for Outlier-Robust Regression
COLT 2018. Adam Klivans, Pravesh Kothari, Raghu Meka
Learning One Convolutional Layer with Overlapping Patches
ICML 2018. Surbhi Goel, Adam Klivans, Raghu Meka
Learning Graphical Models using Multiplicative Weights
FOCS 2017. Adam Klivans, Raghu Meka
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
Explicit resilient functions matching Ajtai-Linial
SODA 2017. Raghu Meka
Anti-concentration for polynomials of independent random variables
Theory of Computing, Volume 12. Raghu Meka, Oanh
Nguyen, Van Vu.
Pseudorandomness via the discrete Fourier transform
FOCS 2015. Parikshit Gopalan,
Daniel Kane, Raghu Meka.
Invited to SICOMP Special Issue on FOCS 2015
Sum-of-squares lower bounds for planted clique
STOC 2015. Raghu Meka, Aaron
Potechin, Avi Wigderson.
Invited to SICOMP Special Issue on STOC 2015
Almost Optimal Pseudorandom Generators for Spherical Caps
STOC 2015. Pravesh Kothari, Raghu Meka.
Rectangles are Nonnegative Juntas
STOC 2015. Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman.
Communication with Imperfectly Shared Randomness
ITCS 2015. Clement Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan.
Fast Pseudorandomness for Independence and Load Balancing
ICALP 2014. Raghu Meka, Omer Reingold, Guy Rothblum, Ron Rothblum.
Volumetric Spanners an Exploration Basis for Learning
COLT 2014. Elad Hazan, Zohar Karnin, Raghu Meka.
Computational Limits for Matrix Completion
COLT 2014. Moritz Hardt, Raghu Meka, Prasad Raghavendra, Benjamin Weitz.
Deterministic Coupon Collection and Better Strong Dispersers
RANDOM 2014. Raghu Meka, Omer Reingold, Yuan Zhou.
Learning Halfspaces under Log-Concave Distributions
COLT 2013. Daniel Kane, Adam Klivans and Raghu Meka.
A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut
STOC 2013. Daniel Kane and Raghu Meka.
Better Pseudorandom Generators from Milder Pseudorandom Restrictions
FOCS 2012. Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil Vadhan.
Pseudorandomness from Shrinkage
FOCS 2012. Russell Impagliazzo, Raghu Meka, David Zuckerman
Constructive Discrepancy Minimization by Walking on The Edges
FOCS 2012. Shachar Lovett, Raghu Meka
Invited to SICOMP Special Issue on FOCS 2012
A PTAS for Computing the Supremum of Gaussian Processes
FOCS 2012. Raghu Meka
Annals of Applied Probability, Volume 25, Issue 2
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
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
Computational Applications of Invariance Principles
Bert Kay Best Dissertation Award in Computer Science
PTAS for Knapsack and Related Problems using Branching Programs
. Parikshit Gopalan, Adam Klivans and Raghu Meka
Conference version to be 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
STOC 2011. Parikshit Gopalan, Raghu Meka, Omer Reingold and David Zuckerman
To appear in SICOMP
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
Bounding the Sensitivity of Polynomial Threshold Functions
. 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.
Small-Bias Spaces for Group Products
Random 2009. Raghu Meka and David Zuckerman
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.
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.
ABSTRACT BibTex PDF Best Paper Runner-up
Journal Version: Statistical Analysis and Data Mining, Volume 1, Issue 3.