Qin Zhang

Associate Professor

Computer Science Department,
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]

We are recruiting! For prospective students: If you are interested in working with me as a PhD student, in Algorithms, Databases, and/or Machine Learning,
     please send an email to qzhangcs@indiana.edu. Fully funded RA positions available.

Internship for international undergraduate students. Please contact me first by email.

I am organizing Theory Seminar. If you wish to give a talk at our seminar, or to join our mailing list please contact me.

The 67th Midwest Theory Day at IU Bloomington (April 15-16, 2017).

Research Interests





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 strong separation between the top-1 arm identification and the top-k arm identifications.

  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.