Papers
 Best Arm Identification in Linear Bandits with Linear Dimension Dependency
Chao Tao,
Saúl Blanco,
Yuan Zhou
ICML 2018 (To appear)
 Optimal Design of Process Flexibility for General Production Systems (SSRN)
Xi Chen,
Tengyu Ma,
Jiawei Zhang,
Yuan Zhou
Operations Research (To appear)
 Optimal Maximum Gap Estimation in the Multiarmed Bandit
Chao Tao,
Yuan Zhou,
Xi Chen,
Assaf Zeevi
Manuscript
 Adaptive MultipleArm Identification (arXiv)
Jiecao Chen,
Xi Chen,
Qin Zhang,
Yuan Zhou
ICML 2017
 Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints (arXiv)
Xue Chen,
Yuan Zhou
SODA 2017
 Optimal Sparse Designs for Process Flexibility via Probabilistic Expanders (SSRN)
Xi Chen,
Jiawei Zhang,
Yuan Zhou
Operations Research 635 (2015), pp. 11591176
 Satisfiability of Ordering CSPs Above Average Is FixedParameter Tractable (pdf)
Konstantin Makarychev,
Yury Makarychev,
Yuan Zhou
FOCS 2015
 Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems (pdf)
Venkatesan Guruswami,
Ali Kemal Sinop,
Yuan Zhou
SIAM Journal on Optimization 244 (2014), pp. 16981717
 Deterministic Coupon Collection and Better Strong Dispersers (pdf)
Raghu Meka,
Omer Reingold,
Yuan Zhou
RANDOM 2014
 Optimal PAC Multiple Arm Identification with Applications to Crowdsourcing (pdf)
Yuan Zhou,
Xi Chen,
Jian Li
ICML 2014
 Optimal strong parallel repetition for projection games on low threshold rank graphs (pdf)
Madhur Tulsiani,
John Wright,
Yuan Zhou
ICALP 2014
 Locally Testable Codes and Cayley Graphs (pdf)
Parikshit Gopalan,
Salil Vadhan,
Yuan Zhou
ITCS 2014
 Approximation Schemes via SheraliAdams Hierarchy for Dense Constraint Satisfaction Problems and Assignment Problems (pdf)
Yuichi Yoshida,
Yuan Zhou
ITCS 2014
 Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs (arXiv)
Ryan O'Donnell,
John Wright,
Chenggang Wu,
Yuan Zhou
SODA 2014
 Hypercontractive inequalities via SOS, and FranklRödl graph (pdf)
Manuel Kauers,
Ryan O'Donnell,
LiYang Tan,
Yuan Zhou
SODA 2014
 Approximability and proof complexity (arXiv)
Ryan O'Donnell,
Yuan Zhou
SODA 2013
 Approximating bounded occurrence ordering CSPs (pdf)
Venkatesan Guruswami,
Yuan Zhou
APPROX 2012
 Hypercontractivity, SumofSquares Proofs, and their Applications (arXiv)
Boaz Barak,
Fernando Brandão,
Aram Harrow,
Jonathan Kelner,
David Steurer,
Yuan Zhou
STOC 2012
 Linear programming, width1 CSPs, and robust satisfaction (pdf)
Gabor Kun,
Ryan O'Donnell,
Suguru Tamaki,
Yuichi Yoshida,
Yuan Zhou
ITCS 2012
 Polynomial integrality gaps for strong SDP relaxations of Densest kSubgraph (pdf)
Aditya Bhaskara,
Moses Charikar,
Venkatesan Guruswami,
Aravindan Vijayaraghavan,
Yuan Zhou
SODA 2012
 Blackbox reductions in mechanism design (pdf)
Zhiyi Huang,
Lei Wang,
Yuan Zhou
APPROX 2011
 The Fourier EntropyInfluence Conjecture for certain classes of Boolean functions (pdf)
Ryan O'Donnell,
John Wright,
Yuan Zhou
ICALP 2011
 Hardness of Max2Lin and Max3Lin over integers, reals, and large cyclic groups (pdf)
Ryan O'Donnell,
Yi Wu,
Yuan Zhou
CCC 2011
ACM Transactions on Computation Theory 7(2), Article 9 (May 2015)
 Finding almostperfect graph bisections (pdf)
Venkatesan Guruswami,
Yury Makarychev,
Prasad Raghavendra,
David Steurer,
Yuan Zhou
ITCS 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)
 Tighter Bounds for Facility Games (pdf)
Pinyan Lu,
Yajun Wang,
Yuan Zhou
WINE 2009
 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


Teaching
Talks
 Optimal Sparse Designs for Process Flexibility via Probabilistic Expanders (pptx)
 Theory Seminar, Indiana University at Bloomington, 2016
 Shanghai University of Finance and Economics, 2016
 ISMP 2015
 Understanding the Power of Convex Relaxation Hierarchies: Effectiveness and Limitations (pptx)
 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
