Yi Wu

Publication Activity (10 Years)

Years Active: 2007-2016
Publications (10 Years): 1

Top Topics

Randomized Algorithm

Approximate String Matching

Agnostic Learning

Top Venues

ACM Trans. Comput. Theory

Publications

Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu
Bypassing UGC from Some Optimal Geometric Inapproximability Results. ACM Trans. Algorithms 12 (1) (2016)
Alina Ene, Jan Vondrák, Yi Wu
Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems. CoRR (2015)
Ryan O'Donnell, Yi Wu, Yuan Zhou
Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups. ACM Trans. Comput. Theory 7 (2) (2015)
Abhiram Natarajan, Yi Wu
Computational Complexity of Certifying Restricted Isometry Property. APPROX-RANDOM (2014)
Karl Wimmer, Yi Wu, Peng Zhang
Optimal Query Complexity for Estimating the Trace of a Matrix. ICALP (1) (2014)
Ryan O'Donnell, Yi Wu, Yuan Zhou
Optimal Lower Bounds for Locality-Sensitive Hashing (Except When q is Tiny). ACM Trans. Comput. Theory 6 (1) (2014)
Abhiram Natarajan, Yi Wu
Computational Complexity of Certifying Restricted Isometry Property. CoRR (2014)
Karl Wimmer, Yi Wu, Peng Zhang
Optimal query complexity for estimating the trace of a matrix. CoRR (2014)
Alina Ene, Jan Vondrák, Yi Wu
Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems. SODA (2013)
Ninghui Li, Wahbeh H. Qardaji, Dong Su, Yi Wu, Weining Yang
Membership privacy: a unifying framework for privacy definitions. CCS (2013)
Mikhail J. Atallah, Elena Grigorescu, Yi Wu
A lower-variance randomized algorithm for approximate string matching. Inf. Process. Lett. 113 (18) (2013)
Yi Wu
Pricing Loss Leaders Can be Hard. J. Comput. Sci. Technol. 27 (4) (2012)
Preyas Popat, Yi Wu
On the hardness of pricing loss-leaders. SODA (2012)
Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu
Bypassing UGC from some optimal geometric inapproximability results. SODA (2012)
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu
Agnostic Learning of Monomials by Halfspaces Is Hard. SIAM J. Comput. 41 (6) (2012)
Yi Wu
Pricing Loss Leaders can be Hard. ICS (2011)
Ryan O'Donnell, Yi Wu, Yuan Zhou
Optimal lower bounds for locality sensitive hashing (except when q is tiny). ICS (2011)
Ryan O'Donnell, Yi Wu, Yuan Zhou
Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups. Computational Complexity Conference (2011)
Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Yi Wu
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions. SODA (2011)
Yi Wu, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan
Fooling functions of halfspaces under product distributions. Electron. Colloquium Comput. Complex. 17 (2010)
Ilias Diakonikolas, Ryan O'Donnell, Rocco A. Servedio, Yi Wu
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions CoRR (2010)
Parikshit Gopalan, Ryan O'Donnell, Yi Wu, David Zuckerman
Fooling Functions of Halfspaces under Product Distributions. Computational Complexity Conference (2010)
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu
Agnostic Learning of Monomials by Halfspaces is Hard. Electron. Colloquium Comput. Complex. 17 (2010)
Venkatesan Guruswami, Subhash Khot, Ryan O'Donnell, Preyas Popat, Madhur Tulsiani, Yi Wu
SDP Gaps for 2-to-1 and Other Label-Cover Variants. ICALP (1) (2010)
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu
Agnostic Learning of Monomials by Halfspaces is Hard CoRR (2010)
Parikshit Gopalan, Ryan O'Donnell, Yi Wu, David Zuckerman
Fooling functions of halfspaces under product distributions CoRR (2010)
Venkatesan Guruswami, Prasad Raghavendra, Rishi Saket, Yi Wu
Bypassing UGC from some optimal geometric inapproximability results. Electron. Colloquium Comput. Complex. 17 (2010)
Ryan O'Donnell, Yi Wu
3-bit dictator testing: 1 vs. 5/8. SODA (2009)
Ryan O'Donnell, Yi Wu, Yuan Zhou
Optimal lower bounds for locality sensitive hashing (except when q is tiny) CoRR (2009)
Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu
Agnostic Learning of Monomials by Halfspaces Is Hard. FOCS (2009)
Ryan O'Donnell, Yi Wu
Conditional hardness for satisfiable 3-CSPs. STOC (2009)
Ryan O'Donnell, Yi Wu, Yuan Zhou
Optimal lower bounds for locality sensitive hashing (except when q is tiny). Electron. Colloquium Comput. Complex. 16 (2009)
Ryan O'Donnell, Yi Wu
An optimal sdp algorithm for max-cut, and equally optimal long code tests. STOC (2008)
Yi Wu, Rong Zhang, Alexander I. Rudnicky
Data selection for speech recognition. ASRU (2007)