Alexander Razborov

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

Alexander Razborov
Información personal
Nacimiento	16 de febrero de 1963 (61 años) Belovo (Rusia)
Nacionalidad	Rusa y soviética
Educación
Educado en	MSU Faculty of Mechanics and Mathematics Universidad Estatal de Moscú
Supervisor doctoral	Sergei Adian
Información profesional
Ocupación	Matemático e informático teórico
Área	Teoría de la complejidad computacional y teoría de la computación
Empleador	Instituto Steklov de Matemáticas Universidad de Chicago
Miembro de	Academia de Ciencias de Rusia Academia Europæa (desde 1993) Academia Estadounidense de las Artes y las Ciencias
Sitio web	people.cs.uchicago.edu/~razborov
Distinciones	O'Reilly Open Source Award (1990) Premio Nevanlinna (1990) Premio Gödel (2007) Gödel Lecturer (2010) Premio David Robbins (2013)
[editar datos en Wikidata]

Investigación

En su trabajo más conocido, conjunto con Steven Rudich, introdujo la idea de pruebas naturales, una clase de estrategias usadas para probar cuotas inferiores fundamentales en complejidad computacional. En particular, Razborov y Rudich mostraron que, bajo la suposición que ciertas clases de funciones unidireccionales existen, tales pruebas no pueden aportar una resolución del problema P = NP, por lo que nuevas técnicas serán requeridas para resolver esta cuestión.

Premios

• Premio Nevanlinna (1990) por introducir el "método de aproximación" para probar el cuotas inferiores para circuitos Booleanos en algunos problemas algorítmicos esenciales,^[1]
• Conferencista Erdős , Universidad hebrea de Jerusalén, 1998.
• Miembro correspondiente de la Academia rusa de Ciencias (2000)^[2][3]
• Premio Gödel (2007, con Steven Rudich) por la publicación "Natural Proofs", o Pruebas Naturales.^[4][5]
• Premio David P. Robbins por la publicación “On the minimal density of triangles in graphs” (Combinatorics, Probability and Computing 17 (2008), núm. 4, 603–618), y por introducir un nuevo y potente método, las álgebras de bandera, para solucionar problemas en combinatoria extremal.
• Conferencista Gödel (2010) con la conferencia titulada Complexity of Propositional Proofs (Complejidad de Pruebas Proposicionales).^[6]
• Profesor de servicio distinguido Andrew MacLeish (2008) en el Departamento de Computación en la Universidad de Chicago.
• Miembro de la Academia Americana de Artes y Ciencias (AAAS) (2020).^[7]

Bibliografía

• Razborov, A. A. (1985). «Lower bounds for the monotone complexity of some Boolean functions» (PDF). Soviet Mathematics - Doklady 31: 354-357.
• Razborov, A. A. (June 1985). «Lower bounds on monotone complexity of the logical permanent». Mathematical Notes of the Academy of Sciences of the USSR 37 (6): 485-493. doi:10.1007/BF01157687.
• Разборов, Александр Александрович (1987). (en ruso). Московский государственный университет http://www.mi.ras.ru/~razborov/phd.pdf. Falta el |título= (ayuda) (PhD thesis. 32.56MB)
• Razborov, A. A. (April 1987). «Lower bounds on the size of bounded depth circuits over a complete basis with logical addition». Mathematical Notes of the Academy of Sciences of the USSR 41 (4): 333-338. doi:10.1007/BF01137685.
• (PDF. 1.41MB|formato= requiere |url= (ayuda)). May 1989. pp. 167-176. doi:10.1145/73007.73023. Falta el |título= (ayuda)
• Razborov, A. A. (December 1990). «Lower bounds of the complexity of symmetric boolean functions of contact-rectifier circuits». Mathematical Notes of the Academy of Sciences of the USSR 48 (6): 1226-1234. doi:10.1007/BF01240265.
• (PostScript|formato= requiere |url= (ayuda)). May 1994. pp. 204-213. doi:10.1145/195058.195134. Falta el |título= (ayuda)
• Razborov, Alexander A. (December 1998). «Lower Bounds for the Polynomial Calculus» (PostScript). Computational Complexity 7 (4): 291-324. doi:10.1007/s000370050013.
• Razborov, Alexander A. (January 2003). «Propositional proof complexity» (PostScript). Journal of the ACM 50 (1): 80-82. doi:10.1145/602382.602406. (Survey paper for JACM's 50th anniversary)

Véase también

• Avi Wigderson
• Complejidad de circuito
• Grupo libre
• Pruebas naturales
• Función unidireccional
• Familia de funciones pseudoaleatorias
• Resolución (lógica)

Notas

1. «International Mathematical Union: Rolf Nevanlinna Prize Winners». Archivado desde el original el 17 de diciembre de 2007.
2. «Russian Academy of Sciences: Razborov Aleksandr Aleksandrovich: General info: History».
3. «Russian Genealogy Agencies Tree: R» (en ruso). Archivado desde el original el 21 de diciembre de 2007. Consultado el 15 de enero de 2008.
4. «ACM-SIGACT Awards and Prizes: 2007 Gödel Prize».
5. «EATCS: Gödel Prize - 2007». Archivado desde el original el 1 de diciembre de 2007.
6. «Gödel Lecturers – Association for Symbolic Logic» (en inglés estadounidense). Archivado desde el original el 8 de noviembre de 2021. Consultado el 10 de noviembre de 2021.
7. «AAAS Fellows Elected». Notices of the American Mathematical Society.

Enlaces externos

• Alexander Razborov en el Mathematics Genealogy Project..
• Página Oficial de Alexander Razborov.
• All-Russian Mathematical Portal: Personas: Razborov Alexander Alexandrovich.
• Esbozo de biografía en el Instituto Tecnológico de Toyota en Chicago (TTIC).
• Curricula Vitae En el Departamento de Computación, Universidad de Chicago.
• DBLP: Alexander Un. Razborov.
• Resultados de Alexander Razborov en la Olimpiada Internacional de Matemáticas (IMO) de 1979.
• MathSciNet: "Razborov, A."
• El Trabajo de A. A. Razborov– Un artículo por László Lovász en el Proceedings of the International Congress of Mathematicians, (Congreso Internacional de Matemáticos), Kyoto, Japón, 1990.

• Datos: Q93019