Raghu Meka

According to our database, Raghu Meka authored at least 93 papers between 2008 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Discrepancy Beyond Additive Functions with Applications to Fair Division.

Alexandros Hollender, Pasin Manurangsi, Raghu Meka, Warut Suksompong

CoRR, September, 2025

Sparsifying Sums of Positive Semidefinite Matrices.

Arpon Basu, Pravesh K. Kothari, Yang P. Liu, Raghu Meka

CoRR, August, 2025

Tight Lower Bound for Multicolor Discrepancy.

Pasin Manurangsi, Raghu Meka

CoRR, April, 2025

2024

Explicit Separations between Randomized and Deterministic Number-on-Forehead Communication.

Zander Kelley, Shachar Lovett, Raghu Meka

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms.

Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps.

Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

On Convex Optimization with Semi-Sensitive Features.

Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension.

Gautam Chandrasekaran, Adam R. Klivans, Vasilis Kontonis, Raghu Meka, Konstantinos Stavropoulos

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

Learning Neural Networks with Sparse Activations.

Pranjal Awasthi, Nishanth Dikkala, Pritish Kamath, Raghu Meka

Proceedings of the Thirty Seventh Annual Conference on Learning Theory, June 30, 2024

2023

Special Issue: APPROX-RANDOM 2020: Guest Editor's Foreword.

Jaroslaw Byrka, Raghu Meka

Theory Comput., 2023

Simple Mechanisms for Representing, Indexing and Manipulating Concepts.

Yuanzhi Li, Raghu Meka, Rina Panigrahy, Kulin Shah

CoRR, 2023

Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank.

Nikhil Bansal, Haotian Jiang, Raghu Meka

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Efficient resilient functions.

Peter Ivanov, Raghu Meka, Emanuele Viola

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Feature Adaptation for Sparse Linear Regression.

Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

User-Level Differential Privacy With Few Examples Per User.

Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

On User-Level Private Convex Optimization.

Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang

Proceedings of the International Conference on Machine Learning, 2023

Strong Bounds for 3-Progressions.

Zander Kelley, Raghu Meka

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

On the Benefits of Learning to Route in Mixture-of-Experts Models.

Nishanth Dikkala, Nikhil Ghosh, Raghu Meka, Rina Panigrahy, Nikhil Vyas, Xin Wang

Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, 2023

Learning Narrow One-Hidden-Layer ReLU Networks.

Sitan Chen, Zehao Dou, Surbhi Goel, Adam R. Klivans, Raghu Meka

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

2022

Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs.

Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi

CoRR, 2022

Lower Bounds on Randomly Preconditioned Lasso via Robust Sparse Designs.

Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Sketching based Representations for Robust Image Classification with Provable Guarantees.

Nishanth Dikkala, Sankeerth Rao Karingula, Raghu Meka, Jelani Nelson, Rina Panigrahy, Xin Wang

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks.

Sitan Chen, Aravind Gollakota, Adam R. Klivans, Raghu Meka

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Lifting with Sunflowers.

Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, Jiapeng Zhang

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing.

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs.

Sitan Chen, Jerry Li, Yuanzhi Li, Raghu Meka

Proceedings of the Tenth International Conference on Learning Representations, 2022

Smoothed Analysis of the Komlós Conjecture.

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Random Restrictions and PRGs for PTFs in Gaussian Space.

Zander Kelley, Raghu Meka

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Monotone Branching Programs: Pseudorandomness and Circuit Complexity.

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2021

Efficiently Learning Any One Hidden Layer ReLU Network From Queries.

Sitan Chen, Adam R. Klivans, Raghu Meka

CoRR, 2021

Online Discrepancy Minimization for Stochastic Arrivals.

Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Efficiently Learning One Hidden Layer ReLU Networks From Queries.

Sitan Chen, Adam R. Klivans, Raghu Meka

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

On the Power of Preconditioning in Sparse Linear Regression.

Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Learning Deep ReLU Networks Is Fixed-Parameter Tractable.

Sitan Chen, Adam R. Klivans, Raghu Meka

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Pseudorandom Generators for Read-Once Monotone Branching Programs.

Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan

