Direkt zum Inhalt

Lexikon der Mathematik: Widgerson, Avi

Informatiker, geb. 9.9.1956.

Widgerson ist Professor am Institue for Advanced Study in Princeton (NJ.) und am Institute for Computer Sciences in Jerusalem.

Er erzielte bedeutende Beiträge zu den mathematischen Grundlagen der Informatik, zu den Grundlagen der Kryptographie und zur Komplexitätstheorie im Großen. Ein spezielles Gebiet, auf dem er eindrucksvolle Ergebnisse erreichte, bilden die sog. Zeroknowledgeinteractiveproofs, d. h. Beweise, mit denen einen Widerpart von der Wahrheit einer mathematischen Aussage überzeugt werden soll, ohne einen formalen Beweis anzugeben. Zusammen mit Kollegen zeigte Widgerson 1988, daß derartige Beweise für NP-Probleme möglich sind, und 1993, daß die dabei auftretende Annahme der Existenz einer sog. Ein-Weg-Funktion wesentlich für die Existenz der Zero-Knowledge-Beweise ist. (Eine Ein-Weg-Funktion ist eine Funktion, für die zu gegebenen x der Funktionswert y = f(x) leicht berechnet werden kann, für die es aber sehr schwierig ist, zu gegebenen y einen zugehörigen x-Wert zu ermitteln. Die Existenz dieser Funktion wird meist akzeptiert, ist aber nicht bewiesen.)

Gleichzeitig gelang Widgerson und Mitarbeitern 1988 eine Veränderung der Zeroknowledgeinteractiveproofs, so daß die Annahme einer Ein-Weg-Funktion vermieden werden kann. Er wandte dann diese Methode in Computernetzen an. Außerdem ermittelte er untere und obere Schranken, um die Komplexität der Berechnungen für verschiedenste Problem abzuschätzen.

Für seine außerordentlichen Ergebnisse wurde Widgerson 1994 mit dem Nevanlinna-Preis geehrt.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte