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 Fall 2004, the regular meetings are in WVH 164 every Friday 15:30-17:00.

Date	Time	Location	Presenter	Paper / Topic
09/10/2004	13:00-13:30	WVH 166		Organizational meeting.
09/17/2004	15:30-17:00	WVH 164	Jiangzhuo Chen	J. Chuzhoy et al.: Asymmetric k-center is log^*n hard to approximate.
09/24/2004	15:30-17:00	WVH 164	Rajmohan Rajaraman	C. Busch et al.: Analysis of Link Reversal Routing Algorithms.
10/01/2004	15:30-17:00	WVH 366	Miroslaw Kutylowski	Adversary Immune Communication Algorithms in Ad Hoc Networks.
10/22/2004	15:30-17:00	WVH 164	Muriel Medard (MIT)	Byzantine security.
10/29/2004	15:30-17:00	WVH 164	Ravi Sundaram	L. Lovász: Semidefinite programs and combinatorial optimization.
11/05/2004	15:30-17:00	WVH 164	Guolong Lin	H. Racke: Minimizing Congestion in General Networks (FOCS 2002).
11/12/2004	15:30-17:00	WVH 164	Stefano Basagni	Hierarchical Organization for Wireless Sensor Networks: Effectiveness and Performance Comparison. [abstract]
11/19/2004	15:30-17:00	WVH 164	S. Muthukrishnan (Rutgers)	Nonuniform Sparse Approximation via Haar Wavelets. [abstract]
12/03/2004	15:30-17:00	WVH 164	Guevara Noubir	M. Agrawal et al.: PRIMES is in P.

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] (suggested by Stefano Basagni)
Analysis of Link Reversal Routing Algorithms. Costas Busch, Srikanth Surapaneni and Srikanta Tirthapura. SPAA 2003. [pdf] [longer version] (suggested by Rajmohan Rajaraman)
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)
Asymmetric k-center is log^*n hard to approximate. Julia Chuzhoy, Sudipto Guha, Eran Halperi, Sanjeev Khanna, Guy Kortsarz and Joseph (Seffi) Nao. STOC 2004. [pdf]
PRIMES is in P. Manindra Agrawal, Neeraj Kayal and Nitin Saxena. [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.