Amitabha Bagchi

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

Research Interests:
Data Algorithmics and Analytics, Probability and Networks.

Currently Teaching:

Note for COL106 in I Sem 2021-22
In I Sem 2021-22 this course is open only for those who have it as part of their core. There are no seats for anyone else. No exceptions will be made. All others please register in the even semester.

• COL863. Spl Topics in Theoretical Computer Science: Mathematics of Data Science. II Sem 2020-21.
  

• COL100 (formerly CSL101/CSL102). Introduction to Computers and Programming. I sem, 2014-15, II sem, 2011-12.
  
  
• CSL102. Introduction to Computer Science. II sem, 2010-11, I sem, 2009-10.
  
  
• COL202 (formerly CSL105). Discrete Mathematical Structures. I Sem 2020-21, I Sem 2019-20, I Sem, 2017-18, I sem, 2005-06, I sem, 2006-07.
  
  
• COL106 (formerly CSL201). Data Structures. I Sem, 2018-19, I Sem, 2016-17, I Sem, 2015-16, I sem 2012-13, I Sem, 2011-12, II sem, 2009-10, II sem, 2008-09, II sem, 2006-07.
  
  
• CSL853. Complexity Theory. II sem, 2005-06.
  
  
• CSL857. Randomized Algorithms. II sem, 2012-13.
  
  
• CSL860. Special topics in Parallel Computation.
  • Some stochastic processes on graphs. I Sem, 2010-11.
  • Routing in the Presence of Faults. I sem, 2008-09.
  • Theory of Network Communication. II sem, 2005-06.
    
    
• COL863 (formerly CSL863). Special topics in Theoretical Computer Science.
  • Spectral Graph Theory. II sem, 2017-18.
    
  • Rapid Mixing in Markov Chains. II Sem, 2016-17.
    
  • The Mathematics of Data Science. II Sem, 2015-16.
    
  • Expander graphs and their applications. II sem, 2014-15.
    
  • Randomized Algorithms. II sem, 2007-08.
    
    
• CSL866. Special topics in Algorithms.
  • Percolation and Random Graphs. I sem, 2007-08.
    
    
• COV883. Special Module in Theoretical Computer Science.
  • Efficient approximations of kernel functions. II Sem 2019-20
  • Matrix Concentration Inequalities. II Sem, 2018-19.
    

Forthcoming

• Iqra Altaf Gillani, Amitabha Bagchi.
  A Queueing Network-Based Distributed Laplacian Solver.
  To appear in Algorithmica.
  doi:10.1007/s00453-021-00845-4.
  Full access journal version.
  Preprint: arXiv:1905.04989 [cs.DC].
  
  
• Iqra Altaf Gillani, Amitabha Bagchi, Pooja Vyavahare.
  A Stochastic Process on a Network with Connections to Laplacian Systems of Equations.
  To appear in Adv. Appl. Probab.
  View video presentation.
  arXiv:1701.05296 [cs.NI].
  
  
• Arindam Bhattacharya, Sumanth Varambally, Amitabha Bagchi, Srikanta Bedathur.
  Fast One-class Classification using Class Boundary-preserving Random Projections.
  To appear in Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2021), August 2021.
  arXiv:2011.14317 [cs.LG]
  
  

• Manas Joshi, Arshdeep Singh, Sayan Ranu, Amitabha Bagchi, Priyank Karia and Puneet Kala.
  Batching and Matching for Food Delivery in Dynamic Road Networks.
  In Proceedings of IEEE 37th Conference on Data Engineering (ICDE 2021), pp 2099-2104, April 2021.
  doi:10.1109/ICDE51399.2021.00207.
  Full version: arXiv:2008.12905 [cs.DB].
  
  
• Iqra Altaf Gillani, Pooja Vyavahare, and Amitabha Bagchi.
  Random walk-based in-network computation of arbitrary functions.
  Distrib. Comput. 34(3):181-193, April 2021.
  Springer online version.
  arXiv:1702.03741 [cs.DC].
  
  
• Kartik Sharma, Iqra Altaf Gillani, Sourav Medya, Sayan Ranu, Amitabha Bagchi.
  Balance Maximization in Signed Networks via Edge Deletions.
  In Proceedings of 14th ACM Intl. Conf. on Web Search and Data Mining (WSDM 2021), pp 752-760, March 2021.
  doi:10.1145/3437963.3441778.
  
  
