Miklos Ajtai
International Business Machines Corporation
|
Primary Section: 34, Computer and Information Sciences Secondary Section: 11, Mathematics Membership Type:
Member
(elected 2021)
|
Biosketch
Miklos Ajtai has worked in various areas of theoretical computer science and mathematics, including sorting networks, lowerbounds for various models of computations, lattice-based cryptography, proof complexity, combinatorics, theory of random graphs, mathematical logic and its connections with theoretical computer science, and axiomatic set theory. He was born in Hungary and grew up in Budapest. Ajtai studied mathematics at the Eotvos Lorand University in Budapest and got his Ph.D. in mathematics (axiomatic set theory) at the Hungarian Academy of Sciences (Hu.A.Sc.) in 1975. He worked at the Mathematical Research Institute of the Hu.A.Sc. till 1983 and then at the Almaden Research Center of IBM Research till 2015. He held visiting positions at the McGill University, University of California, San Diego, and at MIT. Ajtai is an international member of the Hungarian Academy of Sciences, a Honorary Research Fellow of the Renyi Institute of the Hu.A.Sc. and an Emeritus Researcher at the Almaden Research Center of IBM. He won the Knuth Prize in 2003.
Research Interests
Miklos Ajtai’s main interest is the theory of lower bounds in various models of computations, for example, circuits, branching programs, RAMs. Many of the questions in this area are closely related to questions in proof complexity or questions about first-order definability in certain finite structures. Recently he is interested in lower bounds in RAM models, and the connections of these lower bounds with definability questions in the finite structure whose universe is an initial segment of the set of natural numbers and the functions are the restrictions of the arithmetic operations to this universe.
