Alexander Razborov
Alexander Razborov| Fødsel | 16. februar 1963 |
|---|---|
| Hjem |
 Forenede Stater
|
| Nationalitet | Rusland |
| Områder | Teoretisk datalogi , matematik |
| Institutioner | Steklov Mathematical Institute , University of Chicago , Toyota Technological Institute i Chicago (en) |
| Eksamensbevis | Moskva State University |
| Berømt for | gruppeteori , teoretisk datalogi |
| Priser |
Nevanlinna-prisen (1990) Gödel-prisen (2007) |
Alexander Alexandrovich Razborov ( russisk : Алекса́ндр Алекса́ндрович Разбо́ров , født den16. februar 1963), også kendt som Sacha Razborov , er en sovjetisk og russisk matematiker og computerteoretiker . Han vandt Nevanlinna-prisen i 1990 for sit arbejde med kompleksitetsteori og i 2007 Gödel-prisen med Steven Rudich for deres artikel " Natural proofs " .
Biografi
Dens specialevejleder er Sergei Adian . Razborov blev i 2009 Andrew MacLeish (en) Distinguished Service Professor i IT-afdelingen ved University of Chicago .
Præmier og anerkendelse
Han vælges den 26. maj 2000tilsvarende medlem af det russiske videnskabsakademi . Hans Erds nummer er 2. I 2010 var han Gödel-lektor med et foredrag med titlen Complexity of Propositional Proofs . I 2013 modtog han Robbins-prisen for sin artikel "Om den minimale tæthed af trekanter i grafer".
Arbejder
Hans mest kendte arbejde, i samarbejde med Steven Rudich, er introduktionen af begrebet naturlige beviser ( naturlige beviser ), en klasse af strategier for at bevise lavere grænser i teorien om algoritmernes kompleksitet . Især Razborov og Rudich har vist, at under den hypotese, at nogle envejs funktioner eksisterer, behøver sådanne beviser ikke mulighed for at løse problemet P = NP , som derefter ville kræve nye teknikker.
Bibliografi
- (da) " Lavere grænser for monoton kompleksitet af nogle boolske funktioner " , Doklady Akademii Nauk SSSR , bind. 31,1985, s. 354–357 ( læs online [ pdf ])
- (en) " Lavere grænser for monoton kompleksitet af den logiske permanente " , Matematiske noter fra USSR's videnskabsakademi , bind. 37, nr . 6,Juni 1985, s. 485–493 ( DOI 10.1007 / BF01157687 )
- (ru) О системах уравнений в свободной группе , Московский государственный университет ,1987( læs online ) (Ph.d.-afhandling. 32.56MB)
- (en) " Sænk grænserne for størrelsen af afgrænsede dybdekredsløb over et komplet grundlag med logisk tilføjelse " , Matematiske bemærkninger fra USSR's Academy of Sciences , vol. 41, nr . 4,April 1987, s. 333–338 ( DOI 10.1007 / BF01137685 )
- (en) "Om metoden med tilnærmelser" i Proceedings of the 21. Annual ACM Symposium on Theory of Computing , Seattle , Washington , USA,Maj 1989, 167–176 s. ( DOI 10.1145 / 73007.73023 , læs online [pdf. 1.41MB ])
- (en) " Lavere grænser for kompleksiteten af symmetriske boolske funktioner i kontakt-ensretterkredsløb " , Matematiske bemærkninger fra USSR's Academy of Sciences , vol. 48, nr . 6,December 1990, s. 1226-1234 ( DOI 10.1007 / BF01240265 )
- (en) (med Stephen Rudich) , "Natural proofs" , i Proceedings of the 26.th ACM Symposium on Theory of Computing , Montreal , Quebec , Canada,Maj 1994, 204–213 s. , PostScript ( DOI 10.1145 / 195058.195134 , læs online )
- (en) " Nedre grænser for polynomregningen " , Computational Complexity , vol. 7, nr . 4,december 1998, s. 291–324 ( DOI 10.1007 / s000370050013 , læs online [ ps ])
- (en) " Propositional proof complexity " , ACM-tidsskrift , bind. 50, n o 1,januar 2003, s. 80–82 ( DOI 10.1145 / 602382.602406 , læs online [ps] ) (Kortlægningspapir til JACMs 50-års jubilæum)
Noter og referencer
(fr) Denne artikel er helt eller delvist taget fra den engelske Wikipedia- artikel med titlen " Alexander Razborov " ( se forfatterlisten ) .- (in) " International Mathematical Union Rolf Nevanlinna Prize Winners " [ arkiv27. december 2008] (adgang 20. januar 2014 )
- (in) " EATCS: Gödel-prisen - 2007 "
- (in) " Alexander Razborov " på webstedet Mathematics Genealogy Project
- (in) " Russian Academy of Sciences: Razborov Aleksandr Aleksandrovich: Generel info: Historie "
- (in) " Nogle berømte mennesker med begrænsede Erdos-numre: Nevanlinna-vindere "
- Razborov: På den minimale densitet af trekanter i grafer , Kombinatorik, Sandsynlighed og Computing } 17 (4): 603-618, 2008.
Se også
Relaterede artikler
eksterne links
- Myndighedsregistreringer :
- Forskningsressourcer :
- (in) Alexander Razborovs hjemmeside
- (da) All-Russian Mathematical Portal: Persons: Razborov Alexander Alexandrovich
- (en) Biografiskitse i Toyota Technological Institute i Chicago.
- (en) Curricula Vitae ved Institut for Datalogi, University of Chicago
- (en) DBLP: Alexander A. Razborov
- (da) "Elementer forfattet af Razborov, AA" ( MathSciNet , begrænset adgang)
- (en) AA Razborovs arbejde - en artikel af László Lovász i Proceedings of the ICM , Kyoto , Japan , 1990