- Near-Optimal Policies for Dynamic Multinomial Logit Assortment Selection Models
Yining Wang, Xi Chen, Yuan Zhou*
NIPS 2018 - Tight Bounds for Collaborative PAC Learning via Multiplicative Weights
Jiecao Chen, Qin Zhang*, Yuan Zhou*
NIPS 2018 - A Practical Algorithm for Distributed Clustering and Outlier Detection
Jiecao Chen, Erfan Sadeqi-Azer, Qin Zhang*
NIPS 2018 - Smooth q-Gram, and Its Applications to Detection of Overlaps among Long, Error-Prone Sequencing Reads
Haoyu Zhang, Qin Zhang* and Haixu Tang
CIKM 2018 - Distinct Sampling on Streaming Data with Near-Duplicates
Jiecao Chen, Qin Zhang*
PODS 18 - Distributed Statistical Estimation of Matrix Products with Applications [conf. talk]
David P. Woodruff, Qin Zhang*
PODS 18 - Best Arm Identification in Linear Bandits with Linear Dimension Dependency [PMLR]
Chao Tao, Saúl A. Blanco, Yuan Zhou*
ICML 2018 - Optimal Design of Process Flexibility for General Production Systems (SSRN)
Xi Chen, Tengyu Ma, Jiawei Zhang, Yuan Zhou*
Operations Research (To appear) - Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints (arXiv)
Jiecao Chen, Xi Chen, Qin Zhang*, Yuan Zhou*
ICML 2017 - Communication-Efficient Distributed Skyline Computation
Haoyu Zhang, Qin Zhang*
CIKM 2017 - Parameterized Algorithms for Constraint Satisfaction Problems Above Average with Global Cardinality Constraints (arXiv)
Xue Chen, Yuan Zhou*
SODA 2017 - Optimal Sparse Designs for Process Flexibility via Probabilistic Expanders (SSRN)
Xi Chen, Jiawei Zhang, Yuan Zhou*
Operations Research 63-5 (2015), pp. 1159-1176 - Communication-Optimal Distributed Clustering
J. Chen, H. Sun, D. Woodruff, Q. Zhang*
NIPS 2016 - Improved Algorithms for Distributed Entropy Monitoring
J. Chen, Q. Zhang*
Algorithmica 2016 - Streaming Algorithms for Robust Distinct Elements
D. Chen, Q.zhang*
SIGMOD 2016 - Edit Distance: Sketching, Streaming and Document Exchange
D. Belazzougui, Q. Zhang*
FOCS 2016 - On Sketching Quadratic Forms
A. Andoni, J. Chen, R. Krauthgamer, B. Qin and D. P. Woodruff, Q. Zhang*
ITCS 2016 - Communication-Efficient Computation on Distributed Noisy Datasets
Q. Zhang*
SPAA 15 - The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication
D. Van Gucht, R. Williams D. P. Woodruff, Q. Zhang*
PODS 15 - Communication Complexity of Approximate Matching in Distributed Graphs
Z. Huang, B. Radunovic and M. Vojnovic, Q. Zhang*
STACS 2015 - Satisfiability of Ordering CSPs Above Average Is Fixed-Parameter Tractable (pdf)
Konstantin Makarychev, Yury Makarychev, Yuan Zhou*
FOCS 2015 - 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 - Communication Complexity of Approximate Maximum Matching in Distributed Graph Data
Z. Huang, B. Radunovic, M. Vojnovic and Q. Zhang*
MASSIVE 14 - Robust Set Reconciliation
D. Chen, C. Konrad, K. Y, W. Yu and Q. Zhang*
SIGMOD 14 - Online Load Balancing for MapReduce with Skewed Data Input.
Y. Le, J.C. Liu, F. Ergun, D. Wang.
INFOCOM 14 - Palindrome Recognition in the Streaming Model.
P. Berenbrink, F. Ergun, F. Mallmann-Trenn, E. Sadeqi-Azer*
STACS 2014 - Network Design for Tolerating Multiple Link Failures Using Fast Re-Route (FRR) R. Sinha, F. Ergun, K. Oikonomou, K. K. Ramakrishnan.
DRCN 2014 - An Optimal Lower Bound for Distinct Elements in the Message Passing Model
D. P. Woodruff and Q. Zhang*
SODA 2014. - Optimal PAC Multiple Arm Identification with Applications to Crowdsourcing
Yuan Zhou, Xi Chen, Jian Li
ICML 2014 - Optimal strong parallel repetition for projection games on low threshold rank Madhur Tulsiani, John Wright, Yuan Zhou*
ICALP 2014 - Locally Testable Codes and Cayley Graphs
Parikshit Gopalan, Salil Vadhan, Yuan Zhou*
ITCS 2014 - Approximation Schemes via Sherali-Adams Hierarchy for Dense Constraint Satisfaction Problems and Assignment Problems
Yuichi Yoshida, Yuan Zhou*
ITCS 2014 - Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs
Ryan O’Donnell, John Wright, Chenggang Wu, Yuan Zhou*
SODA 2014 - Hypercontractive inequalities via SOS, and Frankl-Rödl graph
Manuel Kauers, Ryan O’Donnell, Li-Yang Tan, Yuan Zhou*
SODA 2014 - 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. - Subspace Embeddings and Lp Regression Using Exponential Random Variables
D. P. Woodruff and Q. Zhang*
COLT 2013 - Approximability and proof complexity
Ryan O’Donnell, Yuan Zhou*
SODA 2013 - Parikh Matching in the Streaming Model
L. K. Lee, M. Lewenstein and Q. Zhang*
SPIRE 2012 - Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance
E. Verbin and Q. Zhang*
ICALP 2012 - Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks
Z. Huang, K. Yi, and Q. Zhang*
PODS 2012 - Tight Bounds for Distributed Functional Monitoring
D. P. Woodruff and Q. Zhang*
STOC 2012
- Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy
J. M. Phillips, E. Verbin and Q. Zhang*
SODA 2012 - Approximating bounded occurrence ordering CSPs
Venkatesan Guruswami, Yuan Zhou*
APPROX 2012 - Hypercontractivity, Sum-of-Squares Proofs, and their Applications
Boaz Barak, Fernando Brandão, Aram Harrow, Jonathan Kelner, David Steurer, Yuan Zhou*
STOC 2012 - Linear programming, width-1 CSPs, and robust satisfaction
Gabor Kun, Ryan O’Donnell, Suguru Tamaki, Yuichi Yoshida, Yuan Zhou*
ITCS 2012 - Polynomial integrality gaps for strong SDP relaxations of Densest k-Subgraph
Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, Yuan Zhou*
SODA 2012 - Approximation Algorithms and Hardness of the k-Route Cut Problem
Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, Yuan Zhou*
SODA 2012 - Sorting, Searching and Simulation in the MapReduce Framework
M. T. Goodrich, N. Sitchinava and Q. Zhang*
ISSAC 2011 - 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 - Black-box reductions in mechanism design
Zhiyi Huang, Lei Wang, Yuan Zhou*
APPROX 2011 - The Fourier Entropy-Influence Conjecture for certain classes of Boolean functions
Ryan O’Donnell, John Wright, Yuan Zhou*
ICALP 2011 - Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups
Ryan O’Donnell, Yi Wu, Yuan Zhou*
CCC 2011 - Finding almost-perfect graph bisections
Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou*
ITCS 2011 - 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) - 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) - Approximation Algorithms for Spanner Problems and Directed Steiner Forest
P. Berman, A. Bhattacharyya, K. Makarychev, S. Raskhodnikova, G. Yaroslavtsev*
ICALP 2011 - Steiner Transitive-Closure Spanners of d-Dimensional Posets
P. Berman, A. Bhattacharyya, E. Grigorescu, S. Raskhodnikova, D. Woodruff, G. Yaroslavtsev*
ICALP 2011 - Periodicity in Streams.
F. Ergun, H. Jowhari, M. Saglam*
RANDOM 2010 - Clustering with Diversity
J. Li, K. Yi and Q. Zhang*
ICALP 2010 - Cache-Oblivious Hashing
R. Pagh, Z. Wei, K. Yi and Q. Zhang*
PODS 2010
Journal version in Algorithmica - Optimal Sampling From Distributed Streams
G. Cormode, S. Muthukrishnan, K. Yi and Q. Zhang*
PODS 2010
Invited to Journal of the ACM - 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 - On the Cell Probe Complexity of Dynamic Membership
K. Yi and Q. Zhang*
SODA 2010 - Dynamic External Hashing: The Limit of Buffering
Z. Wei, K. Yi and Q. Zhang*
SPAA 2009 - Optimal Tracking of Distributed Heavy Hitters and Quantiles
K. Yi and Q. Zhang*
PODS 2009
Journal version in Algorithmica - Revenue Generation for Truthful Spectrum Auction in Dynamic Spectrum Access
J. Jia, Q. Zhang, Q. Zhang and M. Liu
MobiHoc 2009 - Multi-Dimensional Online Tracking
K. Yi and Q. Zhang*
SODA 2009
Journal version in ACM Transactions on Algorithms - Finding Frequent Items in Probabilistic Data
Q. Zhang, F. Li and K. Yi
SIGMOD 2008 - 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.