Yuan Zhou

Yuan Zhou

Contact

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

I am a fifth 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.

My CV is here.

Papers

  • Optimal PAC Multiple Arm Identification with Applications to Crowdsourcing
    Yuan Zhou, Xi Chen, Jian Li
          ICML 2014 (To appear)
  • Optimal strong parallel repetition for projection games on low threshold rank graphs
    Madhur Tulsiani, John Wright, Yuan Zhou
          ICALP 2014 (To appear)
  • Optimal Sparse Designs for Process Flexibility via Probabilistic Expanders (SSRN)
    Xi Chen, Jiawei Zhang, Yuan Zhou
          Manuscript
  • Approximation Schemes via Sherali-Adams Hierarchy for Dense Constraint Satisfaction Problems and Assignment Problems (pdf)
    Yuichi Yoshida, Yuan Zhou
          ITCS 2014
  • Deterministic Coupon Collection and Better Strong Dispersers
    Raghu Meka, Omer Reingold, Yuan Zhou
          Manuscript
  • 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
          ACM Transactions on Computation Theory 6(1), Article 5 (March 2014)
  • Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set (pdf)
    Venkatesan Guruswami, Yuan Zhou
          SODA 2011
          Theory of Computing 8, pp. 239-267 (2012)
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

  • Understanding the Power of Convex Relaxation Hierarchies: Effectiveness and Limitations
    • School of Informatics and Computing, Indiana University at Bloomington, 2014
    • Computer Science Department, Dartmouth College, 2014

  • Approximation Schemes via Sherali-Adams Hierarchy for Dense Constraint Satisfaction Problems and Assignment Problems (Some of the slides are made by Yuichi Yoshida, pptx)
    • ITCS 2014

  • Locally Testable Codes and Cayley Graphs (The slides are made by Parikshit Gopalan, pptx)
    • ITCS 2014

  • Hypercontractive inequalities via SOS, and Frankl-Rödl graph (pptx)
    • SODA 2014

  • Optimal PAC Multiple Arm Identification with Applications to Crowdsourcing
    • Microsoft Research Asia, 2013
    • Institute for Interdisciplinary Information Sciences, Tsinghua University, 2013
    • Nanjing University, 2013

  • Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs (The slides are made by John Wright, pptx)
    • Microsoft Research Redmond, 2013
    • Institute of Computing Technology, Chinese Academy of Sciences, 2013
    • Academy of Mathematics and Systems Science, Chinese Academy of Sciences, 2013
    • Institute for Computational and Experimental Research in Mathematics, Brown University, 2014

  • 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
    • Institute for Interdisciplinary Information Sciences, Tsinghua University, 2014

  • 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