Yi Wu

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