Research Output per year

## Research Output

## Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-Armed bandits

Tao, C., Zhang, Q. & Zhou, Y., Nov 2019,*Proceedings - 2019 IEEE 60th Annual Symposium on Foundations of Computer Science, FOCS 2019.*IEEE Computer Society, p. 126-146 21 p. 8948669. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2019-November).

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

## 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

## 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

## 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

## 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

## 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 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

## 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

## 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 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

## 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.*Association for Computing Machinery, 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

## 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

## 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

## 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

## 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

## 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 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

## 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

## 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