Proceedings of the Approximation, 2021

2020

Improved lifting theorems via robust sunflowers.

Shachar Lovett, Raghu Meka, Jiapeng Zhang

Electron. Colloquium Comput. Complex., 2020

Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing.

Ashutosh Kumar, Raghu Meka, David Zuckerman

Electron. Colloquium Comput. Complex., 2020

Learning Some Popular Gaussian Graphical Models without Condition Number Bounds.

Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Ankur Moitra

Proceedings of the Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, 2020

Extractors and Secret Sharing Against Bounded Collusion Protocols.

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, David Zuckerman

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Balancing Gaussian vectors in high dimension.

Paxton Turner, Raghu Meka, Philippe Rigollet

Proceedings of the Conference on Learning Theory, 2020

Learning Polynomials in Few Relevant Dimensions.

Sitan Chen, Raghu Meka

Proceedings of the Conference on Learning Theory, 2020

2019

Average Bias and Polynomial Sources.

Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka

Electron. Colloquium Comput. Complex., 2019

Pseudorandom generators for width-3 branching programs.

Raghu Meka, Omer Reingold, Avishay Tal

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

On the discrepancy of random low degree set systems.

Nikhil Bansal, Raghu Meka

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Leakage-Resilient Secret Sharing Against Colluding Parties.

Ashutosh Kumar, Raghu Meka, Amit Sahai

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Leakage-Resilient Secret Sharing.

Ashutosh Kumar, Raghu Meka, Amit Sahai

Electron. Colloquium Comput. Complex., 2018

Learning One Convolutional Layer with Overlapping Patches.

Surbhi Goel, Adam R. Klivans, Raghu Meka

Proceedings of the 35th International Conference on Machine Learning, 2018

Efficient Algorithms for Outlier-Robust Regression.

Adam R. Klivans, Pravesh K. Kothari, Raghu Meka

Proceedings of the Conference On Learning Theory, 2018

2017

Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs.

Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Explicit Resilient Functions Matching Ajtai-Linial.

Raghu Meka

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Learning Graphical Models Using Multiplicative Weights.

Adam R. Klivans, Raghu Meka

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Anti-concentration for Polynomials of Independent Random Variables.

Raghu Meka, Oanh Nguyen, Van Vu

Theory Comput., 2016

Special Section on the Fifty-Fourth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013).

Moritz Hardt, Yuval Ishai, Raghu Meka, Virginia Vassilevska Williams

SIAM J. Comput., 2016

2015

Sum-of-squares Lower Bounds for Planted Clique.

Raghu Meka, Aaron Potechin, Avi Wigderson

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract.

Pravesh K. Kothari, Raghu Meka

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Rectangles Are Nonnegative Juntas.

Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Communication with Imperfectly Shared Randomness.

Clément Louis Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan

Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Pseudorandomness via the Discrete Fourier Transform.

Parikshit Gopalan, Daniel M. Kane, Raghu Meka

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Bounding the Sensitivity of Polynomial Threshold Functions.

Prahladh Harsha, Adam R. Klivans, Raghu Meka

Theory Comput., 2014

Almost Optimal Pseudorandom Generators for Spherical Caps.

Pravesh Kothari, Raghu Meka

CoRR, 2014

Pseudorandomness for concentration bounds and signed majorities.

Parikshit Gopalan, Daniel M. Kane, Raghu Meka

CoRR, 2014

Fast Pseudorandomness for Independence and Load Balancing - (Extended Abstract).

Raghu Meka, Omer Reingold, Guy N. Rothblum, Ron D. Rothblum

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Volumetric Spanners: an Efficient Exploration Basis for Learning.

Elad Hazan, Zohar Shay Karnin, Raghu Meka

Proceedings of The 27th Conference on Learning Theory, 2014

Computational Limits for Matrix Completion.

Moritz Hardt, Raghu Meka, Prasad Raghavendra, Benjamin Weitz

Proceedings of The 27th Conference on Learning Theory, 2014

Deterministic Coupon Collection and Better Strong Dispersers.

Raghu Meka, Omer Reingold, Yuan Zhou

Proceedings of the Approximation, 2014

