Research Laboratories

The School's faculty, along with their M.Sc and Ph.D students, conduct extensive and advanced research programs within the framework of a host of research laboratories. A glimpse into the activities of these laboratories provides a good example as to the topics and nature of the research the school excels in.

Experimental research in the School is conducted within the following research laboratories.

Multiprocessor Synchronization Laboratory

With the advent of the Internet, computers are being used more and more as coordination devices, rather than pure computational tools. Due to nature's inherent asynchrony, standard "Turing" notions of computability and complexity do not suffice when setting out to build a mathematical foundation for multi-process coordination. The goal of the research conducted in the Multiprocessor Synchronization Laboratory is to develop the mathematical models and algorithmic tools necessary to make effective multi-process coordination possible. Work in the lab revolves around two axes: the development of new synchronization hardware operations and the creation of highly effective concurrent coordination structures. The two are closely intertwined, a relationship that manifests itself in the way research is conducted in the lab: work continuously revolves around theoretical development of synchronization primitives and their subsequent use in constructing data structures. These in turn are tested on real and simulated multiprocessor machines in the Lab.

The Lab is supervised by: Prof. Yehuda Afek, Prof. Yishay Mansour and Prof. Nir Shavit

Networks and Communication Laboratory

Recent years have seen vast developments in such areas as communication networks and distributed processing systems. The Internet today is a visible part of almost every aspect of our daily life. Heterogeneity of applications, however, translates into a larger number of interacting protocols, service requirements, and traffic patterns. With new technologies coming up rapidly, the researchers need to analyze the performance of these systems. The lab focuses on the study and development of various network protocols and applications, and has focused in the past on ATM (Asynchronous Transfer Mode), a network architecture that can handle a variety of streams, i.e. voice, data, image, text and video in an integrated manner.

In the Communication Networks laboratory at Tel Aviv University's School of Computer Science, advanced network simulators are used to study the behavior of the Internet and other networks. Simulating a communication network is one of the ways to design and analyze communication networks. Practically speaking, the objective of the simulations conducted in the lab is to accelerate the development and testing of new ideas.

Developing buffers, routers, memory management, packet transmission, and designing and analyzing protocols and algorithms for efficient use of computer networks, are important aspects of the research carried out in the lab. Recognizing the problems posed by the communication networks, and, at the same time, comprehending the needs of the users, help the Networks and Communication Lab meet the challenges of this constantly expanding field.

The Lab is supervised by: Prof. Yehuda Afek , Prof. Hanoch Levy and Prof. Yishay Mansour

The Structural Bioinformatics Laboratory

The Structural Bioinformatics Laboratory of the School of Computer Science at Tel Aviv University is engaged in the development of efficient algorithms which should eventually enable computers to automatically predict the biological function of proteins, peptides and drugs and their mutual interactions. The need to introduce advanced Computer Science based techniques into Molecular Biology, Computational Chemistry and Biotechnology became evident a few decades ago. The recent developments in the Human Genome project have forcefully demonstrated the efficacy of state of the art computational techniques to handle the huge quantities of genomic data obtained. The information revealed by this project is one-dimensional and supplies us with long strings of letters representing the composition of genes and their major products - the proteins. However, this is only part of the picture. Biological molecules fold into unique intricate three-dimensional shapes, which enable to predict their activity. The next major step after the Genome project is concentrated in an effort to elucidate and exploit the three-dimensional shapes of the proteins. Analysis of these shapes should supply the next quantum leap in the understanding of molecular function. The Structural Bioinformatics Lab is recognized world wide as one of the leaders in the development of advanced structural protein alignment and protein-protein shape docking algorithms.

