^February March – 2008 ^April

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.

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