^January February – 2008 ^March

This will be a kind of an erasure coding tutorial for the layman. I will give a (very) brief survey of erasure coding, and will then concentrate on the more interesting case of rateless codes. I will present one of the first (if not THE first) works in this field, LT codes, by Michael Luby. As I am not an expert on this subject, I'll not present the finer details and proofs, but the general idea (and the more interesting points).

This will be a kind of an erasure coding tutorial for the layman. I will give a (very) brief survey of erasure coding, and will then concentrate on the more interesting case of rateless codes. I will present one of the first (if not THE first) works in this field, LT codes, by Michael Luby. As I am not an expert on this subject, I'll not present the finer details and proofs, but the general idea (and the more interesting points).

We present a new method for inferring complexity properties for imperative programs with bounded loops. The properties handled are: polynomial (or linear) boundedness of computed values, as a function of the input; and similarly for the running time.

We overcome the classic undecidability obstacle by defining a ``core" programming language that is Turing-incomplete, but strong enough to model real programs of interest. For this language, our method is the first to give a certain answer; in other words, our inference is both sound and complete. This improves on previous approaches that yield sound, but always incomplete, conclusions. Further, analyzing a program takes, itself, polynomial time.

This is joint work with Neil Jones (Copenhagen) and Lars Kristiansen (Oslo).

In recent years there has been a growing interest in bridging Game Theory and Cryptography. While the standard Cryptographic settings view players as either totally honest or arbitrarily malicious, Game Theory assumes that players are rational, selfish individuals. Designing protocols for such settings poses new challenges. We investigate rational versions of two classical problems in foundations of cryptography: secret sharing and function evaluation. We show that schemes for these tasks, in which players' values come from a bounded domain, cannot satisfy some of the most desirable properties. In contrast, we suggest protocols for rational secret sharing where the shares come from an unbounded domain, but have a finite expectation.

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.