Peter Gács

Péter Gács (Hungarian pronunciation: ['pe:ter 'ga:tʃ]; born May 9, 1947), professionally also known as Peter Gacs, is a Hungarian-American mathematician and computer scientist, professor, and an external member of the Hungarian Academy of Sciences. He is well known for his work in reliable computation, randomness in computing, algorithmic complexity, algorithmic probability, and information theory.

Career

Peter Gacs attended high school in his hometown, then obtained a diploma (M.S.) at Loránd Eötvös University in Budapest in 1970. Gacs started his career as a researcher at the Applied Mathematics Institute of the Hungarian Academy of Science. He obtained his doctoral degree from the Goethe University Frankfurt in 1978. Throughout his studies he had the opportunity to visit Moscow State University and work with Andrey Kolmogorov and his student Leonid A Levin. Through 1979 he was a visiting research associate at Stanford University. He was an assistant professor at University of Rochester from 1980 until 1984 when he moved to Boston University where he received tenure in 1985. He has been full professor since 1992.

Work Gacs has made contributions in many fields of computer science. It was Gács and László Lovász who first brought ellipsoid method to the attention of the international community in August 1979 by publishing the proofs and some improvements of it. Gacs also gave contribution in the Sipser–Lautemann theorem. His main contribution and research focus were centered on cellular automata and Kolmogorov complexity.

Work on cellular automata

His most important contribution in the domain of cellular automata besides the GKL rule (Gacs–Kurdyumov–Levin rule) is the construction of a reliable one-dimensional cellular automaton presenting thus a counterexample to the positive rates conjecture. The construction that he offered is multi-scale and complex. Later, the same technique was used for the construction of aperiodic tiling sets.

Work on algorithmic information theory and Kolmogorov complexity

Gacs authored several important papers in the field of algorithmic information theory and on Kolmogorov complexity. Together with Leonid A. Levin, he established basic properties of prefix complexity including the formula for the complexity of pairs and for randomness deficiencies including the result rediscovered later and now known as ample excess lemma. He showed that the correspondence between complexity and a priori probability that holds for the prefix complexity is no more true for monotone complexity and continuous a priori probability. In the related theory of algorithmic randomness he proved that every sequence is Turing-reducible to a random one (the result now known as Gacs–Kucera theorem, since it was independently proven by Antonin Kucera). introduced one of the quantum versions for algorithmic complexity, studied the properties of algorithmic randomness for general spaces and general classes of measures. Some of these results are covered in his surveys of algorithmic information theory. He also proved results on the boundary between classical and algorithmic information theory: the seminal example that shows the difference between common and mutual information (with János Körner). Together with Rudolf Ahlswede and Körner, he proved the blowing-up lemma.