Posts Tagged ‘Sacks Prize’

Some good news

April 17, 2019 Leave a comment

Two of my former Ph.D. students won major prizes recently — Matjaž Konvalinka and Danny Nguyen.  Matjaž is an Associate Professor at University of Ljubljana, Danny is a Lewis Research Assistant Professor at University of Michigan, Ann Arbor.  Congratulations to both of them!

(1) The 2019 Robbins Prize is awarded to Roger Behrend, Ilse Fischer and Matjaž Konvalinka for their paper “Diagonally and antidiagonally symmetric alternating sign matrices of odd order”.  The Robbins Prize is given in Combinatorics and related areas of interest is named after the late David P. Robbins and is given once every 3 years by AMS and MAA.

In many ways, this paper completes the long project of enumerating alternating sign matrices (ASMs) initiated by William Mills, David Robbins, and Howard Rumsey in the early 1980s.  The original #ASM(n)=#TSSCPP(n) conjecture follows from Andrews’s proof of the conjectured product formula for #TSSCPP(n), and Zeilberger’s 84 page computer assisted proof of the the same conjectured product formula for #ASM(n).  This led to a long series of remarkable developments which include Kuperberg’s proof using the Izergin-Korepin determinant for the six vertex model, the Cantini–Sportiello proof of the Razumov-Stroganov conjecture, and a recent self-contained determinantal proof for the number of ASMs by Fischer.  Bressoud’s book (and this talkslides) is a good introduction.  But the full story is yet to be written.

(2)  The 2018 Sacks Prize is awarded to Danny Nguyen for his UCLA Ph.D. dissertation on the complexity of short formulas in Presburger Arithmetic (PA) and many related works (some joint with me, some with others).  See also the UCLA announcement.  The Sacks Prize is given by the international Association for Symbolic Logic for “the most outstanding doctoral dissertation in mathematical logic“.  It is sometimes shared between two awardees, and sometimes not given at all.  This year Danny is the sole winner of the prize.

Danny’s dissertation is a compilation of eight (!) papers Danny wrote during his graduate studies, all on the same or closely related subject.  These papers advance and mostly finish off the long program of understanding the boundary of what’s feasible in PA. The most important of these is our joint FOCS paper which basically says that Integer Programming and Parametric Integer Programming is all that’s left in P, while all longer formulas are NP-hard.  See Featured MathSciNet Review by Sasha Barvinok and an overlapping blog post by Gil Kalai discussing these results.  See also Danny’s FOCS talk video and my MSRI talk video presenting this work.