Mario Szegedy

Mario Szegedy (born 23 October 1960) is a Hungarian-American computer scientist and a professor of computer science at Rutgers University. He is widely known for his contributions to theoretical computer science, with a strong focus on computational complexity theory and quantum computing.

Szegedy completed his Ph.D. in computer science in 1989 at theUniversity of Chicago. His doctoral dissertation was titledAlgebraic Methods in Lower Bounds for Computational Models, which laid the foundation for his later work in complexity theory. After completing his doctorate, he held a Lady Davis Postdoctoral Fellowship at theHebrew University of Jerusalemduring 1989–1990. He later returned to the University of Chicago as a postdoctoral researcher from 1991 to 1992 and then joined Bell Laboratories in 1992, where he worked until 1999. During this period, he carried out influential research in theoretical computer science. After spending a year at the Institute for Advanced Study in Princeton, he joined Rutgers University, where he became a professor of computer science.

Szegedy’s research spans several areas, including computational complexity theory, quantum computing, computational geometry, and data streaming algorithms. In complexity theory, he is known for key results on the in-approximability of combinatorial optimisation problems, achieved in collaboration with other leading researchers. His work on probabilistically checkable proofs played an important role in shaping modern complexity theory.

Another major contribution of Szegedy is his work on streaming algorithms, especially methods for approximating frequency moments in data streams using very limited memory. These results have had a strong impact on data analysis and large-scale computation. In quantum computing, his research includes quantum algorithms, quantum query complexity, and quantum walks. A well-known quantum walk operator is named after him, reflecting the importance of his contributions to the field. In recent years, his main research focus has beenquantum computing.

Szegedy has received several major awards for his work. He won the Gödel Prize twice, in 2001 and 2005, for his contributions to probabilistically checkable proofs and data stream complexity. In 2019, he received the Paris Kanellakis Theory and Practice Award for his work on streaming algorithms. In 2021, he also received the IEEE Foundations of Computer Science Test of Time Award, together with Uriel Feige, Shafi Goldwasser, László Lovász, and Shmuel Safra, for their work on approximating clique problems.

In January 2018, Szegedy joined theAlibabaQuantum Laboratory, further strengthening his involvement in applied and theoretical quantum research.