alt text
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: 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)

  • Best-Fit Bin Packing with Random Order Revisited, MFCS 2020. (paper)
    Recipient of Best Paper Award in MFCS 2020, sponsored by EATCS.
  • On Guillotine Separability of Squares and Rectangles, APPROX 2020. (paper)
  • A Tight (3/2 + epsilon) Approximation for Skewed Strip Packing, APPROX 2020. (paper)
  • On the Matching Augmentation Problem, Mathematical Programming (MAPR), vol 182, pages 315–354, 2020. (paper)
  • Improved Online Algorithms for Knapsack and GAP in the Random Order Model, APPROX 2019. (paper)
    (Also selected for presentation in Highlights in Algorithms (HALG) 2020.)
  • Approximating Geometric Knapsack via L-Packings, IEEE Symposium on Foundations of Computer Science (FOCS) 2017. (paper, slides, video)
    (Also selected for presentation in Highlights in Algorithms (HALG) 2018.)
  • 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.



  • PhD Students: 1. Vishakha Patil (Joint with Prof. Y. Narahari).

  • M.Tech(Research) Students: 2. Swati Allabadi (Joint with Dr. Anand Louis), 3. Eklavya Sharma.

  • Present/Past Undergraduate Interns/Project Assistants: Aditya Varre (IIT Bombay, now at EPFL Switzerland), Karthik Murali (NIT Suratkal, now at Univ. of Waterloo), Arnab Maiti (IIT Kharagpur), Amatya Sharma (IIT Kharagpur), Madhusudhan Reddy Pittu (IIT Kharagpur), Siddharth Jayashankar (IIT Kanpur), KVN Sreenivas (IIT Bombay), Kishen Gowda (IIT Gandhinagar), Debajyoti Kar (IIT Kharagpur), Siba Smarak Panigrahy (IIT Kharagpur), Debarsho Sannyashi (IIT Kanpur), Shreyans Nagori (IIT Delhi), Santanu Rathod (IIT Bombay).

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.

Recent News (2020)

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

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

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

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

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

  • July 2020: One papers is accepted at MFCS, 2020. Another paper is selected for short presentation in Highlights of Algorithms (HALG), 2020.

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

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