Alexander Razborov
Encyclopedia
Aleksandr Aleksandrovich Razborov , sometimes known as Sasha Razborov, is a Soviet and Russia
n mathematician
and computational theorist who won the Nevanlinna Prize
in 1990 for introducing the "approximation method" in proving Boolean circuit
lower bounds of some essential algorithmic problems, and the Gödel Prize
with Steven Rudich
in 2007 for their paper "Natural Proof
s." His advisor was Sergei Adian
. He was elected as a Corresponding Member of the Russian Academy of Sciences
on May 26, 2000. His Erdős number
is 2. In his best known work, joint with Steven Rudich, he introduced the notion of natural proofs, 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
s exist, such proofs cannot give a resolution of the P = NP problem, so new techniques will be required in order to solve this question. Since 2008, he is the Andrew MacLeish
Distinguished Service Professor in the Department of Computer Science, University of Chicago.
Russia
Russia or , officially known as both Russia and the Russian Federation , is a country in northern Eurasia. It is a federal semi-presidential republic, comprising 83 federal subjects...
n mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
and computational theorist who won the Nevanlinna Prize
Nevanlinna Prize
The Rolf Nevanlinna Prize is awarded once every 4 years at the International Congress of Mathematicians, for outstanding contributions in Mathematical Aspects of Information Sciences including:...
in 1990 for introducing the "approximation method" in proving Boolean circuit
Boolean circuit
A Boolean circuit is a mathematical model of computation used in studying computational complexity theory. Boolean circuits are the main object of study in circuit complexity and are a special kind of circuits; a formal language can be decided by a family of Boolean circuits, one circuit for each...
lower bounds of some essential algorithmic problems, and the Gödel Prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
with Steven Rudich
Steven Rudich
Steven Rudich 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 were unlikely to answer many of the important problems in computational complexity theory. For this work,...
in 2007 for their paper "Natural Proof
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 that no such proof can possibly be used to solve the P vs...
s." His advisor was Sergei Adian
Sergei Adian
Sergei Ivanovich Adian, also Adjan is one of the most prominent Soviet and Russian mathematicians. He is a professor at the Moscow State University. He is most famous for his work in group theory, especially on the Burnside problem.-Biography:...
. He was elected as a Corresponding Member of the Russian Academy of Sciences
Russian Academy of Sciences
The Russian Academy of Sciences consists of the national academy of Russia and a network of scientific research institutes from across the Russian Federation as well as auxiliary scientific and social units like libraries, publishers and hospitals....
on May 26, 2000. His Erdős number
Erdos number
The Erdős number describes the "collaborative distance" between a person and mathematician Paul Erdős, as measured by authorship of mathematical papers.The same principle has been proposed for other eminent persons in other fields.- Overview :...
is 2. In his best known work, joint with Steven Rudich, he introduced the notion of natural proofs, a class of strategies used to prove fundamental lower bounds in computational complexity
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
. In particular, Razborov and Rudich showed that, under the assumption that certain kinds of one-way function
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, specifically the theory of polynomial time problems...
s exist, such proofs cannot give a resolution of the P = NP problem, so new techniques will be required in order to solve this question. Since 2008, he is the Andrew MacLeish
Andrew MacLeish
Andrew MacLeish was born in Glasgow, Scotland to Archibald MacLeish and Agnes Lindsay. He received his education at the Glasgow Normal Academy, Hardy's English Academy and Flint's Commercial Academy. He worked in Glasgow and London in 1855 and 1856. That same year he immigrated to the United...
Distinguished Service Professor in the Department of Computer Science, University of Chicago.
See also
- Avi WigdersonAvi WigdersonAvi Wigderson is an Israeli mathematician and computer scientist, a professor of mathematics at the Institute for Advanced Study in Princeton. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, distributed computing, and neural...
- Circuit complexityCircuit complexityIn theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of Boolean circuits that compute them....
- Free groupFree groupIn mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses...
- Natural proofNatural proofIn 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 that no such proof can possibly be used to solve the P vs...
s - One-way functionOne-way functionIn 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, specifically the theory of polynomial time problems...
- Pseudorandom function family
- Resolution (logic)Resolution (logic)In mathematical logic and automated theorem proving, resolution is a rule of inference leading to a refutation theorem-proving technique for sentences in propositional logic and first-order logic...
External links
.- Alexander Razborov's Home Page.
- All-Russian Mathematical Portal: Persons: Razborov Alexander Alexandrovich.
- Biography sketch in the Toyota Technological Institute at Chicago.
- Curricula Vitae at the Department of Computer Science, University of Chicago.
- DBLP: Alexander A. Razborov.
- MathSciNet: "Items authored by Razborov, A. A."
- The Work of A.A. Razborov – an article by László LovászLászló LovászLászló Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
in the Proceedings of the International Congress of MathematiciansInternational Congress of MathematiciansThe International Congress of Mathematicians is the largest conference for the topic of mathematics. It meets once every four years, hosted by the International Mathematical Union ....
, KyotoKyotois a city in the central part of the island of Honshū, Japan. It has a population close to 1.5 million. Formerly the imperial capital of Japan, it is now the capital of Kyoto Prefecture, as well as a major part of the Osaka-Kobe-Kyoto metropolitan area.-History:...
, JapanJapanJapan is an island nation in East Asia. Located in the Pacific Ocean, it lies to the east of the Sea of Japan, China, North Korea, South Korea and Russia, stretching from the Sea of Okhotsk in the north to the East China Sea and Taiwan in the south...
, 1990.