Zum Inhalt springen

Alexander Alexandrowitsch Rasborow

aus Wikipedia, der freien Enzyklopädie
Datei:Aleksandr Aleksandrovich Razborov Oberwolfach 2024.jpg
Alexander Alexandrowitsch Rasborow

Alexander Alexandrowitsch Rasborow ({{#invoke:Vorlage:lang|full|CODE=ru|SCRIPTING=Cyrl|SERVICE=russisch}}, englische Transliteration Alexander Razborov; * 6. Februar 1963 in Belowo) ist ein russischer Informatiker und Mathematiker.

Rasborow studierte 1980 bis 1985 an der Lomonossow-Universität (Fakultät für Mathematik und Mechanik) und nach dem Diplom von 1985 bis 1987 bei Sergei Adjan am Steklow-Institut, bei dem er 1987 promovierte (Über Systeme von Gleichungen in freien Gruppen).<ref>{{#invoke:WLink|getArticleBase}} im Mathematics Genealogy Project (englisch){{#if: | {{{Kommentar}}} }} {{#if: 108275 | {{#ifeq: {{#property:P549}} | 108275 | | {{#if: {{#property:P549}} | {{#if: | | }} | {{#if: | | }} }} }} }}{{#if: 108275 | Vorlage:MathGenealogyProject/Wartung/id verwendet}}{{#if: | Vorlage:MathGenealogyProject/Wartung/name verwendet}}{{#ifeq:|{{#invoke:WLink|getArticleBase}}|Vorlage:MathGenealogyProject/Wartung/unnötige Verwendung von Parameter 2|}}</ref> Danach war er Forscher am Steklow-Institut, ab 1991 als Leiter einer Arbeitsgruppe (Leading Researcher) und ab 2008 mit dem Titel Principal Researcher. 1991 erhielt er den russischen Doktorgrad (Untere Grenzen in der Booleschen Komplexität). Seit 2008 ist er Andrew McLeish Distinguished Service Professor in der Fakultät für Informatik der University of Chicago. 1999 bis 2000 war er Gastwissenschaftler an der Princeton University und 1993 bis 1994 und 2000 bis 2008 war er am Institute for Advanced Study (2003 bis 2008 als Gastprofessor). In Teilzeit ist er auch (2012) noch am Steklow-Institut sowie am Toyota Technological Institute in Chicago.

1990 erhielt er den Nevanlinna-Preis für seine Methode, untere Grenzen für die Schaltkreiskomplexität (Boolean Circuit Complexity) zu finden.<ref>Razborov: Lower bounds for the monotone complexity of some Boolean functions. In: Soviet Mathematics – Doklady. Band 31, Nummer 2, 1985, S. 354–357, (PDF; 482 kB).</ref> Er zeigte, dass die Lücke in der Schaltkreiskomplexität zwischen monotonen Booleschen Funktionen (solche aufgebaut aus logischen und, oder und Identität, nicht mit Negation) und nicht-monotonen Super-polynomial sein kann (von Noga Alon/R. B. Boppana<ref>Noga Alon, Ravi B. Boppana: The monotone circuit complexity of Boolean functions. In: Combinatorica. Band 7, Nummer 1, 1987, S. 1–22, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}.</ref> und Éva Tardos auf exponentiell verbessert).

2007 erhielt er mit Steven Rudich den Gödel-Preis für ihre Arbeit Natural Proof, die zeigte, dass Schaltkreiskomplexitätsmethoden zur Bestimmung einer Untergrenze der Komplexität eines Problems wahrscheinlich nicht geeignet sind, das P-NP-Problem zu lösen.<ref>Razborov, Rudich: Natural Proof. In: Journal of Computer and System Sciences. Band 55, Nummer 1, 1997, S. 24–35, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}, und Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing. Montréal, Quebéc, Canada, May 23–25, 1994. ACM Press, New York NY 1994, ISBN 0-89791-663-8, S. 204, Online, Postscript-Datei.</ref> Dabei isolierten sie eine gemeinsame Eigenschaft dieser Schaltkreiskomplexitäts-Verfahren, die sie Natural Proof nennen. Sie zeigten, dass ein Natural Proof-Beweis für das P=NP-Problem zur Folge hätte, dass keine Pseudozufallsgeneratoren existieren, was aber allgemein angenommen wird. Weiter zeigten sie, dass es keine Natural Proof-Beweise dafür gibt, dass einige bekannte kryptographische Probleme NP-schwer sind (wie die Faktorisierung ganzer Zahlen oder das Problem des diskreten Logarithmus). Die Arbeit von Razborov und Rudich war ein wichtiger Fortschritt im P=NP-Problem, einem der Clay-Probleme, der zeigte, dass man in neuen Richtungen nach der Lösung suchen musste.

In der extremalen Graphentheorie erzielte er Teilresultate beim Cliquen-Dichte-Problem von László Lovász und Miklós Simonovits (allgemein gelöst 2016 von Christian Reiher).

Seit 2000 ist er korrespondierendes Mitglied der Russischen Akademie der Wissenschaften. 2000 hielt er die Tarski Lectures. Seit 1993 ist er Mitglied der Academia Europaea. 1998 hielt er die Paul Erdős Lectures in Jerusalem und die Coxeter Lectures beim Fields Institute in Toronto. 1986 war er Invited Speaker auf dem ICM in Berkeley (Lower bounds for monotone complexity of boolean functions). 2010 war er Gödel-Lecturer.

2013 erhielt er den David P. Robbins Prize der American Mathematical Society für seine Arbeit On the minimal density of triangles in graphs<ref>Combinatorics, Probability and Computing. Band 17, Nummer 4, 2008, S. 603–618, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}.</ref> und für die Einführung von Flaggen-Algebren (Flag Algebras) als mächtige neue Methode in die extremale Kombinatorik.<ref>David P. Robbins Prize.</ref> Rasborow löste damit ein altes lange offenes Problem der extremalen Kombinatorik, die Frage nach der minimalen Anzahl von Dreiecken in Graphen mit n Ecken und m Kanten.

2020 wurde Rasborow in die American Academy of Arts and Sciences gewählt.

Schriften (Auswahl)

Außer die in den Fußnoten zitierten Arbeiten:

  • Lower bounds on monotone complexity of the logical permanent. In: Mathematical Notes of the Academy of Sciences of the USSR. Band 37, 1985, S. 485–493, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}.
  • On the method of approximations. In: Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing. Seattle, Washington, May 15–17, 1989. ACM Press, New York NY 1989, ISBN 0-89791-307-8, S. 167–176, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}.
  • The <math>\mathbf{P}</math><math>\stackrel{\text{?}}=</math><math>\mathbf{NP}</math>-Problem: A View from the 1990s. In: Andrej A. Bolibruch, Yurii S. Osipov, Âkov G. Sinai (Hrsg.): Mathematical Events of the Twentieth Century. Springer u. a., Berlin u. a. 2006, ISBN 3-540-23235-4, S. 331–346, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}.
  • Flag Algebras. In: The Journal of Symbolic Logic. Band 72, Nummer 4, 2007, S. 1239–1282, {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}.

