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

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.

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.