Alexander Razborov

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.

• 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]

• 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)

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

• 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.