Before coming to BU, Peter studied in Budapest, worked at the Hungarian
Academy of Science with trips to Moscow, obtained a PhD in Frankfurt, did postdoc
work at Stanford, and taught in Rochester. Professor Gacs has worked on
problems derived from information theory (classical, and algorithmic) and
reliable computation. With Ahlswede and Körner wrote some of the earliest
papers of multi-user information theory. In algorithmic information theory
(Kolmogorov complexity), Gacs also had some part in developing the fundamental
results (earlier with Levin, later with Vitányi and others). In reliable
computation, his main contributions are to the probabilistic cellular automaton
model: in some sense the most natural one, but mathematically difficult. He has
been the principal investigator of several NSF grants, and is an external member
of the Hungarian Academy of Sciences.
Ilir Capuni and Peter Gacs. A Turing machine resisting isolated bursts of faults. Chicago Journal of Theoretical Computer Science, 2013. See also in arXiv:1203.1335. Extended abstract appeared in SOFSEM 2012.
Laurent Bienvenu, Mathieu Hoyrup, Cristobal Rojas and Alexander Shen. Algorithmic tests and randomness with respect to a class of measures. Proceedings of the Steklov Institute of Mathematics, 274(1):34–89, 2011. In English and Russian, also in arXiv:1103.1529.
Peter Gacs. Clairvoyant Scheduling of Random Walks. Random Structures and Algorithms, 39(4):413–485, 2011. arXiv/math:0109152 [math.PR], www.cs.bu.edu/faculty/gacs/papers/walks.pdf. Short version in STOC ’02.