Michael Saks – Wikipedia

Michael Ezra Saks ist ein US-amerikanischer Informatiker und Mathematiker.

Saks wurde 1980 am Massachusetts Institute of Technology bei Daniel J. Kleitman promoviert (Duality Properties of Finite Set Systems).^[1] Er ist Professor an der Rutgers University.

Saks befasst sich mit Komplexitätstheorie, Kombinatorik und Graphentheorie.

2004 erhielt er den Gödel-Preis mit Maurice Herlihy, Nir Shavit und Fotios Zaharoglou für seinen Aufsatz mit Zaharoglou: Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge (SIAM Journal on Computing, Band 29, 2000). Damit wurde ihre Entdeckung der Rolle der Topologie im verteilten Rechnen gewürdigt, die es ermöglicht die Frage der Existenz von Protokollen für bestimmte Probleme von ihrer dynamischen Natur zu befreien und auf ein topologisches Problem zu reduzieren.^[2] Zaharoglou war 1993 sein Doktorand an der University of California, San Diego.

Von ihm und Ramamohan Paturi, Pavel Pudlák und Francis Zane stammt der schnellste bekannte (randomisierte) Algorithmus für allgemeines k-SAT, PPSZ (benannt nach den Anfangsbuchstaben der Nachnamen der Autoren),^[3][4] entstanden aus dem Vorläufer PPZ von 1999,^[5] der nicht so gut wie der Algorithmus von Schöning war und wie PPSZ auf Encoding basierte. 2014 gab Timon Hertli Verbesserungen für den Fall unique 3-SAT.^[6]

• Homepage
• Michael E. Saks in der Datenbank zbMATH

1. ↑ Michael Saks im Mathematics Genealogy Project (englisch) Vorlage:MathGenealogyProject/Wartung/id verwendet
2. ↑ Laudatio Gödelpreis 2004
3. ↑ Paturi, Pudlàk, Saks, Zane, An improved exponential-time algorithm for K-SAT, J. ACM, Band 52, 2005, S. 337–364
4. ↑ Dominik Schweder, John P. Steinberger, PPSZ for General k-SAT – Making Hertli’s Analysis Simpler and 3-SAT Faster, 2017, Online
5. ↑ Paturi, Pudlàk, Zane, Chicago J. Theor. Computer Science 1999, Artikel 11 (elektronisch)
6. ↑ Hertli, Breaking the PPSZ Barrier for Unique 3-SAT, in: Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias (Hrsg.), Automata, Languages, and Programming – 41st International Colloquium, ICALP 2014, Kopenhagen, Juli 2014, Proc., Teil 1, Proceedings, Part I, Lecture Notes in Computer Science 8572, Springer 2014, S. 600–611