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 and Combinatorial Optimization. I am also interested in Computational Geometry, Graph Algorithms, Parameterized Algorithms and Online Learning.

Selected Recent Publications: (with co-authors)

  • Improved Online Algorithms for Knapsack and GAP in the Random Order Model, APPROX 2019. (paper)
  • On the Matching Augmentation Problem, To appear in journal: Mathematical Programming (MAPR) 2019. (paper)
  • Approximating Geometric Knapsack via L-Packings, IEEE Symposium on Foundations of Computer Science (FOCS) 2017. (paper, slides, video)
  • 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.


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.


  • News: Jan 1, 2019: Joined IISc.

  • Reviewer/subreviewer for conferences: STOC, SODA, ITCS, ICALP, ESA, SPAA, FSTTCS, APPROX, STACS, WAOA, CIAC, WG etc.

  • Reviewer/subreviewer for journals: SIAM Journal on Computing (SICOMP), IEEE Transactions on Information Theory, Algorithmica, Mathematical Programming, Discrete Optimization, Journal of Scheduling, Informs Journal on Computing etc.

  • Why CSA@IISc?, Why Theory@IISc?, Theory Lunch, Reading Group .

  • Funfacts, Other Useful Links.