Algorithms Reading Team

About ART

The Algorithms Reading Team focuses on algorithm-related problems and their applications in various fields. The topics include algorithmic problems encountered in or abstracted from concrete problems in theory, networking, databases, information retrieval and systems. New topics are always welcome.

The objective of the Algorithms Reading Team is to read and understand the most recent works in discrete algorithms, and most importantly (and hopefully) to identify potential topics to work on.

The general format of the meetings will be whiteboard presentations followed by interactive open-problem discussions.


Schedule

In Spring 2005, the regular meetings are in WVH-164 every Friday 15:15-16:45.
Date Time Location Presenter Paper / Topic
01/14/2005 15:30-16:00 WVH-366 Organizational meeting.
01/28/2005 15:15-16:45 WVH-164 Xin Liu F. Dai et al.: An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks.
02/04/2005 15:15-16:45 WVH-164 Guolong Lin S. Arora et al.: Local versus global properties of metric spaces.
02/11/2005 15:15-16:45 WVH-164 Feng Zhu D. Micciancio et al.: Optimal communication complexity of generic multicast key distribution (Eurocrypt 2004).
02/18/2005 15:15-16:45 WVH-164 Robbie Ye S. Muthukrishnan et al.: The Bin-Covering Technique for Thresholding Random Geometric Graph Properties (SODA 2005).
02/25/2005 15:15-16:45 WVH-164 Kofi Laing F. Kuhn et al.: What cannot be computed locally! (PODC 2004)
03/04/2005 Spring break, no meeting.
03/11/2005 15:15-16:45 WVH-164 Ravi Sundaram T. Leighton et al.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms (JACM 1999).
S. Arora et al.: Expander Flows, Geometric Embeddings, and Graph Partitioning (STOC 2004).
03/18/2005 15:15-16:45 WVH-164 April Rasala Lehman (from MIT) Network Capacity. [abstract] [paper] [slides]
03/25/2005 15:15-16:45 WVH-164 Stefano Basagni Exploiting Controlled Sink Mobility for Improving Network Lifetime in Wireless Sensor Networks.

Topics

  1. Near-Collisions of SHA-0. Eli Biham and Rafi Chen. CRYPTO 2004.  [ps] (suggested by Agnes Chan)
  2. SeRLoc: Secure Range-Independent Localization for Wireless Sensor Networks. Loukas Lazos and Radha Poovendran. WiSe 2004. (suggested by Agnes Chan)
  3. An Extended Localized Algorithm for Connected Dominating Set Formation in Ad Hoc Wireless Networks. Fei Dai and Jie Wu. IEEE Transactions on Parallel and Distributed Systems, 15(10), October 2004.  [abstract] [pdf] (suggested by Stefano Basagni)
  4. What cannot be computed locally!. Fabian Kuhn, Thomas Moscibroda and Roger Wattenhofer. PODC 2004.  [pdf] (suggested by Rajmohan Rajaraman)
  5. An Unconditional Lower Bound on the Hardness of Approximation of Distributed Minimum Spanning Tree Problem. M. Elkin. STOC 2004.  [pdf] (suggested by Rajmohan Rajaraman)
  6. Locality in distributed graph algorithms. N. Linial. SIAM Journal on Computing, 21(1) (February 1992), pages: 193 - 201. (suggested by Rajmohan Rajaraman)
  7. Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. Tom Leighton and Satish Rao. Journal of the ACM (JACM), 46(6) (November 1999), pages: 787 - 832. [pdf]
  8. Expander flows, geometric embeddings and graph partitioning. Sanjeev Arora, Satish Rao, and Umesh Vazirani. STOC 2004. [pdf]

Members

Javed A. Aslam Agnes Chan Guevara Noubir Rajmohan Rajaraman Ravi Sundaram
Daria G. Antonova Jiangzhuo Chen Yang Du Lujun Jia Guolong Lin
Xin Liu Huanmei Wu Tian Xia Stefano Basagni

Activities of ART in previous terms: Spring 2003, Fall 2003, Spring 2004, Fall 2004.