Arindam Khan

𝐓𝐡𝐞 𝐦𝐚𝐧 𝐰𝐡𝐨 𝐢𝐧𝐯𝐞𝐧𝐭𝐞𝐝 𝐐𝐮𝐢𝐜𝐤𝐬𝐨𝐫𝐭 𝐩𝐚𝐬𝐬𝐞𝐝 𝐚𝐰𝐚𝐲 𝐥𝐚𝐬𝐭 𝐰𝐞𝐞𝐤.

Turing Award winner Sir Tony Hoare passed away last Thursday at the age of 92. At age 26, he invented Quicksort -- Taught in UG algorithms and still one of the most elegant and widely used algorithms.

#CS #Algorithms #Quicksort

Most of us can trace our journeys back to a few people who shaped how we think & what we work on.
For me, two of them are Prof. Prasad Tetali (Carnegie Mellon University) & Prof. Mark de Berg (TU Eindhoven) -- both visiting us this week.

This week also marks the start of Mark's sabbatical at IISc!

Sandor Fekete visited IISc and gave an awesome talk on "Hard in Theory, Easy in Practice?"

𝗔𝗽𝗽𝗹𝗶𝗰𝗮𝘁𝗶𝗼𝗻 𝗣𝗿𝗼𝗰𝗲𝗱𝘂𝗿𝗲
Applicants should prepare the following documents in PDF format:
• Curriculum Vitae including publication list
• Research statement describing proposed research (1-2 pages)
• Contact details of two referees (they will be contacted later, if needed)

(6/6)

𝗘𝗹𝗶𝗴𝗶𝗯𝗶𝗹𝗶𝘁𝘆
Candidates must:
• Hold a Ph.D. in Computer Science (in areas related to Algorithms) at the time of joining, with an excellent research record
• Candidates who have submitted their Ph.D. thesis may also apply, provided proof of submission is included with the application.
(5/n)

𝗙𝗲𝗹𝗹𝗼𝘄𝘀𝗵𝗶𝗽 𝗢𝘃𝗲𝗿𝘃𝗶𝗲𝘄
Selected fellows will receive:
• A consolidated fellowship of ₹80,000–1,30,000 per month (depending on experience and profile).
• A research grant for conference travel, computing, and contingency support

Foreign nationals are eligible to apply.

(4/n)

𝗥𝗲𝘀𝗲𝗮𝗿𝗰𝗵 𝗔𝗿𝗲𝗮𝘀 (for postdoc applications)
• Approximation Algorithms
• Online Algorithms
• Fair Division and Algorithmic Game Theory
• Computational Geometry
• Data Structures
• Combinatorial Optimization
• Online Learning
• Beyond Worst-case Analysis
• Spectral Algorithms

(2/n)

𝗖𝗮𝗹𝗹 𝗳𝗼𝗿 𝗣𝗼𝘀𝘁𝗱𝗼𝗰𝘁𝗼𝗿𝗮𝗹 𝗙𝗲𝗹𝗹𝗼𝘄𝘀 𝗶𝗻 𝗔𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺𝘀 & 𝗧𝗵𝗲𝗼𝗿𝘆
𝗜𝗻𝗱𝗶𝗮𝗻 𝗜𝗻𝘀𝘁𝗶𝘁𝘂𝘁𝗲 𝗼𝗳 𝗦𝗰𝗶𝗲𝗻𝗰𝗲 (𝗜𝗜𝗦𝗰), 𝗕𝗲𝗻𝗴𝗮𝗹𝘂𝗿𝘂

The Algorithms group at IISc invites applications for multiple 𝗣𝗼𝘀𝘁-𝗗𝗼𝗰𝘁𝗼𝗿𝗮𝗹 𝗙𝗲𝗹𝗹𝗼𝘄𝘀𝗵𝗶𝗽𝘀 in Algorithms & Theory.

𝗔𝗽𝗽𝗹𝗶𝗰𝗮𝘁𝗶𝗼𝗻 𝗟𝗶𝗻𝗸: forms.gle/moz2vx7tiNFC...

𝗗𝗲𝗮𝗱𝗹𝗶𝗻𝗲: 28 February

#postdocs
(1/n)

How hard problems slowly give way -- Sometimes the payoff takes a decade. Some problems don’t yield to quick tricks. They demand patience, structural understanding, and the humility to fail repeatedly.

New Blog:
www.linkedin.com/pulse/how-ha...

Some problems don’t yield to quick tricks.
They demand patience and the humility to fail repeatedly.
If you're working on a hard problem & wondering whether it’s worth it: 𝗧𝗵𝗲 𝗽𝗮𝘆𝗼𝗳𝗳 𝗶𝘀 𝗼𝗳𝘁𝗲𝗻 𝗮 𝗱𝗲𝗰𝗮𝗱𝗲 𝗮𝘄𝗮𝘆. 𝗧𝗵𝗮𝘁’𝘀 𝗼𝗸𝗮𝘆.