By its nature the research is interdisciplinary and is done in full collaboration with the Laboratory of Prof. Ruth Nussinov from the Institute of Molecular Medicine at the Faculty of Medicine. This joint research group was established in 1989 and currently involves about 20 M.Sc. and Ph.D. students, half of whom are from the School of Computer Science and the other half from the Faculty of Medicine. The Lab cooperates with the Computational Biology Laboratory of the National Cancer Institute of the US, the IBM Research Computational Biology center and with Israeli pharmaceutical companies. It is involved in industry-academy consortia sponsored by the Chief Scientist of the Ministry of Industry and trade and has received grants from the Israel Academy of Science, the Ministry of Science and the Binational US-Israel Science foundation. It is part of the Excellence Center for Geometric Computing established in the School of Computer Sciencel by the Israeli National Science Foundation. The principal investigators and the students of the Lab are actively involved in the new undergraduate Bioinformatics program established at Tel Aviv University.

The lab is supervised by: Prof. Haim Wolfson

Databases and Information Systems Laboratory

With the proliferation of database systems, data warehouses, and other forms of information systems, it has become increasingly important to study such systems, and to develop techniques that enable their effective utilization. The Laboratory for Databases and Information Systems is aimed at providing the platform for teaching the relevant tools and at supporting applied and experimental research on these issues.

On the teaching side, the work in the lab is aimed at introducing students to commercial database systems and tools, covering central aspects of such systems, including data models, query languages, database design, optimization, concurrency control, and recovery. The scope of advanced studies and research includes heterogeneous data (data integration and interoperability, semi-structured information), web-based applications, query processing and optimization, and algorithms and data structures for massive data sets.

The lab is supervised by: Prof. Yossi Matias and Prof. Tova Milo.


Robotics, Computer Vision and Geometric Computing

Humans, as well as many other living species, can easily operate within the physical environment that surrounds them: they acquire visual data, they process it into a model that represents the environment, and they use the model to manipulate and to navigate amid the objects present in the scene. In contrast, equipping a computer with similar capabilities is an extremely difficult task, pursued by many researchers for more than three decades. It encompasses the study of Computer Vision, Image Understanding and Object Recognition, and Automatic Task Planning in Robotics and Manufacturing.

It is the charter of the Robotics, Computer Vision and Geometric Computing Lab to study these topics and to develop methodologies and techniques that endow computers with the aforementioned capabilities. The lab, equipped with mobile robots and with state-of-the-art vision systems, conducts applied research, focusing on automatic motion planning in robotics, on object recognition, understanding and tracking in computer vision, and on the development of robust geometric software library (called CGAL) to support the implementation of the techniques developed in these studies.

The lab is supervised by: Prof. Lior Wolf , Prof. Dan Halperin, Prof. Micha Sharir and Prof. Hezy Yeshurun

High-Performance Parallel Computing Laboratory

The laboratory for high-performance computing focuses mainly on the interaction of computer architecture and numerically intensive algorithms. The lab conducts research on parallel algorithms, on algorithms that effectively exploit cache-memories, and on algorithms that manipulate disk-resident data structures that are too large to fit in memory. The research in the lab is both theoretical and applied: nearly every project involves design and analysis of algorithms, design and implementation of these algorithms, and extensive experimental evaluations.

The laboratory also focuses on discrete and combinatorial issues in scientific simulations, a research area that lies on the boundary between computer science and applied math. Recent projects in the lab include research in the following areas:
Communication-efficient parallel algorithms for numerical linear algebra
Parallel and cache-efficient direct solvers for sparse linear systems
Out-of-core sparse linear solvers and out-of-core orthogonalization
Parallel game-playing algorithms (e.g. for Chess)
Graph algorithms for reordering matrices to reduce fill in Gaussian elimination
Graph algorithms for designing iterative linear solvers

The lab is supervised by: Prof. Sivan Toledo

Multimedia Laboratory

Imagining a world devoid of the diverse means of communication which have become such an integral part of our everyday existence, seems an inconceivable notion. Our growing need to communicate seems to meet no boundaries: the mere touch of a key can transport us even to the most distant corners of the globe.

For the past five years, the Multimedia lab at the School of Computer Science at Tel Aviv University has been working on the development of more efficient communication means, particularly the Internet.

