Amitabha Bagchi

Email: bagchi at cse dot iitd dot ac dot in
Phone: (91 11) 2659 6397

Research Interests:
Structural properties of networks, random graphs, network algorithms, approximation algorithms, data structures.

Currently Teaching:

• CSL102. Introduction to Computer Science. I sem, 2009-10.

• CSL863. Randomized Algorithms. II sem, 2007-08.
  
  
• CSL866. Percolation and Random Graphs. I sem, 2007-08.
  
  
• CSL105. Discrete Mathematical Structures. I sem, 2005-06, I sem, 2006-07.
  
  
• CSL201. Data Structures. II sem, 2008-09, II sem, 2006-07.
  
  
• CSL853. Complexity Theory. II sem, 2005-06.
  
  
• CSL860. Routing in the Presence of Faults. I sem, 2008-09, Theory of Network Communication. II sem, 2005-06.
  
  

Unrefereed papers:

• Amitabha Bagchi, Adit Madan, Achal Premi.
  Hierarchical neighbor graphs: An energy-efficient bounded degree connected structure for wireless networks.
  arXiv:0903.0742v3 [cs.NI].
  
  
• Amitabha Bagchi.
  Sparse power-efficient topologies for wireless ad hoc sensor networks.
  arXiv:0805.4060v5 [cs.NI].
  
  
• Amitabha Bagchi, Amitabh Chaudhary, Petr Kolman, Jiri Sgall.
  A simple combinatorial proof of duality of multiroute flows and cuts. (ps, pdf)
  Technical Report. KAM-DIMATIA Series 2004-662 and ITI Series 2004-186.
  Charles University, Prague, 2004.
  
  

