Seminars

by Sanjiva Prasad

Abstract: The talk explores a few elementary concepts from abstract algebra that (should) inform our data-centric development of common programs and data types, but are often elided in most textbook treatments. Included are sets, monoids, boolean algebras, semirings and Kleene algebras, structure-preserving maps and homomorphisms, and notions of co-induction. The talk is intended to be accessible to a general audience.

Coordinates: Bharti 501, 12 noon, 28th April 2025 (Monday)

---

by Surya Panchapakesan (IISER Pune)

Abstract: The central problem in fair division involves allocating a set of M indivisible goods among N agents in a fair and efficient manner. The quintessential fairness notion is "envy freeness" (EF) where every agent prefers their own assignment over that of any other agent's. In the deterministic setting, EF allocations may not always exist, motivating the study of relaxations such as envy-freeness up to any good (EFX). While deciding the existence of EFX allocations remains unresolved even for additive instances with just four agents, interestingly, Hosseini et al. showed that EFX allocations always exist and can be computed efficiently when agents have lexicographic preferences.

On the other hand, when randomization is allowed, it is easy to achieve EF in expectation (ex-ante) - simply by allocating all items to a single agent chosen uniformly at random. However, preserving ex-ante EF while ensuring that every deterministic allocation in the support also satisfies strong fairness guarantees (ex-post) is a far more non-trivial question. In this talk, I will discuss some of our approaches at computing randomized allocations under lexicographic valuations that achieve both ex-ante and ex-post fairness. I will first introduce some of the techniques we use in our methods, and then present an algorithm that achieves ex-ante 6/7-EF and ex-post EFX+PO. Following this (if time permits), we shall see a refinement that strengthens the ex-ante ratio to 9/10-EF while preserving the ex-post guarantees.

This talk is based on ongoing joint work with Rohit Vaish, Vignesh Viswanathan and Jatin Yadav.

Bio: Surya is a fifth-year BS-MS student at IISER Pune, majoring in mathematics. He is currently doing his MS Thesis under the supervision of Dr. Rohit Vaish at IIT Delhi. His current research interests lie in computational social choice, particularly in fair division. He is also keenly interested in combinatorics and graph theory.

Coordinates: Bharti 501, 12 noon, 15th April 2025 (Tuesday)

---

by Keerti Choudhary

Abstract: In this talk, we will look at O(Wn^\omega)-time algorithms for computing the Shortest Cycle, Radius, and Diameter of a graph with integral edge weights in the range [−W, W], under the condition that the graph does not contain negative-weight cycles. The talk will be based on the FOCS 2012 paper by Cygan, Gabow, and Sankowski.

Coordinates: Bharti 501, 12 noon, 2nd April 2025 (Wednesday)

---

by Surender Baswana (IIT Kanpur)

Abstract: Mincuts are one of the most well-researched topics in algorithms. In recent years, there has been phenomenal research on algorithms for computing \((s, t)\)-mincuts and global mincuts. On the other hand, the data structural and graph theoretical aspects of mincuts have also been well-researched in the last 50 years, though they are not as widely known despite being very fundamental and seminal. We shall begin with a light discussion of the following two classical results. (1) There is a directed acyclic graph that stores all (s,t)-mincuts of a graph. (2) There is a tree-like graph that stores all global mincuts of a graph. We shall then discuss a structure that stores Steiner mincuts - generalization of \((s,t)\)-mincuts and global mincuts. This structure, designed by Dinitz and Vainshtein is amazingly elegant and beautiful. We shall discuss this structure along with new and much simpler proofs of its properties. Note: Anyone with basic knowledge of algorithms and elementary graph theory should be able to follow most of the talk.

Bio: Surender Baswana is the Tapas Misra Memorial Chair Professor at the Department of Computer Science and Engineering at IIT Kanpur. He did B.Tech, M.Tech, and Ph.D. from IIT Delhi, and was a postdoctoral researcher at the Max Planck Institute for Computer Science. He has been a faculty member at IIT Kanpur since 2006. His research area is the design and analysis of algorithms.

