Aleksandr Aleksandrovich Razborov (russian: Алекса́ндр Алекса́ндрович Разбо́ров; born February 16, 1963), sometimes known as Sasha Razborov, is a

Soviet The Soviet Union,. officially the Union of Soviet Socialist Republics. (USSR),. was a transcontinental country that spanned much of Eurasia from 1922 to 1991. A flagship communist state, it was nominally a federal union of fifteen nation ...

and Russian

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...

and

computational theorist In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree (e.g., ...

. He is Andrew McLeish Distinguished Service Professor at the

University of Chicago The University of Chicago (UChicago, Chicago, U of C, or UChi) is a private research university in Chicago, Illinois. Its main campus is located in Chicago's Hyde Park neighborhood. The University of Chicago is consistently ranked among the b ...

Research

In his best known work, joint with

Steven Rudich Steven Rudich (born October 4, 1961) is a professor in the Carnegie Mellon School of Computer Science. In 1994, he and Alexander Razborov proved that a large class of combinatorial arguments, dubbed natural proofs, was unlikely to answer many of ...

, he introduced the notion of ''

natural proofs In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one. While these proofs are in some sense "natural", it can be shown (assuming a widely believed conjecture o ...

'', a class of strategies used to prove fundamental lower bounds in computational complexity. In particular, Razborov and Rudich showed that, under the assumption that certain kinds of

one-way function In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here, "easy" and "hard" are to be understood in the sense of computational complexity theory, s ...

s exist, such proofs cannot give a resolution of the

P = NP The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved. The informal term ''quickly'', used abov ...

problem, so new techniques will be required in order to solve this question.

Awards

Nevanlinna Prize The IMU Abacus Medal, known before 2022 as the Rolf Nevanlinna Prize, is awarded once every four years at the International Congress of Mathematicians, hosted by the International Mathematical Union (IMU), for outstanding contributions in Mathemati ...

(1990) for introducing the "approximation method" in proving

Boolean circuit In computational complexity theory and circuit complexity, a Boolean circuit is a mathematical model for combinational digital logic circuits. A formal language can be decided by a family of Boolean circuits, one circuit for each possible inp ...

lower bound In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of . Dually, a lower bound or minorant of is defined to be an eleme ...

s of some essential

algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algorithms are used as specificat ...

ic problems, * Erdős Lecturer, Hebrew University of Jerusalem, 1998. * Corresponding member of the

Russian Academy of Sciences The Russian Academy of Sciences (RAS; russian: Росси́йская акаде́мия нау́к (РАН) ''Rossíyskaya akadémiya naúk'') consists of the national academy of Russia; a network of scientific research institutes from across ...

(2000) *

Gödel Prize The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interes ...

(2007, with

) for the paper "

Natural Proof In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one. While these proofs are in some sense "natural", it can be shown (assuming a widely believed conjecture o ...

s." * David P. Robbins Prize for the paper "On the minimal density of triangles in graphs" (Combinatorics, Probability and Computing 17 (2008), no. 4, 603–618), and for introducing a new powerful method, flag algebras, to solve problems in extremal combinatorics *

Gödel Lecture The Gödel Lecture is an honor in mathematical logic given by the Association for Symbolic Logic, associated with an annual lecture at the association's general meeting. The award is named after Kurt Gödel and has been given annually since 1990. ...

r (2010) with the lecture titled ''Complexity of Propositional Proofs.'' *

Andrew MacLeish Andrew MacLeish (26 June 1838 – 14 January 1928) was a Scottish and American businessman. Life and career MacLeish was born in Glasgow, Scotland, to Agnes (Lindsay) and Archibald MacLeish. He received his education at the Glasgow Normal Academy, ...

Distinguished Service Professor (2008) in the Department of Computer Science,

. * Fellow of the American Academy of Arts and Sciences (AAAS) (2020).

Bibliography

* * * (PhD thesis. 32.56MB) * * * * * * (Survey paper for JACM's 50th anniversary)

Notes

External links

*.
Alexander Razborov's Home Page
*

All-Russian Mathematical Portal The All-Russian Mathematical Portal (better known as Math-Net.Ru) is a web portal that provides extensive access to all aspects of Russian mathematics, including journals, organizations, conferences, articles, videos, libraries, software, and people ...

: Persons
Razborov Alexander Alexandrovich

Biography sketch
in the Toyota Technological Institute at Chicago.
Curricula Vitae
at the Department of Computer Science, University of Chicago.

*

* ttps://web.archive.org/web/20100826170652/http://www.mathunion.org/o/General/Prizes/Nevanlinna/1990/Razborov/page1.html The Work of A.A. Razborov– an article by

László Lovász László Lovász (; born March 9, 1948) is a Hungarian mathematician and professor emeritus at Eötvös Loránd University, best known for his work in combinatorics, for which he was awarded the 2021 Abel Prize jointly with Avi Wigderson. He wa ...

in the ''Proceedings of the

International Congress of Mathematicians The International Congress of Mathematicians (ICM) is the largest conference for the topic of mathematics. It meets once every four years, hosted by the International Mathematical Union (IMU). The Fields Medals, the Nevanlinna Prize (to be rename ...

'',

Kyoto Kyoto (; Japanese language, Japanese: , ''Kyōto'' ), officially , is the capital city of Kyoto Prefecture in Japan. Located in the Kansai region on the island of Honshu, Kyoto forms a part of the Keihanshin, Keihanshin metropolitan area along wi ...

, Japan, 1990. {{DEFAULTSORT:Razborov, Alexander 1963 births 20th-century Russian mathematicians 21st-century Russian mathematicians Gödel Prize laureates Nevanlinna Prize laureates Living people Corresponding Members of the Russian Academy of Sciences Moscow State University alumni Russian computer scientists Soviet computer scientists Soviet mathematicians Theoretical computer scientists International Mathematical Olympiad participants Tarski lecturers Fellows of the American Academy of Arts and Sciences Gödel Lecturers

Research

Awards

Bibliography

See also

Notes

External links