Computer Science and Applied Mathematics

 

Uriel Feige, Head
The Lawrence G. Horowitz Professorial Chair

Research in computer science encompasses theoretical studies on the foundations of computer science, experimental aspects of computer science, computer vision and robotics, machine learning and statistical data analysis, the study of information processing by biological systems, theoretical biology and bio-informatics. On the theoretical side, topics include computational complexity, cryptography, algorithms, distributed computing, methods for system verification, specification and development, logics of programs, combinatorics and number theory, combinatorial games, information retrieval, and numerical analysis. Experimental research includes the development of concurrent languages, visual languages, and programming environments. The study of vision, robotics, and motor control includes both theoretical and experimental components. We have expanded our activity at the interface of biology and computation by adding a program in bio-informatics, and studying computations by biological machinery and modeling and analysis of biological systems.

Research in applied mathematics includes two main themes. The first is the basic study of applied mathematics and the development of new mathematical tools of general applicability in science and engineering. The second theme is the use of mathematical techniques to elucidate phenomena of interest in the natural sciences, such as biology, medicine, and physics.

We describe below some of the research areas addressed by our department members. This presentation is not meant to be exhaustive (additional research interests can be found in individual home pages of department members), not meant to be proportional (length of description is not necessarily correlated with extent of activity), and is not meant to imply a separation among areas (many of the areas overlap in various ways).

Algorithms: Research on algorithms includes the design of approximation algorithms for difficult (NP-hard) optimization problems, the design of heuristics for such problems, and the design of ultra efficient algorithms that work on huge data sets (including so called property testers and streaming algorithms). The analysis of these algorithms often involve the use of tools from mathematical areas such as probability theory and high dimensional geometry.

Complexity theory deals with classifying computational problems by the amount of computational resources they require; in particular, the number of processing steps and the memory required for their solution. In addition to studies aimed at providing absolute answers to questions of the above nature (e.g., lower bounds on the complexity of specific types of computational tasks), much study evolves around relating seemingly different computational phenomena (e.g., the PCP characterization of NP).

Cryptography deals with methods for protecting the privacy, integrity, and functionality of computer and communication systems. The research activities on the area range from providing firm foundations to the construction of such methods to providing actual constructions for specific needs. Correspondingly, research in Cryptography ranges from very abstract (or theoretical) to very applied (or concrete). The full range of these activities is represented in our department.

Distributed computing and communication networks: Work in this area includes the design of efficient communication patterns and efficient transmission of information between sites in a network.

Randomness is related to computation in various ways, and a central question is whether randomness is inherently useful in various computational settings. Research in this area evolves around finding new ways of using and manipulating randomness (e.g., extracting pure randomness from impure random sources) on the one hand, and finding ways to dispense of randomness on the other hand (e.g., pseudorandom generators).

Combinatorics, number theory, combinatorial games. Study of the structure of complementary sequences and nonstandard numeration systems, and their applications to the complexity analysis of combinatorial games.

System and software engineering: Research on languages and methods for the modeling and simulation of complex reactive systems. Work focuses on visual formalisms, based on topological and geometric constructs. It includes the 1984 language of Statecharts, and a more recent language for scenario-based specification, called LSCs (live sequence charts). The latter leads to a novel programming paradigm, behavioral programming (BP). We are working on many aspects of BP, including a non visual Java-based version, hybrid interactive programming techniques, synthesis and compilation, and smart", verification-based program execution methods.

Vision: Object recognition: developing methods for recognizing objects, such as faces or cars, from their images.

Aids for the visually impaired: Using computer vision methods to help the visually impaired.

Video analysis and application: using video analysis to handle and manipulate information from multiple video cameras imaging the same scene (either simultaneously or at different times). Video enhancement, video indexing and browsing (e.g., over the internet), compression (for storage and transmission), video-based surveillance and monitoring, and multi-media applications.

Visually guided navigation: using vision to guide mobile robots and robotic arms to reach a desired position.

Motor control and robotics: Movement control in biological and robotic systems: studying the processes of motion planning and control in biological systems and the strategies employed by the brain in the planning, execution and control of multi-joint movements and different motor tasks, such as reaching, pointing, grasping and drawing. These studies combine behavioral, modeling and brain mapping studies.