Coordinates: Bharti 501, 12 noon, 28th March 2025 (Friday)

---

by Sandeep Sen (Ashoka University)

Abstract: Algorithm design and analysis has been primarily guided by the measure of worst-case complexity for many reasons including robustness, ease of composing them, and also well-understood guarantees. On the other hand, it has also been criticized for being narrow and single-track in its evaluation of efficiency of algorithms on a large class of inputs. Sometimes, the worst-case scenarios are considered as exceptions in which case, we may be missing out on the performance of more commonly occurring inputs. Average case analysis require assumptions about the input distribution that are not known or measurable.

We consider a measure called universal complexity/optimality that can address this gap, albeit, more difficult to achieve, has been gaining some traction. Further, we will try to relate this to a class of algorithms known as oblivious algorithms that could be a useful paradigm for attaining universal optimality. We will illustrate this using some simple examples but far from any general theory.

Coordinates: Bharti 501, 12-1 pm, 24 March 2025 (Monday)

---

by Venkata Koppula

Abstract: Consider a resource-bounded client that wants to outsource some computation \(C\) to a powerful server. The client might want the following desirable features.
(a) Verifiability: some proof that the server has indeed performed the computation \(C\).
(b) Blind delegation: the server performs the computation without learning anything about \(C\).

I will briefly discuss how these properties can achieved in the classical setting (where both client and server are classical, but the server is more powerful than the client). Next, I will discuss some recent progress for these questions in the quantum setting, where the server is quantum, and the client is classical. We will see how to solve both these problems (Verifiability and Blind delegation) using a single cryptographic tool.

This will be a (mostly non-technical) survey talk outlining the main results in this domain, and I will conclude with some open questions. No cryptography/quantum background will be assumed for this talk.

Coordinates: Bharti 501, 12-1 pm, 19 March 2025 (Wednesday)

---

by Syamantak Das (IIITD)

Abstract: In the online/dynamic bipartite metric matching problem, we are given two sets of size \(k\) each - the servers S which are fixed and known apriori and the client set R which is being revealed online. The goal is to assign a client to a free server as soon as it arrives. In the classical online model, there exists a tight bound of \(2k-1\) on the competitive ratio of any deterministic algorithm. A lower bound of \(\Omega(\log k)\) exists for any randomized algorithm while the best upper bound so far stays at \(O(\log^2 k)\).

In this talk, we shall deviate from the classical online model and consider the setting where reassignments are possible - that is, a client may be assigned to a different server in the future than the one currently serving it. Further, we shall also concern ourselves with the actual response time (also known as update time) of such algorithms in addition to good competitiveness. We will discuss a simple data-structure that supports insertion of clients with an amortized update time of \(O(k^{1 + \epsilon})\) while maintaining \(O(1/\epsilon)\) competitiveness. All existing algorithms for this problem rely on the classical Hungarian algorithm which inherently incurs a response time of \(\Omega(k^2)\) for each client arrival. The main contribution is to bypass this barrier by carefully combining a classical algorithm by Gabow and Tarjan along with a greedy push-relabel style greedy matching.

