Co-developer of a classic sorting network algorithm, Ajtai has worked as a computer scientist at the IBM Almaden Research Center in San Jose, CA, USA, with a main field of interest in complexity theory and its connections with combinatorics, logic, and other branches of mathematics. He has been particularly interested in the theory of lower bounds in various settings; for example, constant depth circuits, branching programs, and propositional proof systems. He also worked on problems in the theory of lattices and its application to cryptography.
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 computer science, a sorting network is an algorithm that sorts a fixed number of values using a fixed sequence of comparisons. Such networks can be thought of as networks of wires and comparator modules. Values (of any ordered type) flow across the wires, and the comparators each connect two wires, compare the values coming in on the wires, and sort them by outputting the smaller value to one wire and the larger to the other.
Sorting networks differ from general comparison sorts in that they are not capable of handling arbitrarily large inputs, and in that their sequence of comparisons is set in advance, regardless of the outcome of previous comparisons. This independence of comparison sequences is useful for parallel execution and for implementation in hardware. Despite the simplicity of sorting nets, their theory is surprisingly deep and complex. Sorting networks were first studied circa 1954 by Armstrong, Nelson and O'Connor, who subsequently patented the idea.
Sorting networks can be implemented either in hardware or in software. Donald Knuth describes how the comparators for binary integers can be implemented as simple, three-state electronic devices. Ken Batcher, an emeritus professor of Computer Science at Kent State University, suggested using them to construct switching networks for computer hardware, replacing both buses and the faster, but more expensive, crossbar switches. Since the 2000s, sorting nets (especially bitonic mergesort) have been used by the GPGPU community for constructing sorting algorithms to run on graphics processing units.
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 polynomial in n. He also proved that the statement "any two countable structures that are second-order equivalent are also isomorphic" is both consistent with and independent of ZFC. He 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²/log t upper bound for the Ramsey number R(3,t). The corresponding lower bound was proved by Jeong Han Kim only in 1995, a result that earned him a Fulkerson Prize.
With Chvátal, Newborn, and Szemerédi, Ajtai proved that any drawing of a graph with n vertices and m edges, where m > 4n, has at least m³/100n² crossings. He received his Candidate of Sciences degree in 1976 from the Hungarian Academy of Sciences. From 1995 he has served as an external member of the Hungarian Academy of Sciences.
He is the author or co-author of "Isomorphism and higher order equivalence", Annals of Mathematical Logic 16 (3): 181–203, doi:10.1016/0003-4843(79)90001-9, (1979); and with Komlós, J.; Szemerédi, E. (1982), "Largest random component of a k-cube", Combinatorica 2: 1–7, doi:10.1007/BF02579276.
