STCS Annual Symposium 2025

09:20-09:30: Opening remarks.

In this talk, I will present three research vignettes spanning explainability, model editing, and quantum generative modeling. First, I will discuss a compelling problem in explainability that emerged from our experience deploying XraySetu-a diagnostic service launched during the COVID-19 pandemic. Second, I will describe our work on identifying structural components for model editing. Notably, our approach does not require access to the original training data or knowledge of the loss functions used to train the model. Instead, it hinges on a novel lower bound on the total variation (TV) distance via witness functions-a result that is of independent interest and, for example, enables upper bounds on the Bayes error rate for the Fisher Discriminant. Finally, time permitting, I will present ongoing work on learning algorithms for generative AI models in a quantum computing setting. In particular, I will outline our derivation of Minorant Maximization-style algorithms, in the spirit of Expectation-Maximization (EM), for large-scale transverse-field Ising models.

In the area of convex geometry, the approximation of volumes of convex bodies is an active area of research. In this talk, we will focus our attention to approximate the mixed volumes of convex bodies. The Steiner formula for evaluating volume of the linear combination of m - convex bodies in n-dimensional euclidean space along with respective m non-negative scalars is a multivariate homogeneous polynomial of degree n. The mixed volumes appear as coefficients of this multinomial.

In this talk, we will take a convex polytope K and the euclidean unit ball B in n-dimensional euclidean space. Given $\epsilon > 0$, will we see an algorithm to approximate all the mixed volumes appearing in the steiner formula for evaluating volume of K+B with a relative error of at most $\epsilon$ in polynomial time.

We study the distributed function computation problem with k users of which at most s may be controlled by an adversary and characterize the set of functions of the sources the decoder can reconstruct robustly in the following sense -- if the users behave honestly, the function is recovered with high probability (w.h.p.); if they behave adversarially, w.h.p, either one of the adversarial users will be identified or the function is recovered with vanishingly small distortion.

We study the binary hypothesis testing problem where an adversary may potentially corrupt a fraction of the samples. The detector is, however, permitted to abstain from making a decision if (and only if) the adversary is present. We consider a few natural "contamination models" and characterize for them the trade-off between the error exponents of the four types of errors – errors of deciding in favour of the incorrect hypothesis when the adversary is present and errors of abstaining or deciding in favour of the wrong hypothesis when the adversary is absent, under the two hypotheses. Further, we show that the worst-case error exponent when abstention is allowed is better than the worst-case error exponent without abstention, thereby demonstrating the value of abstention.

Learning paradigms based solely on offline data and those based solely on sequential online learning have been well studied in the literature. In this paper, we consider the combination of offline data with online learning, an area less studied but of obvious practical importance. We consider the stochastic multi-armed bandit problem, where our goal is to identify the arm with the highest mean in the presence of relevant offline data, with confidence $1-\delta$. We perform a lower-bound analysis on policies that provide such probabilistic correctness guarantees. We also identify a boundary region such that zero online samples are needed when the number of offline samples is above that region. We further develop plug-and-play algorithms that rely on the popular generalized likelihood ratio (GLR) method that asymptotically matches the lower bound even up to the multiplicative constant when off-line samples are sufficiently lower than the boundary region. When the offline samples are sufficiently close to the boundary region, the situation is more delicate. We conduct a detailed analysis to bring out conditions under which online sample complexity continues to match the lower bound, and where it does not due to fundamental statistical noise-driven limitations of the GLR method. Algorithms based on plug-and-play into the lower bound, while optimal, can be computationally prohibitive. In online settings, faster top-2 algorithms that are also computationally efficient have been devised. We observe that such algorithms can be suboptimal in our online-offline setting. We shed light on performance degradation and, through nuanced analysis, develop clairvoyant top-2 methods that perform asymptotically optimally. Further, we outline the fluid behavior of the proposed algorithm that illuminates its comparative advantage.

