Ran Raz

Ran Raz
Name	Ran Raz
Native name	רן רז
Birth date	1966
Birth place	Israel
Fields	Computer science, Computational complexity, Cryptography, Proof complexity
Workplaces	Princeton University; Weizmann Institute of Science; Rutgers University; Microsoft Research
Alma mater	Hebrew University of Jerusalem; Massachusetts Institute of Technology
Doctoral advisor	Robert Tarjan
Known for	Proof complexity, Interactive proofs, Probabilistically checkable proofs

Ran Raz is an Israeli theoretical computer scientist noted for contributions to computational complexity theory, cryptography, and proof complexity. He has held faculty positions at several leading institutions and produced influential results on interactive proofs, communication complexity, and probabilistically checkable proofs. His work bridges foundational aspects of NP, hardness of approximation, and cryptographic protocols, influencing research in complexity theory and theoretical cryptography.

Early life and education

Raz was born in Israel and completed his undergraduate studies at the Hebrew University of Jerusalem. He earned his Ph.D. at the Massachusetts Institute of Technology under the supervision of Robert Tarjan, where his dissertation addressed questions in randomized algorithms and complexity theory. During his doctoral and early postdoctoral years he interacted with researchers at institutions such as Princeton University, IBM Research, and Microsoft Research, situating him within networks that include scholars working on the P versus NP problem, interactive proof systems, and circuit complexity.

Academic career

Raz served on the faculty of the Weizmann Institute of Science before moving to the United States, where he held positions at Rutgers University and later at Princeton University. He has been affiliated with industrial research labs including Microsoft Research during sabbaticals and collaborations. Raz has participated in program committees for major conferences such as the ACM Symposium on Theory of Computing and the IEEE Symposium on Foundations of Computer Science, and has delivered invited talks at gatherings including the International Colloquium on Automata, Languages and Programming and the Conference on Computational Complexity.

Research contributions

Raz’s research spans multiple core topics in theoretical computer science. He established lower bounds in communication complexity and circuit complexity, proving limitations for various models of computation and influencing understanding of the P versus NP problem. His work on probabilistically checkable proofs (PCPs) contributed to hardness of approximation results related to optimization problems exemplified by interactions with results on the Unique Games Conjecture and inapproximability of problems such as MAX-CUT and Vertex Cover. Raz made foundational contributions to interactive proofs and multi-prover interactive proofs, connecting them to PCPs and to the classification of complexity classes like NP and MIP.

In cryptography, Raz analyzed the security of primitives under information-theoretic and computational assumptions, engaging with notions such as zero-knowledge proofs and randomness extractors tied to the study of pseudorandomness. His work on extractors and randomness-efficient protocols interacts with research by scholars at MIT, UC Berkeley, and Stanford University on derandomization and explicit constructions. Raz has collaborated with researchers who contributed to major frameworks including the Adleman–Manders theorem and results on circuit lower bounds.

Raz also produced influential papers in proof complexity, deriving bounds on proof systems and establishing separations that inform constraints on automated theorem proving tools used in verification pipelines at institutions like Google Research and Amazon Web Services for formal methods. His research has been cited across literature concerning approximation algorithms and hardness reductions originating in work at Cornell University and Columbia University.

Awards and honors

Raz has received recognition from the theoretical computer science community, including invited presentations at flagship conferences such as the International Congress of Mathematicians satellite events and named lectures at universities. His papers have been awarded best paper distinctions and have been influential in shaping award-winning lines of work tied to recipients of accolades from organizations such as the Association for Computing Machinery and the European Association for Theoretical Computer Science.

Selected publications

- Raz, R., "A parallel repetition theorem", Publications in proceedings of the IEEE Symposium on Foundations of Computer Science and journal versions addressing amplification in interactive proofs. - Raz, R., and Safra, S., papers on PCP constructions and hardness of approximation with conference appearances at the ACM Symposium on Theory of Computing. - Raz, R., works on communication complexity and circuit lower bounds published in venues including the Journal of the ACM and conference proceedings of the Conference on Computational Complexity. - Selected collaborations with researchers from Princeton University and Weizmann Institute of Science on extractors, pseudorandomness, and proof complexity.

Teaching and mentorship

At faculty positions in institutions such as Weizmann Institute of Science, Rutgers University, and Princeton University, Raz has taught undergraduate and graduate courses on algorithms, complexity theory, and cryptography. He has supervised doctoral students who went on to academic and industrial research roles at organizations including Microsoft Research, Google Research, and various university departments. Raz’s mentorship emphasizes rigorous problem formulation, connections between combinatorics and computation, and engagement with the broader theoretical community through conferences like the Symposium on Theory of Computing and workshops hosted by DIMACS.

Category:Theoretical computer scientists Category:Israeli computer scientists