Yi Wu

yiwu at cs dot cmu dot edu

I am now at Google.


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 Lower-Variance 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 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.
    ACM Transactions on Computation Theory, 2014
    Conference version: 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
  •              

    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 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 (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 (STOC), 2008

    • Less is more (ppt)
      • CMU Sphinx Speech Seminar
      • IEEE Automatic Speech Recognition and Understanding Workshop (ASRU), 2007