There are three principle research areas which the lab focuses on:
Development of efficient transfer of multimedia, in narrow and broad band networks of images and video. This includes compression, de-noising, feature extraction, automatic object segmentation and extraction, multiscale processing such as filter design.
Development of efficient algorithm for multicast algorithms to transfer data over diverse networks, the Internet in particular.
Efficient computation and fast solver for the solution of partial differential equation, describing different physical phenomena.

The lab is supervised by: Prof. Amir Averbuch

Systems and Network Biology Laboratory

Classical biological research has focused on the understanding of the function of single genes and specific biological mechanisms. With the recent development of high-throughput technologies for measuring biological data at large scale, a systems view of biology has emerged. Systems Biology investigates the behavior of an entire biological system and the relationships between its elements, with the goal of constructing global models that explain well the measured data. A succssful modeling approach views complex cellular processes as networks of interactions between molecules. The modeling and dissection of these networks presents exciting graph-theoretic and statistical problems with important applications in biology.

Within this scope, our research spans a variety of topics, including the construction and analysis of biological networks, the analysis of transcriptional regulation, and the study of genomic variation and its association with disease. It aims to both develop new analysis methods and models, and to enrich our understanding of the operation of intact biological networks and their alterations in human disorders.

The lab is supervised by: Prof. Eytan Ruppin, and Prof. Roded Sharan.


Neural Computation and Signal Processing Laboratory

Data mining and model inference is becoming an essential tool in many aspects of modern computation tasks. When the amount of free parameters in the data is large, issues related to the "Curse of Dimensionality" become critical for robust model inference and decision making.

The laboratory for Neural Computation and Signal Processing has been studying various methods for robustifying model inference via expert fusion and novel regularization methods as well as, reducing dimensionality via Projection Pursuit methods.

Recently, the lab has been focusing on (time-series) analysis of Gene Expression data and Acoustic Biomedical Signals such as EEG, MEG, EKG, and heart sounds as well as bio-sonar of dolphins and bats and seismic data.

The lab is supervised by: Prof. Nathan Intrator.

Parallel Computation Laboratory

The main research activity in the Parallel Computation Laboratory has been the development of PPPC, an environment for developing portable software for parallel computers. Other projects include SYMPAL, a parallel functional programming language, and the development of various other software tools. The laboratory is also used to implement parallel applications developed by researchers.

The lab is supervised by: Prof. Amir Averbuch and Prof. Amiram Yehudai.

Software Engineering and Artificial Intelligence Laboratory

The Software Engineering and Artificial Intelligence Laboratory is concerned with the practical aspects of large software-intensive applications, especially reactive and real-time computer-embedded systems. Experimental systems are developed to test the ideas formed in the conceptual part of the research. Systems developed include OBSERV an environment for rapid prototyping, MASS a specification system for reactive systems capable of generating a target application, and SIP simulation of reactive systems by deduction that is capable of answering "why", "why not", and "what if" questions.

The lab is supervised by: Prof. Amiram Yehudai .

Computational Genomics Laboratory

Far-reaching biological achievements, epitomized by the Human Genome Project, are the outcome of fast-growing compilations of vast and complex biological information. In order to analyze the plethora of data gathered, Biology requires the aid of computational interpretation - hence, Computational Biology.
The Computational Genomics Laboratory at Tel Aviv University's School of Computer Science, has been researching computational problems related to gene, protein and disease analysis. The lab's research interests include gene expression analysis, modeling and dissection of molecular networks, gene regulation, genomic rearrangements and cancer genomics. The methodologies assisting the researchers in their analysis are graph theory, complexity, probability and statistics. Methods and software tools developed by the group are in use by many laboratories around the world.

The lab is supervised by: Prof. Ron Shamir

Laboratory for Logic

Practical applications of mathematical logic to computer science have burgeoned over the last decade, particularly in the domain of verification of software and hardware, artificial intelligence, and logic-based programming languages. Some of these have attained sufficient maturity to have been packaged in commercial products, most notably the "model checking" technique for verification of protocols and circuits. The potential future impact of formal methods based on logic is enormous.

