alt text
  Home  
  CV  
  Contact Information  
  Research  
    Research Interests    
    Publications    
  Teaching  
    Current Courses    
    Past Courses    
  Other  
    Funfacts    
    Other Links    

alt text

Arindam Khan

alt text 

Arindam Khan
Assistant Professor
Department of Computer Science & Automation
Indian Institute of Science
Bengaluru, India.
Email: arindamkhan (at) iisc (dot) ac (dot) in


I am an Assistant Professor in the CSA Department at IISc. I obtained my PhD in Algorithms, Combinatorics, and Optimization (ACO) from School of Computer Science in Georgia Institute of Technology, Atlanta, USA. Before that I got my B. Tech and M. Tech (Dual Degree) from the Department of Computer Science and Engineering, Indian Institute of Technology (IIT), Kharagpur, India. In the past years, I have spent some wonderful time doing research at TU Munich, IDSIA Switzerland, Microsoft Research Redmond, UC Berkeley, Microsoft Research Silicon Valley, TU Eindhoven and IBM Research. You can find my CV here.

Research

Research: I am broadly interested in the design and analysis of algorithms and theoretical computer science. My current research focus is on Approximation Algorithms, Online Algorithms, Online Learning, and Combinatorial Optimization. I am also interested in Computational Geometry, Graph Algorithms, Parameterized Algorithms, and Algorithms for Big Data and Machine Learning.

Selected Recent Publications: (with co-authors)

  • Guaranteeing Envy-Freeness under Generalized Assignment Constraints, 2023. (under submission)
  • Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits, 2022. (paper)
  • Online and Dynamic Algorithms for Geometric Set Cover and Hitting Set, SoCG 2023. (paper)
  • Finding Fair Allocations under Budget Constraints, AAAI 2023. (paper)
  • Fairness and Welfare Quantification for Regret in Multi-Armed Bandits, AAAI 2023. (paper, slides, video)
  • Fair Rank Aggregation, NeurIPS 2022. (paper)
  • Approximation Algorithms for ROUND-UFP and ROUND-SAP, ESA 2022. (paper, slides, video)
  • Near-optimal Algorithms for Stochastic Online Bin Packing, ICALP 2022. (paper, slides)
  • A PTAS for Packing Hypercubes into a Knapsack, ICALP 2022. (paper, slides)
  • Tight Approximation Algorithms for Two-dimensional Guillotine Strip Packing, ICALP 2022. (paper, slides)
  • Geometry Meets Vectors: Approximation Algorithms for Multidimensional Packing, FSTTCS 2022. (paper)
  • A PTAS for the Horizontal Rectangle Stabbing Problem, IPCO 2022. (paper, slides)
  • Universal and Tight Online Algorithms for Generalized-Mean Welfare, AAAI 2022. (paper, video)
  • A 3-Approximation Algorithm for Maximum Independent Set of Rectangles, SODA 2022. (paper, 2-hour long talk at Recent Trends in Algorithms 2022: part 1, part 2)
  • Multi-Armed Bandits with Bounded Arm-Memory: Near-Optimal Guarantees for Best-Arm Identification and Regret Minimization, NeurIPS 2021. (paper, video)
  • Tight Approximation Algorithms for Geometric Bin Packing with Skewed Items, APPROX 2021. (paper, video)
  • Peak Demand Minimization via Sliced Strip Packing, APPROX 2021. (paper, video)
  • On Guillotine Separable Packings for the Two-dimensional Geometric Knapsack Problem, International Symposium on Computational Geometry (SoCG) 2021. (paper, video)
  • Improved Approximation Algorithms for 2-Dimensional Knapsack: Packing into Multiple L-Shapes, Spirals, and More. International Symposium on Computational Geometry (SoCG) 2021. (paper, video)
  • Group Fairness for Knapsack Problems, AAMAS 2021. (paper)
  • Best-Fit Bin Packing with Random Order Revisited. Algorithmica 2021 (Preliminary version published in MFCS 2020). ( Journal version, conference version, video)
    Recipient of Best Paper Award in MFCS 2020, sponsored by EATCS.
  • Approximating Geometric Knapsack via L-Packings, IEEE Symposium on Foundations of Computer Science (FOCS) 2017. (paper, slides, video)
    ACM Transactions on Algorithms (TALG) 2021.
  • Improved Online Algorithms for Knapsack and GAP in the Random Order Model, Algorithmica 2021 (Preliminary version published in APPROX 2019). (journal version, conference version)
  • On Guillotine Separability of Squares and Rectangles, APPROX 2020. (paper, video)
  • A Tight (3/2 + epsilon) Approximation for Skewed Strip Packing, APPROX 2020. (paper, video)
  • On the Matching Augmentation Problem, Mathematical Programming (MAPR), vol 182, pages 315–354, 2020. (paper)
  • Improved Approximation for Vector Bin Packing, ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016. (paper, slides)
  • Improved Approximation Algorithm for Two-Dimensional Bin Packing, ACM-SIAM Symposium on Discrete Algorithms (SODA) 2014. (paper, slides)

    • A full list of papers is available here.

