From query complexity to computational complexity
- Shahar Dobzinski
- Jan Vondrak
- 2012
- STOC 2012
Conference paper
Publications
6 results at STOC 2012
Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces
- Anindya De
- Ilias Diakonikolas
- et al.
- 2012
- STOC 2012
Conference paperBeating randomized response on incoherent matrices
- Moritz Hardt
- Aaron Roth
- 2012
- STOC 2012
Conference paperTight bounds for distributed functional monitoring
- David P. Woodruff
- Qin Zhang
- 2012
- STOC 2012
Conference paperApproximation algorithms for semi-random partitioning problems
- Konstantin Makarychev
- Yury Makarychev
- et al.
- 2012
- STOC 2012
Conference paperDeterminism versus nondeterminism with arithmetic tests and computation
- Miklós Ajtai
- 2012
- STOC 2012
Conference paper