^February March – 2008 ^April

Let $M$ be some finite graph or a finite metric space and assume that some of the automorphisms of $M$ are stored together with the structure of $M$. Let $N$ be some substructure of $N$. A partial automorphism $p$ of $N$ is implemented by an automorphism $f$ of $M$, if the automorphism $f$ extends $p$. For example, an automorphism of $M$ which moves point $a$ in $N$ to point $b$ in $N$ (but may take other points of $N$ out of $N$) implements the partial automorphims $amapsto b$. Consider the following problem: given a structure $N$ and a list $L_0$ of partial automorphisms of $N$, can you find a larger structure $M$ which cotains (a copy of) $N$ as a substructure so that every partial automorphism $p$ in $L_0$ is implemented in $M$. For example, can you find a graph $M$ extending the graph $N$ such that every vertex of $N$ can be moved to any other vertex of $N$ by an automorphisms of $M$ (here the answer is YES, by a theorem of Babai and Sos). The new results I will present assure that in some cases (including the case of the example above) one can find, for given $N$ and $L_0$, a structure $M$ with a list $L_1$ of (full) automorphisms of $M$, such that: (1) the size of $M$ and the size of $L$ are polynomial in the the size of $N$. (2) every partial automorphism in $L_0$ is implemented by some automorphisms from $L_1$. (3) Property (2) is indestructible by partitions: whenever $M$ is partitioned into two disjoint parts, at least one of the parts contains a copy of $N$ for which (2) holds. I will discuss some open problems at the end of the talk. The results are joint with Stefan Geschke.

Parsing a natural language sentence is the task of automatically assigning a (syntactic) structure to a sentence in a non-formal language (such as English or Hebrew). Parsing a sentence is one of the first steps towards understanding it. This talk is an introduction to one (very common) parsing framework, namely parsing with PCFGs (probabilistic CFGs). I'll start by describing the overall framework, and present some early results. Then, I'll describe several extensions and refinements, ending in the current state-of-the-art in parsing technology.

k-CNF formulas with m clauses over n variables show a phase transition phenomenon in the following aspect. There exists $d=d(k,n)$ such that almost all formulas with $m/n>d$ are not satisfiable whereas most formulas with m/n<d are. While random k-CNFs below the threshold received much attention in recent years, above-threshold distributions over satisfiable k-CNFs were far less studied. One possible reason is that it is not clear how to define such distributions in a natural way, while keeping the problem approachable in some sense. In this talk we will survey recent developments in this area. We shall concentrate on three distributions: the planted k-SAT distribution, the uniform distribution over satisfiable k-CNF formulas (in the regime $m/n>d(k,n)$), and an "on-line" version ofthe uniform distribution. In all cases we are able to show that unlike the typically complicated structure of the solution space of below-threshold formulas, above threshold formulas have a simple, basically single-solution structure. We also present some algorithmic ideas that are useful for solving certain clause-density regimes of these distributions.

Based on joint works with: Amin Coja-Oghlan, Uriel Feige, Abraham Flaxman, Michael Krivelevich, and Benjamin Sudakov

Our next guest is Prof. David Harel (Weizmann Institute of Science). Harel is best known for his work on dynamic logic, computability and software engineering. In the 1980s he invented the graphical language of Statecharts, which has been adopted as part of the UML standard. He has also published expository accounts of computer science, such as his award winning 1987 book "Algorithmics: The Spirit of Computing" and has made appearances on Israeli radio and television. He currently works on many diverse topics, including visual languages, graph layout, systems biology and the communication of odors.

Abstract: The talk shows the way software and systems engineering, especially of reactive systems, can be applied beneficially to the life sciences. We will discuss the idea of comprehensive and realistic computerized modeling of biological systems. In comprehensive modeling the main purpose is to understand an entire system in detail, utilizing in the modeling effort all that is known about the system, and to use that understanding to analyze and predict behavior in silico. In realistic modeling the main issue is to model the behavior of actual elements, making possible totally interactive and modifiable realistic executions/simulations that reveal emergent properties. I will address the motivation for such modeling and the philosophy underlying the techniques for carrying it out, as well as the crucial question of when such models are to be deemed valid, or complete. The examples I will present will be from among the biological modeling efforts my group has been involved in: T cell development in the thymus, lymph node behavior, embryonic development of the pancreas, the C. elegans reproductive system, and a generic cell model. I will also discuss a long-term "grand challenge" — to model a full multi-cellular organism.

In this talk we present efficient secure protocols for a variety of tasks, including oblivious transfer, set intersection and pattern matching. Our protocols for securely computing the set intersection functionality are based on secure pseudorandom function evaluations, in contrast to previous protocols that used secure polynomial evaluation. We also use secure pseudorandom function evaluation in order to achieve secure pattern matching. In this case, we utilize specific properties of the Naor-Reingold pseudorandom function in order to achieve high efficiency. Finally, we show that using standard smartcards it is possible to construct truly practical secure protocols, and demonstrate this on the problem of set intersection. We consider a variety of adversary models and definitions of security in our results. Some of our protocols are secure in the presence of malicious adversaries with full simulation (via the ideal/real paradigm), and some provide only privacy. We also present protocols that are secure in the presence of covert adversaries. Loosely speaking, this means that a malicious adversary can cheat, but will then be caught with good probability

A new problem in phylogenetic inference is presented, based on recent biological findings indicating a strong association between reversals and repeats. These biological findings are formalized here in a new mathematical model, called repeat-annotated phylogenetic trees (RAPT). We show that, under RAPT, the evolutionary process - including both the tree-topology as well as internal node genome orders - is uniquely determined, a property of major significance both in theory and in practice. Furthermore, the repeats are employed to provide linear-time algorithms for reconstructing both the genomic orders and the phylogeny, which are NP-hard problems under the classical model of sorting by reversals (SBR). For that, a new data structure - namely set-tries - is presented, and is shown to support efficient linear-time insert and find operations. Joint work with Michal Ziv-Ukelson and Ron Pinter. The presentation is self contained.