• Amitabha Bagchi and Garima Lahoti.
  Relating Web pages to enable information-gathering tasks.
  In Proceedings of the 20th ACM Conference on Hypertext and Hypermedia (Hypertext '09), pp 109-118, 2009.
  http://doi.acm.org/10.1145/1557914.1557935.
  Earlier version: arXiv:0810.5428v1 [cs.IR].
  
  
• Rohan Choudhary, Sameep Mehta and Amitabha Bagchi.
  On quantifying changes in temporally evolving datasets.
  In Proceedings of the 17th Annual ACM Conference on Information and Knowledge Management (CIKM '08), pp 1459-1460, 2008.
  http://doi.acm.org/10.1145/1458082.1458332.
  
  
• Amitabha Bagchi and Sohit Bansal.
  Nearest-neighbor graphs on random point sets and their applications to sensor networks.
  In Proceedings of the 27th Annual Symposium on Principles of Distributed Computing (PODC '08), page 434, 2008.
  doi:10.1145/1400751.1400828.
  Full version: arXiv:0804.3784v2 [cs.NI].
  
  
• Rohan Choudhary, Sameep Mehta, Amitabha Bagchi and Rahul Balakrishnan.
  A framework for exploration of news corpora by actor evolution and interaction.
  In Proceedings of the 30th European Conference on IR Research (ECIR '08), pp 422-429, Springer LNCS 4956. 2008.
  doi:10.1007/978-3-540-78646-7_39.
  
  
• Rakesh Kumar, David Yao, Amitabha Bagchi, Keith Ross and Dan Rubenstein.
  Fluid modeling of pollution proliferation in P2P networks.
  In Proceedings of SIGMETRICS/Performance '06, pp 335--346. 2006.
  http://doi.acm.org/10.1145/1140277.1140316
  
  
• Amitabha Bagchi, Ankur Bhargava, Amitabh Chaudhary, David Eppstein, Christian Scheideler.
  The effect of faults on network expansion. (ps, pdf)
  In Proceedings of the 16th Annual Symp. on Parallel Algorithms and Architectures (SPAA '04). 2004.
  (Invited to the special issue of Theory of Computing Systems devoted to the best theoretical papers from SPAA '04)
  
  
• Amitabha Bagchi, Amitabh Chaudhary, David Eppstein, Michael T. Goodrich.
  Deterministic sampling and range counting in geometric data streams. (ps, pdf)
  In Proceedings of the 20th ACM Symp. on Computational Geometry (SOCG '04). 2004.
  
  
• Amitabha Bagchi, Amitabh Chaudhary, Michael T. Goodrich, Shouhuai Xu.
  Constructing disjoint paths for secure communication. (ps, pdf)
  In Proceedings of 17th International Conference on Distributed Computing (DISC '03), 2003.
  
  
• Amitabha Bagchi, Amitabh Chaudhary, Petr Kolman.
  Short length Menger's theorem and reliable optical routing. (ps, pdf)
  In Proceedings 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA '03). 2003.
  
  
• Amitabha Bagchi, Adam Buchsbaum and Michael T. Goodrich.
  Biased skip lists. (ps, pdf)
  In Proceedings of 13th International Symposium, ISAAC 2002, Vancouver, BC, Canada, November 21-23, 2002.

• Amitabha Bagchi, Amitabh Chaudhary, Petr Kolman, and Christian Scheideler.
  Algorithms for fault-tolerant touting in circuit switched networks. (ps, pdf)
  In Proc. 14th ACM Symposium on Parallel Algorithms and Architectures (SPAA '02), Winnipeg, Canada, Aug 10-13, 2002.
  
  
• Amitabha Bagchi, Amitabh Chaudhary, Rahul Garg, Michael T. Goodrich, and Vijay Kumar.
  Seller-focused algorithms for online auctioning. (ps, pdf)
  In Proceedings of the 7th International Workshop on Algorithms and Data Structures, WADS 2001, Providence, RI, USA, August, 8-10, 2001.
  

• Amitabha Bagchi, Amitabh Chaudhary, David Eppstein, Michael T. Goodrich.
  Deterministic sampling and range counting in geometric data streams. (ps, pdf)
  Trans. on Algorithms 3(2). May 2007.
  http://doi.acm.org/10.1145/1240233.1240239
  
  
• Amitabha Bagchi, Amitabh Chaudhary, Petr Kolman, and Christian Scheideler.
  Algorithms for fault-tolerant routing in circuit switched networks. (ps, pdf)
  SIAM J. Discrete Math. 21(1):141-157. February 2007.
  doi:10.1137/S0895480102419743.
  
  
• Amitabha Bagchi, Ankur Bhargava, Torsten Suel.
  Approximate maximum branchings. (ps, pdf)
  Inf. Proc. Lett. 99(2):54-58. 2006
  doi:10.1016/j.ipl.2006.02.011.
  
  
• Amitabha Bagchi, Ankur Bhargava, Amitabh Chaudhary, David Eppstein, Christian Scheideler.
  The effect of faults on network expansion. (ps, pdf)
  Theor. Comput. Syst. 39(6):903-928. November 2006.
  doi:10.1007/s00224-006-1349-0.
  
  
• Amitabha Bagchi, Amitabh Chaudhary, Michael T. Goodrich, Chen Li, Michal Shmueli-Scheuer.
  Achieving communication efficiency through push-pull partitioning of semantic spaces in client-server architectures.
  IEEE T. Knowl. Data En. 18(10): 1352-1367. October 2006.
  http://doi.ieeecomputersociety.org/10.1109/TKDE.2006.153.
  
  
• Rakesh Kumar, David Yao, Amitabha Bagchi, Keith Ross and Dan Rubenstein.
  Fluid modeling of pollution proliferation in P2P networks.
  SIGMETRICS Perform. Eval. Rev. 34(1):335-346. June 2006.
  doi:10.1145/1140103.1140316.
  
  
• Amitabha Bagchi, Amitabh Chaudhary, Petr Kolman.
  Short length Menger's theorem and reliable optical routing. (ps, pdf)
  Theoret. Comput. Sci. 339(2-3): 315-332. 2005.
  doi:10.1016/j.tcs.2005.03.009.
  
  
• Amitabha Bagchi, Adam Buchsbaum and Michael T. Goodrich.
  Biased skip lists. (ps, pdf)
  Algorithmica 42(1): 31-48. 2005.
  doi:10.1007/s00453-004-1138-6.
  
  

Efficient strategies for topics in Internet algorithmics. (ps, pdf)
PhD thesis submitted to Johns Hopkins University. October 2002.

Book:

Above Average.
HarperCollins, India. February 2007.