[Research] [CV] [Activities]

News: I will join Indiana University Bloomington as an assistant professor

Research Interests

• Algorithms and data structures: algorithms for massive data; data streams; algorithms on distributed data; data structures; database algorithms.
  
• Complexity: communication complexity.
  

Teaching

• Summer 2012: Linear Sketch and Its Applications in Data Streams and Compressive Sensing
• Spring 2011, Q4: Streaming Algorithms

Service

• Committee TAMC 2013

Publications / Articles

1. When Distributed Computation does not Help
   D. P. Woodruff and Q. Zhang*
   Submitted. Preliminary version in arXiv.
   
   
2. Subspace Embeddings and Lp Regression Using Exponential Random Variables
   D. P. Woodruff and Q. Zhang*
   Proc. Conference on Learning Theory (COLT 13), to appear. Princeton, NJ, U.S.A, June 2013.
   
   
3. Parikh Matching in the Streaming Model
   L. K. Lee, M. Lewenstein and Q. Zhang*
   Proc. International Symposium on String Processing and Information Retrieval (SPIRE 12), pages 336-341. Cartagena de Indias, Colombia, October 2012.
   
   
4. Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance [talk]
   E. Verbin and Q. Zhang*
   Proc. International Colloquium on Automata, Languages and Programming (ICALP 12), pages 834-845. Warwick, U.K., July 2012.
   
   
5. Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks
   Z. Huang, K. Yi, and Q. Zhang*
   Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 12), pages 295-306. Scottsdale, Arizona, U.S.A., May 2012.
   
   
6. Tight Bounds for Distributed Functional Monitoring [conf. talk]
   D. P. Woodruff and Q. Zhang*
   Proc. ACM Symposium on Theory of Computing (STOC 12), pages 941-960. New York, NY, U.S.A., May 2012.
   
   • We resolve several fundamental questions in the area of distributed functional monitoring.
   • A new technique called "composition" is proposed for randomized multiparty communication complexity.

7. Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy [conf. talk]
   J. M. Phillips, E. Verbin and Q. Zhang*
   Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 12), pages 486-501. Kyoto, Japan. January 2012.
   
   • A general technique called "symmetrization" is proposed for randomized multiparty communication complexity.

8. Sorting, Searching and Simulation in the MapReduce Framework
   M. T. Goodrich, N. Sitchinava and Q. Zhang*
   Proc. International Symposium on Algorithms and Computation (ISAAC 11), pages 374-383. Yokohama, Japan. December 2011.
   Preliminary version in arXiv.
   
   
9. Edit Distance to Monotonicity in Sliding Windows
   H. L. Chan, T. W. Lam, L. K. Lee, J. Pan, H. F. Ting and Q. Zhang*
   Proc. International Symposium on Algorithms and Computation (ISAAC 11), pages 564-573. Yokohama, Japan. December 2011.
   
   
10. Communication-Efficient Algorithms for Tracking Distributed Data Streams [defence talk]
    Qin Zhang*
    Ph.D. Thesis. HKUST, May 2010.
    
    
11. Clustering with Diversity [talk]
    J. Li, K. Yi and Q. Zhang*
    Proc. International Colloquium on Automata, Languages and Programming (ICALP 10), pages 188-200. Bordeaux, France. July 2010.
    
    
12. Cache-Oblivious Hashing
    R. Pagh, Z. Wei, K. Yi and Q. Zhang*
    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, to appear.
    
    
13. Optimal Sampling From Distributed Streams
    G. Cormode, S. Muthukrishnan, K. Yi and Q. Zhang*
    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].
    • In the distributed streaming model, random sampling is even easier than counting.

14. The Limits of Buffering: A Tight Lower Bound for Dynamic Membership in the External Memory Model [talk]
    E. Verbin and Q. Zhang*
    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].
    • Buffering is impossible to achieve in the EM model with sublogarithmic query time.
    • EM model is a "clearner'' model than RAM in certain perspectives.

15. On the Cell Probe Complexity of Dynamic Membership [conf. talk]
    K. Yi and Q. Zhang*
    Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 10), pages 123-133. Austin, TX, U.S.A., January 2010.
    
    
16. Dynamic External Hashing: The Limit of Buffering [conf. talk]
    Z. Wei, K. Yi and Q. Zhang*
    Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 09), pages 253-259. Calgary, Canada, August 2009.
    
    
17. Optimal Tracking of Distributed Heavy Hitters and Quantiles [conf. talk]
    K. Yi and Q. Zhang*
    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, volume 65, issue 1, pages 206-223, January 2013 [Link].
    
    
18. Revenue Generation for Truthful Spectrum Auction in Dynamic Spectrum Access
    J. Jia, Q. Zhang, Q. Zhang and M. Liu
    Proc. ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 09), pages 3-12. New Orleans, LA, U.S.A., May 2009.
    
    
19. Multi-Dimensional Online Tracking [conf. talk]
    K. Yi and Q. Zhang*
    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].
    • A new and very natural class of online problems is studied.

20. Finding Frequent Items in Probabilistic Data [conf. talk]
    Q. Zhang, F. Li and K. Yi
    Proc. ACM SIGMOD International Conference on Management of Data (SIGMOD 08), pages 819-832. Vancouver, Canada, June 2008.
    
    
21. Shannon Coding for the Discrete Noiseless Channel and Related Problems [conf. talk]
    M. Du, M. J. Golin and Q. Zhang*
    Working paper. Preliminary version presented in AAAC 2008. Hong Kong, April, 2008.
    
    
22. The Art of Metric Embeddings -- A technique oriented approach [defence talk]
    Qin Zhang*
    Ph.D. Qualify Examination, HKUST, August 2007.
    
    Note: Papers marked with * use alphabetic ordering of authors, following the convention of theoretical computer science.
    

Links

• Reading Library
• Photo Album
• Blog
• Reading Group
• Hobbies

Last Updated: May 19, 2013