 | Thisbiography of a living personneeds additionalcitations forverification. Please help by addingreliable sources.Contentious material about living persons that is unsourced orpoorly sourcedmust be removed immediately from the article and its talk page, especially if potentiallylibelous. Find sources: "Endre Szemerédi" – news ·newspapers ·books ·scholar ·JSTOR(July 2022) (Learn how and when to remove this message) |
Endre Szemerédi | |
|---|---|
 Szemerédi in 2014 | |
| Born | (1940-08-21)August 21, 1940 (age 85) |
| Education | Eötvös Loránd University (BS) Moscow State University (MS,PhD) |
| Awards | Abel Prize (2012) Széchenyi Prize (2012) Rolf Schock Prizes (2008) Leroy P. Steele Prize (2008) George Pólya Prize (1975) Alfréd Rényi Prize (1973) Member of theNational Academy of Sciences |
| Scientific career | |
| Fields | Combinatorics Computer science Mathematics Theoretical computer science |
| Institutions | Rutgers University |
| Doctoral advisor | Israel Gelfand |
| Doctoral students | Jaikumar Radhakrishnan Gábor N. Sárközy |
Endre Szemerédi (Hungarian:[ˈɛndrɛˈsɛmɛreːdi]; born August 21, 1940) is a Hungarian-American[1] mathematician andcomputer scientist, working in the field ofcombinatorics andtheoretical computer science. He has been the State of New Jersey Professor of computer science atRutgers University since 1986. He also holds a professor emeritus status at theAlfréd Rényi Institute of Mathematics of theHungarian Academy of Sciences.
Szemerédi has won prizes in mathematics and science, including theAbel Prize in 2012. He has made a number of discoveries in combinatorics and computer science, includingSzemerédi's theorem, theSzemerédi regularity lemma, theErdős–Szemerédi theorem, theHajnal–Szemerédi theorem and theSzemerédi–Trotter theorem.
Szemerédi was born inBudapest. 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[2] he explained it: "I was not sure I could do work bearing such responsibility.").[3][4][5] He studied at theFaculty of Sciences of theEötvös Loránd University in Budapest and received his PhD fromMoscow State University. His adviser wasIsrael Gelfand.[6] This stemmed from a misspelling, as Szemerédi originally wanted to study withAlexander Gelfond.[3]
Szemerédi has been the State of New Jersey Professor of computer science atRutgers University since 1986. He has held visiting positions atStanford University (1974),McGill University (1980), theUniversity of South Carolina (1981–1983) and theUniversity of Chicago (1985–1986).[7]
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 ofPaul Erdős andPál Turán: if a sequence of natural numbers has positiveupper density then it contains arbitrarily longarithmetic progressions. This is now known asSzemerédi's theorem. One of the lemmas introduced in his proof is now known as theSzemerédi regularity lemma, which has become an important lemma incombinatorics, being used for instance inproperty testing for graphs and in the theory ofgraph limits.
He is also known for theSzemerédi–Trotter theorem inincidence geometry and theHajnal–Szemerédi theorem andRuzsa–Szemerédi problem ingraph theory.Miklós Ajtai and Szemerédi proved thecorners theorem, an important step toward higher-dimensional generalizations of theSzemerédi theorem. With Ajtai andJános Komlós he proved thect2/logt upper bound for theRamsey numberR(3,t), and constructed asorting network of optimal depth. With Ajtai,Václav Chvátal, andMonroe M. Newborn, Szemerédi proved the famouscrossing number inequality, that agraph withn vertices andm edges, wherem > 4n has at leastm3 / 64n2crossings. WithPaul Erdős, he proved theErdős–Szemerédi theorem on the number of sums and products in a finite set. With Wolfgang Paul,Nick Pippenger, andWilliam Trotter, he established a separation betweennondeterministiclinear time anddeterministic linear time,[8] in the spirit of the infamousP versus NP problem.
Szemerédi has won numerous awards and honors for his contribution to mathematics and computer science. A few of them are listed here:
Szemerédi is a corresponding member (1982), and member (1987) of theHungarian Academy of Sciences and a member (2010) of theUnited States National Academy of Sciences.[19] He was elected to theAcademia Europaea in 2022.[16] He is also a member of theInstitute for Advanced Study inPrinceton, New Jersey and a permanent research fellow at theAlfréd Rényi Institute of Mathematics in Budapest. He was the Fairchild Distinguished Scholar at theCalifornia Institute of Technology in 1987–88.He is an honorary doctor[20] ofCharles University in Prague.He was the lecturer in the Forty-Seventh Annual DeLong Lecture Series[21] at theUniversity of Colorado. He is also a recipient of the Aisenstadt Chair at CRM,[22]University of Montreal. In 2008 he was the Eisenbud Professor at theMathematical Sciences Research Institute inBerkeley, California.
In 2012, Szemerédi was awarded theAbel Prize "for his fundamental contributions to discrete mathematics and theoretical computer science, and in recognition of the profound and lasting impact of these contributions onadditive number theory andergodic theory"[23] 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 asGeorge Pólya who emphasized a problem-solving approach to mathematics.[24] 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.[25]
On August 2–7, 2010, theAlfréd Rényi Institute of Mathematics and theJános Bolyai Mathematical Society organized a conference in honor of the 70th birthday of Endre Szemerédi.[26]
Prior to the conference a volume of the Bolyai Society Mathematical Studies Series,An Irregular Mind, a collection of papers edited byImre Bárány andJózsef Solymosi, was published to celebrate Szemerédi's achievements on the occasion of his 70th birthday.[27] Another conference devoted to celebrating Szemerédi's work isthe Third Abel Conference: A Mathematical Celebration of Endre Szemerédi.[28]
Szemerédi is married to Anna Kepes; they have five children, Andrea, Anita, Peter, Kati, and Zsuzsi.[21][29]
| International | |
|---|---|
| National | |
| Academics | |
| People | |
| Other | |
