- Series
- Combinatorics Seminar
- Time
- Friday, March 5, 2021 - 3:00pm for 1 hour (actually 50 minutes)
- Location
- https://bluejeans.com/751242993/PASSWORD (To receive the password, please email Lutz Warnke
- Speaker
- Lilla Tóthmérész – Eötvös Loránd University
- Organizer
- Lutz Warnke
Chip-firing and rotor-routing are two well-studied examples of Abelian networks. We study the complexity of their respective reachability problems. We show that the rotor-routing reachability problem is decidable in polynomial time, and we give a simple characterization of when a chip-and-rotor configuration is reachable from another one. For chip-firing, it has been known that the reachability problem is in P if we have a class of graphs whose period length is polynomial (for example, Eulerian digraphs). Here we show that in the general case, chip-firing reachability is hard in the sense that if the chip-firing reachability problem were in P for general digraphs, then the polynomial hierarchy would collapse to NP.
Talk based on https://arxiv.org/abs/2102.11970