(Ongoing joint work with Sharath Raghvendra (NCSU) and Ritesh Seth (IIIT-Delhi)

Coordinates: Bharti 501, 12-1 pm, 3rd March 2025 (Monday)

---

by Raghuvansh Saxena (TIFR)

Abstract: We show how to convert any circuit of poly-logarithmic depth and polynomial size into a functionally equivalent circuit of polynomial size (and polynomial depth) that is resilient to adversarial short-circuit errors. Specifically, the resulting circuit computes the same function even if up to \(\epsilon d\) gates on every root-to-leaf path are short-circuited, i.e., their output is replaced with the value of one of its inputs, where \(d\) is the depth of the circuit and \(\epsilon > 0\) is a fixed constant.

Previously, such a result was known for formulas (Kalai-Lewko-Rao, FOCS 2012). It was also known how to convert general circuits to error resilient ones whose size is quasi-polynomial in the size of the original circuit (Efremenko et al.~STOC 2022). The reason both these works do not extend to our setting is that there may be many paths from the root to a given gate, and the resilient circuit needs to "remember" a lot of information about these paths, which causes it to be large. Our main idea is to reduce the amount of this information at the cost of increasing the depth of the resilient circuit.

Coordinates: Bharti 501, 12-1 pm, 17th February 2025 (Monday)

---

by Amit Kumar

Abstract: The online convex paging problem (Menache and Singh, 2015; Chiplunkar, Henzinger, Kale, and Votsch, 2023) models a broad class of cost functions for the classical paging problem. In particular, it naturally captures fairness constraints: e.g., that no specific page (or groups of pages) suffers an ``unfairly'' high number of evictions by considering \(\ell_p\) norms of eviction vectors for \(p>1\). The case of the \(\ell_\infty\) norm has also been of special interest, and is called min-max paging.

We give tight upper and lower bounds for the convex paging problem for a broad class of convex functions. Prior to our work, only fractional algorithms were known for this general setting. Moreover, our general result also improves on prior works for special cases of the problem. For example, it implies that the randomized competitive ratio of the min-max paging problem is \(\Theta(\log k\log n)\); this improves both the upper bound and the lower bound given in prior work by logarithmic factors. It also shows that the randomized and deterministic competitive ratios for \(\ell_p\)-norm paging are \(\Theta(p\log k)\) and \(\Theta(pk)\) respectively.

Coordinates: Bharti 501, 12-1 pm, 10th February 2025 (Monday)

---

by Naveen Garg

Abstract: In the dynamic metric \(k\)-median problem, we wish to maintain a set of \(k\) centers \(S \subseteq V\) in an input metric space \((V, d)\) that gets updated via point insertions/deletions, so as to minimize the objective \(\sum_{x \in V} \min_{y \in S} d(x, y)\). The quality of a dynamic algorithm is measured in terms of its approximation ratio, ``recourse'' (the number of changes in \(S\) per update) and ``update time'' (the time it takes to handle an update). The ultimate goal in this line of research is to obtain a dynamic \(O(1)\) approximation algorithm with \(\tilde{O}(1)\) recourse and \(\tilde{O}(k)\) update time.

We come close to resolving this goal by adapting a randomized local search to the dynamic setting. For every \(\epsilon > 0\), we give a dynamic \(k\)-median algorithm with \(O(1/\epsilon)\) approximation ratio, \(\tilde{O}(k^{\epsilon})\) recourse and \(\tilde{O}(k^{1+\epsilon})\) update time. This framework also generalizes to dynamic \(k\)-clustering with \(\ell^p\)-norm objectives. As a corollary, we obtain similar bounds for the dynamic \(k\)-means problem, and a new trade-off between approximation ratio, recourse and update time for the dynamic \(k\)-center problem.

Joint work with Sayan Bhattacharya, Martin Costa (U. Warwick), Silvio Lattanzi, Nikos Parotsidis (Google Zurich)

Coordinates: Bharti 501, 12-1 pm, 3rd February 2025 (Monday)

---

by Sourav Chakraborty (ISI Kolkata)

Abstract: We will present a very simple streaming algorithm on \(F0\) estimation that also caught the eye of Donald E. Knuth. In a recent article, Donald E. Knuth started with the following two paragraphs:

"Sourav Chakraborty, N. V. Vinodchandran, and Kuldeep S. Meel have recently proposed an interesting algorithm for the following problem: A stream of elements \((a_1, a_2,\ldots,a_m)\) is input, one at a time, and we want to know how many of them are distinct. In other words, if \(A = \{a_1, a_2,\ldots,a_m\}\) is the set of elements in the stream, with multiplicities ignored, we want to know |A|, the size of that set. But we don't have much memory; in fact, \(|A|\) is probably a lot larger than the number of elements that we can hold in memory at any one time. What is a good strategy for computing an unbiased estimate of \(|A|\)?
Their algorithm is not only interesting, it is extremely simple. Furthermore, it's wonderfully suited to teaching students who are learning the basics of computer science. (Indeed, ever since I saw it, a few days ago, I've been unable to resist trying to explain the ideas to just about everybody I meet.) Therefore I'm pretty sure that something like this will eventually become a standard textbook topic. This note is an initial approximation to what I might write about it, if I were preparing a textbook about data streams."

