Dr. Wojciech Czerwiński and Prof. Sławomir Lasota from the UW Institute of Informatics are co-authors of the paper awarded by the program committee of the ACM Symposium on Theory of Computing conference (STOC). The article entitled “The Reachability Problem of Petri Nets is Not Elementary” has been considered as the best conference paper.

Annual ACM Symposium on Theory of Computing 2019 will be the 51st edition of that conference. It is the flagship scientific meeting sponsored by the Special Interest Group on Algorithms and Computation Theory (SIGACT). Every year, about 100 most important discoveries in theory of computer science are presented at the STOC conference (and its twin FOCS), selected through a competition after thorough reviews.

 

Since 2003, the program committee of the conference has been choosing papers that were considered as the best ones at particular edition. This year the prize was awarded to the article entitled The Reachability Problem of Petri Nets is Not Elementary’’. Among its co-authors there are two scientists from the UW Mathematics, Informatics and Mechanics Faculty: Dr. Wojciech Czerwiński and Prof. Sławomir Lasota.

 

The awarded work demonstrates a new lower bound on the complexity of the fundamental problem of reachability in Petri nets. The earlier lower bound (exponential space) proved by Richard Lipton in 1976 was conjectured to be optimal. The new result surprisingly refutes this conjecture and shows that this and many other computational problems from areas such as formal languages, logic, concurrent systems and linear algebra are significantly more difficult than we previously thought.

 

The awarded paper was written in cooperation with scientists from other institutions: Ranko Lazic (University of Warwick), Jerome Leroux (CNRS & University of Bordeaux) and Filip Mazowiecki (graduate of the UW, currently at University of Bordeaux).

 

Best Paper Award will be presented during the ACM STOC 2019 conference. It will take place from 23rd to 26th June in Phoenix (USA).

 

The list of previously awarded papers can be found here.

 

Read the article “The Reachability Problem of Petri Nets is Not Elementary”>>