Alexander Razborov
Alexander Razborov | |
|---|---|
| Geboren | 16. Februar 1963 |
| Staatsangehörigkeit | Vereinigte Staaten, Russland |
| Alma Mater | Moskauer Staatsuniversität |
| Bekannt für | Gruppentheorie, Logik in der Informatik, Theoretische Informatik |
| Auszeichnungen |
|
| Wissenschaftliche Karriere | |
| Felder | Mathematiker |
| Institutionen | Universität von Chicago, Steklov Mathematical Institute, Toyota Technological Institute in Chicago |
| Doktorand | Sergei Adian |
Aleksandr Aleksandrovich Razborov (Russisch: Алекса́ндр Алекса́ндрович Разбо́ров; Geboren am 16. Februar 1963), manchmal bekannt als Sasha Razborov, ist ein Sowjet und Russisch Mathematiker und Computertheoretiker. Er ist Andrew McLeish Distinguished Service Professor am Universität von Chicago.
Forschung
In seiner bekanntesten Arbeit mit gemeinsam mit Steven Rudicher führte den Begriff von vor Natürliche Beweise, eine Klasse von Strategien, die verwendet werden, um grundlegende untere Grenzen zu beweisen in Rechenkomplexität. Insbesondere Razborov und Rudich zeigten, dass unter der Annahme, dass bestimmte Arten von Einwegfunktionen Existieren können solche Beweise keine Lösung des P = np Problem, daher sind neue Techniken erforderlich, um diese Frage zu lösen.
Auszeichnungen
- NevanLinna -Preis (1990) zur Einführung der "Approximation -Methode" bei der Beweisung Boolesche Schaltung Untergrenzen von einigen wesentlichen Algorithmisch Probleme,[1]
- ERDős Dozent, Hebräische Universität von Jerusalem, 1998.
- Entsprechendes Mitglied des Russische Akademie der Wissenschaften (2000)[2][3]
- Gödel -Preis (2007 mit Steven Rudich) für das Papier "Natürliche Beweise. "[4][5]
- David P. Robbins Preis Für das Papier „über die minimale Dichte der Dreiecke in Grafiken“ (Kombinatorik, Wahrscheinlichkeit und Computing 17 (2008), Nr. 4, 603–618) und zur Einführung einer neuen leistungsstarken Methode, Flag -Algebren, zur Lösung von Problemen in extremen Kombinatorik
- Gödel Dozent (2010) mit dem Vortrag mit dem Titel " Komplexität von Propositionalbeweisen.[6]
- Andrew MacLeish Distinguished Service Professor (2008) in der Abteilung für Informatik, Universität von Chicago.
- Fellow der American Academy of Arts and Sciences (AAAS) (2020).[7]
Literaturverzeichnis
- Razborov, A. A. (1985). "Untergrenzen für die monotonische Komplexität einiger Booleschen Funktionen" (PDF). Sowjetische Mathematik - Doklady. 31: 354–357.
- Razborov, A. A. (Juni 1985). "Untergrenzen der monotonischen Komplexität der logischen Permanent". Mathematische Notizen der Akademie der Wissenschaften der UdSSR. 37 (6): 485–493. doi:10.1007/bf01157687. S2CID 120875831.
- Разборов, александр александрович (1987). О сizin (PDF) (auf Russisch). Московский г гсдарственный университет. (Doktorarbeit. 32,56 MB)
- Razborov, A. A. (April 1987). "Untergrenzen auf der Größe der begrenzten Tiefenschaltungen über eine vollständige Basis mit logischer Ergänzung". Mathematische Notizen der Akademie der Wissenschaften der UdSSR. 41 (4): 333–338. doi:10.1007/bf01137685. S2CID 121744639.
- Razborov, Alexander A. (Mai 1989). "Proceedings des einundzwanzigsten jährlichen ACM -Symposiums zur Theorie des Computers - STOC '89". Verfahren des 21. jährlichen ACM -Symposiums zur Computertheorie. Seattle, Washington, Vereinigte Staaten. S. 167–176. doi:10.1145/73007.73023. ISBN 0897913078.
- Razborov, A. A. (Dezember 1990). "Untergrenze der Komplexität symmetrischer boolescher Funktionen von Kontaktrezierschaltungen". Mathematische Notizen der Akademie der Wissenschaften der UdSSR. 48 (6): 1226–1234. doi:10.1007/bf01240265. S2CID 120703863.
- Razborov, Alexander A.; Rudich, Stephen (Mai 1994). "Proceedings of the Sechsundzwanzigste jährliche ACM -Symposium über die Theorie des Computers - STOC '94". Verfahren des 26. jährlichen ACM -Symposiums zur Computertheorie. Montreal, Quebec, Kanada. S. 204–213. doi:10.1145/195058.195134. ISBN 0897916638.
- Razborov, Alexander A. (Dezember 1998). "Untergrenzen für den Polynomkalkül" (PostScript). Rechenkomplexität. 7 (4): 291–324. Citeseerx 10.1.1.19.2441. doi:10.1007/S000370050013. S2CID 8130114.
- Razborov, Alexander A. (Januar 2003). "Aussagener Beweiskomplexität" (PostScript). Journal of the ACM. 50 (1): 80–82. doi:10.1145/602382.602406. S2CID 17351318. (Vermessungspapier zum 50 -jährigen Jubiläum von JACM)
Siehe auch
- Avi Wigderson
- Komplexität der Schaltung
- Freie Gruppe
- Natürliche Beweise
- Einweg-Funktion
- Pseudorandom -Funktion Familie
- Auflösung (Logik)
Anmerkungen
- ^ "Internationale Mathematische Union: Rolf NevanLinna -Preisträger". Archiviert von das Original Am 2007-12-17.
- ^ "Russische Akademie der Wissenschaften: Razborov Aleksandr Aleksandrovich: Allgemeine Info: Geschichte".
- ^ "Russische Genealogie -Agenturen Baum: R" (auf Russisch). Archiviert von das Original Am 2007-12-21. Abgerufen 2008-01-15.
- ^ "ACM-Sigact Awards und Preise: 2007 Gödel Prize".
- ^ "Eatcs: Gödel Prize - 2007". Archiviert von das Original Am 2007-12-01.
- ^ "Gödel Dozenten - Assoziation für symbolische Logik". Abgerufen 2021-11-10.
- ^ "AAAS -Stipendiaten gewählt" (PDF). Mitteilungen der American Mathematical Society.
Externe Links
- Alexander Razborov Bei der Mathematik Genealogie -Projekt.
- Alexander Razborovs Startseite.
- All-russisches mathematisches Portal: Personen: Razborov Alexander Alexandrovich.
- Biographie -Skizze im Toyota Technological Institute in Chicago.
- Lebenslauf am Institut für Informatik der Universität von Chicago.
- DBLP: Alexander A. Razborov.
- Alexander Razborovs Ergebnisse bei Internationale mathematische Olympiade
- MathScinet: "Artikel, die von Razborov, A. A. verfasst wurden, verfasst."[Permanent Dead Link]
- Die Arbeit von A.A. Razborov - Ein Artikel von László Lovász in dem Verfahren der Internationaler Kongress der Mathematiker, Kyoto, Japan, 1990.