0368.2490
First Steps in Research for Excellent Students

In the past few years, significant progress has been made in the development of new technologies and in their use as the core of several real-time vision systems for detecting specific classes of objects, including people, faces and cars, within complex images. In this short presentation I will explore several of the more successful image representations and supervised learning algorithms that enable computers to start tackling the challenging task of image understanding

Biology Systems - challenges at a crossroad

In recent years, shape editing has been extensively studied by the geometric modeling community. In particular, research efforts have been devoted to allow the user to directly manipulate surfaces while preserving their geometric surface details.
I will present the background and some State-of-the-art geometric deformation tools and then show that they fall short at preserving the characteristic features and global structure of man-made models. I will explain the challenges and how this research thread has developed in recent years. Then I will introduce iWires, a novel approach based on the argument that man-made models can be distilled using a few special 1D wires and their mutual relations.

Experts speaking different languages wish to carry out joint projects. Every two experts have a known value for the quality of their joint work. The goal is to form disjoint groups where each group has high value and all group members can communicate directly or via other group partners who will act as translators. Mathematically, we are given a graph G=(V,E) where V is the expert set and an edge indicates a common language, and a value function S on the pairs in V, and we seek disjoint sets in V where each set induces a connected subgraph and each set has high value.
This problem is a simple formulation of an important practical problem arising in analyzing biological data: identifying gene subnetworks representing processes of high activity. Different definitions of the value lead to a variety of challenging computational problems. We shall discuss several algorithms and open problems. All the necessary biological background will be given in the lecture.

I will survey some results and open problems related to justice, envy, truth, social welfare, revenue, and auctions.
Based on joint papers with (subsets of) Edith Cohen, Haim Kaplan, Michal Feldman, Stefano Leonardi, Sveltlana Olonetsky, Piotr Sankowski, Jared Saia, Amiram Wingarten.

Cryptography studies ways of carrying out communication or computation, in the presence of adversaries that attempt to learn their content or disrupt their operation. A major line of research in cryptography has aimed to design primitives based on complexity assumptions that are as weak as possible, and to develop general paradigms to convert "somewhat secure" primitives/protocols into fully secure ones.
I will survey some recent exciting result in the this area, and mention what I see as the main open questions.

We'll take a quick tour of modern cryptography, visiting topics like Pseudorandomness, Encryption, Zero Knowledge, Secure Distributed Computation, and Program Obfuscation. We'll come across several open problems along the way.

Let R be a robot moving in an environment cluttered with obstacles. The basic motion planning problem is: "given start and (desired) goal positions for R, decide whether R can move from start to goal without colliding with the obstacles (whose geometry is known to R in the basic problem), and if so plan such a collision-free motion." The motion-planning problem has been intensively studied for several decades. We review milestone results in this study, describing how the perception of what is difficult in motion planning has changed over the years. We demonstrate how the same motion-planning techniques apply not only to common industrial robots but also to molecules, digital actors, machine parts during the assembly process, and more. We outline current research efforts, and point out major open problems in this domain.

The lecture will survey recent advances in algorithms for solving problems in numerical linear algebra, such as solving least-squares problems and eigenvalue problems. Algorithmic ideas that will be covered include randomization, graph algorithms in linear algebra, and spectral analyses.

I will present several basic problems in computational geometry and show the strong connection between the algorithmic and combinatorial aspects of these problems. I will then try to present the main ideas behind some of the techniques that are available for attacking such problems.

Error correcting codes encode information in a redundant way that is immune to limited noise. Error correcting codes are widely used in practice, e.g., in barcodes, storage devices, satellite communication and much more. In this talk we will survey some classical results (definitions, rate vs. distance) and give some examples (Hamming, Hadamard, Reed-Solomon, Reed-Muller). We will also discuss some modern variants of the problem (like list decoding and local decoding) and their relation to computational complexity (derandomization, pseudo-randomness, extractors and PCP). We will conclude with some open problems and suggested projects.

We discuss online and approximation algorithm for optimization problems and in particular for resource allocation. Approximation algorithms are usually given for problems of which we are unable to solve exactly and efficiently.
Online algorithms are provided for problems for which the input is not given in advance and the algorithm has to react at any step with partial information.

I will present some research directions in Software Engineering, and discuss the research methodologies used. I will use present and past work by our students as an illustration.

The large amount of information available on the Web is extremely useful, but also makes data management and exploitation extremely challenging. We will consider key data management issues in Web-based applications such as Recommender Systems, Crowd Computing, and Electronic Commerce and explain how advanced database technology (theory as well as applied) can be used to address these problems.