Yuan Zhou

Yuan Zhou

Contact

Computer Science Department
Carnegie Mellon University
8129 GHC
412-268-8078
my email address

I am a fourth year Ph.D. student at Carnegie Mellon University. I am fortunate to be advised by Venkatesan Guruswami and Ryan O'Donnell. I came here after I finished my undergraduate studies in the Special Pilot CS Class supervised by Prof. Andrew Yao at Institute for Theoretical Computer Science, Tsinghua University, China.

I am supported by a Simons Graduate Fellowship during 2012-2014.

Papers

  • The Fourier Entropy-Influence Conjecture for certain classes of Boolean functions (pdf)
    Ryan O'Donnell, John Wright, Yuan Zhou
          ICALP 2011
  • Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups (pdf)
    Ryan O'Donnell, Yi Wu, Yuan Zhou
          CCC 2011
  • Optimal lower bounds for locality sensitive hashing (except when q is tiny) (pdf)
    Ryan O'Donnell, Yi Wu, Yuan Zhou
          ITCS 2011
  • Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set (pdf)
    Venkatesan Guruswami, Yuan Zhou
          SODA 2011
Undergraduate
  • Surviving Rates of Graphs with Bounded Treewidth for the Firefighter Problem (pdf)
    Leizhen Cai, Yongxi Cheng, Elad Verbin, Yuan Zhou
          SIAM Journal on Discrete Mathematics 24(4), pp. 1322-1335 (2010)
  • On the alpha-Sensitivity of Nash Equilibria in PageRank-Based Network Reputation Games (pdf)
    Wei Chen, Shang-Hua Teng, Yajun Wang, Yuan Zhou
          FAW 2009
          Invited to Theoretical Computer Science

Talks

  • Approximating bounded occurrence CSPs (short-ppt)
    • APPROX + RANDOM 2012

  • Approximability and Proof Complexity (short-ppt, long-ppt)
    • The Microsoft Research-University of Washington Experience Theory Project, 2012
    • Theory Seminar at IBM Almaden Research Center, 2012
    • SODA 2013 (pptx)
    • The Chinese University of Hong Kong, 2013
    • National University of Singapore, 2013
    • Hong Kong University of Science and Technology, 2013

  • Hypercontractive norms, Sum-of-Squares Proofs, and their applications (Some of the slides are made by David Steruer, short-ppt)
    • STOC 2012

  • Polynomial integrality gaps for strong SDP relaxtions of Densest k-Subgraph (Some of the slides are made by Aravindan Vijayraghavan, short-ppt)
    • SODA 2012

  • Approximating k-route cuts (Some of the slides are made by Aravindan Vijayraghavan, short-ppt, long-ppt)
    • Purdue University Theory Seminar, 2012
    • CMU Theory Lunch, 2011
    • China Theory Week 2011 (Aarhus, Denmark)
    • Yangtze Microsoft Colloquium on Theoretical Computer Science, 2011
    • Institute of Computing Technology, Chinese Academy of Sciences, 2011
    • Microsoft Research Asia, 2011

  • Hardness of Solving Sparse Linear Equations over Integers (and Large Cyclic Groups) (short-ppt)
    • CCC 2011

  • Optimal lower bounds for Locality Sensitive Hashing (except when q is tiny) (The slides are mostly made by Ryan O'Donnell, short-ppt, long-ppt)
    • Yangtze Microsoft Colloquium on Theoretical Computer Science, 2011
    • ITCS 2011

  • Finding Almost-Perfect Graph Bisections (short-ppt, long-ppt)
    • CMU Theory Lunch, 2011
    • ITCS 2011

  • Tight Bounds on the Approximability of Almost-satisfiable Horn SAT (and Exact Hitting Set) (short-ppt, long-pdf)
    • SODA 2011
    • CMU Theory Lunch, 2010
    • U of Chicago Theory Seminar, 2010

  • Tighter Bounds for Facility Games (long-pptx)
    • WINE 2009
    • CMU Theory Lunch, 2009

  • The existence of alpha-sensitive Nash equilibria in PageRank games
    • Microsoft Research Asia Theory Group Seminar, 2008

Activities