Aleksandr Aleksandrovich Razborov ( 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 .
Alexander Razborov | |
---|---|
Nació | |
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 |
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
- Premio Nevanlinna (1990) por introducir el "método de aproximación" al probar los límites inferiores del circuito booleano de algunos problemas algorítmicos esenciales , [1]
- Profesor Erdős , Universidad Hebrea de Jerusalén , 1998.
- Miembro correspondiente de la Academia de Ciencias de Rusia (2000) [2] [3]
- Premio David P. Robbins por el trabajo "Sobre la densidad mínima de triángulos en gráficos" (Combinatoria, Probabilidad y Computación 17 (2008), no. 4, 603–618), y por la introducción de un nuevo método poderoso, álgebras de banderas, para resolver problemas en combinatoria extrema
- Premio Gödel (2007, con Steven Rudich ) por el trabajo " Pruebas naturales ". [4] [5]
- Andrew MacLeish Distinguished Service Professor (2008) en el Departamento de Ciencias de la Computación de la Universidad de Chicago .
- Miembro de la Academia Estadounidense de Artes y Ciencias (AAAS) (2020). [6]
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
- Avi Wigderson
- Complejidad del circuito
- Grupo libre
- Pruebas naturales
- Función unidireccional
- Familia de funciones pseudoaleatorias
- Resolución (lógica)
Notas
- ^ "Unión Matemática Internacional: Ganadores del Premio Rolf Nevanlinna" . Archivado desde el original el 17 de diciembre de 2007.
- ^ "Academia de Ciencias de Rusia: Razborov Aleksandr Aleksandrovich: Información general: Historia" .
- ^ "Árbol de agencias de genealogía rusa: R" (en ruso). Archivado desde el original el 21 de diciembre de 2007 . Consultado el 15 de enero de 2008 .
- ^ "Premios y reconocimientos ACM-SIGACT: Premio Gödel 2007" .
- ^ "EATCS: Premio Gödel - 2007" . Archivado desde el original el 1 de diciembre de 2007.
- ^ "Becarios AAAS elegidos" (PDF) . Avisos de la Sociedad Matemática Estadounidense .
enlaces externos
- Alexander Razborov en el Proyecto de genealogía matemática .
- Página de inicio de Alexander Razborov .
- Portal matemático de toda Rusia : Personas: Razborov Alexander Alexandrovich .
- Bosquejo de la biografía en el Instituto Tecnológico de Toyota en Chicago.
- Curricula Vitae en el Departamento de Ciencias de la Computación de la Universidad de Chicago.
- DBLP: Alexander A. Razborov .
- Resultados de Alexander Razborov en la Olimpiada Internacional de Matemáticas
- MathSciNet: "Elementos creados por Razborov, AA" [ enlace muerto permanente ]
- The Work of AA Razborov - un artículo de László Lovász en las Actas del Congreso Internacional de Matemáticos , Kyoto , Japón, 1990.