Budapesten született 1940-ben. Szülei kérésére az orvosi egyetemre iratkozott be, de tanulmányait hamarosan megszakította, majd az Eötvös Loránd Tudományegyetem Természettudományi Karának matematika–fizika szakán szerzett matematika-fizika szakos tanári diplomát. Később a moszkvai Lomonoszov Egyetemen szerzett doktori fokozatot matematikából. A Magyar Tudományos Akadémia Matematikai Kutatóintézetének munkatársa lesz, majd 1980-as évektől különböző amerikai egyetemeken volt vendégkutató, vendégprofesszor. 1990-től a Rutgers Egyetem számítógép-tudományi tanszékének egyetemi tanára. Munkásságát 2012-ben Abel-díjjal ismerték el.
Kutatási területe a számelmélet és algoritmuselmélet. Legjelentősebb eredményét 1975-ben érte el, amikor Erdős Pál és Turán Pál egyik sejtését bizonyította, miszerint minden pozitív felső sűrűségű sorozat tartalmaz tetszőleges hosszú számtani sorozatot. Ehhez fogalmazta meg és igazolta a regularitási lemmát, ami fontos eszközzé vált a nagy gráfok kutatásában. Hajnal Andrással együttműködve bebizonyította Erdős sejtését: ha egy véges gráfban minden pont foka kisebb k-nál, akkor a gráf egyenletesen kiszínezhető k színnel, azaz úgy, hogy a színosztályok mérete legfeljebb 1-gyel tér el egymástól. A számítástudomány területén kiválasztási és rendezési problémákkal foglalkozott. Itteni legnevezetesebb eredménye egy hatékony párhuzamos rendező algoritmus.