Dr. Miklós Ajtai

A computer scientist at the IBM Almaden Research Center in San Jose, CA, USA; his main field of interest is complexity theory and its connections with combinatorics, logic, and other branches of mathematics. He is particularly interested in the theory of lower bounds in various settings; for example, constant depth circuits, branching programs, propositional proof systems. He is also working 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. They can be thought of as networks of wires and comparator modules. Values (of any ordered type) flow across the wires. 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 2000?s, sorting nets (especially bitonic mergesort) are used by the GPGPU community for constructing sorting algorithms to run on graphics processing units. One of his 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 ct2/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, he proved that any drawing of a graph with n vertices and m edges, where m > 4n, has at least m3 / 100n2 crossings. He received his Candidate of Sciences degree in 1976 from the Hungarian Academy of Sciences. Since 1995 he has been 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.