Yi Wu
Yi Wu
Verified email at google.com
TitleCited byYear
Optimal lower bounds for locality-sensitive hashing (except when q is tiny)
R O’Donnell, Y Wu, Y Zhou
ACM Transactions on Computation Theory (TOCT) 6 (1), 1-13, 2014
1152014
Agnostic learning of monomials by halfspaces is hard
V Feldman, V Guruswami, P Raghavendra, Y Wu
Foundations of Computer Science, 2009. FOCS'09. 50th Annual IEEE Symposium …, 2009
1132009
Membership privacy: a unifying framework for privacy definitions
N Li, W Qardaji, D Su, Y Wu, W Yang
Proceedings of the 2013 ACM SIGSAC conference on Computer & communications …, 2013
842013
Data selection for speech recognition
Y Wu, R Zhang, A Rudnicky
2007 IEEE Workshop on Automatic Speech Recognition & Understanding (ASRU …, 2007
642007
An optimal SDP algorithm for Max-Cut, and equally optimal Long Code tests
R O'Donnell, Y Wu
Proceedings of the 40th annual ACM symposium on Theory of computing, 335-344, 2008
512008
Bypassing UGC from some optimal geometric inapproximability results
V Guruswami, P Raghavendra, R Saket, Y Wu
ACM Transactions on Algorithms (TALG) 12 (1), 1-25, 2016
40*2016
Conditional hardness for satisfiable 3-CSPs
R O'Donnell, Y Wu
Proceedings of the 41st annual ACM symposium on Theory of computing, 493-502, 2009
402009
Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
A Ene, J Vondrák, Y Wu
382012
Fooling functions of halfspaces under product distributions
P Gopalan, R O'Donnell, Y Wu, D Zuckerman
2010 IEEE 25th Annual Conference on Computational Complexity, 223-234, 2010
382010
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions
I Diakonikolas, R O'Donnell, RA Servedio, Y Wu
Proceedings of the Twenty-Second Annual ACM-SIAM, 2010
202010
3-bit dictator testing: 1 vs. 5/8
R O'Donnell, Y Wu
Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete …, 2009
202009
A lower-variance randomized algorithm for approximate string matching
MJ Atallah, E Grigorescu, Y Wu
Information Processing Letters 113 (18), 690-692, 2013
162013
Pricing loss leaders can be hard
Y Wu
Proc.2nd Innovation in Computer Science 1 (1), 2.3, 2011
16*2011
Optimal query complexity for estimating the trace of a matrix
K Wimmer, Y Wu, P Zhang
International Colloquium on Automata, Languages, and Programming, 1051-1062, 2014
92014
Computational complexity of certifying restricted isometry property
A Natarajan, Y Wu
arXiv preprint arXiv:1406.5791, 2014
92014
On the hardness of pricing loss-leaders
P Popat, Y Wu
Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete …, 2012
72012
SDP gaps for 2-to-1 and other Label-Cover variants
V Guruswami, S Khot, R O’Donnell, P Popat, M Tulsiani, Y Wu
International Colloquium on Automata, Languages, and Programming, 617-628, 2010
62010
Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups
R O’Donnell, Y Wu, Y Zhou
ACM Transactions on Computation Theory (TOCT) 7 (2), 1-16, 2015
5*2015
Approximability Results of CSPs and Learning
Y Wu
Carnegie Mellon University Pittsburgh, PA, 2010
2010
The system can't perform the operation now. Try again later.
Articles 1–19