BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260408T151816Z
UID:Seminar-dept-1254@lxserverC.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20241126T130000
DTEND:20241126T140000
SUMMARY:School Seminar Series
DESCRIPTION:Andrew Ryzhikov: How combinatorics stands in the way of matrix reachability (and what we can do about that)\n\nFundamental 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.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1254
LOCATION:Ashton Lecture Theatre
END:VEVENT
END:VCALENDAR