#Research #CS #Theory #Algorithms

(6/6)

𝗥𝗲𝘀𝗲𝗮𝗿𝗰𝗵 𝗶𝘀 𝘆𝗲𝗮𝗿𝘀 𝗼𝗳 𝗳𝗮𝗶𝗹𝘂𝗿𝗲𝘀 𝗮𝗻𝗱 𝗮 𝗳𝗲𝘄 𝗱𝗮𝘆𝘀 𝗼𝗳 𝘀𝘂𝗰𝗰𝗲𝘀𝘀.

🥳 𝗧𝗼𝗱𝗮𝘆 𝗶𝘀 𝗼𝗻𝗲 𝗼𝗳 𝘁𝗵𝗼𝘀𝗲 𝗱𝗮𝘆𝘀. 🥳

(5/n)
📈 The results.
1️⃣ Settles a classical open problem
2️⃣ introduces a resource contraction lemma, a structural tool that is likely to be useful far beyond this specific problem.
3️⃣ The paper establishes connections to fine-grained complexity (k-SUM conjecture), and proves structural barriers.

(4/n) It generalizes the classical knapsack problem (NP-hard but admits PTAS).

The central question that resisted progress for decades was:
Can we get PTAS for the two-dimensional knapsack?
It's repeatedly appeared as a major open question in lists of the top open problems in geometric packing.

(3/n)

The problem: The two-dimensional geometric knapsack problem with rotations lies at the heart of packing, scheduling, and resource allocation.
The problem looks deceptively simple:
𝗚𝗶𝘃𝗲𝗻 𝗮 𝘀𝗲𝘁 𝗼𝗳 𝗿𝗲𝗰𝘁𝗮𝗻𝗴𝗹𝗲𝘀, 𝗽𝗮𝗰𝗸 𝗮𝘀 𝗺𝗮𝗻𝘆 𝗮𝘀 𝗽𝗼𝘀𝘀𝗶𝗯𝗹𝗲 𝗶𝗻𝘁𝗼 𝗮 𝘀𝗾𝘂𝗮𝗿𝗲 𝗶𝗻 𝗮𝗻 𝗮𝘅𝗶𝘀-𝗮𝗹𝗶𝗴𝗻𝗲𝗱 𝘄𝗮𝘆.

🚨 𝗣𝗮𝗽𝗲𝗿 𝗶𝗻 𝗦𝗧𝗢𝗖 𝟮𝟬𝟮𝟲 | 𝗔 𝗵𝗶𝘀𝘁𝗼𝗿𝗶𝗰 𝗳𝗶𝗿𝘀𝘁! (1/n)

🎉 Huge congratulations to my PhD student Debajyoti Kar and collaborator Andreas Wiese 🎉
Our joint work has been accepted at STOC 2026 on approximation schemes for geometric knapsack with rotations.

We show a mathematically grounded user-interest model capturing these effects and a near-optimal scheduling algorithm for ad timing.

The main takeaway is simple:
Uniform spacing is rarely optimal.
Timing that respects human psychology matters.

Link: arxiv.org/pdf/2509.20304

#ICLR #ML #Algorithms

We build an optimization framework grounded in three well-known effects from psychology:
Mere exposure: early repetitions can increase interest,
Hedonic adaptation: attention eventually decays,
Fatigue / operant conditioning: overexposure backfires.

𝐈𝐂𝐋𝐑 𝟐𝟎𝟐𝟔 𝐚𝐜𝐜𝐞𝐩𝐭𝐚𝐧𝐜𝐞: 𝐀𝐝𝐬 𝐭𝐡𝐚𝐭 𝐒𝐭𝐢𝐜𝐤

Most ad systems still do something very simple.
They space ads uniformly, or impose crude caps, and hope for the best.
Humans, unfortunately, are not uniform.

This paper asks a basic question:
What if ad scheduling actually respected how human attention works?

Unwavering Grit -- Lunch with "UG" Interns!

Over the past seven years, I have mentored around 40 UG interns, and 20-25 of them joined PhD programs at top universities around the world.
With curious and bright students, learning and enthusiasm flow both ways.

#Internship #TheoryCS

Traditionally hosted in India, FSTTCS is now taking a historic step. For the first time, FSTTCS 2026 will be held outside India, in Abu Dhabi, UAE.

Looking ahead, FSTTCS 2027 will be hosted at IIT Indore. I am delighted to serve as the PC Chair (Track A) for 2027.

#FSTTCS #India #CS #Theory

𝗙𝗦𝗧𝗧𝗖𝗦 𝗴𝗼𝗲𝘀 𝗶𝗻𝘁𝗲𝗿𝗻𝗮𝘁𝗶𝗼𝗻𝗮𝗹!

FSTTCS is a nearly 50-year-old flagship venue of IARCS (Indian Association for Research in Com Science).

