[Research] [CV] [Activities] [Hobbies]

Research Interests

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

Teaching

• Spring 2011, Q4: Streaming Algorithms

Publications / Articles

1. Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance
   E. Verbin and Q. Zhang*
   Proc. International Colloquium on Automata, Languages and Programming (ICALP 12), to appear. Warwick, U.K., July 2012.
   
   
2. 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), to appear. Scottsdale, Arizona, U.S.A., May 2012.
   
   
3. Tight Bounds for Distributed Functional Monitoring
   D. P. Woodruff and Q. Zhang*
   Proc. ACM Symposium on Theory of Computing (STOC 12), to appear. New York, NY, U.S.A., May 2012.
   Preliminary version in arXiv.
   • We resolve several fundamental questions in the area of distributed functional monitoring.
   • Our results also yield significant improvements to classical problems in the standard data stream model.

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

5. 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.
   
   
6. 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.
   
   
7. Communication-Efficient Algorithms for Tracking Distributed Data Streams [defence talk]
   Qin Zhang*
   Ph.D. Thesis. HKUST, May 2010.
   
   
8. 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.
   
   
9. 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.
   
   
10. 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.

11. The Limits of Buffering: A Tight Lower Bound for Dynamic Membership in the External Memory Model (revised version of the conf. paper) [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.
    • Buffering is impossible to achieve in the EM model with sublogarithmic query time.
    • EM model is a "clearner'' model than RAM in certain perspectives.

12. 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.
    
    
13. 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.
    
    
14. 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, accepted in 2011 [Link].
    
    
15. 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.
    
    
16. 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.

17. 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.
    
    
18. 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.
    
    
19. 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

Last Updated: Nov. 22, 2011