Past Seminars

Incorporating actual intelligence into the machines and making them think and perform like humans is impossible. In this talk, a new kind of machine called the EDLM (exact deep learning machine) is introduced. Such EDLMs can achieve the target with probability one and ould be the best alternative for originally designed artificial intelligence models of the mid20th century by Alan Turing and others that have so far not seen reality. In the current context,achieving a target is defined as detecting a given object accurately.

Primary key constraints in databases state there can be at most one tuple for every primary key in a given relation. However, these days it is common to have situations where this property cannot be maintained. Databases that violate constraints are called «inconsistent databases ». In particular, if a database violates primary key constraint, it will contain more than one tuple for the same primary key. In this setting, the notion of a repair is defined by picking exactly one tuple for each primary key (maximal consistent subset of the database). A Boolean conjunctive query q is certain for an inconsistent database D if q evaluates to true over all repairs of D. In this context, there is a dichotomy conjecture that states that for a fixed boolean conjunctive query q, testing whether q is certain for an input database D is either polynomial time or coNP-complete.

The conjecture is open in general and has been open for more than two decades. In this talk we will introduce two new algorithms that we have devised, one based on fix-point computation and the other based on bipartite matching. We will also see how these algorithms can be used to prove the dichotomy for the cases that were previously open.

These results were obtained in collaboration with Diego Figueira, Luc Segoufin and Cristina Sirangelo and combine the results that were presented at ICDT 2023 and PODS 2024.

A total coloring of a graph is an assignment of colors to all the elements of the graph, i.e both vertices and edges, such that any two adjacent elements receive different colors. The total chromatic index of a graph G is the minimum number of colors required in any total coloring of G. Vizing and Behzad independently conjectured that the total chromatic index of a graph G, with maximum degree Delta, is upper-bounded by Delta + 2. This classic conjecture, known as the total coloring conjecture, remains unsolved.

A graph G is said to be an s-degenerate graph if every subgraph of G has a neighbour with degree at most s. An adjacency vertex distinguishing total coloring or AVD total coloring of graph G is a total coloring of G that satisfies the condition that the set of colors seen by any two adjacent vertices are not equal. The set of colors seen by a vertex is the set of colors consisting of the vertex color and the colors of the edges incident on it. The minimum number of colors required for an AVD total coloring of a graph G is known as the AVD total chromatic number of G. The AVD total coloring conjecture, introduced by Zhang et al. in 2005, states that for any simple graph G the AVD total chromatic number is at most Delta + 3. We show the AVD total coloring conjecture to be true for 3-degenerate graphs.

The random oracle model (ROM) in cryptography, introduced by the seminal work of Bellare & Rogaway 1993, can be used to establish the security of a large class of cryptographic schemes. Simply put, the ROM takes a scheme's cryptographic hash function (an infinite binary sequence) to be randomly drawn from the uniform distribution over Cantor space. This assumption is often questioned as all hash functions in practice must be deterministic, i.e. they are particular elements of Cantor space. Examining which deterministic hash functions (if any) can be used to safely instantiate a scheme proven secure in the ROM is an active area research.

Tadaki & Doi 2015 show that Martin-Löf (ML) random sequences, often taken to represent exactly those sequences which are `truly random' in Cantor space, can serve to safely instantiate any signature scheme proven secure in the ROM. This is a philosophically beautiful result, but it is of little practical concern. In addition to being deterministic, all hash functions in practice must also be computable. ML random sequences, while deterministic, are not computable. Till now, it is an open conjecture whether all signature schemes proven secure in the ROM can be safely instantiated by a computable hash function.

While Tadaki & Doi 2015 are able to prove a version of this conjecture for any signature scheme proven ‘effectively’ secure in the ROM, the original problem has remained unsolved. In this talk, we will not appeal to any such notion of `effective' security. Instead, we solve the original problem and show that any signature scheme proven secure in the ROM can be safely instantiated by a single computable hash function. To do so we employ concepts from the literature on resource bounded randomness. We conclude by discussing how future work might attempt to characterize the computational complexity of such a hash function.

The graph coloring problem refers to assigning colors to the vertices of a graph such that no two adjacent vertices receive the same color. This is a widely studied topic in graph theory. As usual, ?(G) and ?(G) respectively denote the chromatic number and the clique number of a graph G. A family G is said to be H-free if for every G ? G, H is not an induced subgraph of G. In this talk, we discuss structural theorems for a few families of H-free graphs and compute their ?-binding functions.

A k-coloring of a graph G is an assignment of at most k colors to the vertices of G so that the ends of each edge get different colors. The reconfiguration graph of the k-colorings of a graph G, denoted Rk(G), is the graph whose vertices are the k-colorings of G and two colorings are adjacent in Rk(G) if they differ in color on exactly one vertex. We say that a graph G is recolorable if R?(G) is connected for all ? ? ?(G)+1. Here we discuss different techniques used in proving a graph is recolorable.

For a graph H, a graph G is H-free if no induced subgraph of G is isomorphic to H. For a collection of graphs H, G is H-free if G is H-free for every H ? H. We demonstrate how to use the modular decomposition of a graph class to prove that the graphs in the class are recolorable. In particular, we prove that every (P5, diamond)-free graph, every (P5, house,bull)-free graph, and every (P5, C5, co-fork)-free graph is recolorable.

