Qin Zhang

Assistant Professor

Computer Science Department,
Indiana University Bloomington,
Luddy Hall, RM 3128,
700 North Woodlawn Avenue,
Bloomington, IN 47405, 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]

Our Algorithm Group is recruiting! For prospective students: If you are interested in working with me as a PhD student,
     please send an email to qzhangcs@indiana.edu. See here for the recruit advertisement.


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

Current Projects

Teaching

Services

Students

Some Talks

Some Papers [ Full List ][ DBLP ]

  1. Distributed Partial Clustering (preliminary full version, 19 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

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

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


    This follow-up work (SIGMOD 16) extends the study to the data stream model.

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

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

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

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

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

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

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

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