How combinatorics stands in the way of matrix reachability (and what we can do about that)

26^th November 2024, 13:00 Ashton Lecture Theatre
Andrew Ryzhikov
University of Oxford

Abstract

Fundamental questions about products of matrices from a given finite set (that is, matrix semigroups) arise in many areas of mathematics and computer science, such as linear dynamical systems, weighted automata, computer algebra, etc. Such problems are computationally hard even in very restricted settings. One of the reasons is that transformations (maps from a finite set to itself) can be expressed by zero-one matrices with at most one 1 in every row, with composition corresponding to the usual matrix product. I will discuss why this is often a "trivial" obstacle for having rich mathematical structure in problems, and what we can do about that. I will also briefly mention the Černý conjecture, explain why I think it is overrated, and propose some lesser-known but (in my opinion) more interesting open problems of similar flavour. The talk is aimed at the general theoretical computer science/combinatorics audience, and will be light and undemanding.

Biography

Andrew Ryzhikov is a postdoc at the University of Oxford, interested in automata theory, matrix theory and logic. He did his PhD in synchronising automata and the theory of codes at Université Paris-Est under the supervision of Dominique Perrin. He is broadly interested in interactions between algebra and combinatorics from the point of view of theoretical computer science.