 |
| Georgia Tech FCRC Participants |
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.
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.
Are you sure that "This problem was known to be primitive recursive "? The abstract of the paper says "the currently best published upper bound is non-primitive recursive Ackermannian of Leroux and Schmitz from LICS 2019". This seems to indicate that no primitive recursive upper bound is known yet.
ReplyDeleteRight. I updated the post.
DeleteI finally read Structurally Cyclic Petri Nets (9 pages) by F Drewes, J Leroux – 2015. It was surprisingly easy to read, and answered many more questions (which I actually had before even starting to read the paper) than indicated by the short three sentence abstract. At the end of section 2, the authors indicate for the first time that they will also prove P-hardness of the structural cyclicity problem. So they obtain the main result of the paper as
ReplyDeleteCorollary 6.4. The structural cyclicity problem is P-complete, regardless of whether numbers are encoded in binary or unary.
but mention it neither in the abstract, nor the introduction, nor the conclusion. Other "bonus material" is at least mentioned in the introduction, like "Theorem 3.1. The cyclicity problem is EXPSPACE complete."
You may ask how this is related to your post. Jérôme Leroux is one of the many authors of the mentioned best paper awardee. Turns out he is also the second author of the paper above. And he is the first author of the paper providing the best published upper bound for the reachability problem. I had never heard of him before. Looks like he made major progress on the reachability problem in 2009, but his paper got rejected from FOCS for being "out of scope".
The decision might actually even be "correct", since decidable problems from Complexity Hierarchies Beyond Elementary are not untypical for theory B, but too "unpractical" for theory A.