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

  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] (suggested by Stefano Basagni)
  4. Analysis of Link Reversal Routing Algorithms. Costas Busch, Srikanth Surapaneni and Srikanta Tirthapura. SPAA 2003.  [pdf] [longer version] (suggested by Rajmohan Rajaraman)
  5. What cannot be computed locally!. Fabian Kuhn, Thomas Moscibroda and Roger Wattenhofer. PODC 2004.  [pdf] (suggested by Rajmohan Rajaraman)
  6. An Unconditional Lower Bound on the Hardness of Approximation of Distributed Minimum Spanning Tree Problem. M. Elkin. STOC 2004.  [pdf] (suggested by Rajmohan Rajaraman)
  7. Locality in distributed graph algorithms. N. Linial. SIAM Journal on Computing, 21(1) (February 1992), pages: 193 - 201. (suggested by Rajmohan Rajaraman)
  8. 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]
  9. 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.