Developing optimization and geometry based models to model, simulate and decompose human movements into the underlying motion primitives.

Studies of movement generation in flexible biological and robotic arms and developing flexible robotic arms inspired by the octopus.

Studies of complex body movements' production and perception, body expression of emotion and movement and gestures characterizing social interactions.

Machine learning and statistical data analysis: development and theoretical analysis of algorithms to perform various data analysis tasks including clustering classification and regression, specifically in high dimensional settings.

Dynamical systems, partial differential equations and applications: We develop and use dynamical systems approach and PDE tools to analyze nonlinear evolution equations which arise in diverse fields of interest. The applications include fluid mechanics, geophysics, chemical reactions, combustion theory, nonlinear fiber optics, lasers, elasticity, biological models and control theory. Our research lies at the interface between rigorous applied analysis and physical applications. Current projects that deal with finite dimensional systems include studying the motion of particles in optical traps (billiards), various aspects of mixing in fluid flows, models that arise in nonlinear optics and the dynamics of certain models in biology. Some of these projects contribute to the understanding of basic underlying structures of nonlinear Hamiltonian systems. Projects which deal with infinite dimensional systems include the study of complex nonlinear phenomena, such as turbulent flows and the long-term behavior (global attractors) to nonlinear dissipative partial differential systems, such as the Navier-Stokes equations, reaction-diffusion systems and other related systems. The dynamics of such dissipative nonlinear PDE models involves a wide spectrum of temporal and spatial scales. This often makes it prohibitively expensive computationally. We approach this challenging problem by developing reliable reduced approximate PDE models, which are possible to implement computationally and to be validated rigorously, for the relevant spatial and temporal scales.

Bioinformatics and computational biology: The recent sequencing projects provide us with all the basic "building blocks" of life, including a nearly complete description of all of the genes. The next challenge is to unravel how these parts interact and assemble into larger cellular machines, capable of carrying out increasingly complex functions. Our research activities address this challenge by developing computational frameworks that model complex biological systems, through integration of heterogeneous sources of biological data. Recent directions include development of: models of transcriptional control that incorporate transcription factors, DNA sequences, transcription degradation, binding competition and synergy; models of translational control through microRNA-RNA interactions; models of chromatin structure through nucleosome positions, post-translational histone modifications, and chromosomal expression domains. Applications of these models that are currently being pursued include understanding pattern formation during development and understanding control of gene expression during the cell cycle. The underlying computational techniques and algorithms are statistical in nature, including general tools from Machine Learning and probabilistic graphical models.

Cell lineage analysis and its applications: We developed a method for reconstructing cell lineage trees based on the detection and analysis of somatic mutations, and now explore its application to cell lineage analysis in mice as well as its application to the analysis of the development of cancer.

Biological modeling: We are involved in several efforts of modeling and analyzing complex biological systems. We view this as reverse engineering, and use techniques from systems and software engineering, including visual formalisms, such as statecharts and LSCs, advanced model executability techniques, such as smart play-out, reactive animation, and verification. In particular, we have worked on cell fate determination in C. elegans and on T cell development in the thymus, as well as on pancreatic organogenesis, and on the lymph node. We are currently involved in an effort to model cancer tumors and a modest neural system. A particularly interesting aspect of the work is the use of verification techniques to prove the consistency between proposed mechanistic models of behavior and laboratory observations.

Olfaction: Recent parts of our work on the synthesis and communication of odors involved predicting pleasantness from eNose measurements and relating molecular characteristics of odorants to neural response and eNose data.

http://www.wisdom.weizmann.ac.il/

Research Staff, Visitors and Students

Professors

Ronen Basri, Ph.D., Weizmann Institute of Science, Rehovot, Israel
       The Elaine and Bram Goldsmith Professorial Chair of Applied Mathematics
Uriel Feige, Ph.D., Weizmann Institute of Science, Rehovot, Israel
       The Lawrence G. Horowitz Professorial Chair
Tamar Flash, Ph.D., Massachusetts Institute of Technology, Cambridge, United States
       The Dr. Hymie Moross Professorial Chair
Oded Goldreich, Ph.D., Technion-Israel Institute of Technology, Haifa, Israel
       The Meyer W. Weisgal Professorial Chair