This week, FSTTCS is underway at BITS Pilani, Goa. This edition is the largest ever, with 50 accepted papers, 8 workshops, and 350+ participants from 18+ countries.

𝗜𝗱𝗲𝗮𝘀 𝗢𝘃𝗲𝗿 𝗖𝗼𝗺𝗽𝘂𝘁𝗲. 𝗦𝗶𝗺𝗽𝗹𝗶𝗰𝗶𝘁𝘆 𝗢𝘃𝗲𝗿 𝗤𝘂𝗮𝗻𝘁𝗶𝘁𝘆.

Happy Theorists during Panel Discussions on Future of Graph Algorithms at the Department of Computer Science and Automation, Indian Institute of Science (IISc), Bangalore.

#IISc #India #Algorithms #Graphs

A fun-filled week of 𝗴𝗿𝗮𝗽𝗵 𝗮𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺𝘀 at IISc, a truly 𝗻𝗲𝘁𝘄𝗼𝗿𝗸𝗲𝗱 and 𝗱𝘆𝗻𝗮𝗺𝗶𝗰 event 𝗱𝗶𝘀𝘁𝗿𝗶𝗯𝘂𝘁𝗲𝗱 over five days, 𝘀𝘁𝗿𝗲𝗮𝗺𝗲𝗱 𝗼𝗻𝗹𝗶𝗻𝗲 and 𝗰𝗼𝗻𝗻𝗲𝗰𝘁𝗶𝗻𝗴 over 150 in-person participants from multiple countries. By many 𝗽𝗮𝗿𝗮𝗺𝗲𝘁𝗲𝗿𝘀, the 𝗯𝗶𝗴𝗴𝗲𝘀𝘁 𝗮𝗹𝗴𝗼𝗿𝗶𝘁𝗵𝗺𝘀 𝗲𝘃𝗲𝗻𝘁 ever in India!

#IISc #India #Algorithms #Graph

With some of the brightest minds I admire.
At my office during Graph Algorithms Workshop!
Debmalya Panigrahi (Duke), Anupam Gupta (NYU), Amit Kumar (IITD), @Sujoy Bhore (IITB), Madhusudhan Reddy Pittu (NYU), and Debajyoti Kar (IISc)!
With Erdős and Prasad Tetali in the background 🙂

#Algorithms

🚀 Biggest-ever Algorithms event in India -- starts tomorrow!

Thrilled to share that we are organizing the Frontiers of Graph Algorithms Workshop, happening from December 8–12, 2025, at the IISc! 🎓

Streaming Link: www.youtube.com/playlist?lis...

Details:
algo.csa.iisc.ac.in/graphworkshop/

Had a wonderful time visiting Université libre de Bruxelles (ULB), Brussels.

Photo with ALGO group (John Iacono, Stefan Langerman, and Jean Cardinal).

#Algo #Geometry

Excited to be at Dagstuhl this week for the seminar on 𝐎𝐧𝐥𝐢𝐧𝐞 𝐀𝐥𝐠𝐨𝐫𝐢𝐭𝐡𝐦𝐬 𝐁𝐞𝐲𝐨𝐧𝐝 𝐂𝐨𝐦𝐩𝐞𝐭𝐢𝐭𝐢𝐯𝐞 𝐀𝐧𝐚𝐥𝐲𝐬𝐢𝐬!

Key themes include learning-augmented algorithms, stochastic input models (random-order, IID, prophet), online algorithms with recourse, etc.

#Algorithms #Beyond-Competitive-Analysis

Registration Open: Ajit Diwan Memorial Workshop on Geometry, Graph, and Combinatorics.

📅 Dates: January 19–20, 2026
📍 Venue: RKMVERI, Belur

- No registration fee.
- Free boarding and lodging for participants.

cs.rkmvu.ac.in/ADMemorialWo...

Algorithms: DAA (IISc): Lec 6A. Closest Pair Problem (Divide and Conquer) YouTube video by Algo-rindam

Part1:

🏴󠁧󠁢󠁥󠁮󠁧󠁿 🇺🇸 English: www.youtube.com/watch?v=oLVj...

🇮🇳 🇧🇩 Bangla: www.youtube.com/watch?v=3NTp...

Part 2:

🏴󠁧󠁢󠁥󠁮󠁧󠁿 🇺🇸 English: www.youtube.com/watch?v=4-ms...

🇮🇳 🇧🇩 Bangla: www.youtube.com/watch?v=faDg...

Part 3:

🏴󠁧󠁢󠁥󠁮󠁧󠁿 🇺🇸 English: www.youtube.com/watch?v=-OeT...

🇮🇳 🇧🇩 Bangla: www.youtube.com/watch?v=x8rM...

⚔️ Divide and Conquer: Not just for empires, but also for matchmaking!

📢 New lecture on the Closest Pair Problem — a cornerstone of computational geometry and an elegant example of the divide-and-conquer paradigm.

(1/n)

All these rates are not uniform across subareas. Small subcommunities often push papers from their cliques.