Yuri Petrovich Ofman
Encyclopedia
Yuri Petrovich Ofman is a Russian mathematician
who works in computational complexity theory
.
He obtained his Doctorate
from Moscow State University
, where he was advised by Andrey Kolmogorov
. He is the co-author with A. A. Karatsuba
of one of the most important papers in computational complexity theory, which showed that it is possible to multiply two n-digit numbers by an algorithm that uses less than Ω
(n2) elementary operations.
He also did important early work on parallel algorithm
s for prefix sum
s and their application in the design of Boolean circuits for addition
.
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....
who works in computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
.
He obtained his Doctorate
Ph.D.
A Ph.D. is a Doctor of Philosophy, an academic degree.Ph.D. may also refer to:* Ph.D. , a 1980s British group*Piled Higher and Deeper, a web comic strip*PhD: Phantasy Degree, a Korean comic series* PhD Docbook renderer, an XML renderer...
from Moscow State University
Moscow State University
Lomonosov Moscow State University , previously known as Lomonosov University or MSU , is the largest university in Russia. Founded in 1755, it also claims to be one of the oldest university in Russia and to have the tallest educational building in the world. Its current rector is Viktor Sadovnichiy...
, where he was advised by Andrey Kolmogorov
Andrey Kolmogorov
Andrey Nikolaevich Kolmogorov was a Soviet mathematician, preeminent in the 20th century, who advanced various scientific fields, among them probability theory, topology, intuitionistic logic, turbulence, classical mechanics and computational complexity.-Early life:Kolmogorov was born at Tambov...
. He is the co-author with A. A. Karatsuba
Anatolii Alexeevitch Karatsuba
Anatolii Alexeevitch Karatsuba was a Russian mathematician, who authored the first fast multiplication method: the Karatsuba algorithm, a fast procedure for multiplying large numbers.- Studies and work :...
of one of the most important papers in computational complexity theory, which showed that it is possible to multiply two n-digit numbers by an algorithm that uses less than Ω
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n2) elementary operations.
He also did important early work on parallel algorithm
Parallel algorithm
In computer science, a parallel algorithm or concurrent algorithm, as opposed to a traditional sequential algorithm, is an algorithm which can be executed a piece at a time on many different processing devices, and then put back together again at the end to get the correct result.Some algorithms...
s for prefix sum
Prefix sum
In computer science, the prefix sum, or scan, of a sequence of numbers is a second sequence of numbers , the sums of prefixes of the input sequence:-Parallel algorithm:A prefix sum can be calculated in parallel by the following steps....
s and their application in the design of Boolean circuits for addition
Adder (electronics)
In electronics, an adder or summer is a digital circuit that performs addition of numbers.In many computers and other kinds of processors, adders are used not only in the arithmetic logic unit, but also in other parts of the processor, where they are used to calculate addresses, table indices, and...
.
Publications
Translated in- Yu. P. Ofman (1965), A universal automaton. Transactions of the Moscow Mathemathematical Society, vol. 14, pp. 200-215.