Yi Wu

According to our database, Yi Wu authored at least 19 papers between 2007 and 2015.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2015

Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups.

Ryan O'Donnell, Yi Wu, Yuan Zhou

ACM Trans. Comput. Theory, 2015

2014

Optimal Query Complexity for Estimating the Trace of a Matrix.

Karl Wimmer, Yi Wu, Peng Zhang

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Computational Complexity of Certifying Restricted Isometry Property.

Abhiram Natarajan, Yi Wu

Proceedings of the Approximation, 2014

2013

A lower-variance randomized algorithm for approximate string matching.

Mikhail J. Atallah, Elena Grigorescu, Yi Wu

Inf. Process. Lett., 2013

Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems.

Alina Ene, Jan Vondrák, Yi Wu

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Membership privacy: a unifying framework for privacy definitions.

Ninghui Li, Wahbeh H. Qardaji, Dong Su, Yi Wu, Weining Yang

Proceedings of the 2013 ACM SIGSAC Conference on Computer and Communications Security, 2013

2012

Agnostic Learning of Monomials by Halfspaces Is Hard.

Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu

SIAM J. Comput., 2012

Pricing Loss Leaders Can be Hard.

Yi Wu

J. Comput. Sci. Technol., 2012

On the hardness of pricing loss-leaders.

Preyas Popat, Yi Wu

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions.

Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Yi Wu

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

The Approximability of Learning and Constraint Satisfaction Problems.

Yi Wu

PhD thesis, 2010

Fooling functions of halfspaces under product distributions.

Yi Wu, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan

Electron. Colloquium Comput. Complex., 2010

Bypassing UGC from some optimal geometric inapproximability results.

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu

Electron. Colloquium Comput. Complex., 2010

SDP Gaps for 2-to-1 and Other Label-Cover Variants.

Venkatesan Guruswami, Subhash Khot, Ryan O'Donnell, Preyas Popat, Madhur Tulsiani, Yi Wu

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

Optimal lower bounds for locality sensitive hashing (except when q is tiny).

Ryan O'Donnell, Yi Wu, Yuan Zhou

Electron. Colloquium Comput. Complex., 2009

Conditional hardness for satisfiable 3-CSPs.

Ryan O'Donnell, Yi Wu

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

3-bit dictator testing: 1 vs. 5/8.

Ryan O'Donnell, Yi Wu

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

2008

An optimal sdp algorithm for max-cut, and equally optimal long code tests.

Ryan O'Donnell, Yi Wu

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007

Data selection for speech recognition.

Yi Wu, Rong Zhang, Alexander I. Rudnicky

Proceedings of the IEEE Workshop on Automatic Speech Recognition & Understanding, 2007