Komitet programowy konferencji ACM Symposium on Theory of Computing (STOC) przyznał nagrodę za najlepszą pracę artykułowi "The Reachability Problem for Petri Nets is Not Elementary", którego autorami są Wojciech Czerwiński i Sławomir Lasota z Instytutu Informatyki MIM UW, oraz Ranko Lazic (U. Warwick), Jerome Leroux (U. Bordeaux) i Filip Mazowiecki (absolwent Wydziału MIM, obecnie na U. Bordeaux). W nagrodzonej pracy autorzy dowodzą nowego dolnego ograniczenia na złożoność fundamentalnego problemu osiągalności w sieciach Petriego. Wcześniejsze dolne ograniczenie udowodnione przez Richarda Liptona w 1976 roku, dotąd pozostawało niepoprawione, podejrzewano nawet, że jest optymalne. Nowy wynik nieoczekiwanie obala tę hipotezę, i pokazuje że ten i wiele innych problemów obliczeniowych, z takich dziedzin jak języki formalne, logika, systemy współbieżne i algebra liniowa, są istotnie trudniejsze, niż dotąd przypuszczano.

Na konferencji STOC (oraz równorzędnej FOCS) co roku prezentowanych jest około 100 najważniejszych w danym roku odkryć w informatyce teoretycznej, wybranych na drodze konkursu po wnikliwych recenzjach. Od 2003r. dodatkowo przyznawane są nagrody za najlepszą pracę. Dotąd nie było wśród nich nagrody dla uczonych afiliowanych przy polskiej instytucji naukowej. Tegoroczna nagroda zostanie wręczona podczas konferencji, w czerwcu, w Pheonix (USA). Listę dotąd nagrodzonych prac można znaleźć na stronie.