^March April – 2008 ^May

Visual texture segregation is the perceptual phenomenon in which perceptually coherent regions can be discriminated solely on the basis of texture information (rather than by their color, luminance, etc…). A central notion in the study of texture segregation is the one of feature gradient (or feature contrast). Indeed, perceptual boundaries in texture stimuli occur where texture features (such as orientation) vary drastically within small spatial distances. However, recent work has shown that salient perceptual singularities occur in visual textures even in the absence of feature gradients. In particular, in smoothly varying orientation-defined textures (ODTs) these non-smooth percepts can be predicted from a differential measure involving two texture curvatures, one tangential and one normal (Ben-Shahar 2006). Based on this recent theory, in this work, we devise a biologically-plausible algorithm for detecting perceptual singularities in images of orientation-defined textures. The model uses a three-layer circuit in which both even-symmetric cells and odd-symmetric cells are used to compute all possible directional derivatives of the dominant orientation, from which the tangential and normal curvatures at each spatial position are selected using non linear shunting inhibition. We present result of this biologically plausible model on ODT images and discuss how this model may be extended to handling general textures and natural images.

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.

We show that for every $n$-point metric space $M$ there exists a spanning tree $T$ with unweighted diameter $O(log n)$ and weight $omega(T) = O! (log n) cdot omega(MST(M))$. Moreover, there is a designated point $rt$ such that for every point $v$, $dist_T(rt,v) le (1+epsilon) cdot dist_M(rt,v)$, for an arbitrarily small constant $epsilon > 0$. We extend this result, and provide a tradeoff between unweighted diameter and weight, and prove that this tradeoff is emph{tight up to constant factors} in the entire range of parameters. These results enable us to settle a long-standing open question in Computational Geometry. In STOC'95 Arya et al. devised a construction of Euclidean Spanners with unweighted diameter $O(log n)$ and weight $O(log n) cdot omega(MST(M))$. Ten years later in SODA'05 Agarwal et al. showed that this result is tight up to a factor of $O(log log n)$. We close this gap and show that the result of Arya et al. is tight up to constant factors. Joint work with Yefim Dinitz and Michael Elkin.

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]

The Internet is an indispensable part of our society, and yet its basic foundations remain vulnerable to simple attacks. In recent years, the networking community has considered a variety of proposals for securing Internet routing; path-quality monitoring is a crucial component of many of these proposals.

In this talk, we give a rigorous treatment of the path-quality monitoring problem. We consider protocols that allow a router to robustly raise an alarm when packet loss and delay exceeds some threshold, even when an adversary tries to bias monitoring results. Despite the strong threat model we considered, we develop secure protocols that efficient enough to be deployed in the highly constrained environment of high-speed routers. We present a simple protocol that combines sketching techniques with ideas from cryptography and requires O(log T) storage in order to monitor T packets sent on an Internet data path; e.g., monitoring billions of packets requires only 200-600 bytes of storage and a single IP packet of communication. We then show how to compose instances of this protocol to obtain a protocol that localizes faulty or malfunctioning links on a data path.

This is joint work with David Xiao, Eran Tromer, Boaz Barak, and Jennifer Rexford.

Sensors are small, low-cost resource limited processors with sensing abilities. Sensor networks are wireless ad-hoc networks of sensors collaborating on a mission. In this talk I will briefly describe the first two parts of my thesis and elaborate on the third one. The first part suggests a polygonal based model as an ad-hoc infrastructure for a implementing basic tasks in sensor networks; such as, broadcast, sense of direction and simultaneous activation. The second part suggests a unique-permutation hash function as an efficient implementation of a home location service application for tracking a mobile node.

This application is built on top of a Virtual Stationary Automata (VSA) layer. Finally, I will elaborate on my latest work "Swarm Unit - Reactive k-Secret Sharing". Motivated by the virtual automata abstraction and swarm computing, we investigate an extension of the $k$-secret sharing scheme, in which the secret shares are changed on the fly, independently and without (internal) communication, as a reaction to a global external trigger. The changes are made while maintaining the requirement that $k$ or more secret shares may reconstruct the secret and no $k-1$ or fewer can do so. The application considered is a swarm of mobile processes, each maintaining a share of the secret which may change according to common outside inputs e.g., inputs received by sensors attached to the process. The proposed schemes support addition and removal of processes from the swarm as well as corruption of a small portion of the processes in the swarm. hash function as an efficient implementation of a home location service application for tracking a mobile node.

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