Peter Gacs

From Wikitia
Jump to navigation Jump to search
Add a Photo
Born(1948-05-09)May 9, 1948
Budapest, Hungary
Alma materEötvös Loránd University
Goethe University Frankfurt
Stanford University
Known for
  • Reliable cellular automata construction
  • GKL rule
Scientific career
  • Computer science
  • Mathematics
InstitutionsHungarian Academy of Sciences
University of Rochester
Boston University
Add a Photo
  • Mathematician
  • Computer scientists
  • Professor

Péter GÁCS is a Hungarian-American mathematician and computer scientists, 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.


Peter Gacs attended a gymnasium in his hometown, then obtained a diploma (M.S.) at Loránd Eötvös University of Science in 1970. Gacs started his career as a researcher at the Alfréd Rényi Institute of Applied Mathematics Institute of the Hungarian Academy of Science working under the supervision of Alfred Renyi himself. He obtained his doctoral degree from the Goethe University Frankfurt. Throughout his studies he had the opportunity to visit Moscow State University and work with Andrey Kolmogorov. In 1979 he moved to Stanford University. He was an assistant professor at University of Rochester from 1980 until 1984 when he moved to Boston University where he got tenured in 1992.


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.[1] Gacs also gave contribution in the Sipser–Lautemann theorem and many other fields of computer science and mathematics. However 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-Kurdiomov- Levin rule) is the construction of a reliable one-dimensional cellular automaton presenting thus a counterexample to the Positive rates conjecture[2]. The construction that he offered is multi-scale and complex. The technique that he used and the entire construction is explained by Lawrence Grey in an exposition paper[3] and later was used for the construction of aperiodic tiling set[4].

Work on algorithmic information theory and Kolmogorov complexity

At the early stages of algorithmic information theory, Gacs gave important contributions to this field tackling the symmetry of algorithmic information[5] and the differences between common and mutual information[6]. Together with Rudolf Ahlswede and János Körner he proved the blowing-up lemma [7].


  1. Gács, Peter; Lovász, Laszlo (1981), König, H.; Korte, B.; Ritter, K. (eds.), "Khachiyan's algorithm for linear programming", Mathematical Programming at Oberwolfach, Berlin, Heidelberg: Springer Berlin Heidelberg, vol. 14, pp. 61–68, doi:10.1007/bfb0120921, ISBN 978-3-642-00805-4, retrieved 2020-11-27
  2. Gács, Peter (2001-04-01). "Reliable Cellular Automata with Self-Organization". Journal of Statistical Physics. 103 (1): 45–267. Bibcode:2001JSP...103...45G. doi:10.1023/A:1004823720305/0003117. ISSN 1572-9613.
  3. Gray, Lawrence F. (2001-04-01). "A Reader's Guide to Gacs's "Positive Rates" Paper". Journal of Statistical Physics. 103 (1): 1–44. Bibcode:2001JSP...103....1G. doi:10.1023/A:1004824203467. ISSN 1572-9613.
  4. Durand, Bruno; Romashchenko, Andrei; Shen, Alexander (2012-05-01). "Fixed-point tile sets and their applications". Journal of Computer and System Sciences. In Commemoration of Amir Pnueli. 78 (3): 731–764. doi:10.1016/j.jcss.2011.11.001. ISSN 0022-0000.
  5. P. Gács, “On the symmetry of algorithmic information”, Dokl. Akad. Nauk SSSR, 218:6 (1974), 1265–1267
  6. Gács, Peter, and János Körner. "Common information is far less than mutual information." Problems of Control and Information Theory 2.2 (1973): 149-162
  7. Ahlswede, Gacs, Körner Bounds on conditional probabilities with applications in multiuser communication, Z. Wahrsch. und Verw. Gebiete 34, 1976, 157–177

External links

Add External links

This article "Peter Gacs" is from Wikipedia. The list of its authors can be seen in its historical. Articles taken from Draft Namespace on Wikipedia could be accessed on Wikipedia's Draft Namespace.