The mathematician Lázló Lovász and the theoretical computer scientist Avi Widgerson are the recipients of the Abel Prize 2021 for "their fundamental contributions to theoretical computing and discrete mathematics, as well as their outstanding role in making them central fields of modern mathematics." Both have worked on one of the most popular discrete structures, graphs, and their results are applied in different contexts of cryptography.
Pentagons and Hexagons The Infinite Mosaic
Widgerson (1956) grew up in the coastal Israeli city of Haifa, in a Jewish family of Polish origin that survived the Nazi holocaust. In 1983, he obtained his Ph.D. in computational complexity from Princeton University, and since then his career has been meteoric. The Abel Award is the latest in a long line of accolades for Widgerson's influential, innovative, and insightful work on the foundation of theoretical computing. Among them, the Nevanlinna prize, the Gödel prize and the Knuth prize.
For his part, Lovász (Budapest, 1948) was a child prodigy of mathematics – he won three gold medals in the international mathematical Olympics, twice with a special jury appreciation – within a golden generation of brilliant young mathematicians, stimulated by the unique scientific environment of post-war Budapest. Among the influences of the young Lovász, the mythical and errant mathematician Pául Erdős stands out, with whom he established a very fruitful collaboration since his adolescence. Like Widgerson, the Abel award is the culmination of a series of recognitions: the Gödel and Knuth awards, as well as the Wolf award, the Kyoto award and the Barcelona Hypatia award.
The objects of interest of both researchers are the discrete structures. These are, for example, finite sets, integers, logical formulas or algorithms
The objects of interest of both researchers are the discrete structures. These are, for example, finite sets, integers, logic formulas or algorithms; in contrast, the temperature function of a room, the curvature of an airplane wing, where the variation occurs smoothly for nearby points, are continuous structures. In short, discrete structures are mathematical objects that can be divided into well-defined parts. The example par excellence are graphs: objects formed by sets of points and relationships between them – called vertices and edges, respectively. Graphs are used to model, for example, the metro network of a city or the relationships between individuals in a social network; In this second case, the underlying graph is constructed taking people as vertices and two people will be connected by an edge if they are known.
Lovász has started many of the theories in this field of research and has obtained important results. Among them, he has shown open conjectures, such as the so-called Kneser conjecture , formulated in 1955, or the elusive perfect graph conjecture . It has also opened completely unexplored fields: discrete optimization, the theory of pairings in graphs or the LLL algorithm , a result that today is fundamental in all post-quantum cryptography theory. In recent years, Lovász has been one of the top developers of limit graph theory, a unifying theory that attempts to mix discrete mathematics and continuous objects.
Widgerson has also worked with graphs, specifically, on complexity results. Given a very large discrete structure – for example, let's think about the graph associated with one of the social networks so popular today – and a property that we want to study – for example, the appearance of highly connected communities, which would be groups of vertices intertwined with many edges, the so-called clusters. Can we invent a mechanism that checks that property, efficiently?
This decision problem – we are only interested in knowing if it can be done or not – is extremely difficult – and time consuming – if the graph is large. In this sense, complexity theory looks for algorithms that work better than those already known and / or to formally demonstrate that the efficiency of a given algorithm cannot be improved. Possibly the star problem in this field is the famous P = NP , one of the seven problems of the millennium, and on which Widgerson has made foundational contributions that have given rise to the theory of complexity as we know it today. Thus, complexity theory has grown around Widgerson in the last 40 years. But in addition, Widgerson has contributed decisively in many other directions: he is one of the reference researchers in the so-called zero-knowledge tests , and he was the creator of the so -called zig-zag product for the construction of expander graphs – that they are very well connected graphs, but at the same time with very few edges; These structures were already the object of study by the previous recipients of the Abel Prize , in part because of their connection with other branches of mathematics such as group theory.
The two winners agree on the use of very novel probabilistic ideas that allow obtaining results that, in a deterministic way it would be impossible. Thus, Lovász invented the so-called local motto , which makes it possible to demonstrate the existence of combinatorial objects that, otherwise, it would be unthinkable to find. And for his part, Widgerson has made essential contributions in the use of probability to find efficient algorithms that improve any deterministic algorithm.
Recognition of the lifetime work of Lovász and Widgerson confirms, once again, the fundamental role of discrete mathematics, computer science and its interaction in the development of contemporary mathematics
Juanjo Rué is a researcher at the Department of Mathematics and the Institute of Mathematics (ImTech) of the Polytechnic University of Catalonia, and a research member of the Center de Recerca Matemàtica (CRM) and the Barcelona Graduate School of Mathematics (BGSMath)
Café y Teoremas is a section dedicated to mathematics and the environment in which it is created, coordinated by the Institute of Mathematical Sciences (ICMAT), in which the researchers and members of the center describe the latest advances in this discipline, share meeting points between mathematics s and other social and cultural expressions and remember those who marked its development and knew how to transform coffee into theorems. The name evokes the definition of the Hungarian mathematician Alfred Rényi: "A mathematician is a machine that transforms coffee into theorems."
Translation, editing and coordination: Ágata A. Timón García-Longoria (ICMAT)
You can follow MATERIA at Facebook , Twitter e Instagram , or sign up here to receive our weekly newsletter .