György Elekes
Encyclopedia
György Elekes was a mathematician
and computer scientist
who specialized in Combinatorial geometry and Combinatorial set theory. He may be best known for his work in the field that would eventually be called Additive Combinatorics
. Particularly notable was his "ingenious" application of the Szemerédi–Trotter theorem
to improve the best known lower bound for the sum-product problem. He also proved that any polynomial-time algorithm approximating the volume
of convex bodies
must have a multiplicative error
, and the error grows exponentially
on the dimension. With Micha Sharir
he set up a framework which eventually led Guth
and Katz to the solution of the Erdős distinct distances problem
.
, which is known for its excellence, especially in mathematics), Elekes studied mathematics at the Eötvös Loránd University. Upon completing his degree, he joined the faculty in the Department of Analysis
at the university. In 1984, he joined the newly forming Department of Computer Science
, which was being headed by László Lovász
. Elekes was promoted to full professor in 2005. He received the Doctor of Mathematical Sciences
title from the Hungarian Academy of Sciences
in 2001.
and Hajnal
. One of his results states that if the set of infinite subsets of the set of natural numbers is split into countably many parts, then in one of them, there is a solution of the equation A∪B=C. His interest later switched to another favorite topic of Erdős, discrete geometry
and geometric algorithm theory
. In 1986 he proved that if a deterministic polynomial algorithm computes a number V(K) for every convex body K in any Euclidean space given by a separation oracle such that V(K) always at least vol(K), the volume of K, then for every large enough dimension n, there is a convex body in the n-dimensional Euclidean space such that V(K)>20.99nvol(K). That is, any polynomial-time estimate the volume of K must be inaccurate by at least an exponential factor.
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 computer scientist
Computer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
who specialized in Combinatorial geometry and Combinatorial set theory. He may be best known for his work in the field that would eventually be called Additive Combinatorics
Additive number theory
In number theory, the specialty additive number theory studies subsets of integers and their behavior under addition. More abstractly, the field of "additive number theory" includes the study of Abelian groups and commutative semigroups with an operation of addition. Additive number theory has...
. Particularly notable was his "ingenious" application of the Szemerédi–Trotter theorem
Szemerédi–Trotter theorem
The Szemerédi–Trotter theorem is a mathematical result in the field of combinatorial geometry. It asserts that given n points and m lines in the plane,the number of incidences The Szemerédi–Trotter theorem is a mathematical result in the field of combinatorial geometry. It asserts that given n...
to improve the best known lower bound for the sum-product problem. He also proved that any polynomial-time algorithm approximating the volume
Volume
Volume is the quantity of three-dimensional space enclosed by some closed boundary, for example, the space that a substance or shape occupies or contains....
of convex bodies
Convex body
In mathematics, a convex body in n-dimensional Euclidean space Rn is a compact convex set with non-empty interior.A convex body K is called symmetric if it is centrally symmetric with respect to the origin, i.e. a point x lies in K if and only if its antipode, −x, also lies in K...
must have a multiplicative error
Numerical stability
In the mathematical subfield of numerical analysis, numerical stability is a desirable property of numerical algorithms. The precise definition of stability depends on the context, but it is related to the accuracy of the algorithm....
, and the error grows exponentially
Exponential growth
Exponential growth occurs when the growth rate of a mathematical function is proportional to the function's current value...
on the dimension. With Micha Sharir
Micha Sharir
Micha Sharir is a professor of computer science at Tel Aviv University, known for his work in computational geometry.After completing his undergraduate studies at Tel Aviv University in 1970, Sharir received a Ph.D. in mathematics from Tel Aviv in 1976 under the supervision of Aldo Lazar...
he set up a framework which eventually led Guth
Larry Guth
Lawrence David Guth is professor of mathematics at the Courant Institute.Guth received his Ph.D. in 2005 from the Massachusetts Institute of Technology under the supervision of Tomasz Mrowka. He won an Alfred P. Sloan Fellowship in . He also was invited speaker at the International Congress of...
and Katz to the solution of the Erdős distinct distances problem
Erdős distinct distances problem
In discrete geometry, the Erdős distinct distances problem states that between distinct points on a plane there are at least distinct distances. It was posed by Paul Erdős in 1946. In a 2010 preprint, Larry Guth and Nets Hawk Katz announced a solution....
.
Life
After graduating from the mathematics program at Fazekas Mihály Gimnázium (i.e., "Fazekas Mihály high school" in BudapestBudapest
Budapest is the capital of Hungary. As the largest city of Hungary, it is the country's principal political, cultural, commercial, industrial, and transportation centre. In 2011, Budapest had 1,733,685 inhabitants, down from its 1989 peak of 2,113,645 due to suburbanization. The Budapest Commuter...
, which is known for its excellence, especially in mathematics), Elekes studied mathematics at the Eötvös Loránd University. Upon completing his degree, he joined the faculty in the Department of Analysis
Mathematical analysis
Mathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of infinitesimal calculus. It is a branch of pure mathematics that includes the theories of differentiation, integration and measure, limits, infinite series, and analytic functions...
at the university. In 1984, he joined the newly forming Department of Computer Science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, which was being headed by László Lovász
László Lovász
Lá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....
. Elekes was promoted to full professor in 2005. He received the Doctor of Mathematical Sciences
Doktor nauk
Doktor nauk is a higher doctoral degree, the second and the highest post-graduate academic degree in the Soviet Union, Russia and in many post-Soviet states. Sometimes referred to as Dr. Hab. The prerequisite is the first degree, Kandidat nauk which is informally regarded equivalent to Ph.D....
title from the Hungarian Academy of Sciences
Hungarian Academy of Sciences
The Hungarian Academy of Sciences is the most important and prestigious learned society of Hungary. Its seat is at the bank of the Danube in Budapest.-History:...
in 2001.
Work
Elekes started his mathematical work in combinatorial set theory, answering some questions posed by ErdősPaul Erdos
Paul Erdős was a Hungarian mathematician. Erdős published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory...
and Hajnal
András Hajnal
András Hajnal is an emeritus professor of mathematics at Rutgers University and a member of the Hungarian Academy of Sciences known for his work in set theory and combinatorics.-Biography:Hajnal was born on 13 May 1931, in Hungary....
. One of his results states that if the set of infinite subsets of the set of natural numbers is split into countably many parts, then in one of them, there is a solution of the equation A∪B=C. His interest later switched to another favorite topic of Erdős, discrete geometry
Discrete geometry
Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles,...
and geometric algorithm theory
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
. In 1986 he proved that if a deterministic polynomial algorithm computes a number V(K) for every convex body K in any Euclidean space given by a separation oracle such that V(K) always at least vol(K), the volume of K, then for every large enough dimension n, there is a convex body in the n-dimensional Euclidean space such that V(K)>20.99nvol(K). That is, any polynomial-time estimate the volume of K must be inaccurate by at least an exponential factor.