Stochastic two-player games model systems with an environment that is both adversarial and stochastic. In this talk, we look at the expected value of quantitative prefix-independent objectives in stochastic games. We show a generic reduction from the expectation problem to linearly many instances of almost-sure satisfaction of threshold Boolean objectives. We see the applicability of the framework to compute the expected window mean-payoff measure in stochastic games. The window mean-payoff measure strengthens the classical mean-payoff measure by computing the mean-payoff over a window of bounded length that slides along an infinite path. We show that the decision problem to check if the expected value is at least a given threshold is in UP ∩ coUP. The result follows from guessing the expected values of the vertices, partitioning them into value classes where each class consists of vertices with the same value, and proving that a unique short certificate for the expected values exists. This is joint work with Laurent Doyen and Shibashis Guha.

Combinatorial discrepancy is a fundamental problem in combinatorics with a rich history. The focus is on set systems, where we colour each element in order to minimise the maximum imbalance across all sets. To this end, we will see 3 key results: Beck-Fiala theorem that bounds discrepancy to O(n^1/2), the algorithmic approach of Spencer Lovasz Vesztergombi using geometric intuition, and Partial Colouring Lemma that leads to a constructive discrepancy bound proof. We will conclude the talk with some discussion on further developments and graph sparsification.

Constructing a Depth First Search (DFS) tree is a well known graph problem, whose parallel complexity is still not settled. While randomized parallel algorithms (and more recently, deterministic quasipolynomial parallel algorithms) are known for constructing a DFS tree in general (di)graphs, giving a deterministic parallel algorithm for DFS in general graphs remains an open question. For restricted graph classes, a series of works gave deterministic NC algorithms for DFS in planar graphs and digraphs. We further extend these results to more general graph classes, by providing NC algorithms for (di)graphs of bounded genus, and for undirected H-minor-free graphs where H is a fixed graph with at most one crossing. For the case of (di)graphs of bounded treewidth, we further improve the complexity to a Logspace bound. Constructing a maximal path is a simpler problem (that reduces to DFS) for which no deterministic parallel bounds are known for general graphs. For planar graphs a bound of O(log n) parallel time on a CRCW PRAM (thus in NC^2) is known. We improve this bound to Logspace.

The shortest path problem is one of the central problems in graph theory and algorithms. In the Replacement Path problem, we are given the source vertex s, the target vertex t, and the shortest path between them. The goal is to compute the cost of replacing each edge in this path - that is, for every edge e on the shortest path, we must find the length of the shortest path from ss to t that avoids e. We study this problem from a distributed perspective, where computational power and responsibility are distributed among the vertices. The algorithm presented will be in the CONGEST model.

Polynomial identity testing (PIT) is a central problem in theoretical computer science with numerous algorithmic applications, including applications to problems with no obvious algebraic character. Known polynomial-time algorithms for PIT crucially rely on the use of randomness. Designing a deterministic polynomial-time algorithm for PIT is a major goal of algebraic complexity theory. Often, algorithms for PIT are obtained by constructing pseudorandom objects known as hitting set generators, which are analogous to the pseudorandom generators seen in boolean derandomization problems like P versus BPP. Recently, there has been interest in constructing such hitting set generators in a “cryptographic” regime of parameters, where the complexity of the generator is very small compared to the class of algebraic circuits it fools. In this talk, I will describe a new construction of a generator where each output can be computed by a formula of constant size and the generator itself fools algebraic circuits of polynomial size and constant depth. Under strong (but reasonable) hardness assumptions, this same generator construction can be used to fool polynomial-size algebraic branching programs. No background in algebra or pseudorandomness is necessary!

Two matrices are said to be principal minor equivalent if they have equal corresponding principal minors of all orders. In this talk, I will discuss a characterization of principal minor equivalence and a deterministic polynomial time algorithm to check if two given matrices are principal minor equivalent. Earlier such results were known for certain special cases like symmetric matrices, skew-symmetric matrices with {0, 1, -1}-entries, and matrices with no cuts (i.e., for any non-trivial partition of the indices, the top right block or the bottom left block must have rank more than 1).

In this talk, we will see that algebraic formulas and constant-depth circuits are closed under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristic zero has a small constant-depth circuit or formula, then all its factors can be computed by small constant-depth circuits or formulas respectively. The result turns out to be an elementary consequence of a fundamental and surprising result of Furstenberg from the 1960s, which gives a non-iterative description of the power series roots of a bivariate polynomial. Combined with standard structural ideas in algebraic complexity, we observe that this theorem yields the desired closure results. Based on joint work with Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi and Shubhangi Saraf.