• Iqra Altaf Gillani, Amitabha Bagchi.
  A Queueing Network-Based Distributed Laplacian Solver for Directed Graphs.
  Inf. Proc. Lett. 166:106040, February 2021.
  doi:10.1016/j.ipl.2020.106040.
  
  
• Iqra Altaf Gillani, Amitabha Bagchi, Sayan Ranu.
  A Group-to-Group Version of Random Walk Betweenness Centrality.
  In Proceedings of ACM India Joint Intl. Conf. on Data Science and Management of Data (CODS-COMAD 2021), pp 127-135, Jan 2021.
  doi:10.1145/3430984.3431020.
  
  

• Iqra Altaf Gillani, Amitabha Bagchi.
  Brief Announcement: A Queueing Network-Based Distributed Laplacian Solver.
  In Proceedings of of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '20), pp 535-537, July 2020.
  doi:10.1145/3350755.3400251.
  View video presentation.
  Full version: arXiv:1905.04989 [cs.DC].
  
  
• Arindam Bhattacharya, Srikanta Bedathur, Amitabha Bagchi.
  Adaptive learned Bloom Filters under incremental workloads.
  In Proceedings of the ACM India Joint Intl. Conf. on Data Science and Management of Data (CODS-COMAD 2020), pp 107-115, January 2020.
  doi:10.1145/3371158.3371171.
  

• Sarisht Wadhwa, Anagh Prasad, Sayan Ranu, Amitabha Bagchi, Srikanta Bedathur.
  Efficiently answering regular simple path queries on large labeled networks.
  In Proceedings of the Intl. Conference on Management of Data (SIGMOD 2019), pp 1463-1480, June-July 2019.
  doi:10.1145/3299869.3319882.
  
  
