20092019
If you made any changes in Pure, your changes will be visible here soon.

Research Output 2009 2019

  • 23 Conference contribution
  • 8 Article
  • 2 Conference article
  • 1 Paper
2019

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 conferencePaper

Maximum likelihood
Feedback
evaluation
learning
Recommender systems

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 journalArticle

Optimal design
Graph
Node
Guarantee
Uncertain demand
2018

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 proceedingConference contribution

Experiments

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 journalConference article

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 journalConference article

Learning algorithms
Polynomials
2017

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 proceedingConference contribution

Hardness
Testing

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 proceedingConference contribution

Cardinality Constraints
Parameterized Algorithms
Constraint satisfaction problems
Global Constraints
Constraint Satisfaction Problem
2016

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 journalArticle

Sum of squares
Reverse Inequality
Q-integers
Proof System
Graph in graph theory
2015

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 journalArticle

Open Access
Hardness
Approximation Algorithms
Connectivity
Bicriteria
Requirements

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 journalArticle

Cyclic group
Hardness
NP-hardness
Integer
Bicriteria

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 journalArticle

Optimality
Graph
Guarantee
Random demand

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 proceedingConference contribution

Constraint satisfaction problems
Linear equations
Decomposition
Atoms
2014

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 proceedingConference contribution

Constraint satisfaction problems
Linear programming
Polynomials

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 journalArticle

Graph Partitioning
Integrality
Separators
Separator
Approximation algorithms

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 proceedingConference contribution

Hash functions
Entropy
Bins
Seed

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 proceedingConference contribution

Graph Isomorphism
Random Graphs
Hardness
Asymmetry
Isomorphic

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 proceedingConference contribution

Sum of squares
Reverse Inequality
Q-integers
Proof System
Graph in graph theory

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 proceedingConference contribution

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 journalArticle

Hashing
Locality
Lower bound
Nearest Neighbor Search
Hamming distance

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 proceedingConference 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 proceedingConference contribution

Projection
Game
Graph in graph theory
Expander
Singular Values
2013

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 proceedingConference contribution

Proof Complexity
Approximability
Sum of squares
Semidefinite Programming
Separators
2012

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 proceedingConference contribution

Constraint satisfaction problems
Constraint Satisfaction Problem
Beat
Assignment
Restriction

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 proceedingConference contribution

Approximation algorithms
Hardness
Approximation Algorithms
Connectivity
Bicriteria

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 proceedingConference contribution

Information theory
Tensors
Polynomials
Eigenvalues and eigenfunctions
Computational complexity

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 proceedingConference contribution

Constraint satisfaction problems
Linear programming

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 proceedingConference contribution

Integrality
Subgraph
Hardness
Polynomials
Polynomial
2011

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 proceedingConference contribution

Mechanism Design
Black Box
Approximation algorithms
Approximation Algorithms
Algorithmic Mechanism Design

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 proceedingConference contribution

Cyclic group
Hardness
NP-hardness
Integer
Bicriteria

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 proceedingConference contribution

Boolean functions
Boolean Functions
Entropy
Verify
Symmetric Functions

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 proceedingConference contribution

Hitting Set
Approximability
Assignment
Hardness
Approximation algorithms
2010

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 journalArticle

Bounded Treewidth
Graph in graph theory
Vertex of a graph
Outerplanar Graph
Treewidth
2009

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 proceedingConference contribution

PageRank
Nash Equilibrium
Websites
Game
Search engines

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 proceedingConference contribution

Game
Welfare
Lower bound
Costs
Approximation