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 SheraliAdams Hierarchy for Dense Constraint Satisfaction Problems and Assignment Problems (pdf)
Yuichi Yoshida,
Yuan Zhou
ITCS 2014
 Hardness of Max2Lin and Max3Lin 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 Almostsatisfiable Horn SAT and Exact Hitting Set (pdf)
Venkatesan Guruswami,
Yuan Zhou
SODA 2011
Theory of Computing 8, pp. 239267 (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. 13221335 (2010)
 On the alphaSensitivity of Nash Equilibria in PageRankBased Network Reputation Games (pdf)
Wei Chen,
ShangHua 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 SheraliAdams Hierarchy for Dense Constraint Satisfaction Problems and Assignment Problems (Some of the slides are made by Yuichi Yoshida, pptx)
 Locally Testable Codes and Cayley Graphs (The slides are made by Parikshit Gopalan, pptx)
 Hypercontractive inequalities via SOS, and FranklRödl graph (pptx)
 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 (shortppt)
 Approximability and Proof Complexity (shortppt, longppt)
 The Microsoft ResearchUniversity 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, SumofSquares Proofs, and their applications (Some of the slides are made by David Steruer, shortppt)
 Polynomial integrality gaps for strong SDP relaxtions of Densest kSubgraph (Some of the slides are made by Aravindan Vijayraghavan, shortppt)
 Approximating kroute cuts (Some of the slides are made by Aravindan Vijayraghavan, shortppt, longppt)
 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) (shortppt)
 Optimal lower bounds for Locality Sensitive Hashing (except when q is tiny) (The slides are mostly made by Ryan O'Donnell, shortppt, longppt)
 Yangtze Microsoft Colloquium on Theoretical Computer Science, 2011
 ITCS 2011
 Finding AlmostPerfect Graph Bisections (shortppt, longppt)
 CMU Theory Lunch, 2011
 ITCS 2011
 Tight Bounds on the Approximability of Almostsatisfiable Horn SAT (and Exact Hitting Set) (shortppt, longpdf)
 SODA 2011
 CMU Theory Lunch, 2010
 U of Chicago Theory Seminar, 2010
 Tighter Bounds for Facility Games (longpptx)
 WINE 2009
 CMU Theory Lunch, 2009
 The existence of alphasensitive Nash equilibria in PageRank games
 Microsoft Research Asia Theory Group Seminar, 2008
Activities
