0368.2490
First Steps in Research for Excellent Students

A key to the utilization of the new multicore machines that are taking over mainstream computing is the design of scalable concurrent data structures. This lecture will discuss concurrent data structures, the challenges facing us when we attempt to make them scale, and the techniques and tools for designing them. One of the emerging tools in this area is the design and use of transactional memory, and we will show how this new algorithmic tools can be designed, and how it can be used to allow us to simply the process of data structure design.

Short genomic sequences (e.g. genes or proteins) have driven early bioinformatics research. With the advent of various high throughput bio technologies, sequences have taken a back seat. But with hundreds of complete genome sequences known (and thousands in the making), we now face new algorithmic challenges, and are able to approach questions that were inaccessible before. I will describe a number of questions and results in this field.

Fundamentals of algorithms
Semantics of programming languages
Machine reasoning
Software and hardware verification
Computational linguistics and natural language processing

The recent developments in sequencing and genotyping technologies bring a tremendous opportunity to improve our understanding of human genetics and the relation between human genetics and complex disease such as cancer or Alzheimer’s disease. I will present the recent computational and statistical methodologies that are used for the discovery of biological phenomena such as the discovery of mutations that affect diseases, or the estimation of evolutionary processes such as selection, mutation, and historical migration of populations.

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.

Biology Systems - challenges at a crossroad

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.

Quantum computing has emerged about a decade ago as a branch of theoretical computer science, with more and more connections to classical computer science. The idea is to use physical systems that follow the laws of quantum mechanics as the building block for new computing machines. Since the groundbreaking result of Shor in 1994, who showed that a quantum computer can factor numbers efficiently (and hence break many of the currently used cryptosystems) this interdisciplinary field has developed at a racing speed. In this lecture we aim to give a basic introduction to this exciting field, with examples from quantum algorithms and quantum cryptography that illustrate what quantum computers can do.

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.

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

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 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.

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 shall present major computational problems in Structural Bioinformatics and Computer Aided Drug Design such as prediction of protein-protein and protein-drug interaction and show, that from the mathematical/geometric viewpoint, they bear strong similarity to classical spatial pattern discovery tasks, such as Object Recognition in Computer Vision.
We shall show, how efficient algorithmic techniques, which have been originally developed for Computer Vision applications, have been adapted and further developed for the Bionformatics domain to solve "real life" problems, such as prediction of protein-drug interactions, modeling od large multi-molecular complexes, prediction of protein function and more.