Publications (27)
Constructive Discrepancy Minimization by Walking on The Edges
Shachar Lovett, Raghu Meka
Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs
Parikshit Gopalan, Adam Klivans, Raghu Meka
Pseudorandom Generators for Width-3 Branching Programs
Raghu Meka, Omer Reingold, Avishay Tal
Making the long code shorter, with applications to the Unique Games Conjecture
Boaz Barak, Parikshit Gopalan, Johan Hastad +3
An Invariance Principle for Polytopes
Prahladh Harsha, Adam Klivans, Raghu Meka
Guaranteed Rank Minimization via Singular Value Projection
Raghu Meka, Prateek Jain, Inderjit S. Dhillon
Average Bias and Polynomial Sources
Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal +1
Almost Optimal Explicit Johnson-Lindenstrauss Transformations
Raghu Meka
Pseudorandomness via the discrete Fourier transform
Parikshit Gopalan, Daniel Kane, Raghu Meka
Anti-concentration for polynomials of independent random variables
Raghu Meka, Oanh Nguyen, Van Vu
Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs
Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra
Pseudorandom Generators for Polynomial Threshold Functions
Raghu Meka, David Zuckerman
On the discrepancy of random low degree set systems
Nikhil Bansal, Raghu Meka
Explicit resilient functions matching Ajtai-Linial
Raghu Meka
Learning Graphical Models Using Multiplicative Weights
Adam Klivans, Raghu Meka
A polynomial time approximation scheme for computing the supremum of Gaussian processes
Raghu Meka
Sum-of-squares lower bounds for planted clique
Raghu Meka, Aaron Potechin, Avi Wigderson
Computational Limits for Matrix Completion
Moritz Hardt, Raghu Meka, Prasad Raghavendra +1
Pseudorandomness for concentration bounds and signed majorities
Parikshit Gopalan, Daniel Kane, Raghu Meka
Bounding the Sensitivity of Polynomial Threshold Functions
Prahladh Harsha, Adam Klivans, Raghu Meka
Better Pseudorandom Generators from Milder Pseudorandom Restrictions
Parikshit Gopalan, Raghu Meka, Omer Reingold +2
DNF Sparsification and a Faster Deterministic Counting Algorithm
Parikshit Gopala, Raghu Meka, Omer Reingold
Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique
Raghu Meka, Avi Wigderson
A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut
Daniel Kane, Raghu Meka
Moment-Matching Polynomials
Adam Klivans, Raghu Meka
Learning One Convolutional Layer with Overlapping Patches
Surbhi Goel, Adam Klivans, Raghu Meka
Almost Optimal Pseudorandom Generators for Spherical Caps
Pravesh Kothari, Raghu Meka