Πίτερ Γκατς

Ο Πέτερ Γκατς (ουγγρικά: Péter Gács, γεννήθηκε στις 9 Μαΐου 1947), ευρέως γνωστός ως Peter Gacs, είναι ουγγρικής καταγωγής Αμερικανός μαθηματικός και επιστήμονας υπολογιστών, καθηγητής και εξωτερικό μέλος της Ουγγρικής Ακαδημίας Επιστημών. Είναι γνωστός για το έργο του σχετικά με την αξιόπιστη υπολογιστική, την τυχαιότητα στην υπολογιστική, την αλγοριθμική πολυπλοκότητα, την αλγοριθμική πιθανότητα και τη θεωρία της πληροφορίας.

Σταδιοδρομία
Ο Πίτερ Γκατς φοίτησε στο γυμνάσιο της γενέτειράς του και στη συνέχεια πήρε δίπλωμα (M.S.) από το Πανεπιστήμιο Loránd Eötvös της Βουδαπέστης το 1970. Ο Γκατς ξεκίνησε τη σταδιοδρομία του ως ερευνητής στο Ινστιτούτο Εφαρμοσμένων Μαθηματικών της Ουγγρικής Ακαδημίας Επιστημών και απέκτησε το διδακτορικό του δίπλωμα από το Πανεπιστήμιο Γκαίτε της Φρανκφούρτης το 1978. Κατά τη διάρκεια των σπουδών του είχε την ευκαιρία να επισκεφθεί το Κρατικό Πανεπιστήμιο της Μόσχας και να συνεργαστεί με τον Αντρέι Κολμογκόροφ και τον μαθητή του Λεονίντ Α Λεβίν. Μέχρι το 1979 ήταν επισκέπτης ερευνητικός συνεργάτης στο Πανεπιστήμιο του Στάνφορντ. Ήταν βοηθός καθηγητή στο Πανεπιστήμιο του Ρότσεστερ από το 1980 έως το 1984, οπότε μετακόμισε στο Πανεπιστήμιο της Βοστώνης, όπου και μονιμοποιήθηκε το 1985. Από το 1992 είναι τακτικός καθηγητής
.

Επιστημονική εργασία 
Ο Γκατς συνεισέφερε σε πολλούς τομείς της επιστήμης των υπολογιστών. Ήταν ο Γκατς και ο Λάσλο Λόβαζ που έφεραν για πρώτη φορά την ελλειψοειδή μέθοδο στην προσοχή της διεθνούς κοινότητας τον Αύγουστο του 1979 δημοσιεύοντας τις αποδείξεις και κάποιες βελτιώσεις της.Kolata, Gina Bari Shenitzer, Abe, and John Stillwell, eds. Mathematical evolutions. MAA, 2002. Ο Γκατς έδωσε επίσης συμβολή στο θεώρημα Σίπσερ-Λάουτεμαν. Η κύρια συμβολή του και η ερευνητική του εστίαση επικεντρώθηκαν στα κυψελοειδή αυτόματα και στην πολυπλοκότητα Κολμογκόροφ.

Εργασία στα κυτταρικά αυτόματα
Η σημαντικότερη συνεισφορά του στον τομέα των κυτταρικών αυτομάτων εκτός από τον κανόνα GKL (Γκατς-Kurdyumov-Levin rule) είναι η κατασκευή ενός αξιόπιστου μονοδιάστατου κυτταρικού αυτομάτου που παρουσιάζει έτσι ένα αντιπαράδειγμα στην εικασία των θετικών ποσοστών. Η κατασκευή που προσέφερε είναι πολλαπλής κλίμακας και πολύπλοκη. Αργότερα, η ίδια τεχνική χρησιμοποιήθηκε για την κατασκευή απεριόδιων συνόλων πλακιδίων.

