Raz, Weinberg Deepen Faculty’s Leadership in Critical Areas

Ran Raz, a global authority on computational complexity theory, and Matthew Weinberg, a rising expert in algorithmic mechanism design, will join the Computer Science Department at the start of the new year, deepening the faculty’s engagement in crucial research areas. Both have ties to Princeton that will make their moves short ones.

Professor Sanjeev Arora described Raz, who will become a full professor, as “the leading expert on computational complexity theory in his generation, worldwide.”

“He has made groundbreaking contributions in understanding fundamental limits on how efficiently certain computations can be performed,” said Arora, the Charles C. Fitzmorris Professor of Computer Science. “The ultimate result in his research area would be a resolution of the ‘P vs NP’ conjecture, and Raz is the leading expert today in efforts building toward it.” [The conjecture, often called the most important unanswered question in theoretical computer science, seeks to nail down exactly what kinds of problems computers can solve and what kinds they can’t.]

“He has also had tremendous impact on advancing our understanding of how well we can compute approximate solutions to NP-hard problems, especially through his parallel repetition theorem. He has also advanced our ability to quantify the amount of communication needed to solve computations where the input is split among various computers, as happens in distributed computing.

Raz’s ties to Princeton’s CS department date back to 1992, when he began a two-year post-doctoral position after receiving his Ph.D. from Hebrew University in Jerusalem, Israel. He was a member of the School of Mathematics at the Institute for Advanced Study from 2000 to 2002, and since 2012 he has been a visiting professor there.

In 1994, Raz joined the faculty of the Weizmann Institute of Science near Tel Aviv as an assistant professor in the Department of Computer Science and Applied Mathematics. He became a full professor in 2003 and has taught graduate courses on Circuit and Communication Complexity, Probabilistically Checkable Proofs, Quantum Computation, and Information Theory and Applications.

His doctoral thesis was titled “Lower Bounds for Probabilistic Communication Complexity and for the Depth of Monotone Boolean Circuits.”

Raz received the Best Paper award at IEEE FOCS 2016 (the IEEE Symposium on Foundations of Computer Science) for his paper “Fast Learning Requires Good Memory: A Time-Space Lower Bound for Parity Learning” and the Best Paper award at STOC 2015 (the ACM Symposium on Theory of Computing) for “Exponential Separation of Information and Communication for Boolean Functions.” One of his two co-authors for the latter paper was Gillat Kol, who also recently joined Princeton’s CS department.

Weinberg, who will become an assistant professor, also is no stranger to Princeton. He has been a postdoctoral researcher and has taught for the CS department’s theory group since earning his Ph.D. in computer science from the Massachusetts Institute of Technology in 2014. His doctoral thesis, titled “Algorithms for Strategic Agents,” won the Doctoral Dissertation Award from SIGecom (ACM’s Special Interest Group on E-commerce) and the George M. Sprowls Award for the best MIT doctoral theses in CS. During the fall semesters of 2015 and 2016, he was a Microsoft research fellow on algorithms and uncertainty at the Simons Institute for the Theory of Computing at the University of California, Berkeley.

Professor Mark Braverman described Weinberg as “a major young expert in the exciting field of algorithmic mechanism design,” the development of algorithms that work in situations where the participants are driven by incentives that are not only distinct but often obscure.

“Traditionally, algorithms have been designed to solve computational problems, such as maintaining databases, or powering a search engine,” Braverman said. “These algorithms are designed to tell machines what to do, and the machines do what they’re expected to do.

“Increasingly complex algorithms are being used to organize the behavior of people, who often act in their own self-interest and not necessarily in expected ways. For example, an Uber customer might reject a ride even though the price is acceptable, in the expectation that a better price may become available. Understanding and bridging the gap in this performance is the key objective of Matt’s work.”

In addition to covering an important area of computer science, Weinberg’s research programs connect broadly on campus, in particular with Princeton’s Center for Information Technology Policy and the Economics Department. He will teach the popular undergraduate class “Economics and Computing” (COS445) in the spring.

— Doug Hulette