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.