Publications
Computational Complexity of Certifying Restricted Isometry Property (arxiv) A. Natarajan, Y. Wu
International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2014
Optimal Query Comlexity of Estimating the Trace of a Matrix (arxiv)
K. Wimmer, Y. Wu, P. Zhang
International Colloquium on Automata, Languages and Programming (ICALP), 2014
Membership Privacy: A Unifying Framework For Privacy Definitions (pdf)
N. Li, W. Qardaji, D. Su, Y. Wu, W. Yang
The ACM Conference on Computer and Communications Security (CCS), 2013
A LowerVariance Randomized Algorithm for Approximate String Matching (pdf)
M. Atallah, E. Grigorescu, Y. Wu
Information Processing Letters, 2013
Lovasz versus Local Distribution: the Approximability of Multiway Partition Problem(pdf)
A. Ene, J. Vondrak, Y. Wu
Symposium on Discrete Algorithms (SODA), 2013
On the hardness of pricing loss leaders (pdf)
P. Popat, Y. Wu
Symposium on Discrete Algorithms (SODA), 2012
Bypassing UGC from some optimal geometric inapproximability results (ECCC)
V. Guruswami, P. Raghavendra, R. Saket, Y. Wu,
Symposium on Discrete Algorithms (SODA), 2012
Invited to Transaction on Algorithms
Hardness of Max2Lin and Max3Lin over integers, reals, and large cyclic groups (pdf )
R. O'Donnell, Y. Wu, Y. Zhou.
IEEE Conference on Computational Complexity (CCC), 2011
Pricing Loss Leaders can be hard (pdf )
Y. Wu.
Journal of Computer Science and Technology, July 2012, Volume 27, Issue 4, pp 718726
Conference version: Innovations in Theoretical Computer Science (ITCS), 2011
Optimal lower bounds for locality sensitive hashing (except when q is tiny) (pdf)
R. O'Donnell, Y. Wu, Y. Zhou.
ACM Transactions on Computation Theory, 2014
Conference version: Innovations in Theoretical Computer Science (ITCS), 2011
Hardness Results of learning LowDegree Polynomial Threshold Functions (pdf )
I. Diakonikolas, R. O'Donnell, R. Servedio, Y. Wu
Symposium on Discrete Algorithms (SODA), 2011
SDP gaps for 2to1 and other LabelCover variants (pdf )
V. Guruswami, S. Khot, R. O'Donnell, P. Popat, M. Tulsiani, Y. Wu.
International Colloquium on Automata, Languages and Programming (ICALP), 2010
Fooling functions of halfspaces under product distributions (pdf)
P. Gopalan, R. O'Donnell, Y. Wu, D. Zuckerman.
IEEE Conference on Computational Complexity (CCC), 2010
Agnostic learning of monomials by halfspaces is hard (pdf )
V. Feldman, V. Guruswami, P. Raghavendra, Y. Wu
SIAM J. Comput. 41(6): 15581590 (2012)
Conference version: Symposium on Foundations of Computer Science (FOCS), 2009
Conditional hardness for satisfiable 3CSPs (pdf)
R. O'Donnell, Y. Wu
Symposium on Theory of Computing (STOC), 2009
3Bit Dictator testing: 1 vs. 5/8 (pdf )
R. O'Donnell, Y. Wu
Symposium on Discrete Algorithms (SODA), 2009
An optimal SDP algorithm for MaxCut, and equally optimal Long Code tests (pdf )
R. O'Donnell, Y.Wu
Symposium on Theory of Computing (STOC), 2008
Data Selection for Speech Recognition (pdf)
Y. Wu, R. Zhang, A. Rudnicky
IEEE Automatic Speech Recognition and Understanding Workshop (ASRU), 2007


Thesis
Teaching
Talks
 Computational Complexity of CertifyingRestricted Isometry Property (pdf)
 International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2014
 The approximability of Mutliway Partition Problem (pptx)
 Workshop on approximation and hardness of approximation, BIRS, 2011
 IBM Almaden Theory Seminar, 2012
 U Chicago Theory Seminar, 2012
 UC Berkeley Simons Institute, 2013
 Bypassing the Unique Games Conjecture for geometric problems (pptx)
 Symposium on Discrete Algorithms (SODA), 2012
 On the hardness of pricing loss leaders (pptx)
 Workshop on approximability of CSPs, Fields Institute
 Symposium on Discrete Algorithms (SODA), 2012
 Hardness Results of Agnostic learning low degree PTFs (pptx)

 Symposium on Discrete Algorithms (SODA), 2011
 Hardness Results of Max 3Lin and Max 2Lin
 East China Normal University Theory Seminar
 Pricing Loss Leaders can be hard
 Innovations in Theoretical Computer Science (ITCS), 2011
 Approximability of NPhard Problems (pptx)
 IBM Almaden Theory Seminar
 Gatech Theory Seminar
 Toronto University Theory Seminar
 Agnostic learning of monomials by halfspaces is hard (pptx)
 CMU Theory Lunch
 China Theory Week 2009
 Symposium on Foundations of Computer Science (FOCS), 2009
 2nd Eastern Great Lakes Theory Talk
 Microsoft Research SVC
 Fooling functions of halfspaces under product distributions (pptx)
 Microsoft Research SVC
 IEEE Conference on Computational Complexity (CCC), 2010
 Conditional Hardness of Satisfiable 3CSPs (pdf)
 CMU Theory Lunch
 Symposium on Theory of Computing (STOC), 2009
 3Bit Dicator testing: 1 vs. 5/8 (pdf)

 Symposium on Discrete Algorithms (SODA), 2009
 An optimal SDP algorithm for MaxCut, and equally optimal Long Code tests (pdf)
 CMU Theory Lunch
 IBM Research T.J. Watson
 Fudan University Theory Seminar
 Symposium on Theory of Computing (STOC), 2008
 Less is more (ppt)
 CMU Sphinx Speech Seminar
 IEEE Automatic Speech Recognition and Understanding Workshop (ASRU), 2007
