Some good news

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.

 

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: