Alexander Razborov
From Wikipedia, the free encyclopedia
Nombre en ruso
Александр Александрович Разборов
Nacionalidad
Estadounidense, rusa y soviética
Educación
candidato de ciencias en Física y Matemática y doctor en Ciencias Físico-Matemáticas
| Alexander Razborov | ||
|---|---|---|
 | ||
| Información personal | ||
| Nombre en ruso | Александр Александрович Разборов | |
| Nacimiento |
16 de febrero de 1963 (63 años) Belovo (Rusia) | |
| Nacionalidad | Estadounidense, rusa y soviética | |
| Educación | ||
| Educación | candidato de ciencias en Física y Matemática y doctor en Ciencias Físico-Matemáticas | |
| 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, teoría de la computación y matemático | |
| 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.
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). 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)