While efficient randomized algorithms for factorization of polynomials given by algebraic circuits have been known for decades, obtaining an even slightly non-trivial deterministic algorithm for this problem has remained an open question of great interest. This is true even when the input algebraic circuit has additional structure, for instance, when it is a constant-depth circuit. Indeed, no efficient deterministic algorithms are known even for the seemingly easier problem of factoring sparse polynomials or even the problem of testing the irreducibility of sparse polynomials. In this work, we make progress on these questions: we design a deterministic algorithm that runs in subexponential time, and when given as input a constant-depth algebraic circuit C over the field of rational numbers, it outputs algebraic circuits (of potentially unbounded depth) for all the irreducible factors of C, together with their multiplicities. In particular, we give the first subexponential time deterministic algorithm for factoring sparse polynomials. In a follow-up work, we show that algebraic formulas and constant-depth circuits are \emph{closed} under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristic zero has a small constant-depth circuit or formula, then all its factors can be computed by small constant-depth circuits or formulas respectively. As a consequence, we get a (significantly) simpler proof of correctness as well as stronger guarantees on the output in the subexponential time deterministic algorithm for factorization of constant-depth circuits

Mobile guards on the vertices of a graph are used to defend it against an infinite sequence of attacks on either its vertices or its edges. A defense against vertex attacks naturally corresponds to maintaining a dominating set, and a defense against edge attacks corresponds to maintaining a vertex cover. These games were introduced by Klostermeyer and Mynhardt. To be explicit, we are considering two player games --- between players whom we will refer to as the attacker and defender --- on a simple, undirected graph G. In the beginning, the defender can choose to place guards on some of the vertices of G. The attacker's move involves choosing an edge (vertex) to attack. The defender is able to defend this attack if she can move the guards along the edges of the graph in such a way that at least one guard moves along the attacked edge (vertex). If such a movement is not possible, then the attacker wins. If the defender can defend the graph against an infinite sequence of attacks, then the defender wins. The minimum number of guards with which the defender has a winning strategy is called the eternal vertex cover (eternal domination) number of the graph G. We will explore some structural aspects of these parameters, with a special focus on relating them to the corresponding static parameters. In particular, we will consider when the eternal vertex cover number coincides with the minimum vertex cover, and explore a structural characterization on bipartite graphs (based on joint work with Saraswati Nanoti). We will also explore the question of eternal domination on infinite grids (based on joint work with Tiziana Calamoneri, Federico Corò, Saraswati Girish Nanoti and Giacomo Paesani).

We study fragments of temporal logics over Mazurkiewicz traces which are well known and established partial-order models of concurrent behaviours. We focus on concurrent versions of "strict past" and ‘strict future’ modalities. Over words, the corresponding fragments have been shown to coincide with natural algebraic conditions on the recognizing monoids. We provide non-trivial generalizations of these classical results to traces. We exploit the local nature of the temporal modalities and obtain modular translations of specifications into asynchronous automata. More specifically, we provide novel characterizations of these fragments via local cascade products of a very simple two-state asynchronous automaton operating on a single process.

A seminal result of Nisan and Szegedy (STOC, 1992) shows that for any total Boolean function, the degree of the real polynomial that computes the function, and the minimal degree of a real polynomial that point-wise approximates the function, are at most polynomially separated. Extending this result from degree to other complexity measures like sparsity of the polynomial representation, or total weight of the coefficients, remains poorly understood. In this work, we consider this problem in the De Morgan basis, and prove an analogous result for the sparsity of the polynomials at a logarithmic scale. Our result further implies that the exact 1 norm and its approximate variant are also similarly related to each other at a log scale. This is in contrast to the Fourier basis, where the analog of our results are known to be false. Our proof is based on a novel random restriction method. Unlike most existing random restriction methods used in complexity theory, our random restriction process is adaptive and is based on how various complexity measures simplify during the restriction process. Joint work with: Arkadev Chattopadhyay and Shachar Lovett.

