Alexander Razborov
| 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 |
| |
| 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 | ||
| Miembro de | ||
| Sitio web | people.cs.uchicago.edu/~razborov | |
| Distinciones |
| |
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.
Investigación[editar]
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[editar]
- 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[editar]
- 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). 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). 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[editar]
- Avi Wigderson
- Complejidad de circuito
- Grupo libre
- Pruebas naturales
- Función unidireccional
- Familia de funciones pseudoaleatorias
- Resolución (lógica)
Notas[editar]
- ↑ «International Mathematical Union: Rolf Nevanlinna Prize Winners». Archivado desde el original el 17 de diciembre de 2007.
- ↑ «Russian Academy of Sciences: Razborov Aleksandr Aleksandrovich: General info: History».
- ↑ «Russian Genealogy Agencies Tree: R» (en ruso). Archivado desde el original el 21 de diciembre de 2007. Consultado el 15 de enero de 2008.
- ↑ «ACM-SIGACT Awards and Prizes: 2007 Gödel Prize».
- ↑ «EATCS: Gödel Prize - 2007». Archivado desde el original el 1 de diciembre de 2007.
- ↑ «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.
- ↑ «AAAS Fellows Elected». Notices of the American Mathematical Society.
Enlaces externos[editar]
- 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
Categorías:
- Hombres
- Nacidos en 1963
- Miembros de la Academia Estadounidense de las Artes y las Ciencias
- Informáticos teóricos
- Matemáticos de la Unión Soviética
- Informáticos de la Unión Soviética
- Informáticos de Rusia
- Alumnado de la Universidad Estatal de Moscú
- Premio Gödel
- Matemáticos de Rusia del siglo XXI
- Matemáticos de Rusia del siglo XX