[LOGO] Abstracts of Talks

The Weizmann CS Research Day for Prospective Students


Speaker: Robi Krauthgamer
Title: Similarity searching, or how to find your neighbors efficiently

Abstract: I will present a few recurring themes in the design of efficient algorithms for analyzing data which is (often) represented by high-dimensional vectors. The topics to be discussed include exploiting "intrinsic low-dimensionality" of the data, and metric embedding as an algorithmic technique.

Speaker: Anat Levin
Title: Computational Photography

Abstract: The digital-photography revolution dramatically simplified how we take and share pictures. Yet, digital photography sticks mostly to the rigid imaging model inherited from traditional photography. The emerging field of computational photography goes one step further and exploits digital technology to enable arbitrary computation between the light array and the final image or video. These computations dictate certain aspects of the camera design, vastly expanding the amount and types of information that can be obtained from the picture during image processing. In this talk I will describe two of our recent projects in the field.

The first one is the coded aperture camera, in which we selectively block incoming light rays by inserting a coding pattern into the aperture of a conventional lens. This simple change has made it possible to calculate depth from a single shot. The idea is to change the defocus patterns at different depths and made them extremely discriminative to depth variations.

In the second part I will show how one of the classical photography challenges- motion blur, can be significantly simplified with a simple change in the capturing process. In this design we deliberately move the camera along a specially designed path during exposure, introducing intentional blur. However, the blur pattern is made completely invariant to the object motion, thereby eliminating the highly challenging task of segmenting the moving objects in the scene or estimating their velocity.

Speaker: Oded Goldreich
Title: Probabilistic Proof Systems

Abstract: Various types of probabilistic proof systems have played a central role in the development of computer science in the last couple of decades. These proof systems deviate from the traditional concept of a proof by introducing randomization and interaction into the verification process. Probabilistic proof systems carry an error probability (which is explicitly bounded and can be decreased by repetitions), but they offer various advantages over deterministic proof systems.

This lecture concentrates on three types of probabilistic proof systems: interactive proofs, zero-knowledge proofs, and probabilistically checkable proofs (PCPs). Surveying the basic results regarding these proof systems, we stress the essential role of randomness in each of them. The following talk by Irit Dinur will focus on PCPs and provide much more details on them.

Speaker: Irit Dinur
Title: Probabilistically Checkable Proofs

Abstract: NP is the class of problems whose solutions are easy to verify. How easy? Do we need to even read the entire solution? It turns out that if the purported solution is written a special "PCP" format then we don't have to read the entire solution. We can do a good job by reading as few as three bits of the solution! In my talk I will talk about the PCP theorem which proves the above, and  consequences to hardness of approximation.