• Chak Fai Yuen, Abhishek Pratap Singh, Sagar Goyal, Sayan Ranu, Amitabha Bagchi.
  Beyond Shortest Paths: Route Recommendations for Ride-sharing.
  In Proceedings of The World Wide Web Conference (WWW '19), pp 2258-2269, May 2019.
  doi:10.1145/3308558.3313465.
  
  
• Neha Sengupta, Amitabha Bagchi, Maya Ramanath, Srikanta Bedathur.
  ARROW: Approximating Reachability using Random-walks Over Web-scale Graphs.
  In Proceedings of the 35th IEEE International Conference on Data Engineering (ICDE 2019), pp 470-481, April 2019.
  doi:10.1109/ICDE.2019.00049.
  
  

• Amitabha Bagchi, Federico Corò, Cristina M. Pinotti, and Vlady Ravelomanana.
  Border effects on connectivity for randomly oriented directional antenna networks.
  In Proceedings of the 17th Annual Mediterranean Ad Hoc Networking Workshop (Med-Hoc-Net 2018). June 2018.
  doi:10.23919/MedHocNet.2018.8407090.
  
  
• Neha Sengupta, Amitabha Bagchi, Srikanta Bedathur, and Maya Ramanath.
  Sampling and reconstruction Using Bloom Filters.
  IEEE T. Knowl. Data En. 30(7):1324-1337, July 2018.
  doi:10.1109/TKDE.2017.2785803.
  Older arXiv version: arXiv:1701.03308 [cs.DS].
  
  

• Harvineet Singh, Amitabha Bagchi, and Parag Singla.
  Learning user representations in Online Social Networks using temporal dynamics of information diffusion.
  arXiv:1710.07622 [cs.SI].
  
  
• Mona Gupta, Happy Mittal, Parag Singla and Amitabha Bagchi.
  Analysis and characterisation of comparison shopping behaviour in the mobile handset domain.
  Elec. Comm. Res. 17(3):521-551, September 2017.
  doi:10.1007/s10660-016-9226-7
  
  
• Neha Sengupta, Amitabha Bagchi, Srikanta Bedathur, and Maya Ramanath.
  Sampling and reconstruction Using Bloom Filters.
  In Proceedings of the 33rd Annual IEEE International Conference on Data Engineering (ICDE 2017), pp 195-198, April 2017.
  doi:10.1109/ICDE.2017.73.
  Full version: arXiv:1701.03308 [cs.DS].
  
  
• Akshit Trehan, Sumit Khurana, and Amitabha Bagchi.
  A user activity-based measurement study characterizing and classifying Stack Exchange communities across multiple domains.
  In Proceedings of the 4th ACM IKDD Conferences on Data Sciences (CoDS '17), pp 7:1-7:11, March 2017.
  doi:10.1145/3041823.3041834.
  
  

• Salik Warsi, Vakul Jindal, Saket Kumar, Deepak Koli, Amitabha Bagchi, Vinay Ribeiro.
  Joint scheduling and routing using space-time graphs for TDM wireless mesh networks.
  Wirel. Netw. 22(7):2355-2367, October 2016.
  doi:10.1007/s11276-015-1102-1
  
  
• Amit Ruhela, Amitabha Bagchi, Anirban Mahanti, Aaditeshwar Seth.
  The rich and middle classes on Twitter: Are popular users indeed different from regular users?
  Comput. Commun. 73:219-228, January 2016.
  doi:10.1016/j.comcom.2015.07.024
  
  

• Siddharth Bora, Harvineet Singh, Anirban Sen, Amitabha Bagchi, Parag Singla.
  On the role of conductance, geography and topology in predicting hashtag virality.
  Soc. Netw. Anal. Min. 5(1):57, December 2015.
  doi:10.1007/s13278-015-0300-2.
  Preprint: arXiv:1504.05351 [cs.SI].
  
  
• Sainyam Galhotra, Amitabha Bagchi, Srikanta Bedathur, Maya Ramanath, Vidit Jain.
  Tracking the conductance of rapidly evolving topic-subgraphs.
  In Proceedings of the VLDB Endowment, Vol 8, Number 13, pp 2170-2181, September 2015.
  Available here.
  
  
• Amitabha Bagchi, Francesco Betti Sorbelli, Cristina Maria Pinotti, Vinay Ribeiro.
  Connectivity of a dense mesh of randomly oriented directional antennas under a realistic fading model.
  In Proceedings of 11th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS '15), pp 13-26, September 2015.
  doi:10.1007/978-3-319-28472-9_2.
  
  
• Amitabha Bagchi, Adit Madan, Achal Premi and Surabhi Sankhla.
  Hierarchical neighbor graphs: A topology control mechanism for data collection in heterogenous wireless sensor networks.
  Ad Hoc Sens. Wirel. Ne 26(1-4):171-191, 2015.
  Available here.
  
  
• Amitabha Bagchi, Cristina M. Pinotti, Sainyam Galhotra, Tarun Mangla.
  Optimal radius for connectivity in duty-cycled wireless sensor networks.
  ACM T Sensor Network 11(2):Article #36, February 2015.
  doi:10.1145/2663353.
  Preprint: arXiv:1408.5069 [cs.NI].
  
  

• Amitabha Bagchi, Rajshekar Kalyappan and Surabhi Sankhla.
  Surveillance using non-stealthy sensors: A new intruder model.
  Security Comm. Networks 7(11):1900-1911, November 2014.
  doi:10.1002/sec.904
  
  
• Rudra Mohan Tripathy, Shashank Sharma, Sachindra Joshi, Sameep Mehta and Amitabha Bagchi.
  Theme Based Clustering of Tweets. (pdf)
  In Proceedings of 1st IKDD Conference on Data Sciences (CoDS '14), pp 1-5, March 2014.
  10.1145/2567688.2567694.
  
  
• Mona Gupta, Happy Mittal, Parag Singla and Amitabha Bagchi.
  Characterizing comparison shopping behavior: A case study.
  Presented at Workshop on Big Data Consumer Analytics (BDCA '14),
  Published in IEEE 30th International Conference on Data Engineering Workshops (ICDEW 2014), pp 115-122, March 2014.
  doi:10.1109/ICDEW.2014.6818314.
  
  

• Rudra Mohan Tripathy, Amitabha Bagchi and Mona Jain.
  Complex Network characteristics and team performance in the game of Cricket. (pdf)
  In Proceedings of the 2nd International Conference on Big Data Analytics (BDA '13), pp 133-150, December 2013.
  doi:10.1007/978-3-319-03689-2_9.
  
  
• Mona Jain, S. Rajyalakshmi, Rudra Mohan Tripathy and Amitabha Bagchi.
  Temporal analysis of user behavior and topic evolution on Twitter.
  In Proceedings of the 2nd International Conference on Big Data Analytics (BDA '13), pp 22-36, December 2013.
  doi:10.1007/978-3-319-03689-2_2.
  
  
• Amit Ruhela, Sipat Triukose, Sebastien G. Ardon, Amitabha Bagchi, Anirban Mahanti and Aaditeshwar Seth.
  The scope for online social network aided caching in Web CDNs.
  In Proceedings of the 9th ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS '13), pp 37-46, October 2013.
  doi:10.1109/ANCS.2013.6665174.
  
  
• Rahul Goyal, Ravee Malla, Amitabha Bagchi, Sameep Mehta and Maya Ramanath.
  ESTHETE: A news browsing system to visualize the context and evolution of news stories,
  A Demo paper in Proceedings of the 22nd ACM International Conference on Information and Knowledge Management (CIKM '13), pp 2529-2532, November 2013.
  doi:10.1145/2505515.2508208.
  
  
• Amitabha Bagchi, Cristina M. Pinotti, Sainyam Galhotra, Tarun Mangla.
  Optimal radius for connectivity in duty-cycled wireless sensor networks. (pdf)
  In Proceedings of the 16th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWIM '13), pp 125-128, November 2013.
  doi:10.1145/2507924.2507985
  
  
• Sebastien Ardon, Amitabha Bagchi, Anirban Mahanti, Amit Ruhela, Aaditeshwar Seth, Rudra Mohan Tripathy, Sipat Triukose.
  Spatio-Temporal and Events-based Analysis of Topic Popularity in Twitter. (pdf)
  In Proceedings of the 22nd ACM International Conference on Information and Knowledge Management (CIKM '13), pp 219-228, November 2013.
  doi:10.1145/2505515.2505525.
  Earlier version: arXiv:1111.2904v1 [cs.SI].
  
  
• Rudra Tripathy, Amitabha Bagchi and Sameep Mehta.
  Towards combating rumors in social networks: Models and metrics. (pdf)
  Intell. Data Anal. 17(1):149-175, 2013.
  doi:10.3233/IDA-120571.
  
  

• S. Rajyalakshmi, Amitabha Bagchi, Soham Das, Rudra M. Tripathy.
  Topic Diffusion and Emergence of Virality in Social Networks.
  Unpublished.
  arXiv:1202.2215 [cs.SI].
  
  
• Pravesh Biyani, Shankar Prakriya, Surendra Prasad and Amitabha Bagchi.
  Dynamic programming based multi-user resource allocation for partial crosstalk cancellation in VSDL.
  IEEE Communications Letters 16(3):420-423, 2012.
  doi:10.1109/LCOMM.2012.020212.111886.
  
  

• Amit Ruhela, Rudra Mohan Tripathy, Sipat Triukose, Sebastien G. Ardon, Amitabha Bagchi and Aaditeshwar Seth.
  Towards the use of Online Social Networks for Efficient Internet Content Distribution .
  In Proceedings of the 5th IEEE International Conference on Advanced Networks and Telecommunication Systems (ANTS '11), pp 1-6, December 2011.
  doi:10.1109/ANTS.2011.6163677
  
  
• Amitabha Bagchi, Adit Madan, Achal Premi.
  A computationally inexpensive and power efficient fully distributed topology for data collection in heterogeneous wireless sensor networks.
  In Proceedings of the 7th IEEE Intl. Conference on Distributed Computing in Sensor Systems (DCOSS '11), pp 1-8, June 2011.
  doi:10.1109/DCOSS.2011.5982151
  
  

• Rudra Tripathy, Amitabha Bagchi and Sameep Mehta.
  A study of rumor control strategies on social networks.
  In Proceedings of the 19th ACM Intl. Conference on Information and Knowledge Management (CIKM '10), pp 1817-1820, October 2010.
  doi:10.1145/1871437.1871737
  
  
• Amitabha Bagchi, Adit Madan, Achal Premi.
  Brief Announcement: Hierarchical neighbor graphs: An energy-efficient bounded degree connected structure for wireless networks.
  In Proceedings of ALGOSENSORS 2010. Springer LNCS Volume 6451 (Ed. C. Scheideler), pp 31-33, July 2010.
  doi:10.1007/978-3-642-16988-5_3
  Full version: arXiv:0903.0742v3 [cs.NI].
  
  
• Amitabha Bagchi.
  Sparse power-efficient topologies for wireless ad hoc sensor networks.
  In Proceedings of the 24th IEEE International Parallel and Distributed Processing Symposium (IPDPS '10), pp 1-10, April 2010.
  doi:10.1109/IPDPS.2010.5470372.
  Full version: arXiv:0805.4060v5 [cs.NI].
  
  

• 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, June 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. (pdf)
  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.
  
  

• 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, 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.
  
  
• Amitabha Bagchi, Ankur Bhargava, Torsten Suel.
  Approximate maximum weight branchings. (ps, pdf)
  Inf. Proc. Lett. 99(2):54-58. 2006
  doi:10.1016/j.ipl.2006.02.011.
  
  
• 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, 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.
  
  

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