Miklós Ajtai
   HOME

TheInfoList



OR:

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
Fellow of the American Association for the Advancement of Science Fellowship of the American Association for the Advancement of Science (FAAAS) is an honor accorded by the American Association for the Advancement of Science (AAAS) to distinguished persons who are members of the Association. Fellows are elected ...
. 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