This simple algorithm comes out of the first ever "efficient" streaming algorithm (from PODS 21) for the Klee's Measure problem, which was a big open problem in the world of streaming for many years.

This work is based on joint works with N. V. Vinodchandran, and Kuldeep S. Meel across multiple articles, notable the following: (i) Estimating the Size of Union of Sets in Streaming Models. PODS 2021; (ii) Distinct Elements in Streams: An Algorithm for the (Text) Book. ESA 2022.

Bio: Sourav Chakraborty is a Professor in the Advanced Computing and Microelectronics Unit (ACMU) of the Computer and Communication Sciences Division (CCSD) at the Indian Statistical Institute (ISI), Kolkata, India. Prior to joining ISI in July 2018, Sourav was a faculty member at the Chennai Mathematical Institute, India, from September 2010.

Coordinates: Bharti 501, 12-1 pm, 27th January 2025 (Monday)

---

by Vijay V. Vazirani (University of California, Irvine)

Abstract: It is well known that the proof of some prominent results in mathematics took a very long time — decades and even centuries. The first proof of the Micali-Vazirani (MV) algorithm, for finding a maximum cardinality matching in general graphs, was recently completed — over four decades after the publication of the algorithm (1980). MV is still the most efficient known algorithm for the problem. In contrast, spectacular progress in the field of combinatorial optimization has led to improved running times for most other fundamental problems in the last three decades, including bipartite matching and max-flow.

The new ideas contained in the MV algorithm, and its proof remain largely unknown, and hence unexplored. We hope to rectify this shortcoming and use ideas from the proof to give a simpler exposition of the algorithm. Based on this paper.

Bio: Vijay Vazirani is a distinguished professor at the University of California, Irvine. A description of his research appears in the citation of his 2022 INFORMS John von Neumann Theory Prize. In 2001, he published Approximation Algorithms, which was followed by two co-edited books, Algorithmic Game Theory in 2007 and Online and Matching-Based Market Design in 2023.

Coordinates: Bharti 501, 2:30-3:30 pm, 20th January 2025 (Monday)

---

by Jai Moondra (Georgia Tech)

Abstract: Real-world optimization problems often involve balancing competing objectives, such as fairness objectives in resource allocation or the trade-off between regret and runtime in online learning. Traditional approaches rely on predefined composite objectives, which (i) require fixing a composite objective a priori (ii) can pose challenges to policymakers in selecting appropriate trade-offs and (iii) lead to unintended biases in outcomes. In this talk, I will present new approaches for addressing these challenges. First, motivated by organ transplantation policies, we introduce "fairness portfolios" for optimization problems, which are small sets of solutions such that any fairness objective is approximately satisfied by some solution in the portfolio. We study the trade-off between portfolio size and solution quality for classical problems such as scheduling and facility location, giving new approximation algorithms and a primal-dual counting technique. I will also discuss applications to real-world settings.

Next, I will discuss the trade-off between regret and runtime in online learning problems. Drawing from applications in recommendation systems, we demonstrate how combining discrete and continuous techniques over submodular base polytopes can significantly reduce runtimes of optimal-regret algorithms such as Mirror Descent.

Bio: Jai Moondra is a fifth-year PhD student at the School of Computer Science at Georgia Tech, advised by Dr. Swati Gupta (MIT) and Dr. Mohit Singh (Georgia Tech). He completed his B.Tech. in Computer Science from IIT Delhi in 2019. His research focuses on discrete optimization and its applications to algorithmic fairness, quantum computing, and machine learning.

Coordinates: Bharti 501, 12-1 pm, 6th January 2025 (Monday)

