Alejandro Razborov

matemático ruso

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 Profesor de Servicio Distinguido Andrew McLeish en la Universidad de Chicago .

Investigación

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 pruebas no pueden dar una resolución del problema P = NP , por lo que se necesitarán nuevas técnicas para resolver esta cuestión.

Premios

• Premio Nevanlinna (1990) por introducir el "método de aproximación" para demostrar 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 Gödel (2007, con Steven Rudich ) por el artículo " Natural Proofs ". ^{[4] [5]}
• Premio David P. Robbins por el artículo "Sobre la densidad mínima de triángulos en gráficos" (Combinatoria, Probabilidad y Computación 17 (2008), núm. 4, 603–618), y por introducir un nuevo método poderoso, álgebras de banderas, para resolver problemas en combinatoria extrema
• Gödel Lecturer (2010) con la conferencia titulada Complejidad de las pruebas proposicionales. ^[6]
• Andrew MacLeish Profesor de Servicio Distinguido (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). ^[7]

Bibliografía

• Razborov, AA (1985). "Límites inferiores de 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 lo permanente lógico". Apuntes Matemáticos de la Academia de Ciencias de la URSS . 37 (6): 485–493. doi :10.1007/BF01157687. S2CID  120875831.
• Разборов, Александр Александрович (1987). О системах уравнений в свободной группе (PDF) (en ruso). Universidad de Moscú . (Tesis doctoral. 32,56MB)
• Razborov, AA (abril de 1987). "Límites inferiores del tamaño de circuitos de profundidad acotados sobre una base completa con suma lógica". Apuntes Matemáticos de la Academia de Ciencias de la URSS . 41 (4): 333–338. doi :10.1007/BF01137685. S2CID  121744639.
• Razborov, Alexander A. (mayo de 1989). "Actas del vigésimo primer simposio anual de ACM sobre teoría de la informática - STOC '89". Actas del 21º Simposio Anual ACM sobre Teoría de la Computación . Seattle , Washington , Estados Unidos. págs. 167-176. doi :10.1145/73007.73023. ISBN 0897913078.
• Razborov, AA (diciembre de 1990). "Límites inferiores de la complejidad de funciones booleanas simétricas de circuitos rectificadores de contacto". Apuntes Matemáticos de la Academia de Ciencias de la URSS . 48 (6): 1226-1234. doi :10.1007/BF01240265. S2CID  120703863.
• Razborov, Alexander A.; Rudich, Stephen (mayo de 1994). "Actas del vigésimo sexto simposio anual de ACM sobre teoría de la informática - STOC '94". Actas del 26º Simposio Anual ACM sobre Teoría de la Computación . Montreal , Quebec , Canadá. págs. 204-213. doi :10.1145/195058.195134. ISBN 0897916638.
• Razborov, Alexander A. (diciembre de 1998). "Límites inferiores del cálculo polinómico" (PostScript) . Complejidad computacional . 7 (4): 291–324. CiteSeerX  10.1.1.19.2441 . doi :10.1007/s000370050013. S2CID  8130114.
• 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. S2CID  17351318. (Documento de encuesta para el 50 aniversario de la 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

1. "Unión Matemática Internacional: ganadores del premio Rolf Nevanlinna". Archivado desde el original el 17 de diciembre de 2007.
2. "Academia de Ciencias de Rusia: Razborov Aleksandr Aleksandrovich: Información general: Historia".
3. "Árbol de agencias genealógicas rusas: R" (en ruso). Archivado desde el original el 21 de diciembre de 2007 . Consultado el 15 de enero de 2008 .
4. "Premios y premios ACM-SIGACT: Premio Gödel 2007".
5. "EATCS: Premio Gödel - 2007". Archivado desde el original el 1 de diciembre de 2007.
6. "Profesores de Gödel - Asociación de Lógica Simbólica". Archivado desde el original el 8 de noviembre de 2021 . Consultado el 10 de noviembre de 2021 .
7. "Becarios AAAS elegidos" (PDF) . Avisos de la Sociedad Matemática Estadounidense .

enlaces externos

• Alexander Razborov en el Proyecto Genealogía de Matemáticas .
• Página de inicio de Alexander Razborov.
• Portal matemático de toda Rusia : Personas: Razborov Alexander Alexandrovich.
• Boceto biográfico en el Instituto Tecnológico Toyota de Chicago.
• Curricula Vitae del 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
• El trabajo de AA Razborov: artículo de László Lovász en las Actas del Congreso Internacional de Matemáticos , Kioto , Japón, 1990.