Miklós Ajtai
Encyclopedia
Miklós Ajtai is a computer scientist at the IBM
Almaden Research Center
. 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.
in n. He also proved that the statement "any two countable structure
s that are second-order equivalent are also isomorphic" is both consistent with and independent
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 ct2/log t upper bound for the Ramsey number R(3,t). The corresponding lower bound was proved by Kim
only in 1995, a result that earned him a Fulkerson Prize
. With Chvátal
, M. M. Newborn and Szemerédi
, Ajtai proved that a planar graph
with n vertices and m edges, where has at least crossings.
. Since 1995 he has been an external member of the Hungarian Academy of Sciences
.
IBM
International Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
Almaden Research Center
Almaden Research Center
The IBM Almaden Research Center is in San Jose, California, and is one of IBM's nine worldwide research labs. Its scientists perform basic and applied research in computer science, services, storage systems, physical sciences, and materials science and technology. The center opened in 1986, and...
. In 2003 he received the Knuth Prize
Knuth Prize
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth.-History:...
for his numerous contributions to the field, including a classic sorting network
Sorting network
A sorting network is an abstract mathematical model of a network of wires and comparator modules that is used to sort a sequence of numbers. Each comparator connects two wires and sorts the values by outputting the smaller value to one wire, and the larger to the other...
algorithm (developed jointly with J. Komlós
János Komlós (mathematician)
János Komlós is a Hungarian-American mathematician, working in probability theory and discrete mathematics. He is a professor of mathematics at Rutgers University since 1988. He graduated from the Eötvös Loránd University, then became a fellow at the Mathematical Institute of the Hungarian Academy...
and Endre Szemerédi
Endre Szemerédi
Endre Szemerédi is a Hungarian mathematician, working in the field of combinatorics and theoretical computer science. He is the State of New Jersey Professor of computer science at Rutgers University since 1986...
), exponential lower bounds, superlinear time-space tradeoffs for branching programs, and other "unique and spectacular" results.
Selected results
One of Ajtai's results states that the length of proofs in propositional logic of the pigeonhole principle for n items grows faster than any polynomialPolynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
in n. He also proved that the statement "any two countable structure
Structure (mathematical logic)
In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it....
s that are second-order equivalent are also isomorphic" is both consistent with and independent
Independence (mathematical logic)
In mathematical logic, independence refers to the unprovability of a sentence from other sentences.A sentence σ is independent of a given first-order theory T if T neither proves nor refutes σ; that is, it is impossible to prove σ from T, and it is also impossible to prove from T that...
of ZFC. Ajtai and Szemerédi
Endre Szemerédi
Endre Szemerédi is a Hungarian mathematician, working in the field of combinatorics and theoretical computer science. He is the State of New Jersey Professor of computer science at Rutgers University since 1986...
proved the corners theorem
Corners theorem
In mathematics, the corners theorem is an important result, proved by Miklós Ajtai and Endre Szemerédi, of a statement in arithmetic combinatorics...
, an important step toward higher dimensional generalizations of the Szemerédi theorem
Szemerédi's theorem
In number theory, Szemerédi's theorem is a result that was formerly the Erdős–Turán conjecture...
. With Komlós
János Komlós (mathematician)
János Komlós is a Hungarian-American mathematician, working in probability theory and discrete mathematics. He is a professor of mathematics at Rutgers University since 1988. He graduated from the Eötvös Loránd University, then became a fellow at the Mathematical Institute of the Hungarian Academy...
and Szemerédi
Endre Szemerédi
Endre Szemerédi is a Hungarian mathematician, working in the field of combinatorics and theoretical computer science. He is the State of New Jersey Professor of computer science at Rutgers University since 1986...
he proved the ct2/log t upper bound for the Ramsey number R(3,t). The corresponding lower bound was proved by Kim
Jeong Han Kim
Jeong Han Kim is a South Korean mathematician specializing in combinatorics and computational mathematics. He studied physics and mathematical physics at Yonsei University, and earned his Ph.D in mathematics at Rutgers University...
only in 1995, a result that earned him a Fulkerson Prize
Fulkerson Prize
The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Programming Society and the American Mathematical Society . Up to three awards of $1500 each are presented at each International Symposium of the MPS...
. With Chvátal
Václav Chvátal
Václav Chvátal is a professor in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Canada, where he holds theCanada Research Chair in Combinatorial Optimization....
, M. M. Newborn and Szemerédi
Endre Szemerédi
Endre Szemerédi is a Hungarian mathematician, working in the field of combinatorics and theoretical computer science. He is the State of New Jersey Professor of computer science at Rutgers University since 1986...
, Ajtai proved that a planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
with n vertices and m edges, where has at least crossings.
Biodata
Ajtai received his Candidate of Sciences degree in 1976 from the Hungarian Academy of SciencesHungarian Academy of Sciences
The Hungarian Academy of Sciences is the most important and prestigious learned society of Hungary. Its seat is at the bank of the Danube in Budapest.-History:...
. Since 1995 he has been an external member of the Hungarian Academy of Sciences
Hungarian Academy of Sciences
The Hungarian Academy of Sciences is the most important and prestigious learned society of Hungary. Its seat is at the bank of the Danube in Budapest.-History:...
.
Selected papers
- .
- .