2013

Association schemes, non-commutative polynomial concentration, and sum-of-squares lower bounds for planted clique.

Raghu Meka, Avi Wigderson

Electron. Colloquium Comput. Complex., 2013

Moment-Matching Polynomials.

Adam R. Klivans, Raghu Meka

Electron. Colloquium Comput. Complex., 2013

Volumetric Spanners and their Applications to Machine Learning.

Elad Hazan, Zohar Shay Karnin, Raghu Meka

CoRR, 2013

A PRG for lipschitz functions of polynomials with applications to sparsest cut.

Daniel M. Kane, Raghu Meka

Proceedings of the Symposium on Theory of Computing Conference, 2013

Learning Halfspaces Under Log-Concave Densities: Polynomial Approximations and Moment Matching.

Daniel M. Kane, Adam R. Klivans, Raghu Meka

Proceedings of the COLT 2013, 2013

2012

Learning Functions of Halfspaces using Prefix Covers.

Parikshit Gopalan, Adam R. Klivans, Raghu Meka

Proceedings of the COLT 2012, 2012

DNF Sparsification and a Faster Deterministic Counting.

Parikshit Gopalan, Raghu Meka, Omer Reingold

Electron. Colloquium Comput. Complex., 2012

A PTAS for Computing the Supremum of Gaussian Processes.

Raghu Meka

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Constructive Discrepancy Minimization by Walking on the Edges.

Shachar Lovett, Raghu Meka

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Pseudorandomness from Shrinkage.

Russell Impagliazzo, Raghu Meka, David Zuckerman

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Better Pseudorandom Generators from Milder Pseudorandom Restrictions.

Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Making the Long Code Shorter.

Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

DNF Sparsification and a Faster Deterministic Counting Algorithm.

Parikshit Gopalan, Raghu Meka, Omer Reingold

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

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

Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer

Electron. Colloquium Comput. Complex., 2011

Pseudorandom generators for combinatorial shapes.

Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

An FPTAS for #Knapsack and Related Counting Problems.

Parikshit Gopalan, Adam R. Klivans, Raghu Meka, Daniel Stefankovic, Santosh S. Vempala, Eric Vigoda

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

Almost Optimal Explicit Johnson-Lindenstrauss Families.

Daniel Kane, Raghu Meka, Jelani Nelson

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Almost Optimal Explicit Johnson-Lindenstrauss Transformations.

Daniel Kane, Raghu Meka, Jelani Nelson

Electron. Colloquium Comput. Complex., 2010

Polynomial-Time Approximation Schemes for Knapsack and Related Counting Problems using Branching Programs.

Parikshit Gopalan, Adam R. Klivans, Raghu Meka

Electron. Colloquium Comput. Complex., 2010

Almost Optimal Explicit Johnson-Lindenstrauss Transformations

Raghu Meka

CoRR, 2010

Pseudorandom generators for polynomial threshold functions.

Raghu Meka, David Zuckerman

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

An invariance principle for polytopes.

Prahladh Harsha, Adam R. Klivans, Raghu Meka

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Bounding the average sensitivity and noise sensitivity of polynomial threshold functions.

Ilias Diakonikolas, Prahladh Harsha, Adam R. Klivans, Raghu Meka, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Guaranteed Rank Minimization via Singular Value Projection.

Prateek Jain, Raghu Meka, Inderjit S. Dhillon

Proceedings of the Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, 2010

2009

Matrix Completion from Power-Law Distributed Samples.

Raghu Meka, Prateek Jain, Inderjit S. Dhillon

Proceedings of the Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting held 7-10 December 2009, 2009

Small-Bias Spaces for Group Products.

Raghu Meka, David Zuckerman

Proceedings of the Approximation, 2009

2008

Simultaneous Unsupervised Learning of Disparate Clusterings.

Prateek Jain, Raghu Meka, Inderjit S. Dhillon

Proceedings of the SIAM International Conference on Data Mining, 2008

Rank minimization via online learning.

Raghu Meka, Prateek Jain, Constantine Caramanis, Inderjit S. Dhillon

Proceedings of the Machine Learning, 2008