---

by Swati Gupta (MIT)

Abstract: When someone is denied a job, offered a different price for the same goods or services, or declined a loan, intent to discriminate is often not the case. The decision system applies the same data and rules to all and yet has a disproportionate effect on various groups. The causes of such disparate impact in machine learning and optimization are many, and these create an opportunity for us to develop new algorithms. I will present three such opportunities. The first is motivated by challenges due to bias and errors in evaluation data. I will present new optimization problems using ordinal data, which can create a pathway to solving discrimination in hiring (Management Science, 2023 with Salem, and UC Davis Law Review, 2023 with Salem and Desai). Next, I will discuss the challenge of selecting the “right” notion of fairness. I will present the concept of “portfolios”, that ask to find a small set of approximate solutions that summarize the set (potentially infinite) set of fairness objectives. I will showcase combinatorial techniques to tackle this challenge, and connections to polyhedral structure (EC 2023, SODA 2025, with Singh and Moondra). Finally, motivated by the recent lawsuits on price fluctuations, I will discuss challenges in trajectory-constrained stochastic optimization, which for example, can provide algorithms that monotonically change prices in demand learning (WINE 2022, with Kamble and Salem). This talk is based on joint work with Jad Salem, Deven Desai, Mohit Singh, Jai Moondra, and Vijay Kamble.

Bio: Dr. Swati Gupta is an Associate Professor at the MIT Sloan School of Management in the Operations Research and Statistics Group, and holds the Class of 1947 Career Development Professorship. She received a Ph.D. in Operations Research from MIT, and a dual Bachelors + Masters in Computer Science and Engineering from IIT Delhi. Her research interests include optimization and machine learning, with a focus on algorithmic fairness. Her work is cross-disciplinary and spans various domains such as hiring, admissions, e-commerce, healthcare, districting, power systems, and quantum optimization. She served as the lead of Ethical AI for the NSF AI Institute on Advances in Optimization, from 2021-2023. She has received the NSF CAREER Award in 2023, the JP Morgan Early Career Faculty Recognition in 2021, the NSF CISE Research Initiation Initiative Award in 2019, Simons-Berkeley Research Fellowship in 2017-2018, and the Google Women in Engineering Award (India) in 2011. Dr. Gupta’s research is partially funded by the National Science Foundation (NSF) and Defense Advanced Research Projects Agency (DARPA), as well as Social and Ethical Responsibilities in Computing (SERC) at MIT.

Coordinates: Bharti 501, 12-1 pm, 9th December 2024 (Monday)

---

by Poojan C Shah

Abstract: Could quantum machine learning someday run faster than classical machine learning? Over the past decade, the field of QML has produced many proposals for attaining large quantum speedups for computationally intensive tasks in machine learning and data analysis. However, it is unclear whether these speedups could be realized in end-to-end applications, as there had been no rigorous way to analyze such speedups. We see that a large class of QML algorithms which assume that the input data is provided in a "quantum accessible data structure" can actually be "dequantized" i.e, have classical counterparts which run in time only polynomially slower.

In this talk, we will briefly introduce and motivate the results and techniques of the algorithmic framework which began as a series of results started by Tang's breakthrough quantum-inspired classical algorithm for recommendation systems [STOC'19].

Coordinates: Bharti 501, 12-1 pm, 4th November 2024 (Monday)

---

by Surya Panchapakesan (IISER Pune)

Abstract: The central problem in fair division is to efficiently allocate a set of M (indivisible) items among N agents, such that the allocation satisfies constraints such as fairness, Pareto efficiency, maximizing Nash Social Welfare etc. In the past few years, there has been great interest to find randomized allocations that simultaneously achieve ex-ante (in expectation) and ex-post (after the randomization is realized) fairness guarantees.

In this talk, we will look at the contributions of this work by Feldman et al., who present the first best-of-both-worlds results for subadditive valuations. We shall see a novel randomized "envy cycle elimination" algorithm to produce allocations (in poly. time) that are simultaneously ex-ante 1/2-EF, ex-post 1/2-EFX and ex-post EF1 for subadditive valuations.

