^May June – 2008 ^July

This talk will describe some of the challenges currently addressed by Web Information Retrieval systems, namely search engines. The first generation of search engines closely resembled classic IR systems in their goal to return relevant documents to a user's query. Those systems relied mostly on on-page contents. The second generation of search engines added the links between Web pages to the mix, and differentiated between several types of information needs. Today's engines tap huge amounts of user generated content, and focus on helping users to complete tasks. This involves both assisting users to break down their tasks into sub-tasks, as well as interpretation, aggregation and integration of diverse content that allows users to more readily digest complex information. The talk will explore some of the search assistance tools available today and will highlight some of the technical challenges in their development.

Secret-sharing schemes are an important tool used in many cryptographic protocols. In these schemes, a dealer holding a secret string distributes shares to the parties such that only pre-defined authorized subsets of participants can reconstruct the secret from their shares. The collection of pre-defined authorized subsets is called an access structure.

In this talk we will discuss ideal secret sharing schemes, that is, schemes in which the shares are taken from the same domain as the secrets (the domain of shares cannot be smaller). Brickell and Davenport have shown an interesting connection between ideal secret sharing schemes and matroids – a combinatorial structure that generalizes the linear independence. They give a necessary condition for an access structure to have an ideal secret sharing scheme – the access structure must be induced by a matroid. Seymour has proved that the necessary condition is not sufficient: There exists an access structure induced by the Vamos matroid that does not have an ideal scheme. We strengthen the result of Seymour by showing that the access structure induced by the Vamos matroid does not have a scheme that is close to being ideal. Our bounds are obtained by using non-Shannon inequalities for the entropy function.

The talk is based on joint works with Carles Padro and Noam Livne.

Polygonal meshes dominate the representations of 3D graphics models due to their compactness and simplicity. Recent advances in design, modeling, and acquisition technologies have simplified the generation of 3D models, which have led to the generation of large 3D models. These models consist of millions of polygons and often exceed the rendering capabilities of advanced graphics hardware. Therefore, there is a need to reduce the complexity of these models to match the hardware's rendering capability, while maintaining their visual appearance. Numerous algorithms have been developed to reduce the complexity of graphics models. These include level-of-detail rendering with multi-resolution hierarchies, occlusion culling, and image-based rendering. View-dependent rendering approaches change the mesh structure at each frame to adapt to the appropriate level of detail. Traditional view-dependent rendering algorithms rely on the CPU to extract a level-of-detail representation. However, within the duration of a single frame, the CPU often fails to extract the frame's geometry. This limitation usually results in unacceptably low frame rates. In this presentation I will present new approaches for interactive view-dependent rendering of large polygonal datasets, which use the advanced features of modern graphics hardware, and free the CPU.

Morphological disambiguation is the process of assigning one set of morphological features (e.g. ילד is a singular masculine noun – a child) to each individual word in a text. When the word is ambiguous (e.g. ילד can be alternatively analyzed as a verb – gave birth), a disambiguation procedure based on the word context must be applied (e.g. given the phrase ילד ירח, the noun analysis is more probable). The most common model for unsupervised learning of stochastic processes is Hidden Markov Models (HMM). In this generative model, a given sequence of observed events is considered to be the emitted output of a stochastic process, over a set of states. In order to estimate the parameters of the model, the Expectation Maximization (EM) algorithm of Baum-Welch is applied over the observed emissions. In the first part of this talk (a type of 'end of PhD. event'), I will overview the Hebrew morphological disambiguation problem, presenting a word-based text encoding, which enables EM learning of HMM model for this task. Then, we will discuss the influence of the initial conditions on the learning process, suggesting several methods for initial estimation of syntagmatic and morpho-lexical distributions.