Raghu Meka

ORCID

Publication Activity (10 Years)

Years Active: 2008-2024
Publications (10 Years): 92

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

COLT

FOCS

Publications

Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
On Convex Optimization with Semi-Sensitive Features. COLT (2024)
Pranjal Awasthi, Nishanth Dikkala, Pritish Kamath, Raghu Meka
Learning Neural Networks with Sparse Activations. COLT (2024)
Gautam Chandrasekaran, Adam T. Klivans, Vasilis Kontonis, Raghu Meka, Konstantinos Stavropoulos
Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension. COLT (2024)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps. COLT (2024)
Pranjal Awasthi, Nishanth Dikkala, Pritish Kamath, Raghu Meka
Learning Neural Networks with Sparse Activations. CoRR (2024)
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
On Convex Optimization with Semi-Sensitive Features. CoRR (2024)
Zander Kelley, Shachar Lovett, Raghu Meka
Explicit Separations between Randomized and Deterministic Number-on-Forehead Communication. STOC (2024)
Gautam Chandrasekaran, Adam R. Klivans, Vasilis Kontonis, Raghu Meka, Konstantinos Stavropoulos
Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension. CoRR (2024)
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. STOC (2024)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps. CoRR (2024)
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. Electron. Colloquium Comput. Complex. (2023)
Badih Ghazi, Pritish Kamath, Ravi Kumar, Raghu Meka, Pasin Manurangsi, Chiyuan Zhang
On User-Level Private Convex Optimization. CoRR (2023)
Zander Kelley, Raghu Meka
Strong Bounds for 3-Progressions. FOCS (2023)
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
On User-Level Private Convex Optimization. ICML (2023)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
Feature Adaptation for Sparse Linear Regression. NeurIPS (2023)
Zander Kelley, Shachar Lovett, Raghu Meka
Explicit separations between randomized and deterministic Number-on-Forehead communication. CoRR (2023)
Amir Abboud, Nick Fischer, Zander Kelley, Shachar Lovett, Raghu Meka
New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms. CoRR (2023)
Sitan Chen, Zehao Dou, Surbhi Goel, Adam R. Klivans, Raghu Meka
Learning Narrow One-Hidden-Layer ReLU Networks. CoRR (2023)
Zander Kelley, Shachar Lovett, Raghu Meka
Explicit separations between randomized and deterministic Number-on-Forehead communication. Electron. Colloquium Comput. Complex. (2023)
Sitan Chen, Zehao Dou, Surbhi Goel, Adam R. Klivans, Raghu Meka
Learning Narrow One-Hidden-Layer ReLU Networks. COLT (2023)
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
User-Level Differential Privacy With Few Examples Per User. CoRR (2023)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
Feature Adaptation for Sparse Linear Regression. CoRR (2023)
Nishanth Dikkala, Nikhil Ghosh, Raghu Meka, Rina Panigrahy, Nikhil Vyas, Xin Wang
On the Benefits of Learning to Route in Mixture-of-Experts Models. EMNLP (2023)
Nikhil Bansal, Haotian Jiang, Raghu Meka
Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank. STOC (2023)
Yuanzhi Li, Raghu Meka, Rina Panigrahy, Kulin Shah
Simple Mechanisms for Representing, Indexing and Manipulating Concepts. CoRR (2023)
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Raghu Meka, Chiyuan Zhang
User-Level Differential Privacy With Few Examples Per User. NeurIPS (2023)
Peter Ivanov, Raghu Meka, Emanuele Viola
Efficient resilient functions. SODA (2023)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Smoothed Analysis of the Komlós Conjecture. CoRR (2022)
Sitan Chen, Jerry Li, Yuanzhi Li, Raghu Meka
Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs. CoRR (2022)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
Lower Bounds on Randomly Preconditioned Lasso via Robust Sparse Designs. NeurIPS (2022)
Sitan Chen, Jerry Li, Yuanzhi Li, Raghu Meka
Minimax Optimality (Probably) Doesn't Imply Distribution Learning for GANs. ICLR (2022)
Sitan Chen, Aravind Gollakota, Adam R. Klivans, Raghu Meka
Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks. CoRR (2022)
Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, Jiapeng Zhang
Lifting with Sunflowers. ITCS (2022)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing. ITCS (2022)
Peter Ivanov, Raghu Meka, Emanuele Viola
Efficient resilient functions. Electron. Colloquium Comput. Complex. (2022)
Sitan Chen, Aravind Gollakota, Adam R. Klivans, Raghu Meka
Hardness of Noise-Free Learning for Two-Hidden-Layer Neural Networks. NeurIPS (2022)
Nishanth Dikkala, Sankeerth Rao Karingula, Raghu Meka, Jelani Nelson, Rina Panigrahy, Xin Wang
Sketching based Representations for Robust Image Classification with Provable Guarantees. NeurIPS (2022)
Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra
Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs. SIAM J. Comput. 51 (2) (2022)
Sitan Chen, Adam R. Klivans, Raghu Meka
Learning Deep ReLU Networks Is Fixed-Parameter Tractable. FOCS (2022)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Smoothed Analysis of the Komlós Conjecture. ICALP (2022)
Nikhil Bansal, Haotian Jiang, Raghu Meka
Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank. CoRR (2022)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
Distributional Hardness Against Preconditioned Lasso via Erasure-Robust Designs. CoRR (2022)
Zander Kelley, Raghu Meka
Random Restrictions and PRGs for PTFs in Gaussian Space. CCC (2022)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
On the Power of Preconditioning in Sparse Linear Regression. FOCS (2022)
Sitan Chen, Adam R. Klivans, Raghu Meka
Efficiently Learning Any One Hidden Layer ReLU Network From Queries. CoRR (2021)
Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan
Monotone Branching Programs: Pseudorandomness and Circuit Complexity. Electron. Colloquium Comput. Complex. 28 (2021)
Dean Doron, Raghu Meka, Omer Reingold, Avishay Tal, Salil P. Vadhan
Pseudorandom Generators for Read-Once Monotone Branching Programs. APPROX-RANDOM (2021)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Online Discrepancy Minimization for Stochastic Arrivals. SODA (2021)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
On the Power of Preconditioning in Sparse Linear Regression. CoRR (2021)
Zander Kelley, Raghu Meka
Random restrictions and PRGs for PTFs in Gaussian Space. Electron. Colloquium Comput. Complex. 28 (2021)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing. CoRR (2021)
Zander Kelley, Raghu Meka
Random restrictions and PRGs for PTFs in Gaussian Space. CoRR (2021)
Sitan Chen, Adam R. Klivans, Raghu Meka
Learning Deep ReLU Networks Is Fixed-Parameter Tractable. FOCS (2021)
Sitan Chen, Adam R. Klivans, Raghu Meka
Efficiently Learning One Hidden Layer ReLU Networks From Queries. NeurIPS (2021)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Dhruv Rohatgi
On the Power of Preconditioning in Sparse Linear Regression. FOCS (2021)
Ashutosh Kumar, Raghu Meka, David Zuckerman
Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing. IACR Cryptol. ePrint Arch. 2020 (2020)
Sitan Chen, Raghu Meka
Learning Polynomials of Few Relevant Dimensions. CoRR (2020)
Sitan Chen, Adam R. Klivans, Raghu Meka
Learning Deep ReLU Networks Is Fixed-Parameter Tractable. CoRR (2020)
Sitan Chen, Raghu Meka
Learning Polynomials in Few Relevant Dimensions. COLT (2020)
Nikhil Bansal, Raghu Meka
On the discrepancy of random low degree set systems. Random Struct. Algorithms 57 (3) (2020)
Ashutosh Kumar, Raghu Meka, David Zuckerman
Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing. Electron. Colloquium Comput. Complex. 27 (2020)
Shachar Lovett, Raghu Meka, Jiapeng Zhang
Improved lifting theorems via robust sunflowers. Electron. Colloquium Comput. Complex. 27 (2020)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Ankur Moitra
Learning Some Popular Gaussian Graphical Models without Condition Number Bounds. NeurIPS (2020)
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Ashutosh Kumar, Xin Li, Raghu Meka, David Zuckerman
Extractors and Secret Sharing Against Bounded Collusion Protocols. FOCS (2020)
Paxton Turner, Raghu Meka, Philippe Rigollet
Balancing Gaussian vectors in high dimension. COLT (2020)
Nikhil Bansal, Haotian Jiang, Raghu Meka, Sahil Singla, Makrand Sinha
Online Discrepancy Minimization for Stochastic Arrivals. CoRR (2020)
Nikhil Bansal, Raghu Meka
On the discrepancy of random low degree set systems. SODA (2019)
Raghu Meka, Omer Reingold, Avishay Tal
Pseudorandom generators for width-3 branching programs. STOC (2019)
Raghu Meka, Philippe Rigollet, Paxton Turner
Balancing Gaussian vectors in high dimension. CoRR (2019)
Jonathan A. Kelner, Frederic Koehler, Raghu Meka, Ankur Moitra
Learning Some Popular Gaussian Graphical Models without Condition Number Bounds. CoRR (2019)
Arnab Bhattacharyya, Philips George John, Suprovat Ghoshal, Raghu Meka
Average Bias and Polynomial Sources. Electron. Colloquium Comput. Complex. 26 (2019)
Russell Impagliazzo, Raghu Meka, David Zuckerman
Pseudorandomness from Shrinkage. J. ACM 66 (2) (2019)
Ashutosh Kumar, Raghu Meka, Amit Sahai
Leakage-Resilient Secret Sharing Against Colluding Parties. FOCS (2019)
Surbhi Goel, Adam R. Klivans, Raghu Meka
Learning One Convolutional Layer with Overlapping Patches. ICML (2018)
Raghu Meka, Omer Reingold, Avishay Tal
Pseudorandom Generators for Width-3 Branching Programs. Electron. Colloquium Comput. Complex. 25 (2018)
Raghu Meka, Omer Reingold, Avishay Tal
Pseudorandom Generators for Width-3 Branching Programs. CoRR (2018)
Adam R. Klivans, Pravesh K. Kothari, Raghu Meka
Efficient Algorithms for Outlier-Robust Regression. CoRR (2018)
Ashutosh Kumar, Raghu Meka, Amit Sahai
Leakage-Resilient Secret Sharing. Electron. Colloquium Comput. Complex. 25 (2018)
Ashutosh Kumar, Raghu Meka, Amit Sahai
Leakage-Resilient Secret Sharing. IACR Cryptol. ePrint Arch. 2018 (2018)
Nikhil Bansal, Raghu Meka
On the discrepancy of random low degree set systems. CoRR (2018)
Surbhi Goel, Adam R. Klivans, Raghu Meka
Learning One Convolutional Layer with Overlapping Patches. CoRR (2018)
Parikshit Gopalan, Daniel M. Kane, Raghu Meka
Pseudorandomness via the Discrete Fourier Transform. SIAM J. Comput. 47 (6) (2018)
Adam R. Klivans, Pravesh K. Kothari, Raghu Meka
Efficient Algorithms for Outlier-Robust Regression. COLT (2018)
Adam R. Klivans, Raghu Meka
Learning Graphical Models Using Multiplicative Weights. FOCS (2017)
Raghu Meka
Explicit Resilient Functions Matching Ajtai-Linial. SODA (2017)
Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan
Communication With Imperfectly Shared Randomness. IEEE Trans. Inf. Theory 63 (10) (2017)
Pravesh K. Kothari, Raghu Meka, Prasad Raghavendra
Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of CSPs. STOC (2017)
Adam R. Klivans, Raghu Meka
Learning Graphical Models Using Multiplicative Weights. CoRR (2017)
Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman
Rectangles Are Nonnegative Juntas. SIAM J. Comput. 45 (5) (2016)
Raghu Meka, Oanh Nguyen, Van Vu
Anti-concentration for Polynomials of Independent Random Variables. Theory Comput. 12 (1) (2016)
Pravesh Kothari, Raghu Meka, Prasad Raghavendra
Approximating Rectangles by Juntas and Weakly-Exponential Lower Bounds for LP Relaxations of CSPs. CoRR (2016)
Moritz Hardt, Yuval Ishai, Raghu Meka, Virginia Vassilevska Williams
Special Section on the Fifty-Fourth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013). SIAM J. Comput. 45 (3) (2016)
Parikshit Gopalan, Daniel M. Kane, Raghu Meka
Pseudorandomness via the Discrete Fourier Transform. FOCS (2015)
Shachar Lovett, Raghu Meka
Constructive Discrepancy Minimization by Walking on the Edges. SIAM J. Comput. 44 (5) (2015)
Pravesh K. Kothari, Raghu Meka
Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract. STOC (2015)
Parikshit Gopalan, Daniel M. Kane, Raghu Meka
Pseudorandomness via the discrete Fourier transform. CoRR (2015)
Raghu Meka
Explicit resilient functions matching Ajtai-Linial. Electron. Colloquium Comput. Complex. 22 (2015)
Clément Louis Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan
Communication with Imperfectly Shared Randomness. ITCS (2015)
Boaz Barak, Parikshit Gopalan, Johan Håstad, Raghu Meka, Prasad Raghavendra, David Steurer
Making the Long Code Shorter. SIAM J. Comput. 44 (5) (2015)
Raghu Meka, Aaron Potechin, Avi Wigderson
Sum-of-squares Lower Bounds for Planted Clique. STOC (2015)

Raghu Meka.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Raghu Meka