Az ELTE matematikus szakán végzett (1976–1981), Frank András tanítványa volt. Egyetemi doktor (1984), a matematikai tudomány kandidátusa (1987, Budapest).
Az Massachusetts Institute of Technology vendégdocense (1987–1989). A Cornell Egyetem adjunktusa illetve docense (1989–1995), majd professzora (1995), 2006 és 2010 között Számításudományi tanszék vezetője, és jelenleg a Számítastudományi tanszék Jacob Gould Schurman professzora valamint a Számítástudományi és Informatikai tanszék helyettes dékánja. A SIAM Journal of Computing főszerkesztője. 2013-ban a Magyar Tudományos Akadémia külső tagjává választották