Alexander Razborov

Alexander Razborov Llave de datos
Nacimiento 16 de febrero de 1963
Casa Bandera de estados unidos Estados Unidos
Nacionalidad Rusia
Áreas Informática teórica , matemáticas
Instituciones Instituto de Matemáticas Steklov , Universidad de Chicago , Instituto Tecnológico de Toyota en Chicago  (en)
Diplomado Universidad estatal de Moscú
Reconocido por teoría de grupos , informática teórica
Premios Premio Nevanlinna (1990)
Premio Gödel (2007)

Alexander Alexandrovich Razborov ( ruso  : Алекса́ндр Алекса́ндрович Разбо́ров , nacido el16 de febrero de 1963), también conocido como Sacha Razborov , es un matemático y teórico informático soviético y ruso . Ganó el Premio Nevanlinna en 1990 por su trabajo sobre teoría de la complejidad y en 2007 el Premio Gödel con Steven Rudich por su artículo “  Pruebas naturales  ” .

Biografía

Su director de tesis es Sergei Adian . Razborov se convirtió en 2009 en Andrew MacLeish  (en) Distinguished Service Professor en el departamento de TI de la Universidad de Chicago .

Premios y reconocimientos

Es elegido en 26 de mayo de 2000miembro correspondiente de la Academia de Ciencias de Rusia . Su número de Erdős es 2. En 2010 fue Gödel Lecturer con una conferencia titulada Complexity of Propositional Proofs . En 2013, recibió el premio Robbins por su artículo “Sobre la densidad mínima de triángulos en gráficos”.

Obras

Su trabajo más conocido, en colaboración con Steven Rudich, es la introducción del concepto de evidencia natural ( pruebas naturales ), una clase de estrategias para probar límites inferiores en la teoría de la complejidad de los algoritmos . En particular, Razborov y Rudich han demostrado que bajo la hipótesis de que existen ciertas funciones unidireccionales , tales demostraciones no permiten resolver el problema P = NP , que entonces requeriría nuevas técnicas.

Bibliografía

Notas y referencias

(fr) Este artículo está tomado parcial o totalmente del artículo de Wikipedia en inglés titulado "  Alexander Razborov  " ( consulte la lista de autores ) .
  1. (en) "  Ganadores del premio de la Unión Matemática Internacional Rolf Nevanlinna  " [ archivo27 de diciembre de 2008] (consultado el 20 de enero de 2014 )
  2. (en) "  EATCS: Premio Gödel - 2007  "
  3. (en) "  Alexander Razborov  " en el sitio Mathematics Genealogy Project
  4. (en) "  Academia de Ciencias de Rusia: Razborov Aleksandr Aleksandrovich: Información general: Historia  "
  5. (in) "  Algunas personas famosas con números finitos de Erdos: ganadores del premio Nevanlinna  "
  6. Razborov: Sobre la densidad mínima de triángulos en gráficos , Combinatoria, Probabilidad y Computación } 17 (4): 603-618, 2008.

Ver también

Artículos relacionados

enlaces externos