Papers

Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in MultiArmed Bandits (arXiv)
Chao Tao,
Qin Zhang,
Yuan Zhou
FOCS 2019 (To appear)
 Exploration via Hindsight Goal Generation (arXiv)
Zhizhou Ren,
Kefan Dong,
Yuan Zhou,
Qiang Liu,
Jian Peng
Manuscript
 Thresholding Bandit with Optimal Aggregate Regret (arXiv)
Chao Tao,
Saúl Blanco,
Jian Peng,
Yuan Zhou
Manuscript
 Tight Regret Bounds for Infinitearmed Linear Contextual Bandits (arXiv)
Yingkai Li,
Yining Wang,
Yuan Zhou
Manuscript
 Nearly MinimaxOptimal Regret for Linearly Parameterized Bandits (arXiv)
Yingkai Li,
Yining Wang,
Yuan Zhou
COLT 2019
 Dynamic Assortment Optimization with Changing Contextual Information (arXiv)
Yining Wang,
Xi Chen,
Yuan Zhou
Manuscript
 Dynamic Assortment Selection under the Nested Logit Models (arXiv)
Yining Wang,
Xi Chen,
Yuan Zhou
Manuscript
 OffPolicy Evaluation and Learning from Logged Bandit Feedback: Error Reduction via Surrogate Policy (arXiv)
Yuan Xie,
Boyi Liu,
Qiang Liu,
Zhaoran Wang,
Yuan Zhou,
Jian Peng
ICLR 2019
 On Asymptotically Tight Tail Bounds for Sums of Geometric and Exponential Random Variables (arXiv)
Yaonan Jin,
Yingkai Li,
Yining Wang,
Yuan Zhou
Manuscript
 An Optimal Policy for Dynamic Assortment Planning Under Uncapacitated Multinomial Logit Models (arXiv)
Yining Wang,
Xi Chen,
Yuan Zhou
Manuscript
Preliminary version NearOptimal Policies for Dynamic Multinomial Logit Assortment Selection Models appeared in NeurIPS 2018 (pdf)
 Tight Bounds for Collaborative PAC Learning via Multiplicative Weights (arXiv)
Jiecao Chen,
Qin Zhang,
Yuan Zhou
NeurIPS 2018
 Best Arm Identification in Linear Bandits with Linear Dimension Dependency (pdf)
Chao Tao,
Saúl Blanco,
Yuan Zhou
ICML 2018
 Optimal Design of Process Flexibility for General Production Systems (SSRN)
Xi Chen,
Tengyu Ma,
Jiawei Zhang,
Yuan Zhou
Operations Research (To appear)
 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, pp. 11591176 (2015)
 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, pp. 16981717 (2014)
 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
 Approximation Algorithms and Hardness of the kRoute Cut Problem (conference versionpdf, full versionpdf)
Julia Chuzhoy,
Yury Makarychev,
Aravindan Vijayaraghavan,
Yuan Zhou
SODA 2012
ACM Transactions on Algorithms 12(1), Article 2 (February 2016)
 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
 Data Driven Algorithms for Assortment Planning Under Nested Logit Model
 INFORMS Annual Meeting, 2018
 Stochastic Optimization with Applications to Operations Management
 ISE Seminar, University of Illinois UrbanaChampaign, 2018
 School of Economics and Management, Tsinghua University, 2018
 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
