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] [CV] [Publication] [Activities]

I might have lost many emails in the past few years due to an unexpected (and hard to fix) issue in the IU email spam filtering system.
If you cannot reach me by my IU email, please try qzhangcs@gmail.com

Research Interests


Current Teaching



Some Papers [ Full List ][ DBLP ]

  1. 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), to appear. Baltimore, MD, U.S.A., November 2019.

    This follow-up work (FOCS 20) extends the work to top-k arm identifications, and shows a separation between the top-1 arm identification and the top-k arm identifications.
    This follow-up work (SPAA 24) extends the work to the heterogeneous collaborative learning (CL) model, and shows a separation between the homogeneous CL model and the heterogeneous CL model for adaptive algorithms.

  2. 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.
    Invited to special issue for SPAA 2017 papers in ACM Transactions on Parallel Computing (TOPC)
    Best Paper Award

    This follow-up work (NIPS 18) gives a more practical algorithm for distributed clustering with outliers.

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

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

    This follow-up work (SODA 14) resolves the communication complexity of distinct elements in all parameters.

  5. Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy (preliminary full version, 22 pages) [conf. talk]
    with J. M. Phillips and 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].

  6. 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].

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

    Note: In all papers above, authors are ordered alphabetically.