Optimal long code test with one free bit
- Nikhil Bansal
- Subhash Khot
- 2009
- FOCS 2009
Publications
7 results at FOCS 2009
The data stream space complexity of cascaded norms
- T.S. Jayram
- David P. Woodruff
- 2009
- FOCS 2009
Efficient sketches for Earth-Mover Distance, with applications
- Alexandr Andoni
- Khanh Do Ba
- et al.
- 2009
- FOCS 2009
Regularity lemmas and combinatorial algorithms
- Nikhil Bansal
- Ryan Williams
- 2009
- FOCS 2009
A complete characterization of statistical query learning with applications to evolvability
- Vitaly Feldman
- 2009
- FOCS 2009
Symmetry and approximability of submodular maximization problems
- Jan Vondrák
- 2009
- FOCS 2009
Agnostic learning of monomials by halfspaces is hard
- Vitaly Feldman
- Venkatesan Guruswami
- et al.
- 2009
- FOCS 2009