Theory of Computation

Theory of Computation (TOC) is the rigorous study of computation, and is thus part of both computer science and mathematics. It seeks to understand computational phenomena, be it natural, man-made or imaginative, and to use this understanding towards the design of more efficient computational processes. Efficiency refers to the use of resources, which typically include computation time and space. Research in TOC has been extremely productive in the few decades of its existence, and its momentum is growing continuously. This research and its dissemination through education and interaction have been responsible for enormous technological progress

The current research activities of the TOC group at Weizmann spans diverse areas within TOC, including Algorithmic Game Theory, Algorithmic Fairness, Approximation Algorithms, Computational Complexity, Cryptography, Distributed Computing, Fine-Grained Complexity, Graph Algorithms, Probabilistic Proof Systems, Property Testing, Pseudorandomness, Randomized Algorithms, Quantum Computation, and Streaming Algorithms.

Over the years, Weizmann researchers have made fundamental contributions to Cryptography, Computational Complexity, and Algorithms. Contributions to Cryptography include the RSA public-key cryptosystem, providing sound foundations for the area at large, the introduction and construction of zero-knowledge proofs, the construction of secure multi-party computations, and the construction of fully homomorphic encryption schemes.

Contributions to Computational Complexity include the introduction of interactive proof systems and characterization of their power (i.e., IP=PSPACE), the introduction and construction of probabilistically checkable proofs (PCP), the introduction and construction of doubly-efficient interactive proofs (aka delegation schemes), and the study of various notions of pseudorandom generators, derandomization and randomness extraction. In addition, significant contributions were made to the study of Property Testing, Circuit Lower Bounds, Fine-Grained Complexity, and Quantum Computation.

Contributions to Algorithms include the design of sparse representation of graphs, designing approximation algorithms for central graph parameters, algorithmic characterizing low-dimensional metric spaces, new bounds on diameter-reducing shortcuts in graphs, and fast algorithms for maximum-flow between all pairs in a graph. In addition, faculty members contributed to the study of Distributed Computing, Machine Learning, Algorithmic Game Theory, Differential Privacy, and Algorithmic Fairness.

Recurring seminars and meetings

Foundations of Computer Science Seminar: This seminar mainly features international speakers. It takes place irregularly.
TheoryLunch meeting: This extended format of a group meeting combines an informal presentation (of 30 minutes) and a social meeting over lunch. It usually takes place every 1-2 weeks.