Parameterized Complexity of Network Dynamics
Description:
During the COVID-19 pandemic, we have observed the virus spreading through the network of physical human contacts in complex ways. Apart from uncertainty about the data and the dynamics, there is another important challenge, and it is the one that we will deal with in this subproject: Even in an idealized situation where we have perfect knowledge of the network as well as of the local rules governing the network's dynamics, the random process can exhibit a behavior of emergent complexity. This means that the behavior is difficult to predict other than by a costly simulation, either because doing so is inherently intractable for reasons that have to do with the computational complexity of the task at hand, or simply because the scientific theory of network dynamics has not been developed far enough yet. While the subproject is motivated by the COVID-19 pandemic, the results we aim to achieve will generalize to opinion dynamics, Glauber dynamics, graph neural networks, and more.
Staff:
- Prof. Dr. Holger Dell (Main PI)