Αλγοριθμική θεωρία πληροφοριών και στην πολυπλοκότητα Κολμογόροφ
Ο Γκατς συνέγραψε αρκετές σημαντικές εργασίες στον τομέα της αλγοριθμικής θεωρίας της πληροφορίας και της πολυπλοκότητας Κολμογόροφ Μαζί με τον Λεονίντ Α. Λέβιν, καθιέρωσε βασικές ιδιότητες της πολυπλοκότητας προθέματος, συμπεριλαμβανομένου του τύπου για την πολυπλοκότητα των ζευγαριών Peter Gacs. On the symmetry of algorithmic information. Doklady Akademii Nauk SSSR, 218(6):1265–1267, 1974. In Russian. και για τις ελλείψεις τυχαιότητας, συμπεριλαμβανομένου του αποτελέσματος που ανακαλύφθηκε εκ νέου αργότερα και είναι πλέον γνωστό ως λήμμα της άφθονης περίσσειας Peter Gacs. Exact expressions for some randomness tests. Z. Math. Log. Grdl. M., 26:385–394, 1980.  Downey, Rodney G., and Denis R. Hirschfeldt. Algorithmic randomness and complexity. Springer, 2010. Έδειξε ότι η αντιστοιχία μεταξύ πολυπλοκότητας και εκ των προτέρων πιθανότητας που ισχύει για την πολυπλοκότητα προθέματος δεν ισχύει πλέον για μονοτονική πολυπλοκότητα και συνεχή εκ των προτέρων πιθανότητα. Peter Gacs. On the relation between descriptional complexity and algorithmic probability. Theoretical Computer Science, 22:71–93, 1983. Short version: Proc. 22nd
IEEE FOCS (1981) 296-303Li, Ming, and Paul Vitányi. An introduction to Kolmogorov complexity and its applications. Vol. 3. New York: Springer, 2008.  Στη συναφή θεωρία της αλγοριθμικής τυχαιότητας απέδειξε ότι κάθε ακολουθία είναι αναγώγιμη κατά Turing σε μια τυχαία ακολουθία (το αποτέλεσμα που σήμερα είναι γνωστό ως θεώρημα Gacs-Kucera, καθώς είχε αποδειχθεί ανεξάρτητα από τον Antonin Kucera) Αργότερα εισήγαγε (μαζί με τους συν-συγγραφείς του) την έννοια της αλγοριθμικής απόστασης και απέδειξε τη σύνδεσή της με την υπό συνθήκη πολυπλοκότητα Charles H. Bennett, Peter Gacs, Ming Li, Paul M. B. Vitanyi, and Woiciech Zurek. Information distance. IEEE Transactions on Information Theory, 44(4):1407–1423, 1998. (Preliminary version appeared in STOC’97, arXiv:1006.3520.) According to Google Scholar, this paper has been cited 687 times by April, 2021  .

Ήταν ένας από τους πρωτοπόρους της αλγοριθμικής στατιστικής, Peter Gacs, John Tromp, and Paul M. B. Vitanyi. Algorithmic statistics. IEEE Transactions on Information Theory, 47:2443–2463, 2001. arXiv:math/0006233[math.PR]. Short version with similar title in Algorithmic Learning Theory, LNCS 1968/2000. εισήγαγε μια από τις κβαντικές εκδοχές για την αλγοριθμική πολυπλοκότητα, Aditi Dhagat, Peter Gacs, and Peter Winkler. On playing "twenty questions" with a liar. In Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, SODA’92, pages 16–22, Philadelphia, PA, USA, 1992. Society for Industrial and Applied Mathematics. μελέτησε τις ιδιότητες της αλγοριθμικής τυχαιότητας για γενικούς χώρους  Peter Gacs. Uniform test of algorithmic randomness over a general space. Theoretical Computer Science, 341(1-3):91–137, 2005. Peter Gacs, Mathieu Hoyrup, and Cristobal Rojas. Randomness on computable probability spaces - a dynamical point of view. Theory of Computing Systems, 48:465–485, 2011. 10.1007/s00224-010-9263-x, arXiv:0902.1939. Appeared also in
STACS 2009.  και γενικές κατηγορίες μέτρων  Laurent Bienvenu, Peter Gacs, Mathieu Hoyrup, Cristobal Rojas, and Alexander Shen. 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. Lecture notes on descriptional complexity and randomness. Technical report, Boston University, Computer Science Dept., Boston, MA 02215, 2009.
www.cs.bu.edu/faculty/gacs/papers/ait-notes.pdf. Thomas M. Cover, Peter Gacs, and Robert M. Gray. Kolmogorov’s contributions to information theory and algorithmic complexity. The Annals of Probability,  17(3):840–865, 1989.   Επίσης, απέδειξε αποτελέσματα στα όρια μεταξύ της κλασικής και της αλγοριθμικής θεωρίας πληροφορίας: το θεμελιώδες παράδειγμα που δείχνει τη διαφορά μεταξύ κοινής και αμοιβαίας πληροφορίας (με τον János Körner) Peter Gacs and Janos Korner. Common information is far less than mutual information. Problems of Control and Inf. Th., 2:149–162, 1973. Μαζί με τον Ρούντολφ Άλσβεντε και τον Körner απέδειξε το λήμμα της ανατίναξης (blowing-up lemma)  Ahlswede, Gacs, Körner Bounds on conditional probabilities with applications in multiuser communication, Z. Wahrsch. und Verw. Gebiete 34, 1976, 157–177.

Δημοσιεύσεις
 Packing of convex sets in the plane with a large number of neighbors (1972)
 On the relation between descriptional complexity and algorithmic (1983)
 Deterministic computations whose history is independent of the order of ´ updating (1995)
 The angel wins (2006)
 A Turing machine resisting isolated bursts of faults (2013) - kun iu alia

Παραπομπές

Κατηγορία:Μαθηματικοί αναλυτές
Κατηγορία:Ούγγροι μαθηματικοί
Κατηγορία:Μαθηματικοί του 20ού αιώνα
Κατηγορία:Μαθηματικοί του 21ου αιώνα