Recent UCLA math graduate Danh (Danny) Nguyen Luu has been named the sole winner of the 2018 Sacks Prize by the International Association for Symbolic Logic (ASL). The Sacks Prize is awarded for the best dissertation of the year in logic. Previous winners include Gregory Hjorth (former UCLA faculty), Itay Neeman, Matthias Aschenbrenner and Artem Chernikov (current faculty).
Danny received his Ph.D. in Spring 2018, under the direction of Igor Pak. According to ASL, Danny’s thesis, The Computational Complexity of Presburger Arithmetic, “contains stunning results on the complexity of the decision problem for the linear theory of the integers. For example, whereas it has been known since the 70’s that the full decision procedure has doubly-exponential lower bounds, Nguyen’s thesis shows that even very restricted fragments have high complexity. Other results deal with VC-dimension of PA formulas and the complexity of the counting problem for various PA-definable sets. The dissertation is a tour de force, combining methods from number theory, discrete geometry, model theory, and computational complexity.”
The Association for Symbolic Logic is an international organization supporting research and critical studies in logic. Its primary function is to provide an effective forum for the presentation, publication, and critical discussion of scholarly work in this area of inquiry.
