Vector Addition Systems
Wojciech Czerwiński (University of Warsaw).
Course Summary |
About the lecturer |
Location and schedule
Videos
|
Assignment
The topic of the lecture will be Vector Addition Systems (VASes), which are a fundamental model of computation. Despite of having a very simple definition many basic problems for these systems are still poorly understood. I will focus on the reachability problem, which asks whether a given target vector can be reached from a starting vector by a sequence of moves (each one adding a single vector). A lot of research on VASes concentrates on this problem, as it is representative of the complex structure of VASes. Understanding the complexity of this problem remains a challenge since a few decades already. I will present a few combinatorial techniques used in the field, each one interesting in its own. I plan to finish with an open problem, whose solving is currently a challenging goal.
About the lecturer:Wojciech Czerwiński is an assistant professor at the University of Warsaw, he received his habilitation degree in 2020. He obtained significant results on various topics, publishing at SODA, PODS, CONCUR, LICS, among others. He developed a research program pursuing the separation problem in automata theory. But his most spectacular achievement till now was an improvement of the lower bound for the reachability problem in Petri nets from exponential space to non-elementary; this landmark result (with co-authors) was qualified as the Best Paper st STOC 2019. Wojtek is also a laureate of the ERC starting grant, and– last but not least – an editor of a popular scientific magazine Delta.
Location and schedule:ZOOM, link received upon registration.
|
|
|
||||||||||||||||||
Videos: The video recordings of the lectures are available here.
Assignment: problem set (corrected version Feb.8). Please submit the solutions to the address listed in the pdf by 21 March .