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*
    Proc. Annual Conference on Neural Information Processing Systems (NIPS 16)
  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. Private Algorithms for the Protected in Social Network Search
    M. Kearns, A. Roth, S. Wu, G. Yaroslavtsev*
    PNAS 2016 (Proceedings of the National Academy of Sciences)
  9. Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model
    S. Assadi, S. Khanna, Y. Li, G. Yaroslavtsev*
    SODA 2016
  10. Communication-Efficient Computation on Distributed Noisy Datasets
    Q. Zhang*
    SPAA 15
  11. The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication 
    D. Van Gucht, R. Williams D. P. Woodruff, Q. Zhang*
    PODS 15
  12. Communication Complexity of Approximate Matching in Distributed Graphs 
    Z. Huang, B. Radunovic and M. Vojnovic, Q. Zhang*
    STACS 2015
  13. Satisfiability of Ordering CSPs Above Average Is Fixed-Parameter Tractable (pdf)
    Konstantin Makarychev, Yury Makarychev, Yuan Zhou*
    FOCS 2015
  14. Near Optimal LP Rounding Algorithm for Correlation Clustering on Complete and Complete k-partite Graphs
    S. Chawla, K. Makarychev, T. Schramm, G. Yaroslavtsev*
    STOC 2015
  15. Amplification of One-Way Information Complexity via Codes and Noise Sensitivity
    M. Molinaro, D. Woodruff, G. Yaroslavtsev*
    ICALP 2015
  16. 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
  17. Communication Complexity of Approximate Maximum Matching in Distributed Graph Data
    Z. Huang, B. Radunovic, M. Vojnovic and Q. Zhang*
    MASSIVE 14
  18. Robust Set Reconciliation
    D. Chen, C. Konrad, K. Y, W. Yu and Q. Zhang*
    SIGMOD 14
  19. Online Load Balancing for MapReduce with Skewed Data Input.
    Y. Le, J.C. Liu, F. Ergun, D. Wang.
    INFOCOM 14
  20. Palindrome Recognition in the Streaming Model.
    P. Berenbrink, F. Ergun, F. Mallmann-Trenn, E. Sadeqi-Azer*
    STACS 2014
  21. Network Design for Tolerating Multiple Link Failures Using Fast Re-Route (FRR) R. Sinha, F. Ergun, K. Oikonomou, K. K. Ramakrishnan.
    DRCN 2014
  22. An Optimal Lower Bound for Distinct Elements in the Message Passing Model 
    D. P. Woodruff and Q. Zhang*
    SODA 2014.
  23. Optimal PAC Multiple Arm Identification with Applications to Crowdsourcing
    Yuan Zhou, Xi Chen, Jian Li
    ICML 2014
  24. Optimal strong parallel repetition for projection games on low threshold rank   Madhur Tulsiani, John Wright, Yuan Zhou*
    ICALP 2014
  25. Locally Testable Codes and Cayley Graphs
    Parikshit Gopalan, Salil Vadhan, Yuan Zhou*
    ITCS 2014 
  26. Approximation Schemes via Sherali-Adams Hierarchy for Dense Constraint Satisfaction Problems and Assignment Problems
    Yuichi Yoshida, Yuan Zhou*
    ITCS 2014 
  27. Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs
    Ryan O’Donnell, John Wright, Chenggang Wu, Yuan Zhou*
    SODA 2014 
  28. Hypercontractive inequalities via SOS, and Frankl-Rödl graph
    Manuel Kauers, Ryan O’Donnell, Li-Yang Tan, Yuan Zhou*
    SODA 2014
  29. Lp-Testing
    P. Berman, S. Raskhodnikova, G. Yaroslavtsev*
    STOC 2014
  30. Parallel Algorithms for Geometric Graph Problems
    A. Andoni, A. Nikolov, K. Onak, G. Yaroslavtsev*
    STOC 2014
  31. Certifying Equality with Limited Interaction
    J. Brody, A. Chakrabarti, R. Kondapally, D. Woodruff, G. Yaroslavtsev*
    RANDOM 2014
  32. Beyond Set Disjointness: The Communication Complexity of Finding the Intersection
    J. Brody, A. Chakrabarti, R. Kondapally, D. Woodruff, G. Yaroslavtsev*
    PODC 2014
  33. Lower Bounds for Testing Properties of Functions over Hypergrid Domains
    E. Blais, S. Raskhodnikova, G. Yaroslavtsev*
    CCC 2014
  34. 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.
  35. Subspace Embeddings and Lp Regression Using Exponential Random Variables
    D. P. Woodruff and Q. Zhang*
    COLT 2013
  36. Approximability and proof complexity
    Ryan O’Donnell, Yuan Zhou*
    SODA 2013
  37. Beating the Direct Sum Theorem in Communication Complexity with Applications to Sketching
    M. Molinaro, D. Woodruff, G. Yaroslavtsev*
    SODA 2013
  38. Learning Pseudo-Boolean k-DNF and Submodular Functions
    S. Raskhodnikova, G. Yaroslavtsev*
    SODA 2013
  39. Accurate and Efficient Private Release of Datacubes and Contingency Tables
    G. Yaroslavtsev, G. Cormode, C. M. Procopiuc, D. Srivastava
    ICDE 2013
  40. Parikh Matching in the Streaming Model
    L. K. Lee, M. Lewenstein and Q. Zhang*
    SPIRE 2012
  41. Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance
    E. Verbin and Q. Zhang*
    ICALP 2012
  42. Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks
    Z. Huang, K. Yi, and Q. Zhang*
    PODS 2012
  43. Tight Bounds for Distributed Functional Monitoring
    D. P. Woodruff and Q. Zhang*
    STOC 2012
  44. Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy
    J. M. Phillips, E. Verbin and Q. Zhang*
    SODA 2012
  45. Approximating bounded occurrence ordering CSPs
    Venkatesan Guruswami, Yuan Zhou*
    APPROX 2012 
  46. Hypercontractivity, Sum-of-Squares Proofs, and their Applications
    Boaz Barak, Fernando Brandão, Aram Harrow, Jonathan Kelner, David Steurer, Yuan Zhou*
    STOC 2012 
  47. Linear programming, width-1 CSPs, and robust satisfaction
    Gabor Kun, Ryan O’Donnell, Suguru Tamaki, Yuichi Yoshida, Yuan Zhou*
    ITCS 2012
  48. Polynomial integrality gaps for strong SDP relaxations of Densest k-Subgraph
    Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, Yuan Zhou*
    SODA 2012 
  49. Approximation Algorithms and Hardness of the k-Route Cut Problem
    Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou*
    SODA 2012
  50. Primal-Dual Algorithms for Node-Weighted Network Design in Planar Graphs 
    P. Berman, G. Yaroslavtsev*
    APPROX 2012
  51. Sorting, Searching and Simulation in the MapReduce Framework
    M. T. Goodrich, N. Sitchinava and Q. Zhang*
    ISSAC 2011
  52. 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
  53. Black-box reductions in mechanism design
    Zhiyi Huang, Lei Wang, Yuan Zhou*
    APPROX 2011
  54. The Fourier Entropy-Influence Conjecture for certain classes of Boolean functions
    Ryan O’Donnell, John Wright, Yuan Zhou*
    ICALP 2011 
  55. Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups
    Ryan O’Donnell, Yi Wu, Yuan Zhou*
    CCC 2011 
  56. Finding almost-perfect graph bisections
    Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou*
    ITCS 2011 
  57. 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) 
  58. 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)
  59. Private Analysis of Graph Structure
    V. Karwa, S. Raskhodnikova, A. Smith, G. Yaroslavtsev*
    VLDB 2011
  60. Approximation Algorithms for Spanner Problems and Directed Steiner Forest
    P. Berman, A. Bhattacharyya, K. Makarychev, S. Raskhodnikova, G. Yaroslavtsev*
    ICALP 2011
  61. Steiner Transitive-Closure Spanners of d-Dimensional Posets 
    P. Berman, A. Bhattacharyya, E. Grigorescu, S. Raskhodnikova, D. Woodruff, G. Yaroslavtsev*
    ICALP 2011
  62. Periodicity in Streams.
    F. Ergun, H. Jowhari, M. Saglam*
    RANDOM 2010
  63. Clustering with Diversity
    J. Li, K. Yi and Q. Zhang*
    ICALP 2010
  64. Cache-Oblivious Hashing
    R. Pagh, Z. Wei, K. Yi and Q. Zhang*
    PODS 2010
    Journal version in Algorithmica
  65. Optimal Sampling From Distributed Streams
    G. Cormode, S. Muthukrishnan, K. Yi and Q. Zhang*
    PODS 2010
    Invited to Journal of the ACM
  66. 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
  67. On the Cell Probe Complexity of Dynamic Membership
    K. Yi and Q. Zhang*
    SODA 2010
  68. Dynamic External Hashing: The Limit of Buffering
    Z. Wei, K. Yi and Q. Zhang*
    SPAA 2009
  69. Optimal Tracking of Distributed Heavy Hitters and Quantiles
    K. Yi and Q. Zhang*
    PODS 2009
    Journal version in Algorithmica
  70. Revenue Generation for Truthful Spectrum Auction in Dynamic Spectrum Access
    J. Jia, Q. Zhang, Q. Zhang and M. Liu
    MobiHoc 2009
  71. Multi-Dimensional Online Tracking
    K. Yi and Q. Zhang*
    SODA 2009
    Journal version in ACM Transactions on Algorithms
  72. Finding Efficient Circuits Using SAT-solvers
    A. Kojevnikov, A. Kulikov, G. Yaroslavtsev*
    SAT 2009
  73. Finding Frequent Items in Probabilistic Data
    Q. Zhang, F. Li and K. Yi
    SIGMOD 2008
  74. 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.