Yuan Zhou

Yuan Zhou

    
     Assistant Professor
     Computer Science Department
     Indiana University at Bloomington
     430D Lindley Hall
     Email address
     CV


Papers

  • Optimal Maximum Gap Estimation in the Multi-armed Bandit
    Chao Tao, Yuan Zhou, Xi Chen, Assaf Zeevi
          Manuscript
  • Adaptive Multiple-Arm Identification
    Jiecao Chen, Xi Chen, Qin Zhang, Yuan Zhou
          ICML 2017 (To appear)
  • Optimal Design of Process Flexibility for General Production Systems (SSRN)
    Xi Chen, Tengyu Ma, Jiawei Zhang, Yuan Zhou
          Manuscript
  • 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 63-5 (2015), pp. 1159-1176
  • Satisfiability of Ordering CSPs Above Average Is Fixed-Parameter 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 24-4 (2014), pp. 1698-1717
  • 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 Sherali-Adams 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 Frankl-Rödl graph (pdf)
    Manuel Kauers, Ryan O'Donnell, Li-Yang 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, Sum-of-Squares Proofs, and their Applications (arXiv)
    Boaz Barak, Fernando Brandão, Aram Harrow, Jonathan Kelner, David Steurer, Yuan Zhou
          STOC 2012
  • Linear programming, width-1 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 k-Subgraph (pdf)
    Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, Yuan Zhou
          SODA 2012
  • Approximation Algorithms and Hardness of the k-Route Cut Problem (conference version-pdf, full version-pdf)
    Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou
          SODA 2012
  • Black-box reductions in mechanism design (pdf)
    Zhiyi Huang, Lei Wang, Yuan Zhou
          APPROX 2011
  • 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
          ACM Transactions on Computation Theory 7(2), Article 9 (May 2015)
  • Finding almost-perfect 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 Almost-satisfiable Horn SAT and Exact Hitting Set (pdf)
    Venkatesan Guruswami, Yuan Zhou
          SODA 2011
          Theory of Computing 8, pp. 239-267 (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. 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
 

Teaching

Talks

  • Optimal Sparse Designs for Process Flexibility via Probabilistic Expanders (pptx)
    • Theory Seminar, Indiana University at Bloomington, 2016
    • Shanghai University of Fianance 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 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