Teaching

Students

  • PhD Students: P1. Vishakha Patil (Joint with Prof. Y. Narahari), P2. Aditya Subramanian, P3. KVN Sreenivas, P4. Debajyoti Kar.

  • M.Tech (Research) Students: MR4. Aditya Lonkar .

  • Graduated M.Tech (Research) Students:
    MR1. Eklavya Sharma (-> PhD student at UIUC). Thesis: Approximation Algorithms for Geometric Packing Problems (pdf).
    MR2. Swati Allabadi (-> Software Engineer at Siemens)(Joint advising with Dr. Anand Louis). Thesis: Algorithms for Fair Clustering (pdf).
    MR3. KVN Sreenivas (-> PhD student at IISc). Thesis: Improved Algorithms for Variants of Bin Packing and Knapsack (pdf).

  • Graduated M.Tech (Coursework) Students: MT1. Arka Ray (-> RA at IISc). Thesis: Approximability of Packing and Covering Problems (pdf).

  • Undergraduate Interns/Project Assistants: Arnab Maiti (IIT Kharagpur -> U Washington), Amatya Sharma (IIT Kharagpur -> U Michigan), Madhusudhan Reddy Pittu (IIT Kharagpur -> Carnegie Mellon University), Siddharth Jayashankar (IIT Kanpur -> CMU), Kishen Gowda (IIT Gandhinagar -> University of Maryland), Debajyoti Kar (IIT Kharagpur -> IISc), Siba Smarak Panigrahy (IIT Kharagpur -> McGill), Debarsho Sannyashi (IIT Kanpur->Graviton Research), Shreyans Nagori (IIT Delhi-> NK Securities Research)), Nikhil Ayyadevara (IIT Delhi -U Michigan), Soumita Hait (IIT Kharagpur) [Through Google exploreCS Research Award], Divyanshi Rajput (IIIT Bangalore) [Through Google exploreCS Research Award], Aryan Agarwala (CMI), Aaryan Gupta (IIT Bombay).

  • Project Associates: Aditya Varre (IIT Bombay-> EPFL Switzerland), Karthik Murali (NIT Suratkal -> Univ. of Waterloo), KVN Sreenivas (IIT Bombay -> IISc), Santanu Rathod (IIT Bombay -> Wadhwani AI), Rajni Dabas (DU, through ACM India Anveshan Setu Fellowship), Dhawal Jethwani (IIT BHU), Sudharshan Shyam (UCSD->Aarhus), Neel Karia (IIT Kharagpur/MSR -> Columbia).

Available positions

  • Postdoc: I have short-term postdoc positions available. If you are interested in approximation algorithms/ online algorithms/ graph algorithms/ geometric algorithms or combinatorial optimization, and have published in top-tier conferences such as STOC, FOCS, SODA, ICALP, ESA, APPROX, FSTTCS etc., please send me an email.

  • Project Assistant/Interns: I have short-term/intern positions available. If you already have some research experience in design and analysis of algorithms and have done advanced theory courses (graph theory, linear algebra, probability, advanced algorithms etc.), please send me an email.

Research Centers, Seminars and Workshops

  • PolyAlg Center: (with UC Berkeley, Georgia Tech, and TIFR) I am a co-PI for the center on polynomials as an algorithmic paradigm, supported by Indo-US Science and Technology Forum (IUSSTF). This is a joint Indo-US Virtual Network Center with Georgia Tech, University of California Berkeley and TIFR Bombay. See the webpage for exciting talks and related research activities.

  • IISc-MSR Theory Seminar Series 2021: We organize IISc-MSR Theory seminar where eminent researchers talk about their recent breakthroughs. Visit the webpage for exciting talks.

  • Bin Packing Seminar 2021: Recently, We organized an international bin packing seminar. Visit the webpage for exciting talks.

