Miklós Ajtai (born 2 July 1946) is a
computer scientist
A computer scientist is a scientist who specializes in the academic study of computer science.
Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...
at the
IBM
International Business Machines Corporation (using the trademark IBM), nicknamed Big Blue, is an American Multinational corporation, multinational technology company headquartered in Armonk, New York, and present in over 175 countries. It is ...
Almaden Research Center, United States. In 2003, he received the
Knuth Prize for his numerous contributions to the field, including a classic
sorting network algorithm (developed jointly with
J. Komlós and
Endre Szemerédi), exponential lower bounds, superlinear time-space tradeoffs for branching programs, and other "unique and spectacular" results. He is a member of the U.S.
National Academy of Sciences
The National Academy of Sciences (NAS) is a United States nonprofit, NGO, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the ...
.
Selected results
One of Ajtai's results states that the length of proofs in
propositional logic
The propositional calculus is a branch of logic. It is also called propositional logic, statement logic, sentential calculus, sentential logic, or sometimes zeroth-order logic. Sometimes, it is called ''first-order'' propositional logic to contra ...
of the
pigeonhole principle
In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, of three gloves, at least two must be right-handed or at least two must be l ...
for ''n'' items grows faster than any
polynomial
In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
in ''n''. He also proved that the statement "any two
countable
In mathematics, a Set (mathematics), set is countable if either it is finite set, finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function fro ...
structure
A structure is an arrangement and organization of interrelated elements in a material object or system, or the object or system so organized. Material structures include man-made objects such as buildings and machines and natural objects such as ...
s that are second-order equivalent are also
isomorphic
In mathematics, an isomorphism is a structure-preserving mapping or morphism between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between the ...
" is both
consistent
In deductive logic, a consistent theory is one that does not lead to a logical contradiction. A theory T is consistent if there is no formula \varphi such that both \varphi and its negation \lnot\varphi are elements of the set of consequences ...
with and
independent
Independent or Independents may refer to:
Arts, entertainment, and media Artist groups
* Independents (artist group), a group of modernist painters based in Pennsylvania, United States
* Independentes (English: Independents), a Portuguese artist ...
of
ZFC. Ajtai and
Szemerédi proved the
corners theorem, an important step toward higher-dimensional generalizations of the
Szemerédi theorem. With
Komlós and
Szemerédi, he proved the ''ct''
2/log ''t'' upper bound for the
Ramsey number ''R''(3,''t''). With Komlós and
Tusnády he proved in 1984 the
AKT optimal matching theorem. The corresponding lower bound was proved by
Kim only in 1995, a result that earned him a
Fulkerson Prize
The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e ...
. With
Chvátal,
Newborn
In common terminology, a baby is the very young offspring of adult human beings, while infant (from the Latin word ''infans'', meaning 'baby' or 'child') is a formal or specialised synonym. The terms may also be used to refer to Juvenile (orga ...
, and
Szemerédi, Ajtai proved the
crossing number inequality, that any drawing of a graph with ''n'' vertices and ''m'' edges, where , has at least
crossings. Ajtai and
Dwork devised in 1997 a lattice-based
public-key cryptosystem
Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic a ...
; Ajtai has done extensive work on
lattice problems. For his numerous contributions in Theoretical Computer Science, he received the Knuth Prize.
Biography
Ajtai received his
Candidate of Sciences
A Candidate of Sciences is a Doctor of Philosophy, PhD-equivalent academic research degree in all the post-Soviet countries with the exception of Ukraine, and until the 1990s it was also awarded in Central and Eastern European countries. It is ...
degree in 1976 from the
Hungarian Academy of Sciences. Since 1995, he has been an external member of the
Hungarian Academy of Sciences.
In 1998, he was an Invited Speaker of the
International Congress of Mathematicians
The International Congress of Mathematicians (ICM) is the largest conference for the topic of mathematics. It meets once every four years, hosted by the International Mathematical Union (IMU).
The Fields Medals, the IMU Abacus Medal (known before ...
in Berlin. In 2012, he was elected as a
. In 2021, he was elected a member of the National Academy of Sciences.
Bibliography
*
*
*
Selected papers
#
#
References
External links
Miklós Ajtai home page*
*
1946 births
Living people
Knuth Prize laureates
20th-century Hungarian mathematicians
21st-century Hungarian mathematicians
Hungarian computer scientists
Members of the Hungarian Academy of Sciences
Fellows of the American Association for the Advancement of Science
Theoretical computer scientists
Hungarian expatriates in the United States
American computer scientists
IBM employees
Members of the United States National Academy of Sciences
{{compu-scientist-stub