Beating the direct sum theorem in communication complexity with implications for sketching
- Marco Molinaro
- David P. Woodruff
- et al.
- 2013
- SODA 2013
Publications
6 results at SODA 2013
Online submodular welfare maximization: Greedy is optimal
- Michael Kapralov
- Ian Post
- et al.
- 2013
- SODA 2013
Communication complexity of combinatorial auctions with submodular valuations
- Shahar Dobzinski
- Jan Vondrák
- 2013
- SODA 2013
The fast cauchy transform and faster robust linear regression
- Kenneth L. Clarkson
- Petros Drineas
- et al.
- 2013
- SODA 2013
Local distribution and the symmetry gap: Approximability of multiway partitioning problems
- Alina Ene
- Jan Vondrák
- et al.
- 2013
- SODA 2013
Lower bounds for adaptive sparse recovery
- Eric Price
- David P. Woodruff
- 2013
- SODA 2013