Automated theorem proving and verification have been topics of research since the earliest days of computers. Attempting to prove correctness of programs, and similarly verification of circuits, faces many difficulties. The general problem is unsolvable, many restrictions that are solvable are intractable, and those that are fast enough require human intervention.

A recent strategy for dealing with these issues is finite model checking, which is a very important method for verifying sequential designs (in those cases where there are only finitely many possibilities). In bounded model checking, one tries larger and larger paths through the design in a search for a satisfying assignment, which serves as counterexample to the correctness of the design (that is, a "bug"). A major problem with model checking, however, is the explosion of states in the temporal model generated, hence, of the number of possibilities that need to be checked. This project touches on many different areas of computer science, either to describe the problem or help analyze and attack it, for example, automated deduction, concurrent programming, temporal logic, complexity theory, computer algebra, computational group theory. One specific aspect we intend to address is that of solving satisfiability and validity problems for symbolic model checking faster.

The lab is supervised by: Prof. Nachum Dershowitz and Prof. Alexander Rabinovich.

Laboratory for Information Security

Information systems have become a pillar of our lives, both as individuals and as a community. The continued secure operation of these systems is thus paramount for the stability and well being of our global society. Indeed, the need to maintain the security of information is playing a central role in the shaping of our future.
Keeping information systems secure is a complex and multi-faceted task. It involves a range of disciplines including the mathematical foundations of computational hardness, the theory of program analysis, the design of cryptographic algorithms and protocols, operating system and network design, computing hardware design, Human interface design, as well as Sociology, Economy, and Law.
The Laboratory for Information Security, created as part of the Check Point Institute for Information Security, hosts research in all aspects of cryptography and information security.

The Lab is supervised by: Prof. Ran Canetti, Eran Tromer and Iftach Haitner.

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. Smuel Safra, Prof. Amos Fiat, Prof. Haim Kaplan, Prof. Yishay Mansour, Prof. Yossi Azar and Prof. Uri Zwick.

Programming Languages and Systems Laboratory

The theme of the Programming Languages and Systems lab is to develop new programming languages and environments for producing robust and efficient software applications. The lab specializes in complex programming features such as pointers, dynamically allocated data structures, and multithreading.

The lab develops profiling (runtime) algorithms that provide information on the dynamic behavior of the program in a given run, and static (compile-time) algorithms which provide information on the way the program behaves on all inputs. The information can be employed by programmers, e.g., to detect bugs and to verify that the program is partially correct according to a certain criteria. The information can also be utilized by an optimizing compiler to yield more efficient executable code. Some of these algorithms have already been implemented for programs in C and Java. Detected example errors include memory-leaks, deadlocks, and string related errors.

The lab is supervised by: Prof. Smuel Sagiv.

Computational Genetics Laboratory

The computational genetics lab focuses on the development of computational tools for the analysis of population genetics data; we are mostly interested in the development of tools that enable and facilitate genetic studies of common complex diseases, such as cancer, cardiovascular diseases, or type 2 Diabetes. These studies shed important light on the biological mechanisms of these diseases, and they will pave the way to improved diagnosis and a personalized treatment based on an individual's genetics.

In addition to the disease studies, the lab is also developing method for the inference of ancestry and family relations based on DNA data. These methods have application in personalized genomics and in population genetics studies that explore human history, including the identification of genomic regions that have been under natural selection, and the inference of DNA of extinct human populations.

Our activities touch upon a wide range of quantitative disciplines, including combinatorial and optimization algorithms, machine learning, statistical genetics, population genetics, and bioinformatics. We are working closely with many groups of geneticists around the world on genetic studies of different diseases, and so far we successfully identified genes associated with Non-Hodgkin's Lymphoma, coronary artery disease, and related conditions.

The lab is supervised by: Dr. Eran Halperin.

tau.ac.il cs.tau.ac.il cs.tau.ac.il