How does the structure of a graph influence the arithmetic complexity of computing a polynomial associated with it? This question connects graph structure with fundamental computational models such as circuits, branching programs, and formulas. For graph homomorphism polynomials, several such connections are already known: treewidth characterizes monotone circuit complexity, pathwidth characterizes monotone algebraic branching program complexity, and treedepth characterizes monotone formula complexity. However, the corresponding picture for formulas with bounded product depth has remained incomplete.
In this talk, we introduce baggy elimination trees, a graph decomposition that generalizes elimination trees by allowing multiple vertices to be grouped into a single bag. We define a depth-restricted cost measure for these decompositions and show that it precisely characterizes the monotone formula complexity of graph homomorphism and colored isomorphism polynomials at bounded product depth. Our characterization also yields separations between monotone circuits and formulas of the same product depth, as well as a strict hierarchy between monotone formulas of consecutive product depths. These results show how structural properties of graphs can explain the computational limitations of different algebraic models.
CAPTCHAs rest on a simple premise: there are tasks humans find easy, and computers find hard. Can that premise be made rigorous, and does it survive contact with real adversaries? This talk examines “telling humans and computers apart” through three lenses: cryptographic reductions to hard AI problems, a game-theoretic view of an attacker who simply hires humans, and computational pricing as an alternative to proving humanity. Along the way, we ask what security means when the honest party is a person, why making a test harder can make it weaker, and whether, now that machines pass these tests better than we do, anything remains that only a human can prove.
Polynomial Identity Testing (PIT) is a foundational problem in algebraic complexity theory: given an arithmetic circuit over addition and multiplication gates, how do we determine whether it computes the zero polynomial? While PIT is well-studied in the commutative setting, asking the same question when variables do not commute (x1x2 ≠ x2x1) introduces fascinating structural and algorithmic challenges.
In this talk, we will explore the noncommutative PIT problem, focusing on circuits that compute sparse polynomials (those with a small number of monomials). We will examine an elegant solution that substitutes matrix variables in place of noncommuting indeterminates, showing that non-zero polynomials reliably remain non-zero under matrix evaluation (Paper). Additionally, we will discuss the classical Amitsur–Levitzki theorem and its application toward randomized PIT algorithms for small-degree noncommutative polynomials.
The talk will be self-contained, requiring only a basic background in linear algebra.
We study algorithms for detecting induced subgraphs corresponding to fixed pattern graphs in host graphs.
We show that at least five of the 21 connected graphs on five vertices can be detected in time roughly the product of the number of vertices and the number of edges, and that at least 65 of the 112 connected graphs on six vertices can be detected in time nearly quadratic in the number of edges. We also give algorithms for detecting induced paths and cycles on seven vertices, running in time roughly the number of vertices times the square of the number of edges.
Our main technical tool is a generalized notion of tree decomposition width, called (p, q)-width. It yields algorithms whose running times depend on both the number of vertices and the number of edges, and are never worse than existing bounds. Whenever the host graph has fewer than roughly quadratically many edges in its number of vertices, our bounds are strictly faster. For some patterns, including the seven-vertex cycle, our algorithms are optimal under standard complexity-theoretic assumption
We further develop this approach using pattern-based polynomials that exploit the structure of tree decompositions, not just their width. This gives algorithms for detecting induced paths and cycles on an even number of vertices in bipartite graphs, running in time roughly the (k-1)-th power of the number of edges for paths on 2k vertices, and that same bound times the number of vertices for cycles on 2k vertices. These are faster than the best known algorithms for general graphs.
Many classes of graphs can be defined by what is missing. In this talk, we will explore this theme of Forbidden Structures and see snapshots of some landmark results in Graph Colouring. This is an overview intended for students of all levels.
We are given an undirected weighted graph G with n vertices and m edges, edge weights in [1, W], and a designated source vertex s. We design a single-source dual fault-tolerant distance oracle for G. Given a destination vertex t and a set F of at most two faulty edges, the oracle returns a (1 + O(ε))-approximation of the weight of the shortest path from the source s to t avoiding F. Our oracle uses Õ(n√n) space and has Õ(1) query time. Prior to our result, single-source single-fault-tolerant oracles were known to return a (1 + ε)-approximation of the weight of the shortest path using Õ(n) space and O(1) query time. However, extending these approaches to multiple faults remained an open problem. Indeed, all (1 + ε)-approximate distance oracles that handle multiple faults require Ω(n²) space. We break this bound by presenting the first dual fault-tolerant distance oracle with o(n²) space.
This work is a collaboration with Prof. Manoj Gupta and has been accepted at ESA 2026.