Weblinks

      | {{#ifeq: 20090423014429 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Gödel-Preis für Razborov | {{#invoke:WLink|getEscapedTitle|Gödel-Preis für Razborov}} | {{#invoke:Webarchiv|getdomain|http://sigact.acm.org/prizes/godel/2007.html}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20090423014429}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: Gödel-Preis für Razborov | {{#invoke:WLink|getEscapedTitle|Gödel-Preis für Razborov}} | {{#invoke:Webarchiv|getdomain|http://sigact.acm.org/prizes/godel/2007.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20090423014429}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Gödel-Preis für Razborov | {{#invoke:WLink|getEscapedTitle|Gödel-Preis für Razborov}} | {{#invoke:Webarchiv|getdomain|http://sigact.acm.org/prizes/godel/2007.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Gödel-Preis für Razborov | {{#invoke:WLink|getEscapedTitle|Gödel-Preis für Razborov}} | {{#invoke:Webarchiv|getdomain|http://sigact.acm.org/prizes/godel/2007.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Gödel-Preis für Razborov | {{#invoke:WLink|getEscapedTitle|Gödel-Preis für Razborov}} | {{#invoke:Webarchiv|getdomain|http://sigact.acm.org/prizes/godel/2007.html}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Gödel-Preis für Razborov | {{#invoke:WLink|getEscapedTitle|Gödel-Preis für Razborov}} | {{#invoke:Webarchiv|getdomain|http://sigact.acm.org/prizes/godel/2007.html}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20090423014429|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://sigact.acm.org/prizes/godel/2007.html}}
    || {{#if:  || }}
  }}{{#if: Gödel-Preis für Razborov
    | {{#if: {{#invoke:WLink|isBracketedLink|Gödel-Preis für Razborov}}
        | {{#if:  || }}
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://sigact.acm.org/prizes/godel/2007.html%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://sigact.acm.org/prizes/godel/2007.html%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://sigact.acm.org/prizes/godel/2007.html }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }}

Einzelnachweise

<references />

{{#ifeq: p | p | | {{#if: 311393238 | |

}} }}Vorlage:Hinweisbaustein{{#ifeq: p | p | | {{#if: 311393238 | |

}} }}{{#ifeq:||{{#if: 2023-10-12 | [[Kategorie:Wikipedia:GND fehlt {{#invoke:Str|left|2023-10-12|7}}]] }}{{#if: ja | {{#if: 2023-10-12 | | }} }} }}{{#if: | {{#ifeq: 0 | 2 | | }} }}{{#if: | {{#ifeq: 0 | 2 | | }} }}{{#ifeq: p | p | {{#if: | | {{#if: {{#statements:P227}} | | }} }} }}{{#ifeq: p | p | {{#if: | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P227}} | | }} }} }} }}{{#ifeq: p | p | {{#if: | | {{#if: {{#statements:P244}} | | }} }} }}{{#ifeq: p | p | {{#if: | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P244}} | | }} }} }} }}{{#ifeq: p | p | {{#if: 311393238 | | {{#if: {{#statements:P214}} | | }} }} }}{{#ifeq: p | p | {{#if: 311393238 | {{#if: {{#invoke:Wikidata|pageId}} | {{#if: {{#statements:P214}} | | }} }} }} }}Vorlage:Wikidata-Registrierung

{{#if: Rasborow, Alexander Alexandrowitsch | {{#if: Razborov, Alexander; Разборов, Александр Александрович (russisch) | {{#if: russischer Mathematiker | {{#if: 6. Februar 1963 | {{#if: Belowo | {{#if: | {{#if: |
Personendaten
NAME Rasborow, Alexander Alexandrowitsch

}}

ALTERNATIVNAMEN Razborov, Alexander; Разборов, Александр Александрович (russisch)

}}

KURZBESCHREIBUNG russischer Mathematiker

}}

GEBURTSDATUM 6. Februar 1963

}}

GEBURTSORT Belowo

}}

STERBEDATUM

}}

STERBEORT

}}

Vorlage:Wikidata-Registrierung

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=Alexander_Alexandrowitsch_Rasborow&oldid=1807451“