Itsykson and Sokolov (2014) identified resolution over parities, denoted by $ ext{Res}(\oplus)$, as a natural and simple fragment of $ ext{AC}^0[2]$-Frege for which no super-polynomial lower bounds on size of proofs are known. Building on a recent line of work, Efremenko and Itsykson (2025) proved lower bounds of the form $ ext{exp}(N^{\Omega(1)})$, on the size of $ ext{Res}(\oplus)$ proofs whose depth is upper bounded by $O(N\log N)$, where $N$ is the number of variables of the unsatisfiable CNF formula. The hard formula they used was Tseitin on an appropriately expanding graph, lifted by a $2$-stifling gadget. They posed the natural problem of proving super-polynomial lower bounds on the size of proofs that are $\Omega(N^{1+\epsilon})$ deep, for any constant $\epsilon > 0$. We provide a significant improvement by proving a lower bound on size of the form $ ext{exp}( ilde{\Omega}(N^{\epsilon}))$, as long as the depth of the $ ext{Res}(\oplus)$ proofs are $O(N^{2-\epsilon})$, for every $\epsilon > 0$. Our hard formula is again Tseitin on an expander graph, albeit lifted with a different type of gadget. Our gadget needs to have small correlation with all parities. An important ingredient in our work is to show that arbitrary distributions \emph{lifted} with such gadgets fool \emph{nice} affine spaces, an idea which originates in the earlier work of Bhattacharya, Chattopadhyay and Dvorak (2024). This is joint work with Arkadev Chattopadhyay

Classical cooperative game theory assumes that the worth of a coalition is determined solely by the \emph{set} of agents involved. In practice, however, the worth may also depend on the \emph{order} in which agents arrive. For example, if a highly skilled individual, rather than a less skilled one, leads the development of a company, the resulting market value may be significantly higher. Motivated by such scenarios, we introduce \emph{temporal cooperative games}, where the worth of a set of agents depends on their order of arrival. Here, the worth function $v$ becomes a function of a sequence of agents $\pi$, rather than just the set $S$ of agents. This shift requires a fundamental rethinking of the desired axioms from the classical setting.

A key property in this temporal framework is the \emph{incentive for optimal arrival} (I4OA), which encourages agents to join in the order that maximizes total worth. Alongside this, we define two additional natural properties: \emph{online individual rationality} (OIR), which incentivizes earlier agents to invite additional agents, and \emph{sequential efficiency} (S-EFF), which requires that the total worth for any sequence is fully distributed among its agents. We identify a class of reward-sharing mechanisms uniquely characterized by these three properties. The celebrated Shapley value does not directly apply here, as the worth function is no longer defined on coalitions. We construct natural analogs of the Shapley value in two variants: the \emph{sequential} world, where rewards are defined for each sequence-player pair, and the \emph{extended} world, where rewards are defined for each player alone. In the sequential world, we show that \emph{symmetry} follows from \emph{efficiency}, \emph{additivity}, and \emph{additivity}; these three properties uniquely determine the Shapley analogs in both worlds. Crucially, this class of mechanisms is disjoint from those satisfying the properties I4OA, OIR, and S-EFF. The conflict persists even for the restricted classes of \emph{convex} and \emph{simple} temporal cooperative games.

Our results thus reveal a fundamental tension: when players arrive sequentially, reward-sharing mechanisms that satisfy desirable temporal properties must differ in nature from Shapley value analogs.

[Joint work with Ashwin Goyal and Drashthi Doshi]

In the hidden action model of classical contract theory, a principal incentivizes an agent to take an action by offering a payment, termed a contract, that depends on the probabilistic outcome for the action taken. Prior work in contracts has studied various settings, including contracts with multiple principals. We introduce a new model for contracts between multiple principals and a single agent, where the principals can cooperate to improve their total utility, in contrast to prior work that emphasized competition between principals. In our model, the single agent chooses an action independently for each principal, and each principal then observes an outcome depending on the specific action. However, the principals can cooperate and offer a contract based on joint outcomes, rather than individual contracts based on their own outcome. We show that cooperating principals can have significantly greater power than a single principal. In fact, even for two cooperating principals, we show that the total utility can be nearly $n$ times larger than the sum of their individual utilities if they acted independently, where $n$ is the number of actions with any single principal. We then show that in any instance, as the number of principals increases, the principals can extract the entire social welfare. In both these results, cooperation severely disadvantages the agent, who is left with negligible utility when the principals cooperate. Finally, we study how the utility of a single principal is affected if the agent is given an additional action. We show that the availability of the additional action may reduce the principal's utility by a factor of $n$. All our bounds are tight or nearly tight.