Shafrira Goldwasser, Ph.D., University of California, Berkeley, United States
David Harel, Ph.D., Massachusetts Institute of Technology, Cambridge, United States
       The William Sussman Professorial Chair of Mathematics
Michal Irani, Ph.D., The Hebrew University of Jerusalem, Jerusalem, Israel
Moni Naor, Ph.D., University of California, Berkeley, United States
       The Judith Kleeman Professorial Chair
David Peleg, Ph.D., Weizmann Institute of Science, Rehovot, Israel
       The Norman D. Cohen Professorial Chair of Computer Sciences
Ran Raz, Ph.D., The Hebrew University of Jerusalem, Jerusalem, Israel
Vered Rom-Kedar, Ph.D., California Institute of Technology, Pasadena, United States
       The Estrin Family Professorial Chair of Computer Science and Applied Mathematics
Adi Shamir, Ph.D., Weizmann Institute of Science, Rehovot, Israel
       The Paul and Marlene Borman Professorial Chair of Applied Mathematics
Ehud Shapiro, Ph.D., Yale University, New Haven, United States
       The Harry Weinrebe Professorial Chair of Computer Science and Biology
Edriss S. Titi, Ph.D., Indiana University, Bloomington, United States
Shimon Ullman, Ph.D., Massachusetts Institute of Technology, Cambridge, United States
       The Ruth and Samy Cohn Professorial Chair of Computer Sciences

Professors Emeriti

Ari Ben-Menahem, Ph.D., California Institute of Technology, Pasadena, United States
Achi Brandt, Ph.D., Weizmann Institute of Science, Rehovot, Israel
Aviezri S. Fraenkel, Ph.D., University of California, Los Angeles, United States

Associate Professors

Irit Dinur, Ph.D., Tel Aviv University, Tel-Aviv, Israel
Daniel Michelson, Ph.D., Tel Aviv University, Tel-Aviv, Israel
Elchanan Mossel, Ph.D., The Hebrew University of Jerusalem, Jerusalem, Israel
Omer Reingold, Ph.D., Weizmann Institute of Science, Rehovot, Israel

Senior Scientists

Robert Krauthgamer, Ph.D., Weizmann Institute of Science, Rehovot, Israel
       Yigal Allon Fellow
Anat Levin, Ph.D., The Hebrew University of Jerusalem, Jerusalem, Israel
       Yigal Allon Fellow
       Incumbent of the Helena Rubinstein Career Development Chair
Boaz Nadler, Ph.D., Tel Aviv University, Tel-Aviv, Israel
Eran Segal, Ph.D., Stanford University, Stanford, United States
Amos Tanay, Ph.D., Tel Aviv University, Tel-Aviv, Israel
       Yigal Allon Fellow

Associate Staff Scientist

Meirav Galun, Ph.D., Weizmann Institute of Science, Rehovot, Israel

Assistant Staff Scientists

Dorit Ron, Ph.D., Weizmann Institute of Science, Rehovot, Israel
Adina Weinberger, Ph.D., Weizmann Institute of Science, Rehovot, Israel

Special Contract

Assaf Marron, Ph.D., University of Houston, Texas, United States

Interns

Sharon Alpert, Ph.D., Weizmann Institute of Science, Rehovot, Israel (left October 2010)
Avital Sadot, Ph.D., Weizmann Institute of Science, Rehovot, Israel (left March 2010)
Yaakov Setty, Ph.D., Weizmann Institute of Science, Rehovot, Israel

Engineers

Yorram Kalef, M.Sc., Technion-Israel Institute of Technology, Haifa, Israel (left June 2010)
Leah Mory, M.Sc., Weizmann Institute of Science

Consultants

Binyamin Applebaum, Tel Aviv University, Ramat-Aviv, Tel-Aviv, Israel
Avi Barliya, Primesense, Tel-Aviv, Israel
Nayantara Bhatnagar, The Hebrew University of Jerusalem, Jerusalem, Israel (left November 2010)
Erick Fredj, Jerusalem College of technology, Jerusalem, Israel
Leonid Karlinsky, Elop, Rehovot, Israel
Shahar Maoz
Yoram Yekutieli, Hadassah Academic College, Jerusalem
Ido Zelman, Havruta School, ICYL, Neve Hadassa (left August 2010)

