^March April – 2008 ^May

Design by contract is a practical methodology for developing code together with its specification. It enhances code quality in several significant ways. It is an integral part of the Eiffel language, but is little used outside that community. A major reason for that is the lack of tools supporting the methodology in other languages. In this talk I will describe several tools that support design by contract in Java. One tool instruments Java programs with their contracts for runtime checking. Another is an Eclipse plugin that refactors programs with their contracts, modifying the contracts as well as using them to check the correctness of the proposed transformations. A third tool attempts to discover draft contracts for existing code, enabling the use of the methodology for code originally developed without contracts.

Wireless networks are particularly susceptible to malicious and malfunctioning devices. For example, a malicious device can easily jam the airwaves, disrupting all communication. In this talk, I will present new techniques for overcoming network disruptions in wireless networks, specifically in the context of multi-channel networks. In order to provide some intuition as to the challenges posed by malicious disruption, I will begin by demonstrating a lower bound for oblivious gossip algorithms. (Underlying the lower bound proof lies an interesting connection between epsilon-gossip and extremal graph theory.) I will then present an adaptive algorithm that improves on the lower bound, relying on a new combinatorial tool, the multiselector (which, as a natural generalization of a selector, we believe to be of potentially independent interest). Finally, I will present a randomized algorithm that can tolerate even more severe forms of malicious misbehavior. Joint work with Shlomi Dolev, Rachid Guerraoui, Darek Kowalski and Calvin Newport

An out-tree T in a digraph D is subgraph of D which is an orientation of a tree that has only one vertex of in-degree 0 (root). A vertex of T is a leaf if it has out-degree 0. A spanning out-tree is called an out-branching. We overview the following recent results:

• the problem of finding an out-branching with minimum number of leaves is polynomial-time solvable for acyclic digraphs (it is NP-hard for general digraphs) [Gutin, Kim, Razgon, 2008]
• the problem of finding an out-branching with at least k non-leaves is fixed-parameter tractable (FPT) [Gutin, Kim, Razgon, 2008]
• the problem of finding an out-tree with at least k leaves is FPT [Alon, Fomin, Gutin, Krivelevich, Saurabh, 2007]
• the problem of finding an out-branching with at least k leaves is FPT [Bonsma and Dorn, 2007]

This talk describes a research project exploring new ways for augmenting search using multiple types and sources of social information. Our goal is to allow searching for all object types such as documents, persons and tags, while also retrieving related objects of all types. To realize this goal, we implemented a social-search engine using a unified approach. In this approach, the search space is expanded to represent heterogeneous information objects that are interrelated by several relation types. Our novel solution is based on multifaceted search and it provides an efficient update mechanism for relations between objects, as well as efficient search over the heterogeneous data. We describe a social search engine positioned within a large enterprise, applied over social data gathered from several Web 2.0 applications. We conducted a large user study with over 600 people to evaluate the contribution of social data for search. Our results demonstrate the high precision of social search results and confirm the strong relationship of users to the topics they were retrieved for. Joint work with Einat Amitay, David Carmel, Nadav Golbandi, Nadav Har'El and Shila Ofek-Koifman