Research Laboratory - Theory Laboratory
The basic purpose of research in foundation of computing is to classify computing problems according to the amount of resources (mainly time and memory) required. Such an investigation is naturally divided into two categories: On the one hand, obtaining algorithms that solve a problem within some time and using some memory. Alternatively, one may prove a certain problem cannot be computed without using some amount of time or memory, that is, show that the problem is efficiently unsolvable.
Very little has been achieved so far with regards to showing a problem being efficiently unsolvable. In fact, the most fundamental open problem of computer science, as to whether an entire class of problems - referred to as the class NP - has an efficient solution, is wide open. To date, no efficient algorithm is known for many problems in this class, nor is there a proof showing those problems to be efficiently unsolvable.
Most of the open problems in the field belong both to computer science and combinatorics, and it is therefore fitting that researchers of the lab pursue research in both fields. The lab's goals are to improve known algorithms for computing problems, or, alternatively, show that they are computationally hard.
The lab is supervised by: Prof. Noga Alon, Prof. Yossi Azar, Prof. Ran Canetti, Dr. Shiri Chechik, Prof. Amos Fiat, Prof. Iftach Haitner, Prof. Haim Kaplan, Prof. Yishay Mansour, Dr. Rotem Oshman, Prof. Ronit Rubinfeld, Prof. Shmuel Safra, Prof. Amir Shpilka, Prof. Amnon Ta-Shma and Prof. Uri Zwick.