Visiting Scientists

Andrej Bogdanov - Chinese University of Hong Kong, Shatin, NT, Hong Kong
Peter Constantin, University of Chicago, Il, U.S.A.
Matthias Englert - Univ. of Warwick, Coventry, United Kingdom
Dirk Fahland - Humboldt University, Berlin, Germany
Jasmin Fisher, Microsoft Research, Cambridge, U.S.A.
Fred Hamprecht - Univ. of Heidelberg, Heidelberg, Germany
Brendan Juba - M.I.T., Cambridge, MA, USA
Keren Livescu, Texas A&M University, U.S.A.
Krzystof Pietrzak - Centrum voor Wisukunde en Informatica (CWI), Amsterdam, Holland
Toniann Pitassi, University of Toronto, Canada
Milena Radnovic, SANU, Belgrade, Serbia
Ronald Rivest - M.I.T., Cambridge, MA, USA
Warren Schudy - Brown University, Providence, RI, USA
Gregory Shakhnarnovich, Trinity College, Dublin, Ireland
Nathan Srebro, University of Chicago, Il, U.S.A.
Eitan Tadmor - Univ.of maryland, College Park, MD, USA
Dmitry Turaev, Imperial College, London, UK

Postdoctoral Fellows

Noa Agmon, Bar-Ilan University, Israel
Adi Akavia, MIT, Cambridge, MA., USA
Binyamin (Benny) Applebaum, Technion - Israel Institute of Technology, Israel
Nitsan Ben-Gal, Brown University
Lucas Carey, Stony Brook University
Eden Chlamtac, Princeton University
Maya Dadiani, Weizmann Institute of Science, Israel
Eran Dayan, Weizmann Institute of Science, Israel
Michael Henry Dinitz, Carnegie Mellon University
Orr Dunkelman, Technion - Israel Institute of Technology, Israel
Yair Field, Weizmann Institute of Science, Israel
Ronit Fuchs, Weizmann Institute of Science, Israel
Lee-Ad Gottlieb, New York University
Carmit Hazay, Bar-Ilan University, Israel
Tali Kaufman, Tel-Aviv University, Israel
Michael Kertesz, Weizmann Institute of Science, Israel
Robby Lampert, Hebrew University of Jerusalem, Israel
Yosef Efraim Maruvka, Bar-Ilan University, Israel
Ricky (Rivka) Rosen, Tel-Aviv University, Israel
Oded Schwartz, Tel-Aviv University, Israel
Elad Segev, Hebrew University of Jerusalem, Israel
Kushal Kumar Shah, Indian Institute of Technology Madras
Avital Tsofe, Tel-Aviv University, Israel
Oren Weimann, Massachusetts Institute of Technology
Einat Zalckvar, Weizmann Institute of Science, Israel

Research Students

Sharon AlpertMica Arie-Nachimson
Noam Arkind Yoram Atir
Shai Bagon Avi Barliya
Naamah Bloch (Swerdlin)Zvika Brakerski
Shiri Chechik Gil Cohen
Michael Dinerstein Itai Dinur
Nimrod DorfmanYair Field
Ronit Roxana FuchsDaniel Glasner
Elazar GoldenbergMichal Gordon
Daniel Harari Simon Israeli-Korn
Ram Jaschek Shlomo Jozeph
Amir Kantor Erez Kantor
Noam Kaplan Matan Karklinsky
Leonid Karlinsky Ephraim Kenigsberg
Michael Kertesz Orit Kliper-Gross
Gillat Kol Michal Levo
Jasmine Sonia Linshiz Noam Livne
Shachar LovettShai Lubliner
Roy MalkaOhad Manor
Or Meir Yaron Meirovitch
Netta Mendelson Cohen Merav Parter
Tom Ran Daniel Reichman
Ron RothblumYaniv Sa'Ar
Tali Sadka-Raveh Itai Segall
Gil SegevEilon Sharon
Igor Shinkar Marina Shudler
Konrad Simon Eitan Yaffe
Danny Zeevi Maria Zontak

Administrator

Raanan Michael