Department of Computer Science and Applied Mathematics

Uriel Feige, Head


The principal interests of the department lie in the areas of computer science and applied mathematics. Research in computer science includes the study of computational complexity, the development and analysis of algorithms, cryptography, proof theory, parallel and distributed computing, logic of programs, specification methodologies, the formal study of hybrid systems, combinatorial games, biological applications, brain modeling, visual perception and recognition, robotics and motion control. Research in applied mathematics includes dynamical systems, combinatorics, numerical analysis, the use of mathematical techniques to elucidate phenomena of interest in the natural sciences, such as biology and geophysics, and on the development of new numerical tools for solving differential equations, computing integrals, providing efficient approximations to complex continuous models, and solving other mathematical problems.

The departmental computer facilities include a multiple-CPU server, SGI, Sun and DEC workstations, and NCD X-terminals. The vision and robotics laboratories contain state-of-the-art equipment, including an Adept four-axis SCARA manipulator, an Eshed Robotec Scorbot ER IVV manipulator, Optotrak system for three-dimensional motion tracking, and a variety of input and output devices.


R. Basri

Computer vision, image processing, object recognition under unknown lighting and pose, categorization, perceptual grouping and segmentation.


I. Dinur

Probabilistically Checkable Proofs

Hardness of Approximation


U. Feige

NP-hard combinatorial optimization problems, computational complexity, algorithms, cryptography, random walks, combinatorial optimization.


T. Flash

Robotics, motor control and learning, movement disorders, computational neuroscience, virtual reality.


O. Goldreich

Probabilistic proof systems, Pseudorandomness, Foundations of Cryptography, Property Testing, and Complexity theory.


S. Goldwasser

Probabilistic proofs, cryptography, computational number theory, complexity theory.


D. Harel

Visual formalisms, software engineering, biological modeling, visualization, odor communication and synthesis


M. Irani

Video information analysis and applications, Computer Vision, Image Processing.


R. Krauthgamer

Design and Analysis of Algorithms, including Massive Data Sets, Data Analysis, and Combinatorial Optimization

Embeddings of Finite Metric Spaces, High Dimensional Geometry


D. Michelson

Numerical analysis, differential equations, dynamical systems.


M. Naor

Cryptography and Complexity

Distributed Computing

Concrete Complexity


D. Peleg

Graph algorithms, approximation algorithms, distributed computing, fault tolerance, communication networks


R. Raz

Complexity Theory: In particular; Boolean circuit complexity, arithmetic circuit complexity, communication complexity, propositional proof theory, probabilistic checkable proofs, quantum computation and communication, randomness and derandomization.


O. Reingold

Foundations of Computer Science

  1.   Computational Complexity

  2.  Foundations of Cryptography

  3.  Randomness, Derandomization and Explicit Combinatorial Constructions


V. Rom-Kedar

Hamiltonian systems - theory and applications
V. Rom-Kedar, M. Radnovic, A. Rapoport, E. Shlizerman, D. Turaev

  1.  Near-integrable systems

  2.  The Boltzmann ergodic hypothesis and soft billiards.

  3.  Chaotic scattering.

  4.  Resonant surface waves.

  5.  Perturbed nonlinear Schrodinger equation.

Mathematical models of the hematopoietic system and their medical implications
V. Rom-Kedar, R. Malka, E. Shochat.

Chaotic mixing of fluid flows
V. Rom-Kedar, R. Aharon, H. Gildor


E. Segal

Quantitative models for transcription and chromatin regulation

Modeling the role of microRNAs and non-coding RNAs in gene regulation


A. Shamir

Cryptography, cryptanalysis, electronic money, smartcard security, internet security, complexity theory, the design and analysis of algorithms.


E. Shapiro

Biomolecular computing and its medical applications


E. Titi

Nonlinear Partial Differential Equations

  1.  Infinite-dimensional dynamical systems

  2.  Numerical analysis of dissipative PDEs

  3.  Control theory for dissipative systems

Fluid Dynamics

  1.  Navier-Stokes and related equations

  2.  Turbulence theory

  3.  Geophysical models of aceanic and atmospheric dynamics


S. Ullman

Vision, image understanding, brain theory, artificial intelligence.