^December January – 2010 ^February

I will begin with presenting some problems from computational and combinatorial geometry. After that I will discuss problems of the following type: Is there a constant $f=f(k)$ such that any finite set of points in the plane can be colored with $k$ colors so that any halfplane that contains at least $f$ points, also contains a point from every color class? Similarly, one can reformulate the problem by changing halfplanes to a different family of regions. For halfplanes, Pach and G. Toth proved that $f(k)=O(k^2)$. This bound was later improved by Aloupis et al. to $f(k)=O(k)$. We will see that $f(k)=2k-1$, thus completely solving this question for the case of halfplanes. The above questions are related to problems of battery consumption in sensor networks and some other fields in computational geometry.

Whether or not parallel repetition improves security, is a fundamental question in the study of protocols. While parallel repetition improves the security of 3-message protocols and of public-coin protocols, Bellare, Impagliazzo and Naor (FOCS '97) gave an example of a protocol for which parallel repetition does not improve the security at all. We show that by slightly modifying any protocol, in a way that preserves its other properties, we get a protocol for which parallel repetition does improve the security (to any degree) .

In the second part of the talk (if time permits), I will presents our recent results on basing cryptography on minimal hardness assumptions, where we give simpler and more efficient (in some cases tight) constructions of pseudorandom generators, statistically hiding commitments and universal one-way hash functions based on one-way functions.

In this talk I will present several problems I have been working on in geometric modeling, computational geometry and computer graphics. The first problem is the construction, under the exact computation paradigm, of arrangements of Bezier curves. The second is the computation of Voronoi cells of free-form curves and the third is the visualization of solid models using the graphics processing unit (GPU). The common theme in these problems is that they contain geometric constructions, which either cannot be represented using their standard geometric representation or computing them is too expensive. Previous methods for attacking these problems typically use approximations, either of the input or of the problematic geometric constructions. Our methods, on the other hand, use procedural representations, which enable to answer a set of queries that are sufficient for solving the problem at hand. In arrangements of Bezier curves, we represent intersection vertices with references to intersecting curves, and to bounding polygons. This enables us to avoid the prohibitive running times incurred by exact algebraic arithmetic. In the computation of Voronoi cells of free-form curves, the bisector curves cannot be represented in standard (Bezier or B-spline) form. Instead we use a representation based on an implicit function in the curves parametric domain combined with a mapping to the Euclidean plane. Using this representation we can answer the queries required to compute the lower envelope of the bisector distance functions and thus compute the boundary of the Voronoi cell. When rendering solid models using the GPU, a common problem is the appearance of cracks between faces in the model visualization. These are a result of the non-exact representation of trimming curves in the model. Using a representation that stores references to intersecting surfaces we are able to avoid these cracks and render a smooth water tight model. This work is part of an ongoing project. In my talk, I will present the different problems and how applying procedural representations helps in their computation. I will also present other problems for which I believe applying such representations can be useful. The work described in this talk was done in collaboration with Gershon Elber, Ron Wein, Kirk Haller and others.

Over the past decades the evolutionary approach has been used in many fields of computer science research. Lately, with the growth of computation power, Genetic Programming (GP) has been showing much promise. We present an attempt to apply the tree based GP approach to zero-sum deterministic full knowledge board games, using Lose Checkers as a test-case. Our system implements strongly typed GP trees, explicitly defined introns and multi-tree individuals. We use the GP trees to evaluate possible future game states. Used together with traditional search techniques the results show much promise and imply that tree based GP may be useful in finding good players for other similar games.

How much computational power is required to perform basic cryptographic tasks? We will survey a number of recent results on the complexity of basic cryptographic primitives such as one-way functions, pseudorandom generators, encryption schemes and digital signatures. Specifically, we will consider the possibility of computing instances of these primitives by NC0 functions, in which each output bit depends on only a constant number of input bits. Somewhat surprisingly and unintuitively, it turns out that most cryptographic tasks can be carried out by such simple functions. We will also explore the cryptographic strength of several interesting subclasses of NC0. This includes simple forms of natural computation that can be performed by real-world dynamical systems in a constant number of steps. On the application side, we will mention new connections between NC0 cryptography and other seemingly unrelated areas such as secure distributed computation, program checking, and hardness of approximation. We will focus on a new approach for constructing public-key encryption schemes based on the intractability of random NC0 functions. Most, if not all, existing constructions of public-key encryption use hardness assumptions with significant algebraic structure. The main advantage of the new schemes is the relatively general and combinatorial nature of the new assumptions, which seem qualitatively different than previous ones. Based on joint works with Yuval Ishai and Eyal Kushilevitz and with Boaz Barak and Avi Wigderson. The talk is self-contained, and does not assume previous background in cryptography.

Digitization of health care data is creating an opportunity for a new way of studying diseases and improving medical care. Using the vast amount of patient data collected daily at hospitals can assist us in circumventing the inherent faults of current medical research of studying phenomenon using various imperfect models, as experimenting on humans is unethical and illegal. The majority of information is stored in free text written by doctors. Using that data requires adapted Natural Language Processing methods combined with domain specific knowledge. Here I will present one project that originated from challenges in Medical Hebrew Processing: In most professional domains of languages with non-Latin alphabet, proper names, named entities and adjectives are transliterated from English. We show that recognizing these words as well as the original word is important for term recognition. We developed a method for identifying said words combining unsupervised classifiers and a lexicon. The lexicon based approach produced F-Measures of 87%-92% across domains, the combined approach produced F-Measures of 93%-94% respectively. Using this classifier to improve term matching we obtained 77% more matches with precision of 92%.

The images acquired via medical imaging modalities are frequently subject to low signal-to-noise ratio, bias field and partial volume effects. These artifacts, together with the naturally low contrast between image intensities of some neighboring structures, make the extraction of regions of interest (ROIs) in clinical images a challenging problem. Probabilistic atlases, typically generated from comprehensive sets of manually labeled examples, facilitate the analysis by providing statistical priors for tissue classification and structure segmentation. However, the limited availability of training examples that are compatible with the images to be segmented, renders the atlas-based approaches impractical in many cases. In the talk I will present a generative model for joint segmentation of corresponding regions of interest in a collection of aligned images that does not require labeled training data. Instead, the evolving segmentation of the entire image set supports each of the individual segmentations. This is made possible by iteratively inferring a subset of the model parameters, called the spatial parameters, as part of the joint segmentation processes. These spatial parameters are defined in the image domain and can be viewed as a latent atlas, that is used as a spatial prior on the tissue labels. Our latent atlas formulation is based on probabilistic principles, but we solve it using partial differential equations (PDEs) and energy minimization criteria. We evaluate the method successfully for the segmentation of cortical and subcortical structures within different populations and of brain tumors in a single-subject multi-modal longitudinal experiment.

In experimental optimization the quality of candidate solutions can be evaluated only by means of an experiment in the real-world. These experiments are often time-consuming and/or expensive, and are typically limited to several dozens or hundreds of trials. High-dimensional problems (i.e., at least 80 search variables) cannot be efficiently handled by classical convex optimizers, and thus require an alternative treatment. Derandomized Evolution Strategies (DES) are powerful bio-inspired search methods, originating from Evolutionary Algorithms, that incorporate statistical learning for efficient derandomized search. This talk will focus on the theory behind state-of-the-art DES, as well as on their application to experimental optimization. Especially, it will discuss optimization efficiency, attainment of robust solutions, exploration of the actual search landscape, and the generalization into Pareto optimization of multiple objectives. Special emphasis will be put on a particular experimental platform employing DES at present times, namely Quantum Control experiments. The Quantum Control (QC) field aims at altering the course of quantum dynamics phenomena for specific target realizations, by means of closed-loop, adaptively learned laser pulses. The optimization task of QC experiments typically poses many algorithmic challenges, e.g., high-dimensionality, noise, constraints handling, and thus offers a rich domain for the development and application of specialized optimizers. Toward that end, the computational aspects of several real-world laboratory optimization case-studies will be presented. **This talk will be self-contained, and will target the general audience of CS, Engineering, and Applied Physics. It will not require any specialized background in Quantum Mechanics nor in Optimization.

Today's computers run numerous processes of different sensitivity and trustworthiness, and often the only boundary between a hostile network and sensitive data relies on flimsy confinement assumptions. The platform purports to protect processes from each other, but side channels arise from lower architectural layers, such as contention for shared hardware resources, and create inadvertent cross-talk. For example, we have shown how observing contention for the CPU cache allows an attacker to steal other users' encryption keys in a few milliseconds. Such cross-talk is especially grievous in the context of cloud computing ("infrastructure as a service"), where users acquire computational capacity in the form of virtual machines running on a service provider's shared hardware pool. The presence of multiple mutually-untrusting virtual machines on the same hardware creates the risk of information exfiltration across virtual machines and between clients, as we demonstrated on Amazon EC2. These security vulnerabilities raise the challenge of achieving trustworthy computation on leaky platforms. We discuss potential solutions, including a new work on mitigating side channels using just-in-time dynamic transformation of x86 machine code.

This talk includes joint works with Saman Amarasinghe, Dag Arne Osvik, Thomas Ristenpart, Ron Rivest, Stephan Savage, Hovav Shacham, Adi Shamir and Qin Zhao.

Regardless of the technology that surrounds us and the virtual realms we use and inhabit, we are still physical beings, living and acting in physical spaces. Various current trends in human-computer interaction attempt to enhance usability by exploring new physical interfaces attributes and mappings.

My group's research is directed at designing and exploring new interactive experiences based on physical entities and environments. Our interests include human-robot interaction, physical and tangible user interfaces, mixed reality, computer game interfaces and ubiquitous computing. In this talk I will present a brief overview of physicality in interaction, its potential and challenges. The talk includes a discussion of several current projects my students and I are pursuing, ranging from 3D sketch-based interaction and mixed reality games, to sociable robotic interfaces and robotic cartoon art expression.