Research Publications
- Membership Privacy: A Unifying Framework For Privacy Definitions
Ninghui Li,
Wahbeh Qardaji,
Dong Su,
Y. Wu,
Weining Yang,
The ACM Conference on Computer and Communications Security (CCS), 2013
- A Lower-Variance Randomized Algorithm for Approximate String Matching (pdf)
Mike Atallah,
Elena Grigorescu,
Y. Wu
Information Processing Letters, 2013
- Lovasz versus Local Distribution: the Approximability of Multiway Partition Problem(pdf)
Alina Ene,
Jan 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 (pdf)
V. Guruswami, P. Raghavendra,
R. Saket, Y. Wu,
Symposium on Discrete Algorithms (SODA), 2012
Invited to Transaction on Algorithms
- Hardness of Max-2Lin and Max-3Lin 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 718-726
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.
Innovations in Theoretical Computer Science (ITCS), 2011
- Hardness Results of learning Low-Degree Polynomial Threshold Functions (pdf )
I. Diakonikolas,
R. O'Donnell,
R. Servedio, Y. Wu
Symposium on Discrete Algorithms (SODA), 2011
- SDP gaps for 2-to-1 and other Label-Cover 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): 1558-1590 (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
- 3-Bit Dictator testing: 1 vs. 5/8
(pdf )
R. O'Donnell, Y. Wu
Symposium on Discrete Algorithms (SODA), 2009
- An optimal SDP algorithm for Max-Cut, 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
|
|
Teaching
Talks
- 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
- 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 NP-hard 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 3-CSPs (pdf)
- CMU Theory Lunch
- Symposium on Theory of Computing (Symposium on Theory of Computing (STOC),), 2009
- 3-Bit Dicator testing: 1 vs. 5/8 (pdf)
- Symposium on Discrete Algorithms (SODA), 2009
- An optimal SDP algorithm for Max-Cut, and equally optimal Long Code tests
(pdf)
- CMU Theory Lunch
- IBM Research T.J. Watson
- Fudan University Theory Seminar
- Symposium on Theory of Computing (Symposium on Theory of Computing (STOC),), 2008
- Less is more (ppt)
- CMU Sphinx Speech Seminar
- IEEE Automatic Speech Recognition and Understanding Workshop (ASRU), 2007
|