Coordinates: Bharti 501, 12-1 pm, 21st October 2024 (Monday)

---

by Pranjal Dutta

Abstract: Polynomial Identity Testing (PIT) is the problem of testing whether a succinctly given polynomial is zero. Though efficient randomized algorithms exist, derandomizing PIT is a fundamental challenge with remarkable consequences in algebraic complexity theory and various classical algorithmic problems. Significant progress has been made on this problem in the last decade. In this talk, we will present a comprehensive overview of these recent developments and discuss a few techniques behind them. This survey talk is based on many recent papers on PIT, and the survey, jointly written with Sumanta Ghosh (CMI), which got invited and published in the ACM SIGACT Complexity Theory Column; one can find it here.

Bio: Pranjal Dutta is currently a Postdoc at the School of Computing, NUS, hosted by Prof. Divesh Aggarwal. His broad research area is Complexity theory. He finished his PhD in Computer Science (2018-2022), from Chennai Mathematical Institute (CMI), under the guidance of Prof. Nitin Saxena (IIT Kanpur). He was a Google PhD Fellow (2018-2022) and subsequently, he won the ACM India Doctoral Dissertation Award 2023. He obtained his bachelor's in Mathematics and Computer science (2013-2016) and master's in Computer science (2016-2018) both from CMI.

Coordinates: Bharti 501, 12-1 pm, 16th October 2024 (Thursday)

---

by Sanjoy Dasgupta

Abstract: The widely-used k-means procedure returns k clusters that have arbitrary convex shapes. In high dimension, such a clustering might not be easy to understand. A more interpretable alternative is to constraint the clusters to be the leaves of a decision tree with axis-parallel splits; then each cluster is a hyperrectangle given by a small number of features. Is it always possible to find clusterings that are intepretable in this sense and yet have k-means cost that is close to the unconstrained optimum? A recent line of work has answered this in the affirmative and moreover shown that these interpretable clusterings are easy to construct. I will give a survey of these results: algorithms, methods of analysis, and open problems.

Bio: Sanjoy Dasgupta is Professor of Computer Science at UC San Diego. He works primarily on unsupervised and minimally supervised learning. He is the author of a textbook, Algorithms, with Christos Papadimitriou and Umesh Vazirani.

Coordinates: Bharti 501, 12-1 pm, 23rd September 2024 (Monday)

---

by Amit Kumar

Abstract: This work, by Yuda Feng and Shi Li, presents the first constant approximation for weighted Nash social welfare with additive valuations and received the Best Paper Award at ICALP 2024.

Coordinates: Bharti 501, 12-1 pm, 9th September 2024 (Monday)

---

by Shashwat Agrawal

Abstract: Deciding whether two given combinatorial or algebraic structures are isomorphic is a notorious question in the theory of computing. A well-known special case of this problem is the Graph Isomorphism Problem (GIP), in which given two graphs G1 and G2 one has to decide whether there exists an edge-preserving bijection from the vertex set of G1 to that of G2. Another example comes from Lattice theory, namely the Lattice Isomorphism Problem (LIP) in which given two lattices L1 and L2 one has to decide if there exists an orthogonal linear transformation mapping L1 to L2.

The best known algorithms for both these problems is 2^{O(√n)} and 2^{O(n logn)} respectively. However these problems are not known (in fact unlikely) to be NP-Hard. This motivates us to see what 'intermediate' complexity classes can these problems lie in.

SZK (Statistical Zero Knowledge) represents a class of decision problems for which there exists an interactive proof system where the verifier learns nothing beyond the validity of the statement being proven. SZK lies between P and PSPACE but is incomparable with NP.

In this talk we will briefly introduce SZK. We will then construct zero knowledge interactive proof systems for both GIP and LIP, showing that GIP, LIP are in SZK.

Coordinates: Bharti 501, 12-1 pm, 2nd September 2024 (Monday)

---