The existence of EFX allocations is one of the most significant open questions in fair division. Recent work by Christodoulou, Fiat, Koutsoupias, and Sgouritsa (``Fair allocation in graphs,'' EC 2023) establishes the existence of EFX allocations for graphical valuations, when agents are vertices in a graph, items are edges, and each item has zero value for all agents other than those at its end-points. Thus, in this setting, each good has non-zero value for at most two agents, and there is at most one good valued by any pair of agents. This marks one of the few cases when an exact and complete EFX allocation is known to exist for more than three agents. In this work, we partially extend these results to multi-graphs, when each pair of vertices can have more than one edge between them. The existence of EFX allocations in multi-graphs is a natural open question given their existence in simple graphs. We show that EFX allocations exist, and can be computed in polynomial time, for agents with cancelable valuations in the following cases: (i) bipartite multi-graphs, (ii) multi-trees with monotone valuations, and (iii) multi-graphs with girth at least $(2t-1)$, where $t$ is the chromatic number of the multi-graph. The existence of EFX in cycle multi-graphs follows from (i), (iii), and the known existence of EFX for three agents.

How can we divide a set of indivisible items among multiple agents in a way that is both fair and respects structural constraints? In this talk, I will explore the problem of fair division under laminar matroid constraints, where agents have additive valuations and the allocation must adhere to nested capacity limits across groups of items. The fairness notion we aim to achieve is envy-freeness up to one item (EF1), a widely accepted relaxation in the indivisible setting. While EF1 allocations are known to exist in unconstrained domains, extending these guarantees to constrained settings is a growing area of interest. Prior work has addressed EF1 under cardinality and partition matroid constraints (Biswas & Barman, IJCAI 2018), and under certain conditions like identical valuations or two-agent settings (Dror et al., JAIR 2023). In this talk, I will present a constructive algorithm that guarantees an EF1 allocation for three agents under general laminar matroid constraints. The approach reduces the problem to a structured core subproblem involving six items across three categories, which we solve recursively while maintaining both feasibility and fairness.

Given an undirected graph G and a set A⊆V(G), an A-path is a path with endpoints in A and internal vertices in V(G)∖A. An (A,ℓ)-path has length exactly ℓ. The (A,ℓ)-Path Packing problem (ALPP) asks whether G contains k vertex-disjoint (A,ℓ)-paths. The problem is known to be FPT when parameterized by k+ℓ via color coding, but NP-hard for parameter k or ℓ alone. Belmonte et al. showed that ALPP parameterized by pathwidth+∣A∣ is W[1]-hard. We strengthen this by proving intractability for the larger parameter ∣A∣+dtp, where dtp is the distance to a path. Our proof uses a randomized reduction based on a variant of the isolation lemma, which we expect to have broader applications. This hardness result rules out the existence of FPT algorithms for several other parameters, including FVS+∣A∣ and treewidth+∣A∣. On the positive side, we give FPT algorithms for ALPP parameterized by CVD+∣A∣ and CVD+ℓ, where CVD (cluster vertex deletion number) is incomparable with treewidth. This is a joint work with Aritra Banik, Diptapriyo Majumdar, and Abhishek Sahu.

Analysis of two-player games played on graphs is central to reactive synthesis and it has been carried out in much detail. In this talk, we will explore some natural extensions of these games which are played between a distributed team of processes and an adversarial environment. Many real-life distributed applications can be modelled using them. Our games are played on a network of asynchronous processes modelled as finite-state devices which synchronize on shared actions and support true concurrency. Processes are allowed to exchange the entire casual past on shared actions to respond to the environment.

Given a distributed game structure and a winning objective, the key algorithmic problem is: whether a distributed winning strategy meeting that objective exists or not. We will discuss some special classes of these games with natural winning objectives such as global safety, local parity etc and develop algorithms to solve this key decision problem efficiently. Another important concern is: for the affirmative instance of the above problem, existence of a finite-state distributed winning strategy and its construction. For the above mentioned cases, we will see an explicit construction of a finite-state distributed winning strategy.

This is ongoing work with PhD student Nehul Jain.

17:00-17:10: Closing Remarks.