Endre Szemerédi (; born August 21, 1940) is a Hungarian-American mathematician and

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (a ...

, working in the field of

combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...

and

theoretical computer science computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the ...

. He has been the State of New Jersey Professor of computer science at

Rutgers University Rutgers University (; RU), officially Rutgers, The State University of New Jersey, is a public land-grant research university consisting of four campuses in New Jersey. Chartered in 1766, Rutgers was originally called Queen's College, and was ...

since 1986. He also holds a professor emeritus status at the

Alfréd Rényi Institute of Mathematics The Alfréd Rényi Institute of Mathematics ( hu, Rényi Alfréd Matematikai Kutatóintézet) is the research institute in mathematics of the Hungarian Academy of Sciences. It was created in 1950 by Alfréd Rényi, who directed it until his death ...

of the

Hungarian Academy of Sciences The Hungarian Academy of Sciences ( hu, Magyar Tudományos Akadémia, MTA) is the most important and prestigious learned society of Hungary. Its seat is at the bank of the Danube in Budapest, between Széchenyi rakpart and Akadémia utca. Its ma ...

. Szemerédi has won prizes in mathematics and science, including the

Abel Prize The Abel Prize ( ; no, Abelprisen ) is awarded annually by the King of Norway to one or more outstanding mathematicians. It is named after the Norwegian mathematician Niels Henrik Abel (1802–1829) and directly modeled after the Nobel Pri ...

in 2012. He has made a number of discoveries in combinatorics and computer science, including

Szemerédi's theorem In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers ''A'' with positive natural density contains a ''k''-ter ...

, the

Szemerédi regularity lemma Szemerédi's regularity lemma is one of the most powerful tools in extremal graph theory, particularly in the study of large dense graphs. It states that the vertices of every large enough graph can be partitioned into a bounded number of parts so ...

, the

Erdős–Szemerédi theorem In arithmetic combinatorics, the Erdős–Szemerédi theorem states that for every finite set A of integers, at least one of A+A, the set of pairwise sums or A\cdot A, the set of pairwise products form a significantly larger set. More precisely, t ...

, the

Hajnal–Szemerédi theorem In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that *No two adjacent vertices have the same color, and *The numbers of vertices in any two color class ...

and the Szemerédi–Trotter theorem.

Early life

Szemerédi was born in

Budapest Budapest (, ; ) is the capital and most populous city of Hungary. It is the ninth-largest city in the European Union by population within city limits and the second-largest city on the Danube river; the city has an estimated population o ...

. Since his parents wished him to become a doctor, Szemerédi enrolled at a college of medicine, but he dropped out after six months (in an interview he explained it: "I was not sure I could do work bearing such responsibility."). He studied at the Faculty of Sciences of the

Eötvös Loránd University Eötvös Loránd University ( hu, Eötvös Loránd Tudományegyetem, ELTE) is a Hungarian public research university based in Budapest. Founded in 1635, ELTE is one of the largest and most prestigious public higher education institutions in Hung ...

in Budapest and received his PhD from

Moscow State University M. V. Lomonosov Moscow State University (MSU; russian: Московский государственный университет имени М. В. Ломоносова) is a public research university in Moscow, Russia and the most prestigious ...

. His adviser was

Israel Gelfand Israel Moiseevich Gelfand, also written Israïl Moyseyovich Gel'fand, or Izrail M. Gelfand ( yi, ישראל געלפֿאַנד, russian: Изра́иль Моисе́евич Гельфа́нд, uk, Ізраїль Мойсейович Гел� ...

. This stemmed from a misspelling, as Szemerédi originally wanted to study with

Alexander Gelfond Alexander Osipovich Gelfond (russian: Алекса́ндр О́сипович Ге́льфонд; 24 October 1906 – 7 November 1968) was a Soviet mathematician. Gelfond's theorem, also known as the Gelfond-Schneider theorem is named after hi ...

Academic career

Szemerédi has been the State of New Jersey Professor of computer science at

since 1986. He has held visiting positions at

Stanford University Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is conside ...

(1974),

McGill University McGill University (french: link=no, Université McGill) is an English-language public research university located in Montreal, Quebec, Canada. Founded in 1821 by royal charter granted by King George IV,Frost, Stanley Brice. ''McGill Univer ...

(1980), the University of South Carolina (1981–1983) and 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 ...

(1985–1986).

Work

Endre Szemerédi has published over 200 scientific articles in the fields of discrete mathematics, theoretical computer science, arithmetic combinatorics and discrete geometry. He is best known for his proof from 1975 of an old conjecture of

Paul Erdős Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...

and Pál Turán: if a sequence of natural numbers has positive upper density then it contains arbitrarily long

arithmetic progression An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...

s. This is now known as

. One of the lemmas introduced in his proof is now known as the

, which has become an important lemma in

, being used for instance in

property testing In computer science, a property testing algorithm for a decision problem is an algorithm whose query complexity to its input is much smaller than the instance size of the problem. Typically property testing algorithms are used to distinguish if s ...

for graphs and in the theory of graph limits. He is also known for the Szemerédi–Trotter theorem in

incidence geometry In mathematics, incidence geometry is the study of incidence structures. A geometric structure such as the Euclidean plane is a complicated object that involves concepts such as length, angles, continuity, betweenness, and incidence. An ''inciden ...

and the

and

Ruzsa–Szemerédi problem In combinatorial mathematics and extremal graph theory, the Ruzsa–Szemerédi problem or (6,3)-problem asks for the maximum number of edges in a graph in which every edge belongs to a unique triangle. Equivalently it asks for the maximum number ...

graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

Miklós Ajtai Miklós Ajtai (born 2 July 1946) is a computer scientist at the IBM Almaden Research Center, United States. In 2003, he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm (deve ...

and Szemerédi proved the

corners theorem In arithmetic combinatorics, the corners theorem states that for every \varepsilon>0, for large enough N, any set of at least \varepsilon N^2 points in the N\times N grid \^2 contains a corner, i.e., a triple of points of the form \ with h\ne 0. It ...

, an important step toward higher-dimensional generalizations of the Szemerédi theorem. With Ajtai and János Komlós he proved the ''ct''²/log ''t'' upper bound for the

Ramsey number In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours ( ...

''R''(3,''t''), and constructed a sorting network of optimal depth. With Ajtai,

Václav Chvátal Václav (Vašek) Chvátal () is a Professor Emeritus in the Department of Computer Science and Software Engineering at Concordia University in Montreal, Quebec, Canada and a Visiting Professor at Charles University in Prague. He has published ext ...

, and Monroe M. Newborn, Szemerédi proved the famous Crossing Lemma, that a

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discre ...

with ''n'' vertices and ''m'' edges, where has at least crossings. With

, he proved the

on the number of sums and products in a finite set. With Wolfgang Paul, Nick Pippenger, and William Trotter, he established a separation between nondeterministic

linear time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

and

deterministic Determinism is a philosophical view, where all events are determined completely by previously existing causes. Deterministic theories throughout the history of philosophy have developed from diverse and sometimes overlapping motives and cons ...

linear time, in the spirit of the infamous

P versus NP problem 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 above ...

Awards and honors

Szemerédi has won numerous awards and honors for his contribution to mathematics and computer science. A few of them are listed here: * Honorary

John von Neumann Professor John is a common English name and surname: * John (given name) * John (surname) John may also refer to: New Testament Works * Gospel of John, a title often shortened to John * First Epistle of John, often shortened to 1 John * Second E ...

(2021) Recipients are listed on Budapest University of Technology and Economics website: * Grünwald Prize (1967) * Grünwald Prize (1968) * Rényi Prize (1973) *

George Pólya Prize The Society for Industrial and Applied Mathematics (SIAM) has three prizes named after George Pólya: the George Pólya Prize for Mathematical Exposition, established in 2013; the George Pólya Prize in Applied Combinatorics, established in 1969, ...

for Achievement in Applied Combinatorics (SIAM), (1975) * Prize of the Hungarian Academy of Sciences (1979) * State of New Jersey Professorship (1986) * The Leroy P. Steele Prize for Seminal Contribution to Research (AMS), (2008) * The Rolf Schock Prize in Mathematics for deep and pioneering work from 1975 on arithmetic progressions in subsets of the integers (2008) * The Széchenyi Prize of the Hungarian Republic for his many fundamental contributions to mathematics and computer science (2012) * The

for his fundamental contributions to discrete mathematics and theoretical computer science (2012) *

Hungarian Order of Saint Stephen The Hungarian Order of Saint Stephen ( Hungarian: ''Magyar Szent István Rend'') is the highest state honour bestowed by the President of Hungary. The order is made up of one grade which is "Grand Cross". History The order's origins can be t ...

(2020) Szemerédi is a corresponding member (1982), and member (1987) of the

and a member (2010) of the

National Academy of Sciences The National Academy of Sciences (NAS) is a United States nonprofit, non-governmental organization. NAS is part of the National Academies of Sciences, Engineering, and Medicine, along with the National Academy of Engineering (NAE) and the Nat ...

. He is also a member of the

Institute for Advanced Study The Institute for Advanced Study (IAS), located in Princeton, New Jersey, in the United States, is an independent center for theoretical research and intellectual inquiry. It has served as the academic home of internationally preeminent schola ...

Princeton, New Jersey Princeton is a municipality with a borough form of government in Mercer County, in the U.S. state of New Jersey. It was established on January 1, 2013, through the consolidation of the Borough of Princeton and Princeton Township, both of w ...

and a permanent research fellow at the

in Budapest. He was the Fairchild Distinguished Scholar at the

California Institute of Technology The California Institute of Technology (branded as Caltech or CIT)The university itself only spells its short form as "Caltech"; the institution considers other spellings such a"Cal Tech" and "CalTech" incorrect. The institute is also occasional ...

in 1987–88. He is an honorary doctor of

Charles University ) , image_name = Carolinum_Logo.svg , image_size = 200px , established = , type = Public, Ancient , budget = 8.9 billion CZK , rector = Milena Králíčková , faculty = 4,057 , administrative_staff = 4,026 , students = 51,438 , under ...

in Prague. He was the lecturer in the Forty-Seventh Annual DeLong Lecture SeriesDeLong Lecture Series
Math.colorado.edu. Retrieved on March 22, 2012. at the

University of Colorado The University of Colorado (CU) is a system of public universities in Colorado. It consists of four institutions: University of Colorado Boulder, University of Colorado Colorado Springs, University of Colorado Denver, and the University o ...

. He is also a recipient of the Aisenstadt Chair at CRM,

University of Montreal A university () is an institution of higher (or tertiary) education and research which awards academic degrees in several academic disciplines. Universities typically offer both undergraduate and postgraduate programs. In the United States, th ...

. In 2008 he was the Eisenbud Professor at the

Mathematical Sciences Research Institute The Simons Laufer Mathematical Sciences Institute (SLMath), formerly the Mathematical Sciences Research Institute (MSRI), is an independent nonprofit mathematical research institution on the University of California campus in Berkeley, Calif ...

Berkeley, California Berkeley ( ) is a city on the eastern shore of San Francisco Bay in northern Alameda County, California, United States. It is named after the 18th-century Irish bishop and philosopher George Berkeley. It borders the cities of Oakland and E ...

. In 2012, Szemerédi was awarded the

"for his fundamental contributions to discrete mathematics and theoretical computer science, and in recognition of the profound and lasting impact of these contributions on

additive number theory Additive number theory is the subfield of number theory concerning the study of subsets of integers and their behavior under addition. More abstractly, the field of additive number theory includes the study of abelian groups and commutative semigr ...

and

ergodic theory Ergodic theory ( Greek: ' "work", ' "way") is a branch of mathematics that studies statistical properties of deterministic dynamical systems; it is the study of ergodicity. In this context, statistical properties means properties which are expr ...

" The Abel Prize citation also credited Szemerédi with bringing combinatorics to the centre-stage of mathematics and noted his place in the tradition of Hungarian mathematicians such as

George Pólya George Pólya (; hu, Pólya György, ; December 13, 1887 – September 7, 1985) was a Hungarian mathematician. He was a professor of mathematics from 1914 to 1940 at ETH Zürich and from 1940 to 1953 at Stanford University. He made fundamenta ...

who emphasized a problem-solving approach to mathematics. Szemerédi reacted to the announcement by saying that "It is not my own personal achievement, but recognition for this field of mathematics and Hungarian mathematicians," that gave him the most pleasure.

Conferences

On August 2–7, 2010, the

and the

János Bolyai Mathematical Society The János Bolyai Mathematical Society (Bolyai János Matematikai Társulat, BJMT) is the Hungarian mathematical society, named after János Bolyai, a 19th-century Hungarian mathematician, a co-discoverer of non-Euclidean geometry. It is the profes ...

organized a conference in honor of the 70th birthday of Endre Szemerédi. Prior to the conference a volume of the Bolyai Society Mathematical Studies Series, ''An Irregular Mind'', a collection of papers edited by

Imre Bárány Imre Bárány (Mátyásföld, Budapest, 7 December 1947) is a Hungarian mathematician, working in combinatorics and discrete geometry. He works at the Rényi Mathematical Institute of the Hungarian Academy of Sciences, and has a part-time a ...

and

József Solymosi József Solymosi is a Hungarian-Canadian mathematician and a professor of mathematics at the University of British Columbia. His main research interests are arithmetic combinatorics, discrete geometry, graph theory, and combinatorial number theo ...

, was published to celebrate Szemerédi's achievements on the occasion of his 70th birthday. Another conference devoted to celebrating Szemerédi's work is the Third Abel Conference: A Mathematical Celebration of Endre Szemerédi.Third Abel Conference: A Mathematical Celebration of Endre Szemerédi
/ref>

Personal life

Szemerédi is married to Anna Kepes; they have five children, Andrea, Anita, Peter, Kati, and Zsuzsi.

References

External links

Personal Homepage
at the

6,000,000 and Abel Prize
– Numberphile
Interview by Gabor Stockert
(translated from the Hungarian into English by Zsuzsanna Dancso) {{DEFAULTSORT:Szemeredi, Endre 1940 births Living people Institute for Advanced Study visiting scholars Rolf Schock Prize laureates Rutgers University faculty 20th-century Hungarian mathematicians 21st-century Hungarian mathematicians Combinatorialists Theoretical computer scientists American computer scientists American mathematicians Hungarian computer scientists Members of the Hungarian Academy of Sciences Hungarian emigrants to the United States Members of the United States National Academy of Sciences Abel Prize laureates