Current Trends in Algorithm Design
A workshop celebrating Samir Khuller’s 60th birthday
Join us for a special workshop in honor of Samir’s 60th anniversary! We’ll be celebrating Samir’s remarkable contributions and exploring exciting new developments in Theoretical Computer Science.
We look forward to celebrating with you!
When
Date: May 9th, 2025
Time: 2pm-6pm
Where
Northwestern University
Mudd Library 3rd floor (Room 3514)
2233 Tech Drive, Evanston IL, USA
Reception (6pm-8pm)
Ford Hive, Room 2350 (Technological Institute, 2145 Sheridan Road, Evanston, IL 60208)
Parking: For those driving to the workshop, attendees can park in the North Campus garage 2311 N Campus Dr #2300, Evanston, IL 60208. https://maps.northwestern.edu/
Workshop Program
There will be technical talks in the afternoon, followed by a reception in the Tech building.
Schedule
| Time | Session Title | Speaker | Relationship |
| 02:00 – 2:05 | Opening Remarks | Aravindan Vijayaraghavan (Northwestern) | Colleague |
| 2:05 – 2:20 | Approximate shortest path trees | Frederic Koehler (U. Chicago) | UG Mentee REU |
| 2:20 – 2:35 | Facility Location | Sudipto Guha (ZScalar) | Collaborator |
| 2:35 – 2:50 | Allocating Wisdom and Matching Milestones | Quanquan Liu (Yale) | Postdoc Northwestern |
| 2:50 – 3:05 | Fair Resource Allocation under Structured Constraints | Arpita Biswas (Rutgers) | Collaborator |
| 3:05 – 3:20 | Reflections from Northwestern | Sara Sood (Northwestern) | Colleague |
| 3:20 – 3:30 | Dean Christopher Schuh (Northwestern) | ||
| 3:30 – 3:40 | Jason Harline (Northwestern) | Colleague | |
| 3:40 – 4:00 | Coffee Break | ||
| 4:00 – 4:15 | Online metric matching with advice | Julian Mestre (U Sydney) | Ph.D. U. Maryland 2007 |
| 4:15 – 4:30 | Linear Elastic Caching via Ski Rental | Manish Purohit (Google) | Ph.D. U. Maryland 2016 |
| 4:30 – 4:45 | Approximation Algorithms: Now and Then | Barna Saha (UC San Diego) | Ph.D U. Maryland 2011 |
| 4:45 – 5:00 | Mechanism Design with Deferred Inspection | Azaraksh Malekian (U Toronto) | Ph.D U. Maryland 2009 |
| 5:00 – 5:15 | The power of collaboration: Building the Iribe Center | Stacey Sickels Boyce (Stanford) | Collaborator |
| 5:15 – 5:30 | My association with Samir for more than a quarter century | Rajiv Gandhi (Rutgers U/U Penn) | Ph.D. U. Maryland 2003 |
| 5:30 – 5:45 | Closing remarks | Samir Khuller (Northwestern) | Chair of Computer Science |
| 5:45 – 6:00 | |||
| 6:00 – 8:00 | Reception | Ford Hive, Room 2350 (Technological Institute, 2145 Sheridan Road, Evanston, IL 60208) | |
Abstracts
- Approximate shortest path trees (Frederic Koehler)
The structure of approximate shortest paths in random graphs is surprisingly interesting. I will mention some related phenomena which appear when we look at shortest path trees. - Facility Location (Sudipto Guha)
The facility location problem has been the location for developing many great algorithmic techniques. This talk showcases some of the aspects of Samir’s work in approximation algorithms for facility location that remain relevant to this day. - Allocating Wismon and Matching Milestones (Quanquan Liu)
In this talk, we’ll discuss maximum matching and fair allocations with timeless wisdom from Samir sprinkled in. Fair allocation keeps classrooms balanced and students happy. In this celebratory talk, I’ll trace how our algorithms with Samir—from scalable auction methods to conflict-free course assignment—have shaped both theory and practice. Along the way, expect a few personal favorite “Samir-isms,” photographs from my time at Northwestern, and the lessons he still teaches us about curiosity, collaboration, and keeping theory elegant at any point in our lives. - Fair Resource Allocation under Structured Constraints (Arpita Biswas)
The problem of fairly allocating indivisible items among a set of heterogeneous agents with competing preferences is a fundamental and challenging problem in the field of computational social choice theory. The problem becomes more computationally challenging when there are additional constraints on the type of allocation that could be made, for example, each allocate bundle may need to meet cardinality constraints, laminar constraints, matroid constraints, non-conflicting constraints, and other graphical constraints. The goal is to obtain a fair and feasible allocation of items among the agents while ensuring that each allocated bundle is feasible. In this talk, I’ll discuss various fairness notions, such as maximin fairness and almost envy freeness, that are pertinent to this problem of fair allocation. I’ll present algorithmic solutions designed for different models of agent preferences, and highlight key open questions in this rich and evolving research area. - Linear Elastic Caching via Ski Rental (Manish Purohit)
We study the Linear Elastic Caching problem, where the goal is to minimize the total cost of a cache inclusive of not just its misses, but also its memory footprint integrated over time. We demonstrate a theoretical connection to the classic ski rental problem and propose a practical algorithm that combines online caching algorithms with ski rental policies. We also introduce a lightweight machine learning-based algorithm for ski rental that is optimized for production workloads and is easy to integrate within existing database systems. - Approximation Algorithms: Now and Then (Barna Saha)
In this talk we will explore the evolution of approximation algorithms landscape in the last two decades. - Mechanism Design with Deferred Inspection (Azaraksh Malekian)
Motivated by applications in e-commerce, we consider a mechanism design setting in which, after the allocation, the designer can inspect the buyer’s true type and adjust the payment. This means that the allocation is based on the reported types, but the payment is based on both the reported and true types. We will highlight how the analysis departs from the classical mechanism design. Using techniques from convex analysis and calculus of variations, we fully characterize the optimal mechanism for a single agent for any distribution of values. Then, using Border’s theorem and duality, we find conditions under which our characterization extends to multiple agents. Interestingly, the optimal allocation function, unlike the classic settings without inspection, is not a threshold strategy and instead is an increasing and continuous function of the types. Based on joint work with Saeed Alaei, Alex Belloni, and Ali Makhdoumi. - Online metric matching with advice (Julian Mestre)
In this talk I will revisit a classical result of Samir for online metric biparite matching by looking at the problem through the les of learning-augmented algorithms. - My association with Samir for more than a quarter century: Research, Conversations, Secrets, and more (Rajiv Gandhi)
I will discuss the things that I have learned from Samir and about Samir since I first met him in 1998.
Recent Comments