From query complexity to computational complexity
- Shahar Dobzinski
- Jan Vondrak
- 2012
- STOC 2012
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
Beating randomized response on incoherent matrices
- Moritz Hardt
- Aaron Roth
- 2012
- STOC 2012
Tight bounds for distributed functional monitoring
- David P. Woodruff
- Qin Zhang
- 2012
- STOC 2012
Approximation algorithms for semi-random partitioning problems
- Konstantin Makarychev
- Yury Makarychev
- et al.
- 2012
- STOC 2012
Determinism versus nondeterminism with arithmetic tests and computation
- Miklós Ajtai
- 2012
- STOC 2012