imported>1234qwer1234qwer4: lk

2026-01-05T23:07:35Z

Neue Seite

'''Mario Szegedy''' (* [[23. Oktober]] [[1960]]) ist ein [[Vereinigte Staaten|US-amerikanischer]] [[Informatiker]].

Szegedy wurde 1989 an der [[University of Chicago]] bei [[László Babai]] promoviert (''Algebraic Methods in Lower Bounds for Computational Models''). Als Post-Doc war er an der [[Hebräische Universität|Hebräischen Universität]] in Jerusalem, an der Universität Chicago und den [[Bell Laboratories]] (1992), an denen er danach bis 1999 war. 1999 war er am [[Institute for Advanced Study]]. Er ist Professor für Informatik an der [[Rutgers University]], an der er seit 2000 ist.

Szegedy beschäftigt sich mit [[Komplexitätstheorie]], [[Kombinatorik]], kombinatorischer Geometrie und Quanten-Informatik (er gründete QCteam, ein Quantum Computing Labor an der Rutgers University).

1992 formulierte er mit [[Noam Nisan]] die ''Sensibilitäts-Vermutung'' für Boolesche Funktionen.<ref>Nisan, Szegedy ''On the Degree of Boolean Functions As Real Polynomials'', Proc. of the Twenty-fourth Annual ACM Symposium on Theory of Computing. STOC '92, S. 462–467. </ref> Die Sensibilität ist eines von mehreren Komplexitätsmaßen für Boolesche Funktionen und misst die Wahrscheinlichkeit, dass die Änderung des Wertes eines Input-Bits den Output ändert. Bei den anderen Komplexitätsmaßen Boolescher Funktion war bekannt, dass sie in polynomialer Beziehung zueinander stehen, nur bei der Sensibilität war dies offen. Nisan und Szegedy vermuteten, dass auch die Sensitivität in polynomialer Beziehung mit den anderen Maßen stand. Die Vermutung war bis zu ihrer – überraschend eleganten und kurzen – bejahenden Lösung 2019 durch [[Hao Huang (Mathematiker)|Hao Huang]] eine der bedeutendsten ungelösten Probleme der Informatik.<ref>[https://www.quantamagazine.org/mathematician-solves-computer-science-conjecture-in-two-pages-20190725/ Erica Klarreich, Decades-Old Computer Science Conjecture Solved in Two Pages], Quanta Magazine, 25. Juli 2019.</ref><ref>Hao Huang, Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture, [https://arxiv.org/abs/1907.00847 Arxiv 2019].</ref>

Er erhielt zweimal den [[Gödel-Preis]], 2001 für seine Beteiligung am Beweis des PCP Theorems und 2005 für die Komplexitätsanalyse von Datenströmen. Für 2019 wurde ihm der [[Paris-Kanellakis-Preis]] zugesprochen.

== Weblinks ==
* [https://www.cs.rutgers.edu/~szegedy/ Homepage]

== Einzelnachweise ==
<references />

{{Normdaten|TYP=p|GNDfehlt=ja|GNDCheck=2024-01-07}}

{{SORTIERUNG:Szegedy, Mario}}
[[Kategorie:Informatiker]]
[[Kategorie:US-Amerikaner]]
[[Kategorie:Geboren 1960]]
[[Kategorie:Mann]]

{{Personendaten
|NAME=Szegedy, Mario
|ALTERNATIVNAMEN=
|KURZBESCHREIBUNG=US-amerikanischer Informatiker
|GEBURTSDATUM=23. Oktober 1960
|GEBURTSORT=
|STERBEDATUM=
|STERBEORT=
}}

Mario Szegedy - Versionsgeschichte

imported>1234qwer1234qwer4: lk