Noam Nisan

rdf:langString Noam Nisan

rdf:langString Noam Nisan (* 1961) ist ein israelischer Informatiker. Er ist Professor an der Hebräischen Universität in Jerusalem. Nisan erhielt 1984 seinen Bachelor-Abschluss summa cum laude an der Hebräischen Universität, war 1984/85 Software-Ingenieur bei Clarity Systems in (CAD für VLSI-Systeme) und setzte dann sein Studium an der University of California, Berkeley, fort mit dem Master-Abschluss und der Promotion 1988 bei Richard Karp (Complexity of Pseudonumber Generation). Seit 1990 ist er an der Hebräischen Universität mit einer vollen Professur seit 1997. 2007 bis 2009 forschte er für Google Research in Tel Aviv. Er befasst sich mit Komplexität von Zufallszahlengeneratoren, algorithmischer Spieltheorie (spezielle elektronische Märkte und Auktionen) und interaktiven Beweissystemen. 1998 bis 2002 war er Gründer und CTO der Softwarefirma SeeRun. 1992 formulierte er mit Mario Szegedy die Sensibilitäts-Vermutung für Boolesche Funktionen. 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 eine der bedeutendsten ungelösten Probleme der Informatik. Für 2018 wurde Nisan der EATCS-Award und der Rothschild-Preis zugesprochen. 2016 erhielt er den Knuth-Preis, 2012 gemeinsam mit Amir Ronen den Gödel-Preis für Arbeiten zur Algorithmischen Spieltheorie, in denen sie den Begriff Algorithmic Mechanism Design einführten. 2004 erhielt Nisan den Bruno Award. 1994 war er Invited Speaker auf dem Internationalen Mathematikerkongress in Zürich (Pseudorandom generators for derandomization of algorithms).