A graph is prime if it cannot be decomposed by modular decomposition except into single vertices. For a prime graph H, we study the complexity of deciding if H is k-colorable and the complexity of deciding if there exists a path between two given k-colorings in Rk(H). A blowup of a graph G is a graph obtained by substituting non-empty cliques for some vertices of G. Suppose G is a hereditary class of graphs. We prove that if every blowup of every prime graph in G is recolorable, then every graph in G is recolorable.
This is a joint work with Kathie Cameron and Dewi Sintiari.

Linear layers are widely used in block ciphers to ensure diffusion, where small input differences are spread out to many outputs. The implementation cost of these circuits is measured by the number of XOR/CNOT gates used and the computation depth. In this talk, we discuss methods for optimising linear layer implementations by modelling it using elementary matrix decomposition. We will also distinguish how depth is calculated differently in classical and quantum circuits.

Actuarial mathematics is the science of modelling and managing uncertain future events, especially in insurance, pensions, and risk management. While probability provides the theoretical foundation, it is statistics that makes actuarial models operational by connecting them with real-world data. This seminar highlights the central role of statistics in actuarial practice, showing how data-driven methods enable actuaries to estimate, predict, and make informed financial decisions under uncertainty.

Key areas to be discussed include survival models and life contingencies, where statistical techniques underlie mortality estimation and survival analysis; risk models and loss distributions, where inference methods help quantify claims frequency and severity; and credibility theory, which anticipated modern Bayesian and hierarchical approaches. The seminar will also explore extreme value theory for modelling catastrophic risks, and stochastic processes for describing insurance events over time.

By linking actuarial concepts with statistical thinking, the talk will demonstrate how statistics transforms abstract probability models into practical tools for pricing, reserving, and risk assessment, making it indispensable to actuarial science.

We begin with discussing some key notions in mathematical logic. Next, we dive into classical modal logic, which shall take us to the notion of sabotage modal logic (SML) to deal with sabotage games. Subsequently, if time permits, we shall discuss sabotage games with imperfect information and a variant of SML to reason about such games.

This talk explores the model checking and satisfiability problems in logical systems for reasoning about knowledge and observations of intelligent agents and their interactions. We examine the foundations laid by Kripke and Hintikka, which paved the way towards the development of their dynamic counterparts, e.g., Public announcement logic, and its extensions like Dynamic epistemic logic and Public observation logic. Complexity studies for these logics stem from similar studies in temporal logics initiated by Halpern and Vardi, among others.

We focus on Public observation logic and analyze its model checking and satisfiability problems. By investigating these problems, we uncover insights into effective and efficient reasoning about knowledge in multi-agent scenarios. Moreover, we explore how these insights can be applied in solving standard problems in relevant domains like planning.

This talk is based on several works with Sourav Chakraborty (ISI Kolkata), Sujata Ghosh (ISI Chennai), François Schwarzentruber (ENS Lyon).

Game theorists have proposed backward induction as the reasoning procedure that rational players follow in turn-taking games. In order to find out how people really reason in such simple turn-taking games with perfect information, we designed certain centipede-like games and ran experiments with human participants, based on marble drop visualizations of the payoff structures. The participants played a perfect information game against a computer, which was programmed to deviate often from its backward induction strategy right at the beginning of the game. Participants knew that in each game, the computer was nevertheless optimizing against some belief about the participant's future strategy. In the course of the experiment, participants were asked questions about their own and the opponent's reasoning at all decision nodes of a sample game. We checked how their verbalized strategies fit to their choices in the experimental games. Although in the aggregate, participants tend to favor the forward induction choice, their verbalized strategies usually involve explicit theory of mind, their own attitudes towards risk, and those they assign to the opponent, as well as considerations about cooperativeness.

This is a joint work with Aviad Heifetz, Rineke Verbrugge and Harmen de Weerd.

Given an edge-colored (directed or undirected) graph, our objective is to find a specific type of subgraph, like a spanning tree, an arborescence, a single-source shortest path tree, a perfect matching, etc., with constraints on the number of edges of each color. Some of these problems, like color-constrained spanning tree, have elegant solutions, and some of them, like color-constrained perfect matching, are longstanding open questions. In this work, we study color-constrained arborescences and shortest path trees. Computing a color-constrained shortest path tree (CC-SPT) on weighted digraphs turns out to be NP-hard in general but polynomial-time solvable when all cycles have positive weight. This polynomial-time solvability is due to the fact that the solution space is essentially the set of all color-constrained arborescences (CC-ARB) of a directed acyclic subgraph of the original graph. While finding CC-ARB of digraphs is NP-hard in general, we give an efficient algorithm when the input digraph is acyclic. Our algorithm generalizes to the problem of finding a CC-SPT with the minimum total weight. Both our algorithms use a single-source shortest path algorithm and a (minimum cost) maximum flow algorithm as subroutines. By using the algorithm by van den Brand et al. (FOCS 2023) for these subroutines, our algorithms achieve near-linear running time when the edge weights are integral and polynomially-bounded in the size of the graph. Our approach can also be adapted to find a largest common independent set of two generalized partition matroids in near-linear time. 

TCS 2025: https://doi.org/10.1016/j.tcs.2025.115486