Early PhD Problems presentation abstract

Brief definitions of One Counter Nets (OCN), Vector Addition Systems with States (VASS) and semi-linear sets and complexity classes in the first two levels of the Polynomial Hierarchy and Non-deterministic Log-space (NL). An introduction to decision problems on OCNs, VASS and semi-linear sets and the different encodings for OCNs and VASS. Complexity results for Coverability and Reachability on k-dimensional VASS and current complexity bounds for unary input alphabet, binary counter update, non-deterministic OCN Compressed Membership and Universality. Plus my current personal thoughts and anecdotes from my attempts to improve the complexity gaps.

FoCS PhD Reading Group 2020

Henry Sinclair-Banks, 12/11/20, University of Warwick (UK).