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