Algorithms Reading Team

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.

Each team member is supposed to read at least the beginning sections (introduction, problem setup, main results) before the meeting, so that the minimum amout of time will be spent on definitions, notations and other background knowledge.
The presenter is supposed to read through the main part of the paper, so that s/he can quickly review the main idea / logic / technique of the works, answer some non-trivial questions and initiate and lead the discussion.
After each meeting, the presenter shall write a memo summarizing the open problems either mentioned in the paper or raised by the team members and publish them on the mailing list (one paragraph in text format would be good).

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

Near-Collisions of SHA-0. Eli Biham and Rafi Chen. CRYPTO 2004. [ps] (suggested by Agnes Chan)
SeRLoc: Secure Range-Independent Localization for Wireless Sensor Networks. Loukas Lazos and Radha Poovendran. WiSe 2004. (suggested by Agnes Chan)
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)
What cannot be computed locally!. Fabian Kuhn, Thomas Moscibroda and Roger Wattenhofer. PODC 2004. [pdf] (suggested by Rajmohan Rajaraman)
An Unconditional Lower Bound on the Hardness of Approximation of Distributed Minimum Spanning Tree Problem. M. Elkin. STOC 2004. [pdf] (suggested by Rajmohan Rajaraman)
Locality in distributed graph algorithms. N. Linial. SIAM Journal on Computing, 21(1) (February 1992), pages: 193 - 201. (suggested by Rajmohan Rajaraman)
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]
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.