Publications

  1. Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints (arXiv)
    Xue Chen, Yuan Zhou*
    Manuscript
  2. Optimal Sparse Designs for Process Flexibility via Probabilistic Expanders (SSRN)
    Xi Chen, Jiawei Zhang, Yuan Zhou*
    Operations Research (To appear)
  3. Communication-Optimal Distributed Clustering 
    J. Chen, H. Sun, D. Woodruff, Q. Zhang*
    NIPS 2016
  4. Improved Algorithms for Distributed Entropy Monitoring 
    J. Chen, Q. Zhang*
    Algorithmica 2016
  5. Streaming Algorithms for Robust Distinct Elements 
    D. Chen, Q.zhang*
    SIGMOD 2016
  6. Edit Distance: Sketching, Streaming and Document Exchange 
    D. Belazzougui, Q. Zhang*
    FOCS 2016
  7. On Sketching Quadratic Forms 
    A. Andoni, J. Chen, R. Krauthgamer, B. Qin and D. P. Woodruff, Q. Zhang*
    ITCS 2016
  8. Communication-Efficient Computation on Distributed Noisy Datasets
    Q. Zhang*
    SPAA 15
  9. The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication 
    D. Van Gucht, R. Williams D. P. Woodruff, Q. Zhang*
    PODS 15
  10. Communication Complexity of Approximate Matching in Distributed Graphs 
    Z. Huang, B. Radunovic and M. Vojnovic, Q. Zhang*
    STACS 2015
  11. Satisfiability of Ordering CSPs Above Average Is Fixed-Parameter Tractable (pdf)
    Konstantin Makarychev, Yury Makarychev, Yuan Zhou*
    FOCS 2015
  12. Constant Factor Lasserre Integrality Gaps for Graph Partitioning Problems
    Venkatesan Guruswami, Ali Kemal Sinop, Yuan Zhou*
    SIAM Journal on Optimization 24-4 (2014), pp. 1698-1717
  13. Communication Complexity of Approximate Maximum Matching in Distributed Graph Data
    Z. Huang, B. Radunovic, M. Vojnovic and Q. Zhang*
    MASSIVE 14
  14. Robust Set Reconciliation
    D. Chen, C. Konrad, K. Y, W. Yu and Q. Zhang*
    SIGMOD 14
  15. Online Load Balancing for MapReduce with Skewed Data Input.
    Y. Le, J.C. Liu, F. Ergun, D. Wang.
    INFOCOM 14
  16. Palindrome Recognition in the Streaming Model.
    P. Berenbrink, F. Ergun, F. Mallmann-Trenn, E. Sadeqi-Azer*
    STACS 2014
  17. Network Design for Tolerating Multiple Link Failures Using Fast Re-Route (FRR) R. Sinha, F. Ergun, K. Oikonomou, K. K. Ramakrishnan.
    DRCN 2014
  18. An Optimal Lower Bound for Distinct Elements in the Message Passing Model 
    D. P. Woodruff and Q. Zhang*
    SODA 2014.
  19. Optimal PAC Multiple Arm Identification with Applications to Crowdsourcing
    Yuan Zhou, Xi Chen, Jian Li
    ICML 2014
  20. Optimal strong parallel repetition for projection games on low threshold rank   Madhur Tulsiani, John Wright, Yuan Zhou*
    ICALP 2014
  21. Locally Testable Codes and Cayley Graphs
    Parikshit Gopalan, Salil Vadhan, Yuan Zhou*
    ITCS 2014 
  22. Approximation Schemes via Sherali-Adams Hierarchy for Dense Constraint Satisfaction Problems and Assignment Problems
    Yuichi Yoshida, Yuan Zhou*
    ITCS 2014 
  23. Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs
    Ryan O’Donnell, John Wright, Chenggang Wu, Yuan Zhou*
    SODA 2014 
  24. Hypercontractive inequalities via SOS, and Frankl-Rödl graph
    Manuel Kauers, Ryan O’Donnell, Li-Yang Tan, Yuan Zhou*
    SODA 2014
  25. When Distributed Computation is Communication Expensive
    D. P. Woodruff and Q. Zhang*
    DISC 2013
    Invited to the special issue for DISC, 2013, in Distributed Computing.
  26. Subspace Embeddings and Lp Regression Using Exponential Random Variables
    D. P. Woodruff and Q. Zhang*
    COLT 2013
  27. Approximability and proof complexity
    Ryan O’Donnell, Yuan Zhou*
    SODA 2013
  28. Parikh Matching in the Streaming Model
    L. K. Lee, M. Lewenstein and Q. Zhang*
    SPIRE 2012
  29. Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance
    E. Verbin and Q. Zhang*
    ICALP 2012
  30. Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks
    Z. Huang, K. Yi, and Q. Zhang*
    PODS 2012
  31. Tight Bounds for Distributed Functional Monitoring
    D. P. Woodruff and Q. Zhang*
    STOC 2012
  32. Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy
    J. M. Phillips, E. Verbin and Q. Zhang*
    SODA 2012
  33. Approximating bounded occurrence ordering CSPs
    Venkatesan Guruswami, Yuan Zhou*
    APPROX 2012 
  34. Hypercontractivity, Sum-of-Squares Proofs, and their Applications
    Boaz Barak, Fernando Brandão, Aram Harrow, Jonathan Kelner, David Steurer, Yuan Zhou*
    STOC 2012 
  35. Linear programming, width-1 CSPs, and robust satisfaction
    Gabor Kun, Ryan O’Donnell, Suguru Tamaki, Yuichi Yoshida, Yuan Zhou*
    ITCS 2012
  36. Polynomial integrality gaps for strong SDP relaxations of Densest k-Subgraph
    Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, Yuan Zhou*
    SODA 2012 
  37. Approximation Algorithms and Hardness of the k-Route Cut Problem
    Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou*
    SODA 2012
  38. Sorting, Searching and Simulation in the MapReduce Framework
    M. T. Goodrich, N. Sitchinava and Q. Zhang*
    ISSAC 2011
  39. Edit Distance to Monotonicity in Sliding Windows
    H. L. Chan, T. W. Lam, L. K. Lee, J. Pan, H. F. Ting and Q. Zhang*
    ISAAC 2011
  40. Black-box reductions in mechanism design
    Zhiyi Huang, Lei Wang, Yuan Zhou*
    APPROX 2011
  41. The Fourier Entropy-Influence Conjecture for certain classes of Boolean functions
    Ryan O’Donnell, John Wright, Yuan Zhou*
    ICALP 2011 
  42. Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups
    Ryan O’Donnell, Yi Wu, Yuan Zhou*
    CCC 2011 
  43. Finding almost-perfect graph bisections
    Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou*
    ITCS 2011 
  44. Optimal lower bounds for locality sensitive hashing (except when q is tiny)
    Ryan O’Donnell, Yi Wu, Yuan Zhou*
    ITCS 2011
    ACM Transactions on Computation Theory 6(1), Article 5 (March 2014) 
  45. Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set
    Venkatesan Guruswami, Yuan Zhou*
    SODA 2011
    Theory of Computing 8, pp. 239-267 (2012)
  46. Approximation Algorithms for Spanner Problems and Directed Steiner Forest
    P. Berman, A. Bhattacharyya, K. Makarychev, S. Raskhodnikova, G. Yaroslavtsev*
    ICALP 2011
  47. Steiner Transitive-Closure Spanners of d-Dimensional Posets 
    P. Berman, A. Bhattacharyya, E. Grigorescu, S. Raskhodnikova, D. Woodruff, G. Yaroslavtsev*
    ICALP 2011
  48. Periodicity in Streams.
    F. Ergun, H. Jowhari, M. Saglam*
    RANDOM 2010
  49. Clustering with Diversity
    J. Li, K. Yi and Q. Zhang*
    ICALP 2010
  50. Cache-Oblivious Hashing
    R. Pagh, Z. Wei, K. Yi and Q. Zhang*
    PODS 2010
    Journal version in Algorithmica
  51. Optimal Sampling From Distributed Streams
    G. Cormode, S. Muthukrishnan, K. Yi and Q. Zhang*
    PODS 2010
    Invited to Journal of the ACM
  52. The Limits of Buffering: A Tight Lower Bound for Dynamic Membership in the External Memory Model
    E. Verbin and Q. Zhang*
    STOC 2010
    Journal version in SIAM Journal of Computing
  53. On the Cell Probe Complexity of Dynamic Membership
    K. Yi and Q. Zhang*
    SODA 2010
  54. Dynamic External Hashing: The Limit of Buffering
    Z. Wei, K. Yi and Q. Zhang*
    SPAA 2009
  55. Optimal Tracking of Distributed Heavy Hitters and Quantiles
    K. Yi and Q. Zhang*
    PODS 2009
    Journal version in Algorithmica
  56. Revenue Generation for Truthful Spectrum Auction in Dynamic Spectrum Access
    J. Jia, Q. Zhang, Q. Zhang and M. Liu
    MobiHoc 2009
  57. Multi-Dimensional Online Tracking
    K. Yi and Q. Zhang*
    SODA 2009
    Journal version in ACM Transactions on Algorithms
  58. Finding Frequent Items in Probabilistic Data
    Q. Zhang, F. Li and K. Yi
    SIGMOD 2008
  59. On Distance to Monotonicity and Longest Increasing Subsequence of a Data Stream.
    F. Ergun, H. Jowhari*
    SODA 2008

Note: Papers marked with * use alphabetic ordering of authors, following the convention of theoretical computer science.