Alexander Razborov - Alexander Razborov

Alexander Razborov
Nació ( 16/02/1963 ) 16 de febrero de 1963 (58 años)
Belovo , RSFS de Rusia , Unión Soviética
Nacionalidad Estados Unidos, Rusia
alma mater Universidad estatal de Moscú
Conocido por teoría de grupos , lógica en informática , informática teórica
Premios Premio Nevanlinna  (1990)
Premio Gödel  (2007)
Premio David P. Robbins  (2013)
Carrera científica
Campos Matemático
Instituciones Universidad de Chicago , Instituto de Matemáticas Steklov , Instituto Tecnológico de Toyota en Chicago
Asesor de doctorado Sergei Adian

Aleksandr Aleksandrovich Razborov (en ruso : Алекса́ндр Алекса́ндрович Разбо́ров ; nacido el 16 de febrero de 1963), a veces conocido como Sasha Razborov , es un matemático y teórico computacional soviético y ruso . Es Andrew McLeish Distinguished Service Professor en la Universidad de Chicago .

Investigar

En su trabajo más conocido, junto con Steven Rudich , introdujo la noción de pruebas naturales , una clase de estrategias utilizadas para demostrar límites inferiores fundamentales en la complejidad computacional . En particular, Razborov y Rudich demostraron que, bajo el supuesto de que existen ciertos tipos de funciones unidireccionales , tales demostraciones no pueden dar una resolución del problema P = NP , por lo que se requerirán nuevas técnicas para resolver esta cuestión.

Premios

Bibliografía

  • Razborov, AA (1985). "Límites inferiores para la complejidad monótona de algunas funciones booleanas" ( PDF ) . Matemáticas soviéticas - Doklady . 31 : 354–357.
  • Razborov, AA (junio de 1985). "Límites inferiores de la complejidad monótona de la lógica permanente". Notas matemáticas de la Academia de Ciencias de la URSS . 37 (6): 485–493. doi : 10.1007 / BF01157687 .
  • Разборов, Александр Александрович (1987). О системах уравнений в свободной группе (PDF) (en ruso). Московский государственный университет . (Tesis doctoral. 32.56MB)
  • Razborov, AA (abril de 1987). "Límites inferiores en el tamaño de los circuitos de profundidad acotada sobre una base completa con adición lógica". Notas matemáticas de la Academia de Ciencias de la URSS . 41 (4): 333–338. doi : 10.1007 / BF01137685 .
  • Razborov, Alexander A. (mayo de 1989). "Sobre el método de aproximaciones" (PDF. 1,41 MB ) . Actas del 21º Simposio Anual de ACM sobre Teoría de la Computación . Seattle , Washington , Estados Unidos. págs. 167-176. doi : 10.1145 / 73007.73023 .
  • Razborov, AA (diciembre de 1990). "Límites inferiores de la complejidad de las funciones booleanas simétricas de los circuitos rectificadores de contacto". Notas matemáticas de la Academia de Ciencias de la URSS . 48 (6): 1226-1234. doi : 10.1007 / BF01240265 .
  • Razborov, Alexander A .; Rudich, Stephen (mayo de 1994). "Pruebas naturales" ( PostScript ) . Actas del 26º Simposio Anual de ACM sobre Teoría de la Computación . Montreal , Quebec , Canadá. págs. 204–213. doi : 10.1145 / 195058.195134 .
  • Razborov, Alexander A. (diciembre de 1998). "Límites inferiores para el cálculo de polinomios" (PostScript) . Complejidad computacional . 7 (4): 291–324. CiteSeerX   10.1.1.19.2441 . doi : 10.1007 / s000370050013 .
  • Razborov, Alexander A. (enero de 2003). "Complejidad de la prueba proposicional" (PostScript) . Revista de la ACM . 50 (1): 80–82. doi : 10.1145 / 602382.602406 . (Documento de encuesta para el 50 aniversario de JACM)

Ver también

Notas

enlaces externos