{"id":9069,"date":"2017-03-02T08:10:09","date_gmt":"2017-03-02T12:10:09","guid":{"rendered":"https:\/\/www.bu.edu\/cs\/?post_type=profile&#038;p=9069"},"modified":"2026-03-11T23:14:07","modified_gmt":"2026-03-12T03:14:07","slug":"peter-gacs","status":"publish","type":"profile","link":"https:\/\/www.bu.edu\/cs\/profiles\/peter-gacs\/","title":{"rendered":"Peter Gacs"},"content":{"rendered":"<p style=\"text-align: justify;\"><span>Before coming to BU, Peter studied in Budapest, worked at the Hungarian\u00a0<\/span><span>Academy of Science with trips to Moscow, obtained a PhD in Frankfurt, did postdoc\u00a0<\/span><span>work at Stanford, and taught in Rochester. Professor Gacs has worked on\u00a0<\/span><span>problems derived from information theory (classical, and algorithmic) and\u00a0<\/span><span>reliable computation. With Ahlswede and K\u00f6rner wrote some of the earliest\u00a0<\/span><span>papers of multi-user information theory. In algorithmic information theory\u00a0<\/span><span>(Kolmogorov complexity), Gacs also had some part in developing the fundamental\u00a0<\/span><span>results (earlier with Levin, later with Vit\u00e1nyi and others). In reliable\u00a0<\/span><span>computation, his main contributions are to the probabilistic cellular automaton\u00a0<\/span><span>model: in some sense the most natural one, but mathematically difficult. He has\u00a0<\/span><span>been the principal investigator of several NSF grants, and is an external member\u00a0<\/span><span>of the Hungarian Academy of Sciences.<\/span><\/p>\n<p><a href=\"https:\/\/cs-web.bu.edu\/faculty\/gacs\/\">Personal homepage<\/a><\/p>\n<h3>Selected Publications<\/h3>\n<p>Ilir Capuni and Peter Gacs.\u00a0<a href=\"http:\/\/www.cs.bu.edu\/~gacs\/papers\/bursty-Turing.pdf\">A Turing machine resisting isolated bursts of faults<\/a>. Chicago Journal of Theoretical Computer Science, 2013. See also in arXiv:1203.1335. Extended abstract appeared in SOFSEM 2012.<\/p>\n<p>Laurent Bienvenu, Mathieu Hoyrup, Cristobal Rojas and Alexander Shen.\u00a0<a href=\"http:\/\/www.cs.bu.edu\/~gacs\/papers\/classes.pdf\">Algorithmic tests and randomness with respect to a class of measures<\/a>. Proceedings of the Steklov Institute of Mathematics, 274(1):34\u201389, 2011. In English and Russian, also in arXiv:1103.1529.<\/p>\n<p>Peter Gacs.\u00a0<a href=\"http:\/\/www.cs.bu.edu\/~gacs\/papers\/walks.pdf\">Clairvoyant Scheduling of Random Walks<\/a>. Random Structures and Algorithms, 39(4):413\u2013485, 2011. arXiv\/math:0109152 [math.PR], www.cs.bu.edu\/faculty\/gacs\/papers\/walks.pdf. Short version in STOC \u201902.<\/p>\n","protected":false},"author":1690,"template":"","_links":{"self":[{"href":"https:\/\/www.bu.edu\/cs\/wp-json\/wp\/v2\/profile\/9069"}],"collection":[{"href":"https:\/\/www.bu.edu\/cs\/wp-json\/wp\/v2\/profile"}],"about":[{"href":"https:\/\/www.bu.edu\/cs\/wp-json\/wp\/v2\/types\/profile"}],"author":[{"embeddable":true,"href":"https:\/\/www.bu.edu\/cs\/wp-json\/wp\/v2\/users\/1690"}],"version-history":[{"count":7,"href":"https:\/\/www.bu.edu\/cs\/wp-json\/wp\/v2\/profile\/9069\/revisions"}],"predecessor-version":[{"id":15184,"href":"https:\/\/www.bu.edu\/cs\/wp-json\/wp\/v2\/profile\/9069\/revisions\/15184"}],"wp:attachment":[{"href":"https:\/\/www.bu.edu\/cs\/wp-json\/wp\/v2\/media?parent=9069"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}