Reading list for CSL860: Theory of Network Communication

II semester: 2005-06


  1. O. Angel, I Benjamini, E. Ofek, and U. Wieder.
    Routing complexity on faulty networks.
    In Proc. of PODC '05. pp 209-217. 2005. (Available online.)

    Reader: Satnam.
    Discussants: Rajesh, Monika.
    Presentation Date:

  2. B. Awerbuch, Y. Azar, and S. Plotkin.
    Throughput-competitive online routing.
    In Proc. of FOCS '93. pp 32-40. 1993. (Available online.)

    Reader: Varun Nayyar.
    Discussants: Arun, Monika.
    Presentation Date:Mar 7.
    Varun's slides. (ppt).

  3. D. R. Karger, E. Lehman, F. T. Leighton, R. Panigrahy, M. S. Levin, and D. Lewin.
    Consistent hashing and random trees: Distributed caching protocols for relieving hotspots on the World Wide Web.
    In Proc. of STOC '97. pp 654-663. 1997. (Available online.)

    Reader: Arun.
    Discussants: Siddharth, Varun.
    Presentation Date:

  4. Harald RŠcke.
    Minimizing congestion in general networks.
    In Proc. of FOCS '02. pp 43-52. 2002. (Available online.)

    Reader: Gaurav Gupta.
    Discussants: Murtaza, Abhishek (MTech).
    Presentation Date: Mar 22.
    Gaurav's slides. (pdf).

  5. T. Roughgarden and E. Tardos.
    How bad is selfish routing?
    J. ACM. 49(2):236-259. March 2002. (Available online.)

    Reader: Murtaza.
    Discussants: Ashish Saxena, Nitya Prakash.
    Presentation Date: Apr 19.

  6. Prabhakar Raghavan.
    Robust algorithms for packet routing in a mesh.
    In Proc. of SPAA '89. pp 344-350. 1989. (Linked here, available from IIT IP address.)

    Reader: Abhishek (Dual).
    Discussants: Shweta, Abhishek (MTech).
    Presentation Date:

  7. R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal.
    Stochastic models for the web graph.
    In Proc. of FOCS '00. pp 57-65. 2000. (Available online.)

    Reader: Rajesh.
    Discussants: Gaurav Gupta, Abhishek (Dual).
    Presentation Date: Apr 5.

  8. Jon Kleinberg.
    The small-world phenomenon: An algorithmic perspective.
    In Proc. of STOC '00. pp 163-170. 2000. (Available online.)

    Reader: Siddharth Srinivasan.
    Discussants: Murtaza, Nitya Prakash.
    Presentation Date: Mar 8.
    Siddharth's slides. (ppt, pdf).

  9. B. Ghosh, F. T. Leighton, B. M. Maggs, S. Muthukrishnan, C. G. Plaxton, R. Rajaraman, A. W. Richa, R. E. Tarjan, and D. Zuckerman.
    Tight Analyses of Two Local Load Balancing Algorithms.
    SIAM J. Comput. 29(1): 29-64. 1999. (Available online.)

    Reader: Abhishek (MTech).
    Discussants: Abhishek (Dual), Gaurav.
    Presentation Date: Apr 4.

  10. Yair Bartal.
    Probabilistic Approximation of Metric Spaces and its Algorithmic Applications.
    In Proc. of FOCS '96. pp 184-193. 1996. (Available online.)

    Reader: Shweta Agarwal.
    Discussants: Virat, Arun.
    Presentation Date: Apr 25.

  11. S. Arora, S. Rao, and U. Vazirani.
    Expander flows, geometric embeddings, and graph partitioning.
    In Proc. of STOC '04. pp 222-231. 2004. (Available online.)

    Reader: Available.
    Discussants: .
    Presentation Date:

  12. R. Karp, M. Luby, F. Meyer auf der Heide.
    Efficient PRAM simulations on a distributed memory machine.
    Algorithmica 16(4/5):517-542. 1996. (Available online.)

    Reader: Monika Gupta.
    Discussants: Virat, Rajesh.
    Presentation Date: Mar 14.
    Monika's slides. (pdf).

  13. P. Gupta and R. Kumar.
    The capacity of wireless networks.
    IEEE Trans. on Information Theory IT-46(2):388-404. 2000. (Available online.)

    Reader: Nitya Prakash.
    Discussants: Varun, Ashish.
    Presentation Date: Apr 12.

  14. F. T. Leighton and S. Rao.
    Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms.
    J. ACM 46(6): 787-832. 1999. (Linked here, available from IIT IP address.)

    Reader: Virat Agarwal.
    Discussants: Siddharth, Shweta.
    Presentation Date: Mar 21.

  15. C. G. Plaxton, R. Rajaraman and A. Richa.
    Accessing nearby copies of replicated objects in a distributed environment.
    Theory Comput. Syst. 32:241-280. 1999. (Available online.)

    Reader: Available.
    Discussants: .
    Presentation Date:

Amitabha Bagchi