73 citations · 347 across the 51 of their papers we have counts for
4 papers · 2 filters
Pseudorandomness for concentration bounds and signed majorities
Parikshit Gopalan, Daniel Kane, Raghu Meka
The problem of constructing pseudorandom generators that fool halfspaces has been studied intensively in recent times. For fooling halfspaces over the hypercube with polynomially s…
Almost Optimal Pseudorandom Generators for Spherical Caps
Pravesh Kothari, Raghu Meka
Halfspaces or linear threshold functions are widely studied in complexity theory, learning theory and algorithm design. In this work we study the natural problem of constructing ps…
Communication with Imperfectly Shared Randomness
Clément L. Canonne, Venkatesan Guruswami, Raghu Meka +1
The communication complexity of many fundamental problems reduces greatly when the communicating parties share randomness that is independent of the inputs to the communication tas…
Computational Limits for Matrix Completion
Moritz Hardt, Raghu Meka, Prasad Raghavendra +1
Matrix Completion is the problem of recovering an unknown real-valued low-rank matrix from a subsample of its entries. Important recent results show that the problem can be solved…