Recent News (2020-22)

  • February 2023: A paper got accepted in Symposium on Computational Geometry (SoCG) 2023.

  • January 2023: Gave an invited talk at Google Research Week 2023.

  • December 2022: Received SERB-Core grant for the project "Optimization under Intractability and Uncertainty".

  • November 2022: Two papers got accepted in AAAI 2023.

  • November 2022: Debajyoti Kar and KVN Sreenivas were provisionally selected for prestigious PMRF fellowship (Direct-entry).

  • October 2022: KVN Sreenivas received prestigious Google PhD Fellowship. Among six students in India in all areas of CS, and five in the world in Algorithms, Optimization, and Markets.

  • October 2022: Our recent result on MISR was mentioned in Communications of the ACM (CACM) as one of the top results from India during 2019-2022.

  • September 2022: A paper got accepted in NeurIPS 2022.

  • September 2022: A paper got accepted in FSTTCS 2022.

  • August 2022: KVN Sreenivas and Debajyoti Kar joined PhD.

  • July 2022: Will be a PC Member for SoCG 2023.

  • June 2022: A paper got accepted in ESA 2022.

  • April 2022: Three papers got accepted in ICALP 2022.

  • April 2022: Gave an invited talk at Capillary Technologies External Talk.

  • March 2022: Gave 2-hour long invited talk at Recent Trends in Algorithms 2022.

  • February 2022: Delighted to receive a Google India Research Award 2021.

  • January 2022: Our research got featured on IISc homepage: Breakthrough Result in Computational Geometry.

  • January 2022: Our paper is accepted in IPCO'22.

  • December 2021: Gave an invited talk at International Graph Theory Seminar (organized by Martin Golumbic).

  • December 2021: Delighted to receive Google ExploreCSR Award.

  • December 2021: Our paper is accepted in AAAI'22.

  • November 2021: PhD student Vishakha Patil wins prestigious CII-SERB Prime Minister’s Fellowship for Doctoral Research. She was earlier a recipient of Google PhD fellowship and PMRF fellowship (declined).

  • October 2021: Elevated to the grade of IEEE Senior member.

  • October 2021: A paper is accepted in SODA'22. It makes progress on Maximum independent Set of Rectangles, a longstanding open problem in computational geometry and approximation algorithms.

  • September 2021: A paper is accepted in NeurIPS'21, provides near-optimal guarantees for multi-armed bandits under bounded arm-memory, an important problem in online learning.

  • August 2021: Delighted to receive Pratiksha Trust Young Investigator Award 2021.

  • July 2021: M.Tech research student Eklavya defended this thesis. His single-author paper got accepted in FSTTCS and another joint work was published in APPROX. He has joined UIUC for PhD. Congrats Eklavya!

  • July 2021: The journal version of FOCS'17 conference paper is accepted for the journal ACM Transactions on Algorithms (TALG).

  • July 2021: Gave an invited talk on Online Algorithms at IIITB Summer School on Theoretical Foundations of Computer Science . Video

  • June 2021: Two papers are accepted at APPROX/RANDOM 2021. The journal version of MFCS'20 conference paper is accepted for the journal Algorithmica.

  • May 2021: Five papers are accepted for contributed presentations at Highlights of Algorithms (HALG 2021).

  • March 2021: Gave a survey talk on multidimensional bin packing in bin packing seminar. See talk video and slides.

  • February 2021: Two papers are accepted at Symposium on Computational Geometry (SoCG 2021), the top venue for computational geometry.

  • January 2021: The journal version of APPROX'19 conference paper is accepted for the journal Algorithmica.

  • December 2020: A papers is accepted for full publication and oral presentation at International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2021 (Core A*).

  • September 2020: PhD Student Vishakha Patil wins prestigious Google PhD Fellowship. She is one of 53 recipients in all areas of CS in the world. One of the 4 students from India to win the fellowship this year. Vishakha also received PMRF fellowship (declined).

  • August 2020: Our paper receives the Best Paper Award at MFCS 2020, out of 242 submissions. This award is sponsored by EATCS (European Association for Theoretical Computer Science).

  • June 2020: Two papers are accepted at APPROX/RANDOM, 2020. One journal paper is published in Mathematical Programming.

  • February 2020: Invited talk at Recent Trends in Algorithms, IIT Gandhinagar, India, 2020.

  • February 2020: Invited talk at CALDAM Indo-French Pre-Conference School, IIT Hyderabad.

  • January 2020: Invited talk at research workshop at Santiago, Chile.

  • January 2020: Delighted to be a co-PI for the center on polynomials as an algorithmic paradigm, supported by Indo-US Science and Technology Forum (IUSSTF). This is a joint Indo-US Virtual Network Center with Georgia Tech, University of California Berkeley and TIFR Bombay. See the webpage for exciting talks and related research activities.

Other