The School's faculty,
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
Experimental research in
the School is conducted within the following research laboratories.
With the advent of the Internet,
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,
Mansour and Prof.
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
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
The Lab is supervised by: Prof. Yehuda Afek
Hanoch Levy and Prof. Yishay
The Structural Bioinformatics
|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
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
The lab is supervised by: Prof. Haim
Databases and Information Systems
|With the proliferation of database
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
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
The lab is supervised by: Prof. Yossi Matias
Robotics, Computer Vision and
|Humans, as well as many other living
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,
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
The lab is supervised by: Prof.
Lior Wolf ,
Prof. Dan Halperin, Prof. Micha Sharir
High-Performance Parallel Computing
|The laboratory for high-performance
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
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
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
Graph algorithms for designing iterative linear solvers
The lab is supervised by: Prof. Sivan Toledo
|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
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
Classical biological research has
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
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,
Neural Computation and Signal
Data mining and model inference is
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
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
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
Software Engineering and Artificial
The Software Engineering and
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"
The lab is supervised by: Prof. Amiram
Computational Genomics Laboratory
biological achievements, epitomized by the Human Genome Project, are
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
Computational Genomics Laboratory at Tel Aviv
University's School of Computer Science, has been researching
problems related to gene, protein and disease analysis. The lab's
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
graph theory, complexity, probability and statistics. Methods and
tools developed by the group are in use by many laboratories around the
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
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
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
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,
Tromer and Iftach
|The basic purpose of research in
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
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,
Amos Fiat, Prof.
Haim Kaplan, Prof.
Prof. Yossi Azar and Prof. Uri Zwick.
Programming Languages and Systems
|The theme of the Programming
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
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
the development of tools that enable and facilitate genetic studies of
complex diseases, such as cancer, cardiovascular diseases, or type 2
These studies shed important light on the biological mechanisms of
diseases, and they will pave the way to improved diagnosis and a
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
have application in personalized genomics and in population genetics
that explore human history, including the identification of genomic
that have been under natural selection, and the inference of DNA of
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
closely with many groups of geneticists around the world on genetic
different diseases, and so far we successfully identified genes
Non-Hodgkin's Lymphoma, coronary artery disease, and related conditions.
The lab is supervised by: Dr.