^January February – 2010 ^March

Images taken through a medium may suffer from poor visibility and loss > of contrast. Light passing through undergoes absorption and > scattering. Wavelength dependent attenuation causes changes in color > and brightness. In addition, light that is scattered back from the > medium into the camera (backscatter) veils the object, degrading > visibility and contrast. Low signal to noise ratio imposes resolution > limits, even if there is no blur. Moreover, refraction between the > medium and the camera (in air) causes geometric distortions that harm > geometric reconstruction. Nevertheless, there is a strong need to > perform vision tasks in such media. Thus, in this work, we look both > at photometric and geometrical aspects of imaging in these conditions. > > In the talk I give an overview of our contributions in this subject: > - Resolution limits imposed by noise > - Geometry limits: The non-single viewpoint nature of imaging systems > looking into water through a flat glass. > - Polarization-based removal of backscatter. > All the above is demonstrated in field experiments underwater and in haze. > > * A PhD research under the supervision of Prof. Yoav Y. Schechner > > >

Many businesses offer their services to customers via Web-based application interfaces. Reasoning about execution flows of such applications is extremely valuable for companies: it can be used to optimize business processes, employ targeted advertisements, reduce operational costs, and ultimately increase competitiveness. Such reasoning often operates in an environment inducing partial information and uncertainty of various flavors. First, the execution traces recorded for a Web application often contain only partial information on the activities that were performed at run-time, due to confidentiality, lack of storage space, etc. Second, even in the presence of fully detailed traces of the past executions, prediction of future executions may still operate under terms of uncertainty. This is because executions often depend on unknown external parameters, such as users behavior, interaction with other applications, servers response time, etc.

In this talk I will consider (1) models for capturing Web applications and their executions. These models are expressive enough to capture common scenarios, while restrictive enough to allow for efficient query evaluation; (2) query evaluation algorithms over applications/execution traces under these models, and (3) practical implementations, e.g. for recommending navigation flows within web applications.

A democratic election is a classic example of a task in which multiple adversarial parties must collaborate and agree on an outcome. Traditional election systems (such as the one used in Israel) employ various means to ensure that the result will be accurate even if some of the people involved are corrupt or dishonest. However, the final tally is only as trustworthy as the people who count the votes. Even in the most secure systems these are usually fairly small committees. If an entire committee colludes, they can manufacture their own results. Even worse, depending on the exact setup, it may be feasible to stuff ballot boxes, destroy votes or perform other manipulations.

Using cryptographic techniques, it is possible to design a fair voting system whose correct operation can be verified by anyone, while still retaining ballot secrecy. This can be done even if the computers used to run the election are untrustworthy.

In the talk, I will briefly survey the techniques used to accomplish this and present in more detail examples with some unique properties, such as a practical solution for securely tallying Single Transferable Vote elections (a ranked voting system that is used in Australia, Ireland and Malta, among others). The talk will contain any necessary cryptographic background.

If time permits, I will also give a brief introduction to the Qilin project, a Java SDK for rapid prototyping of cryptographic protocols. The purpose of the Qilin project is to make it easier to build practical implementations of new cryptographic protocols, such as those for cryptographic voting. To this end, the API attempts to use the concepts and language from the theory of cryptography. The SDK is open-sourced and available on the web.

Based on joint works with Moni Naor and with Josh Benaloh, Lee Naish, Kim Ramchen and Vanessa Teague.

The Multiscale method is a class of algorithmic techniques for solving efficiently and effectively large-scale computational and optimization problems. This method was originally invented for solving elliptic partial differential equations and up to now it represents the most effective class of numerical algorithms for them. During the last two decades, there were many successful attempts to adapt the multiscale method for combinatorial optimization problems. Whereas the variety of continuous systems' multiscale algorithms turned into a separate field of applied mathematics, for combinatorial optimization problems they still have not reached an advanced stage of development, consisting in practice of a very limited number of multiscale techniques. In the first part of this talk we formulate the principles of designing multiscale algorithms for combinatorial optimization problems defined on a simple graph model. We present the results for the k-partitioning and a variety of linear ordering functionals (minimum linear arrangement/2-sum/bandwidth/workbound/wavefront sum). Since our algorithms were developed for practical purposes we compared them to many different heuristics: Spectral Sequencing, Optimally Oriented Decomposition Tree, Multilevel based, Simulated Annealing, Genetic Hillclimbing and other (including their combinations). In almost all cases we observed significant improvement of previous state-of-the-art results. We will cover a recently introduced measure of graph connectivity which can be important component of multilevel algorithms and other optimization problems on graphs.

If time permits we will present a multiscale coarsening scheme for minimizing a quadratic objective functional under planar inequality constraints. The scheme is demonstrated on a graph drawing problem in which the economical space utilization demand is evolved over the desired area rather than the widely used force-directed method, which preserves the non-overlapping property of the graph vertices. The non-overlapping property is automatically almost preserved as a result of equidensity constraints defined over the entire area. This demonstrates an ability of the algorithm to be used for solving a famous VLSI placement problem.