Qin Zhang

Professor in Computer Science

Adjunct Professor in Mathematics

Indiana University Bloomington,
Luddy Hall, RM 3044,
700 North Woodlawn Avenue,
Bloomington, IN 47408-3901, USA

Email: qzhangcs@indiana.edu

Before joining IU, I spent a couple of great years at Theory Group, IBM Almaden Research Center,
      and Center for Massive Data Algorithmics, Aarhus University.
I obtained my PhD at Department of Computer Science and Engineering, HKUST.

[Home] [Publication] [Activities]

Papers

Note: In all papers, except mentioned otherwise, authors are ordered alphabetically.
  1. Communication-Efficient Collaborative Regret Minimization in Multi-Armed Bandits
    with N. Karpov
    Proc. AAAI Conference on Artificial Intelligence (AAAI 24). Vancouver, Canada. February 2024.

  2. MinJoin++: A Fast Algorithm for String Similarity Joins under Edit Distance
    with N. Karpov and H. Zhang
    VLDB Journal. Published in August 2023.

  3. SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins.
    with N. Karpov
    Proc. International Conference on Very Large Databases (VLDB 23). Vancouver, Canada. August-September 2023.

  4. Communication-Efficient Collaborative Best Arm Identification
    with N. Karpov
    Proc. AAAI Conference on Artificial Intelligence (AAAI 23). Washington, D.C., USA. February 2023.

  5. Meta Proximal Policy Optimization for Cooperative Multi-Agent Continuous Control
    B. Fang, Z. Peng, H. Sun, and Q. Zhang (by contribution)
    Proc. International Joint Conference on Neural Networks (IJCNN 22). Padova, Italy, July 2022.

  6. Technical perspective: Can data structures treat us fairly?
    Q. Zhang
    Communications of the ACM 65(8): 82, 2022.

  7. Instance-Sensitive Algorithms for Pure Exploration in Multinomial Logit Bandit
    with N. Karpov
    Proc. AAAI Conference on Artificial Intelligence (AAAI 22). Vancouver, February-March 2022.

  8. Technical Perspective: Fair Near Neighbor Search via Sampling
    Q. Zhang
    SIGMOD Record 50(1): 41, 2021.

  9. Learning to Cluster via Same-Cluster Queries
    with Y. Li and Y. Song
    Proc. ACM International Conference on Information and Knowledge Management (CIKM 21). Virtual conference, November 2021.

  10. Batched Coarse Ranking in Multi-Armed Bandits
    with N. Karpov
    Proc. Annual Conference on Neural Information Processing Systems (NeurIPS 20). Virtual conference, December 2020.

  11. Collaborative Top Distribution Identifications with Limited Interaction (preliminary full version, 47 pages)
    with N. Karpov and Y. Zhou
    Proc. IEEE Symposium on Foundations of Computer Science (FOCS 20), 160-171. Virtual conference, November 2020.

  12. Multinomial Logit Bandit with Low Switching Cost (preliminary full version, 25 pages)
    with K. Dong, Y. Li, and Y. Zhou
    Proc. International Conference on Machine Learning (ICML 20), 2607-2615. Virtual conference, July 2020.

  13. MinSearch: An Efficient Algorithm for Similarity Search under Edit Distance
    with H. Zhang
    Proc. ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 20), pages 566-576. Virtual conference, August 2020.

  14. A Multi-criteria Approximation Algorithm for Influence Maximization with Probabilistic Guarantees.
    with M. Khan, G. Pandurangan, N. D. Pham, and A. Vullikanti
    Proc. SIAM Symposium on Algorithm Engineering and Experiments (ALENEX 20), pages 81-93. Salt Lake City, UT, U.S.A., January 2020.

  15. Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits (preliminary full version, 37 pages) [conf. talk]
    with C. Tao and Y. Zhou
    Proc. IEEE Symposium on Foundations of Computer Science (FOCS 19), pages 126-146. Baltimore, MD, U.S.A., November 2019.

  16. MinJoin: Efficient Edit Similarity Joins via Local Hash Minima
    with H. Zhang
    Proc. ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 19), oral presentation, pages 1093-1103. Anchorage, AK, U.S.A., August 2019.

  17. Distributed and Streaming Linear Programming in Low Dimensions
    with S. Assadi and N. Karpov
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 19), pages 236-253. Amsterdam, The Netherlands, June-July 2019.
    Invited to the special issue for PODS 2019 in ACM Transactions on Database Systems (TODS).

  18. Tight Bounds for Collaborative PAC Learning via Multiplicative Weights
    with J. Chen and Y. Zhou
    Proc. Annual Conference on Neural Information Processing Systems (NeurIPS 18), pages 3602-3611. Montreal, Canada, December 2018.

  19. A Practical Algorithm for Distributed Clustering and Outlier Detection
    with J. Chen and E. Sadeqi-Azer
    Proc. Annual Conference on Neural Information Processing Systems (NeurIPS 18), pages 2253-2262. Montreal, Canada, December 2018.

  20. Smooth q-Gram, and Its Applications to Detection of Overlaps among Long, Error-Prone Sequencing Reads
    H. Zhang, Q. Zhang and H. Tang   (by contribution)
    Proc. ACM International Conference on Information and Knowledge Management (CIKM 18), pages 267-276. Turin, Italy, October 2018.
    Journal version (together with Y. Song) in Bioinformatics
    under the title "Overlap Detection on Long, Error-Prone Sequencing Reads via Smooth q-Gram". [Link]

  21. Distinct Sampling on Streaming Data with Near-Duplicates
    with J. Chen
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 18), pages 369-382. Houston, TX, U.S.A., June 2018.

  22. Distributed Statistical Estimation of Matrix Products with Applications [conf. talk]
    with D. P. Woodruff
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 18), pages 383-394. Houston, TX, U.S.A., June 2018.

  23. Communication-Efficient Distributed Skyline Computation
    with H. Zhang
    Proc. ACM International Conference on Information and Knowledge Management (CIKM 17), pages 437-446. Singapore, November 2017.

  24. A Concise Forwarding Information Base for Scalable and Fast Name Switching
    Y. Yu, D. Belazzougui, C. Qian and Q. Zhang   (by contribution)
    Proc. IEEE International Conference on Network Protocols (ICNP 17), to appear. Toronto, Canada, October 2017.
    Journal version in IEEE/ACM Transactions on Networking (TON)
    under the title "Memory-efficient and Ultra-fast Network Lookup and Forwarding using Othello Hashing", 26(3): 1151-1164 (2018). [Link].

  25. EmbedJoin: Efficient Edit Similarity Joins via Embeddings
    with H. Zhang
    Proc. ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 17), oral presentation, pages 585-594. Halifax, Nova Scotia, Canada, August 2017.

  26. Adaptive Multiple-Arm Identification (preliminary full version, 30 pages)
    with J. Chen, X. Chen and Y. Zhou
    Proc. International Conference on Machine Learning (ICML 17), pages 722-730. Sydney, Australia, August 2017.

  27. Distributed Partial Clustering (preliminary full version, 20 pages) [conf. talk]
    with S. Guha and Y. Li
    Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 17), pages 143-152. Washington D.C., U.S.A., July 2017.
    Best Paper Award
    Invited to special issue for SPAA 2017 papers in ACM Transactions on Parallel Computing (TOPC). [Link].

  28. Bias-Aware Sketches
    with J. Chen
    Proc. International Conference on Very Large Databases (VLDB 17), pages 961-972. Munich, Germany, August-September 2017.

  29. Improved Algorithms for Distributed Entropy Monitoring
    with J. Chen
    Algorithmica (Algorithmica), volume 78, issue 3, pages 1041-1066, July 2017.

  30. Submodular Maximization over Sliding Windows
    with J. Chen and H. L. Nguyen
    Manuscript, 2016.

  31. Communication-Optimal Distributed Clustering
    with J. Chen, H. Sun and D. Woodruff
    Proc. Annual Conference on Neural Information Processing Systems (NIPS 16), pages 3720-3728. Barcelona, Spain, December 2016.

  32. Edit Distance: Sketching, Streaming and Document Exchange (preliminary full version, 30 pages) [conf. talk]
    with D. Belazzougui
    Proc. IEEE Symposium on Foundations of Computer Science (FOCS 16), pages 51-60. New Brunswick, NJ, U.S.A., October 2016.

  33. Streaming Algorithms for Robust Distinct Elements
    with D. Chen
    Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD 16), pages 1433-1447. San Francisco, CA, U.S.A., June 2016.

  34. On Sketching Quadratic Forms (preliminary full version, 47 pages)
    with A. Andoni, J. Chen, R. Krauthgamer, B. Qin and D. P. Woodruff
    Proc. Innovations in Theoretical Computer Science (ITCS 16), pages 311-319. Cambridge, MA, U.S.A., January 2016.

  35. Communication-Efficient Computation on Distributed Noisy Datasets [conf. talk]
    Q. Zhang
    Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 15), pages 313-322. Portland, Oregon, U.S.A., June 2015.

  36. The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication
    with D. Van Gucht, R. Williams and D. P. Woodruff
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 15), pages 199-212. Melbourne, VIC, Australia, May-June 2015.

  37. Communication Complexity of Approximate Matching in Distributed Graphs
    with Z. Huang, B. Radunovic and M. Vojnovic
    Proc. Symposium on Theoretical Aspects of Computer Science (STACS 15), pages 460-473. Munich, Germany, March 2015.

  38. Robust Set Reconciliation
    with D. Chen, C. Konrad, K. Yi and W. Yu
    Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD 14), pages 135-146. Snowbird, UT, U.S.A., June 2014.
    See an earlier version of this paper for the lower bound proofs.

  39. An Optimal Lower Bound for Distinct Elements in the Message Passing Model
    with D. P. Woodruff
    Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 14), pages 718-733. Portland, OR, U.S.A., January 2014.

  40. When Distributed Computation is Communication Expensive (preliminary full version) [talk]
    with D. P. Woodruff
    Proc. International Symposium on Distributed Computing (DISC 13), pages 16-30. Jerusalem, Israel, October 2013.
    Invited to the special issue for DISC 2013 in Distributed Computing , volume 30, issue 5, pages 309-323, October 2017. [Link].

  41. Subspace Embeddings and Lp Regression Using Exponential Random Variables (preliminary full version, 27 pages) [conf. talk]
    with D. P. Woodruff
    Proc. Conference on Learning Theory (COLT 13), pages 546-567. Princeton, NJ, U.S.A., June 2013.

  42. Parikh Matching in the Streaming Model
    with L. K. Lee and M. Lewenstein
    Proc. International Symposium on String Processing and Information Retrieval (SPIRE 12), pages 336-341. Cartagena de Indias, Colombia, October 2012.

  43. Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance [talk]
    with E. Verbin
    Proc. International Colloquium on Automata, Languages and Programming (ICALP 12), pages 834-845. Warwick, U.K., July 2012.

  44. Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks
    with Z. Huang and K. Yi
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 12), pages 295-306. Scottsdale, Arizona, U.S.A., May 2012.
    Journal version in Algorithmica (Algorithmica). [Link].

  45. Tight Bounds for Distributed Functional Monitoring (preliminary full version, 50 pages) [conf. talk]
    with D. P. Woodruff
    Proc. ACM Symposium on Theory of Computing (STOC 12), pages 941-960. New York, NY, U.S.A., May 2012.

  46. Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy (preliminary full version, 22 pages) [conf. talk]
    with J. M. Phillips, E. Verbin
    Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 12), pages 486-501. Kyoto, Japan, January 2012.
    Journal version in SIAM Journal of Computing (SICOMP), volume 45, issue 1, pages 174-196, February 2016 [Link].

  47. Sorting, Searching and Simulation in the MapReduce Framework
    with M. T. Goodrich and N. Sitchinava
    Proc. International Symposium on Algorithms and Computation (ISAAC 11), pages 374-383. Yokohama, Japan, December 2011.
    Preliminary version in arXiv.

  48. Edit Distance to Monotonicity in Sliding Windows
    with H. L. Chan, T. W. Lam, L. K. Lee, J. Pan and H. F. Ting
    Proc. International Symposium on Algorithms and Computation (ISAAC 11), pages 564-573. Yokohama, Japan, December 2011.

  49. Clustering with Diversity [talk]
    with J. Li and K. Yi
    Proc. International Colloquium on Automata, Languages and Programming (ICALP 10), pages 188-200. Bordeaux, France, July 2010.

  50. Cache-Oblivious Hashing
    with R. Pagh, Z. Wei and K. Yi
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 10), pages 297-304. Indianapolis, IN, U.S.A., June 2010.
    Journal version in Algorithmica (Algorithmica), volume 69, issue 4, pages 864-883, August 2014.

  51. Optimal Sampling From Distributed Streams (preliminary full version, 25 pages) [talk]
    with G. Cormode, S. Muthukrishnan and K. Yi
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 10), pages 77-86. Indianapolis, IN, U.S.A., June 2010.
    Invited to Journal of the ACM (JACM), volume 59, issue 2, pages 10:1-10:25, April 2012 [Link].

  52. The Limits of Buffering: A Tight Lower Bound for Dynamic Membership in the External Memory Model (preliminary full version, 18 pages) [talk]
    with E. Verbin
    Proc. ACM Symposium on Theory of Computing (STOC 10), pages 447-456. Cambridge, MA, U.S.A., June 2010.
    Journal version in SIAM Journal of Computing (SICOMP), volume 42, issue 1, pages 212-229, January 2013 [Link].

  53. On the Cell Probe Complexity of Dynamic Membership [conf. talk]
    with K. Yi
    Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 10), pages 123-133. Austin, TX, U.S.A., January 2010.

  54. Dynamic External Hashing: The Limit of Buffering [conf. talk]
    with Z. Wei and K. Yi
    Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 09), pages 253-259. Calgary, Canada, August 2009.

  55. Optimal Tracking of Distributed Heavy Hitters and Quantiles (preliminary full version) [conf. talk]
    with K. Yi
    Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 09), pages 167-174. Providence, RI, U.S.A., June 2009.
    Journal version in Algorithmica (Algorithmica), volume 65, issue 1, pages 206-223, January 2013 [Link].

  56. Multi-Dimensional Online Tracking (preliminary full version, 18 pages) [conf. talk]
    with K. Yi
    Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 09), pages 1098-1107. New York, NY, U.S.A., January 2009.
    Journal version in ACM Transactions on Algorithms (TALG), volume 8, issue 2, pages 12:1-12:16, April 2012 [Link].

  57. Revenue Generation for Truthful Spectrum Auction in Dynamic Spectrum Access
    J. Jia, Q. Zhang, Q. Zhang and M. Liu   (by contribution)
    Proc. ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 09), pages 3-12. New Orleans, LA, U.S.A., May 2009.

  58. Finding Frequent Items in Probabilistic Data [conf. talk]
    Q. Zhang, F. Li and K. Yi   (by contribution)
    Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD 08), pages 819-832. Vancouver, Canada, June 2008.