Research Output per year

## Research Output 2009 2019

## Adaptive multiple-arm identification

Chen, J., Chen, X., Zhang, Q. & Zhou, Y., Jan 1 2017,*34th International Conference on Machine Learning, ICML 2017.*International Machine Learning Society (IMLS), p. 1202-1210 9 p. (34th International Conference on Machine Learning, ICML 2017; vol. 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Approximability and proof complexity

O'Donnell, R. & Zhou, Y., Apr 16 2013,*Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013.*p. 1537-1556 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Approximating bounded occurrence ordering CSPs

Guruswami, V. & Zhou, Y., Aug 28 2012,*Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Proceedings.*p. 158-169 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 7408 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Approximation algorithms and hardness of the k-route cut problem

Chuzhoy, J., Makarychev, Y., Vijayaraghavan, A. & Zhou, Y., Apr 30 2012,*Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012.*p. 780-799 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Approximation algorithms and hardness of the k-route cut problem

Chuzhoy, J., Makarychev, Y., Vijayaraghavan, A. & Zhou, Y., Dec 1 2015, In : ACM Transactions on Algorithms. 12, 1, 2.Research output: Contribution to journal › Article

## Approximation schemes via sherali-adams hierarchy for dense constraint satisfaction problems and assignment problems

Yoshida, Y. & Zhou, Y., Jan 1 2014,*ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science.*Association for Computing Machinery, p. 423-437 15 p. (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Best arm identification in linear bandits with linear dimension dependency

Tao, C., Blanco, S. A. & Zhou, Y., Jan 1 2018,*35th International Conference on Machine Learning, ICML 2018.*Krause, A. & Dy, J. (eds.). International Machine Learning Society (IMLS), p. 7773-7786 14 p. (35th International Conference on Machine Learning, ICML 2018; vol. 11).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Black-box reductions in mechanism design

Huang, Z., Wang, L. & Zhou, Y., Sep 8 2011,*Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings.*p. 254-265 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6845 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Constant factor Lasserre integrality gaps for graph partitioning problems

Guruswami, V., Sinop, A. K. & Zhou, Y., Jan 1 2014, In : SIAM Journal on Optimization. 24, 4, p. 1698-1717 20 p.Research output: Contribution to journal › Article

## Deterministic coupon collection and better strong dispersers

Meka, R., Reingold, O. & Zhou, Y., Sep 1 2014,*Leibniz International Proceedings in Informatics, LIPIcs.*Jansen, K., Moore, C., Devanur, N. R. & Rolim, J. D. P. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 872-884 13 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 28).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups

O'Donnell, R., Wu, Y. & Zhou, Y., Aug 29 2011,*Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011.*p. 23-33 11 p. 5959818. (Proceedings of the Annual IEEE Conference on Computational Complexity).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups

O'Donnell, R., Wu, Y. & Zhou, Y., May 1 2015, In : ACM Transactions on Computation Theory. 7, 2, 9.Research output: Contribution to journal › Article

## Hardness of robust graph isomorphism, lasserre gaps, and asymmetry of random graphs

O'Donnell, R., Wright, J., Wu, C. & Zhou, Y., Jan 1 2014,*Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014.*Association for Computing Machinery, p. 1659-1677 19 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Hypercontractive inequalities via SOS, and the frankl-rodl graph

Kauers, M., O'Donnell, R., Tan, L. Y. & Zhou, Y., Jan 1 2014,*Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014.*Association for Computing Machinery, p. 1644-1658 15 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Hypercontractive inequalities via SOS, and the Frankl-Rödl graph

Kauers, M., O'Donnell, R., Tan, L. Y. & Zhou, Y., Jan 1 2016, In : Discrete Analysis. 4, 2016, p. 1-21 21 p.Research output: Contribution to journal › Article

## Hypercontractivity, sum-of-squares proofs, and their applications

Barak, B., Brandão, F. G. S. L., Harrow, A. W., Kelner, J., Steurer, D. & Zhou, Y., Jun 26 2012,*STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing.*p. 307-326 20 p. (Proceedings of the Annual ACM Symposium on Theory of Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Linear programming, width-1 CSPs, and robust satisfaction

Kun, G., O'Donnell, R., Tamaki, S., Yoshida, Y. & Zhou, Y., Feb 6 2012,*ITCS 2012 - Innovations in Theoretical Computer Science Conference.*p. 484-495 12 p. (ITCS 2012 - Innovations in Theoretical Computer Science Conference).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Locally testable codes and cayley graphs

Gopalan, P., Vadhan, S. & Zhou, Y., Jan 1 2014,*ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science.*Association for Computing Machinery, p. 76-86 11 p. (ITCS 2014 - Proceedings of the 2014 Conference on Innovations in Theoretical Computer Science).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Near-optimal policies for dynamic multinomial logit assortment selection models

Wang, Y., Chen, X. & Zhou, Y., Jan 1 2018, In : Advances in Neural Information Processing Systems. 2018-December, p. 3101-3110 10 p.Research output: Contribution to journal › Conference article

## Off-policy evaluation and learning from logged bandit feedback: Error reduction via surrogate policy

Xie, Y., Liu, Q., Zhou, Y., Liu, B., Wang, Z. & Peng, J., Jan 1 2019.Research output: Contribution to conference › Paper

## On the α-sensitivity of nash equilibria in pagerank-based network reputation games

Chen, W., Teng, S. H., Wang, Y. & Zhou, Y., Nov 9 2009,*Frontiers in Algorithmics - Third International Workshop, FAW 2009, Proceedings.*p. 63-73 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5598 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Optimal design of process flexibility for general production systems

Chen, X., Ma, T., Zhang, J. & Zhou, Y., Jan 1 2019, In : Operations Research. 67, 2, p. 516-531 16 p.Research output: Contribution to journal › Article

## Optimal lower bounds for locality-sensitive hashing (except when q is tiny)

O'Donnell, R., Wu, Y. & Zhou, Y., Mar 2014, In : ACM Transactions on Computation Theory. 6, 1, 5.Research output: Contribution to journal › Article

## Optimal PAC multiple arm identification with applications to crowdsourcing

Zhou, Y., Chen, X. & Li, J., Jan 1 2014,*31st International Conference on Machine Learning, ICML 2014.*International Machine Learning Society (IMLS), p. 1446-1469 24 p. (31st International Conference on Machine Learning, ICML 2014; vol. 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Optimal sparse designs for process flexibility via probabilistic expanders

Chen, X., Zhang, J. & Zhou, Y., Sep 1 2015, In : Operations Research. 63, 5, p. 1159-1176 18 p.Research output: Contribution to journal › Article

## Optimal strong parallel repetition for projection games on low threshold rank graphs

Tulsiani, M., Wright, J. & Zhou, Y., Jan 1 2014,*Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings.*PART 1 ed. Springer-Verlag, p. 1003-1014 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 8572 LNCS, no. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Parameterized algorithms for constraint satisfaction problems above average with global cardinality constraints

Chen, X. & Zhou, Y., Jan 1 2017,*28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017.*Klein, P. N. (ed.). Association for Computing Machinery, p. 358-377 20 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph

Bhaskara, A., Charikar, M., Guruswami, V., Vijayaraghavan, A. & Zhou, Y., Apr 30 2012,*Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012.*p. 388-405 18 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Satisfiability of Ordering CSPs above Average is Fixed-Parameter Tractable

Makarychev, K., Makarychev, Y. & Zhou, Y., Dec 11 2015,*Proceedings - 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015.*IEEE Computer Society, p. 975-993 19 p. 7354438. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2015-December).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Surviving rates of graphs with bounded treewidth for the firefighter problem

Cai, L., Cheng, Y., Verbin, E. & Zhou, Y., Dec 1 2010, In : SIAM Journal on Discrete Mathematics. 24, 4, p. 1322-1335 14 p.Research output: Contribution to journal › Article

## The fourier entropy-influence conjecture for certain classes of Boolean functions

O'Donnell, R., Wright, J. & Zhou, Y., Jul 11 2011,*Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Proceedings.*PART 1 ed. p. 330-341 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 6755 LNCS, no. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Tight bounds for collaborative PAC learning via multiplicative weights

Chen, J., Zhang, Q. & Zhou, Y., Jan 1 2018, In : Advances in Neural Information Processing Systems. 2018-December, p. 3598-3607 10 p.Research output: Contribution to journal › Conference article

## Tight bounds on the approximability of almost-satisfiable horn SAT and exact hitting set

Guruswami, V. & Zhou, Y., May 12 2011,*Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011.*p. 1574-1589 16 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

## Tighter bounds for facility games

Lu, P., Wang, Y. & Zhou, Y., Dec 1 2009,*Internet and Network Economics - 5th International Workshop, WINE 2009, Proceedings.*p. 137-148 12 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 5929 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution