Michael Saks (Mathematiker)

Michael Ezra saks ist ein amerikanischer Mathematiker. Derzeit ist er Abteilungsvorsitzender der Mathematikabteilung an der Rutgers University (2017–17–2017) und war von 2006 bis 2010 Direktor des Mathematics Graduate Program bei Rutgers University. Saks erhielt seine Ph.D. von dem Massachusetts Institute of Technology 1980 nach Abschluss seiner Dissertation mit dem Titel " Dualitätseigenschaften von endlichen Set -Systemen[1] unter seinem Berater Daniel J. Kleitman.

Eine Liste seiner Veröffentlichungen und Kooperationen kann bei gefunden werden DBLP.[2]

2016 wurde er ein Fellow der Vereinigung für Computermaschinen.[3][4]

Forschung

Saks recherch in Computerkomplexitätstheorie, Kombinatorik, und Graphentheorie hat zur Untersuchung der unteren Grenzen in beigetragen Ordnungstheorie, Randomisierte Berechnung, und Weltraum -Zeit -Kompromiss.

In Kahn und Saks (1984) wurde gezeigt teilweise bestellt Informationen bis zu einer multiplikativen Konstante.[5]

Im [1] Die erste superlineare Untergrenze für das verrückte Rundfunkproblem wurde bewiesen. In einem lauten Rundfunkmodell, Prozessoren werden ein lokales Eingangsbit zugewiesen . Jeder Prozessor kann a durchführen laute Sendung an alle anderen Prozessoren, bei denen die empfangenen Bits unabhängig mit einer festen Wahrscheinlichkeit umgedreht werden können. Das Problem ist der Prozessor bestimmen für eine gewisse Funktion . Saks et al. zeigten, dass ein vorhandenes Protokoll von Gallager tatsächlich durch eine Verringerung einer verallgemeinerten Lautstärke optimal war Entscheidungsbaum und produzierte a Untergrenze an der Tiefe des Baumes, der die Eingabe lernt.[6]

In Beam et al. (2003) wurde nachgewiesen, dass das erste Mal-Raum-Untergrenze für randomisierte Berechnung von Entscheidungsproblemen nachgewiesen wurde.[7]

Positionen

Saks hält Positionen in den folgenden Zeitschriften -Redaktionsgremien innehatte:

  • Siam J. On Computing, Associate Editor
  • Kombinatorica, Redaktionsvorstandsmitglied
  • Journal of Graph Theory, Redaktionsvorstandsmitglied
  • Diskrete angewandte Mathematik, Redaktionsvorstandsmitglied

Verweise

  1. ^ Saks, Michael Ezra (1980). Dualitätseigenschaften von endlichen Set -Systemen (Ph.D. -These). Massachusetts Institute of Technology. OCLC 7447661.
  2. ^ Michael E. Saks bei DBLP Bibliographieserver Edit this at Wikidata
  3. ^ CACM -Mitarbeiter (März 2017), "ACM erfasst neue Stipendiaten", Kommunikation der ACM, 60 (3): 23, doi:10.1145/3039921, S2CID 31701275.
  4. ^ "Empfänger". Awards.Acm.org. Abgerufen 2018-07-01.
  5. ^ Kahn, J.; Saks, M. (1984). "Jeder Poset hat einen guten Vergleich". Verfahren des sechzehnten jährlichen ACM -Symposiums über die Theorie des Computers - STOC '84. p. 299. doi:10.1145/800057.808694. ISBN 978-0897911337. S2CID 17374296.
  6. ^ Gallager, R. G. (1988). "Parität in einfachen Broadcast -Netzwerken finden". IEEE -Transaktionen zur Informationstheorie. 34 (2): 176–180. Citeseerx 10.1.1.422.3311. doi:10.1109/18.2626.
  7. ^ Beame, P.; Saks, M.; Sun, X.; Vee, E. (2003). "Zeit-Raum-Kompromiss unteren Grenzen für randomisierte Berechnung von Entscheidungsproblemen". Journal of the ACM. 50 (2): 154. Citeseerx 10.1.1.16.8696. doi:10.1145/636865.636867. S2CID 9459178.

Externe Links