Alexander Razborov - Alexander Razborov

Alexander Razborov
narozený (1963-02-16) 16. února 1963 (věk 57)
Belovo, Ruský SFSR, Sovětský svaz
NárodnostUSA, Rusko
Alma materMoskevská státní univerzita
Známý jakoteorie skupin, logika v informatice, teoretická informatika
OceněníCena Nevanlinna  (1990)
Gödelova cena  (2007)
Cena Davida P. Robbinse  (2013)
Vědecká kariéra
PoleMatematik
InstituceUniversity of Chicago, Steklov matematický institut, Technologický institut Toyota v Chicagu
Doktorský poradceSergej Adian

Aleksandr Aleksandrovič Razborov (ruština: Александр Александрович Разбо́ров; narozený 16. února 1963), někdy známý jako Sasha Razborov, je sovětský a rusky matematik a výpočetní teoretik. On je Andrew McLeish Distinguished Service Professor at the University of Chicago.

Výzkum

V jeho nejznámějším díle společně s Steven Rudich, představil pojem přírodní důkazy, třída strategií používaných k prokázání základních dolních mezí v výpočetní složitost. Zejména Razborov a Rudich to ukázali za předpokladu, že určité druhy jednosměrné funkce takové důkazy nemohou poskytnout rozhodnutí o P = NP problém, takže k vyřešení této otázky budou zapotřebí nové techniky.

Ocenění

Bibliografie

  • Razborov, A. A. (1985). „Dolní hranice pro monotónní složitost některých booleovských funkcí“ (PDF ). Sovětská matematika - Doklady. 31: 354–357.
  • Razborov, A. A. (červen 1985). "Nižší hranice monotónní složitosti logického permanentu". Matematické poznámky Akademie věd SSSR. 37 (6): 485–493. doi:10.1007 / BF01157687.
  • Разборов, Александр Александрович (1987). О системах уравнений в свободной группе (PDF) (v Rusku). Московский государственный университет. (Disertační práce. 32,56 MB)
  • Razborov, A. A. (duben 1987). "Dolní hranice velikosti obvodů ohraničené hloubky na úplném základě s logickým přidáním". Matematické poznámky Akademie věd SSSR. 41 (4): 333–338. doi:10.1007 / BF01137685.
  • Razborov, Alexander A. (květen 1989). „O metodě aproximací“ (PDF. 1,41 MB). Sborník 21. výročního sympozia ACM o teorii práce s počítačem. Seattle, Washington, Spojené státy. 167–176. doi:10.1145/73007.73023.
  • Razborov, A. A. (prosinec 1990). "Dolní hranice složitosti symetrických booleovských funkcí obvodů kontaktního usměrňovače". Matematické poznámky Akademie věd SSSR. 48 (6): 1226–1234. doi:10.1007 / BF01240265.
  • Razborov, Alexander A .; Rudich, Stephen (květen 1994). "Přírodní důkazy" (PostScript ). Proceedings of the 26. Annual ACM Symposium on the Theory of Computing. Montreal, Quebec, Kanada. 204–213. doi:10.1145/195058.195134.
  • Razborov, Alexander A. (prosinec 1998). „Dolní hranice polynomiálního počtu“ (PostScript). Výpočetní složitost. 7 (4): 291–324. CiteSeerX  10.1.1.19.2441. doi:10,1007 / s000370050013.
  • Razborov, Alexander A. (leden 2003). „Propoziční složitost důkazů“ (PostScript). Deník ACM. 50 (1): 80–82. doi:10.1145/602382.602406. (Anketa k 50. výročí JACM)

Viz také

Poznámky

  1. ^ „International Mathematical Union: Rolf Nevanlinna Prize Prize“. Archivovány od originál dne 17.12.2007.
  2. ^ "Russian Academy of Sciences: Razborov Aleksandr Aleksandrovich: General info: History".
  3. ^ „Strom ruských genealogických agentur: R“ (v Rusku). Archivovány od originál dne 21.12.2007. Citováno 2008-01-15.
  4. ^ „Ocenění a ceny ACM-SIGACT: Cena Gödel za rok 2007“.
  5. ^ „EATCS: Gödel Prize - 2007“. Archivovány od originál dne 01.12.2007.
  6. ^ „Členové AAAS zvoleni“ (PDF). Oznámení Americké matematické společnosti.

externí odkazy