Miklós Ajtai

Biography

Miklós Ajtai has made foundational contributions to understanding the power and limitations of computational models. Defining the boundaries of formal models of computation is a central challenge in computer science, with the P vs. NP question being the most prominent, carrying both philosophical and practical implications. Even seemingly simple problems, like determining in linear time whether a sequence of numbers contains a duplicate, have remained unsolved for decades. There are only a few success stories in proving rigorous bounds on computational limitations, and Ajtai has been at the forefront of nearly every major breakthrough in this field. He has also cracked the code of sorting algorithms. While a logarithmic lower bound for sorting was known, a matching upper bound remained unresolved until the early 1980s, when Ajtai and his co-authors solved the problem through an intricate mathematical construction using expander graphs. This breakthrough pioneered the use of expander graphs in another significant research area in theoretical computer science, which explores whether randomness—used in many elegant and powerful algorithms—can be treated as a resource to be minimized. Ajtai also founded the field of lattice-based cryptography. The field of “geometry of numbers” was defined over a century ago to study generalizations of the greatest common divisor (GCD) problem. Unlike the GCD problem, the shortest lattice vector problem has been frustratingly open since the birth of computer science. In a tour de force, Ajtai established the computational difficulty of the shortest lattice vector problem. Building on this breakthrough, he co-invented a novel public-key cryptosystem based on lattice problems. This development, along with subsequent work, has revolutionized cryptography over the past two decades and offers the best current defense against quantum attacks.

An IEEE Senior Member, Ajtai is Emeritus Researcher, IBM Almaden Research Center, Los Gatos, California, USA.