FCRC 2019

Computational Complexity 2019-08-20

Georgia Tech FCRC ParticipantsI'm heading home from the 2019 ACM Federated Computing Research Conference in Phoenix, a collection of computer science meetings including STOC, COLT and EC. Geoff Hinton and Yann LeCun gave their Turing award lectures, their co-winner Yoshua Bengio not in attendance. Hinton talked about how machine learning triumphed over symbolic AI. LeCun argued that under uncertainty, one should learn the distribution instead of just the average. If you want more, just watch it yourself.

To get to the STOC lectures you go up and down escalators and pass through ISCA (Computer Architecture) and PLDI (Programming Languages). It's like you are going up the computing stack until you reach algorithms and complexity.

The conference center was just two blocks from Chase Field so we could take in a Diamondbacks baseball game. They opened the roof because the temperature dropped into the double digits. Last night, Paul McCartney played at an arena just a block from the conference center, but instead I hung out at an Uber reception for the EC conference.

Let me mention a best paper awardee, The Reachability Problem for Petri Nets is Not Elementary by Wojciech Czerwinski, Slawomir Lasota, Ranko Lazic, Jerome Leroux and Filip Mazowiecki. In a Petri net you have a list of vectors of integers and an initial and final vector. You start with the initial vector and can add any of the other vectors nondeterministically as often as you like as long as no coordinate goes negative. Can you get to the final vector? This problem was known to be computable in "Ackermannian" time and EXPSPACE-hard. This paper shows the problem is not elementary, i.e. not solvable in running time a tower of 2's to the n. A recent result shows Petri Nets reachability is primitive recursive for fixed dimensions. Avi Wigderson gave the Knuth Prize lecture exploring deep connections between mathematics and algorithms. Hopefully the video will be online soon. STOC next year in Chicago, EC as part of the Game Theory Congress in Budapest.