|
Arindam Khan
I am an Associate Professor in the CSA Department at IISc.
I obtained my PhD in Algorithms, Combinatorics, and Optimization (ACO) (from School of Computer Science) and an MS in Mathematics from Georgia Institute of Technology, Atlanta, USA.
Before that I got my BTech and MTech (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.
Awards and Honors:
-- Best Paper Award, MFCS 2020,
-- Prof. Priti Shankar Teaching Award 2023,
-- Google India Research Award 2021, and
-- Pratiksha Trust Young Investigator Award 2021
Recent PCs: SODA'26, SODA'25, FSTTCS'24, APPROX'24, LATIN'24, WAOA '23, FCT'23, SoCG'23; Graduate Forum Chair IndoML'24, Area Chair ACM ARCS Event.
Co-organizer: Frontiers of Graph Algorithms 2025, Algorithmic Foundations of ML 2024, Theory CS Winter School 2024, Frontiers of Geometric Algorithms 2024, Art of Computing 2023, Bin Packing Seminar 2021.
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, Computational Geometry, Online Learning, and Combinatorial Optimization. I am also interested in
Fairness, Algorithms for Big Data, and Machine Learning Theory.
Selected Recent Publications: (with co-authors)
- Improved Approximation Algorithms for Three-Dimensional Bin Packing, ICALP 2025.
(paper)
- Improved Approximation Algorithms for Three-Dimensional Knapsack, SoCG 2025.
(paper)
- Bin Packing under Random-Order: Breaking the Barrier of 3/2, SODA 2024.
(paper)
- On Approximation Schemes for Stabbing Rectilinear Polygons, FSTTCS 2024.
(paper)
- Random-Order Online Independent Set of Intervals and Hyperrectangles, ESA 2024.
(paper)
- Approximation Algorithms for Geometric Knapsack for Packing Spheres and Fat Objects, ICALP 2024.
(paper)
- Guaranteeing Envy-Freeness under Generalized Assignment
Constraints, EC 2023.
(paper)
- Mitigating Disparity while Maximizing Reward: Tight Anytime Guarantee for Improving Bandits, IJCAI 2023.
(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
Interns, Students, and PostDocs
Postdocs:
D1. Mohit Garg, [PhD, TIFR] [2023 April - present]
D2. Akash Pareek, [PhD, IIT GN] [2024 July - present]
PhD Students:
P2. Aditya Subramanian, [Recipient of KIAC (Kotak AI/ML Center) Fellowship]
P3. KVN Sreenivas, [Recipient of Google PhD Fellowship, Direct-entry PMRF Fellowship (declined)]
P4. Debajyoti Kar (co-advising with Siddharth Barman). [Recipient of Google PhD Fellowship, Direct-entry PMRF Fellowship (declined)] Past Postdocs:
D3. Soumi Nandi, [PhD, ISI Kolkata -> IMSc] [2024 August - 2025 February]
Graduated PhD Students: (submitted PhD thesis)
P1. Vishakha Patil (Co-advised with Prof. Y. Narahari).
Thesis: Exploring Fairness and Causality in Online Decision-Making (pdf).
[Recipient of Google PhD Fellowship, PMRF Fellowship (declined), CII-SERB Prime Minister’s
Fellowship for Doctoral Research] Graduated M.Tech (Research) Students:
MR1. Eklavya Sharma (-> PhD student at UIUC, USA).
Thesis: Approximation Algorithms for Geometric Packing Problems (pdf).
[Recipient of Dr. MNS Swamy
Medal for Best MTech (Research)
Thesis 2022 ]
MR2. Swati Allabadi (-> Software Engineer at Siemens)(Co-advised 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).
[Recipient of Dr. MNS Swamy
Medal for Best MTech (Research)
Thesis 2023 ]
MR4. Aditya Lonkar (-> PhD student at Georgia Tech, USA).
Thesis: Algorithms for Geometric Packing and Covering Problems (pdf).
[Recipient of Dr. MNS Swamy
Medal for Best MTech (Research)
Thesis 2024 ]
Graduated M.Tech (Coursework) Students:
MT1. Arka Ray (-> RA at IISc). Thesis: Approximability of Packing and Covering Problems (pdf).
MT2. Rounak Das,
MT3. Sudhanshu More, Graduated BS (IISc) Students:
U1. Anish Hebbar (-> PhD student at Duke University, USA).
Thesis: Online Bin Packing under Random Order Arrival (pdf).
Undergraduate Interns/Project Assistants:
Arnab Maiti (IIT Kharagpur -> U Washington) [See: How IISc changed my life],
Madhusudhan Reddy Pittu (IIT Kharagpur -> Carnegie Mellon University) [See: Exchange Diaries],
Amatya Sharma (IIT Kharagpur -> U Michigan), 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 -> University of Southern California), Divyanshi Rajput (IIIT Bangalore) [Through Google exploreCS Research Award], Aryan Agarwala (CMI -> MPII Germany), Prayas Routray (IISc -> NUS), Aaryan Gupta (IIT Bombay), Pritam Acharya (IISER Pune), Bratin Mondal (IIT Kharagpur), Pradyot Mohanty (CMI), Samyak Jha (IIT Bombay), Sooraj A P (IIT Bombay), Kailash Gopal D (IIT Madras), Sreehari C (IIT G), Soumyaprava Dey (IIT Delhi). Project Associates/Predocs:
Aditya Varre (IIT Bombay-> EPFL Switzerland), Karthik Murali (NIT Suratkal -> Univ. of Waterloo), KVN Sreenivas (IIT Bombay -> IISc), Santanu Rathod (IIT Bombay -> ELLIS PhD at Cambridge), Rajni Dabas (DU, through ACM India Anveshan Setu Fellowship), Dhawal Jethwani (IIT BHU), Sudharshan Shyam (IIT Kharagpur/UCSD->Aarhus), Neel Karia (IIT Kharagpur/MSR -> Columbia), Shashankh Chandarr (IITK/École Polytechnique), Vijaykrishna Gurunathan (IITB/Stanford).
Available positions
-
Postdoc: One postdoc position is available (salary upto 1,30,000 INR/month). 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, SOCG, EC, ICALP, ESA, APPROX, IPCO, ITCS, etc., please send me an email.
-
Project Assistant/Interns/Predocs: I have short-term/intern/Predoc positions available (salary upto 40,000 INR/month). 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
- Frontiers of Graph Algorithms:
The Algorithms group at IISc --- supported by the Walmart Center--- is organizing a workshop on "Frontiers of Graph Algorithms" during 9-12 December 2025.
- Frontiers of Geometric Algorithms:
The Algorithms group at IISc --- supported by the Walmart Center---organized a workshop on "Frontiers of Geometric Algorithms" between 11-15 December 2024.
This was a momentous event on Algorithms --- with 30 eminent speakers (24 international speakers) from 28 universities in 8 countries and more than 70 faculty participants from around the globe.
List of Twenty-Five Open Problems from the workshop.
- Algorithmic Foundations of ML:
The Algorithms group at IISc --- supported by the Walmart Center---organized a lecture series on "Algorithmic Foundations of Machine Learning" during 15-16 December 2024.
- Winter School:
The Algorithms group at IISc --- supported by the Walmart Center---organized an winter school for UGs on "Theory CS" between 7-10 December 2024. The event was attended by 100+ students from 35+ universities in 16 states in India.
- Art of Computing:
The Algorithms group at IISc has organized an outreach event "Art of Computing" during 17-18 February 2024.
- Equitable AI Lab:
I am a co-PI for Equitable AI Lab, supported by a generous grant from Ittiam Systems.
- Walmart Center for Tech Excellence:
I am a co-PI for Walmart Center for Tech Excellence
, supported by a generous grant from Walmart. The center supports predocs, PhDs, postdocs, and also hosts several international research workshops and outreach events.
- 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 (2022-25)
April 2025: New paper accepted at ICALP. Gives an improved approximation algorithm for 3D bin packing, a fundamental problem in combinatorial optimization and computational geometry -- an improvement after three decades!
January 2025: New paper accepted at SoCG. Gives an improved approximation algorithm for 3D knapsack, a fundamental problem in combinatorial optimization and computational geometry -- an improvement after 17 years!
December 2024: Ten-day long Algorithms fest at IISc: Frontiers of Geometric Algorithms, Winter School on Theory CS, Algorithmic Foundations of Machine Learning.
December 2024: Excited to be part of Equitable AI initiative at IISc -- supported by Ittiam. Press Release.
September 2024: Attended Workshop on Massive Data Models and Computational Geometry at Hausdorff School of Mathematics, Bonn, Germany.
July 2023: KVN Sreenivas received Dr. MNS Swamy Medal for Best MTech (Research) Thesis 2023. June 2024: A month spent in Europe. Visited University of Copenhagen, Denmark and MPII, Germany. Also, attended Highlights of Algorithms in Poland, SoCG in Greece, and MAPSP in Denmark.
June 2024: Tenured! Received fast-track promotion (effective from March, 2024).
May 2024: Serving as PC Member in SODA 2025 and FSTTCS 2024. Please submit your papers! April 2024: Gave an invited talk at Workshop on Computational and Combinatorial Geometry at ISI Kolkata. April 2024: Inauguration of Walmart Center for Tech Excellence
at IISc. April 2024: New paper acceptance in ICALP'24 on sphere packing. February 2024: Organized Art of Computing -- a workshop dedicated to the beauty of Computer Science. November 2023: Debajyoti Kar receives prestigious Google PhD Fellowship. One of the seven recipients in the world in Algorithms and Theory. September 2023: New SODA paper, with Anish Hebbar and KVN Sreenivas, makes progress on Kenyon's classical conjecture from SODA'95 on Best-Fit Bin Packing. Anish was a BS student at IISc and now have joined Duke university for PhD. This is the first instance of a SODA paper by an UG from IISc. Congrats Anish! August 2023: Aditya Lonkar defends his MTech (Research) thesis. He is joining Georgia Tech ACO PhD program. Congrats Aditya! July 2023: Eklavya Sharma received Dr. MNS Swamy Medal for Best MTech (Research) Thesis 2022. June 2023: Travel to USA -- PolyAlg visit at Berkeley, CA; SOCG at Dallas, TX; STOC at Orlando, FL; ARC Seminar at Georgia Tech, GA. March 2023: Received Prof. Priti Shankar Teaching Award for Assistant Professors. 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: 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 (a longstanding open problem in computational geometry and approximation algorithms) was mentioned in Communications of the ACM (CACM) as one of the top results from India during 2019-2022. 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: 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).
January 2022: Elevated to the grade of IEEE Senior member.
Other
|
hide forever |
hide once
