October – 2007 ^November

The Asynchronous Backtracking algorithm is considered the state of the art algorithm for solving Distributed Constraint Satisfaction Problems. A strong assumption of all previous studies of this algorithm is that a static order is required for its correctness and completeness when polynomial space is used. In the present study, an algorithm that performs asynchronous backtracking on distributed CSPs, with dynamic ordering of agents was presented, ABT_DO. Agents propose reorderings of lower priority agents and send these proposals whenever they send assignment messages. The dynamic ordered asynchronous backtracking algorithm uses polynomial space, similarly to standard ABT. The ABT_DO algorithm with three different ordering heuristics was compared to standard ABT on randomly generated DisCSPs. A Nogood-triggered heuristic,inspired by dynamic backtracking, was found to outperform static order ABT by a large factor in run-time and improve the network load. A further investigation of this successful heuristic shows the relation between it and the Min-Domain property. This relation was brought to an extreme in a later study in which a Retroactive ordering heuristic improved the run of both distributed and centralized algorithms. The improvement on structured realistic problems was much larger than on random problems.

Symmetry and self-similarity is the cornerstone of Nature, exhibiting itself through the shapes of natural creations and omnipresent laws of physics. Since many natural objects are symmetric, the absence of symmetry can often be an indication of some anomaly or abnormal behavior. Therefore, detection of asymmetries is important in numerous practical applications, including crystallography, medical imaging, and face recognition, to mention a few. Conversely, the assumption of underlying shape symmetry can facilitate many problems in shape reconstruction and analysis. Traditionally, symmetries are described as extrinsic geometric properties of the shape. While being adequate for rigid shapes, such a description is inappropriate for non-rigid ones. Extrinsic symmetry can be broken as a result of shape deformations, while its intrinsic symmetry is preserved. We pose the problem of finding intrinsic symmetries of non-rigid shapes and propose an efficient method for their computation.

*Research under the supervision of Prof. Ron Kimmel, in collaboration with Dr. Alex Bronstein and Dr. Michael Bronstein.

The talk will be on Geometric Spanners with Small Chromatic number. Two variants of this problem will be discussed

Variant 1: Given a complete k-partite geometric graph K whose vertex set is a set of n points in $\R^d$, compute a spanner of K that has a "small" stretch factor and "few" edges. We present two algorithms for this problem. The first algorithm computes a $(5+\epsilon)$-spanner of K with $O(n)$ edges in $O(n \log n)$ time. The second algorithm computes a $(3 + \epsilon)$-spanner of $K$ with $O(n log n)$ edges in $O(n \log n)$ time. The latter result is optimal: We show that there exist complete k-partite geometric graphs K such that every subgraph of K with a subquadratic number of edges has stretch factor at least 3.

Variant 2: Given an integer $k > 1$, we consider the problem of computing the smallest real number $t(k)$ such that for each set $P$ of points in the plane, there exists a $t(k)$-spanner for $P$ that has a chromatic number at most $k$. We prove that $t(2) = 3$, $t(3) = 2$, $t(4) = \sqrt{2}$, and give upper and lower bounds on $t(k)$ for $k>4$. We also show that for any $\epsilon >0$, there exists a $(1+\epsilon)t(k)$-spanner for $P$ that has $O(|P|)$ edges and whose chromatic number is at most $k$. We also consider an on-line variant of the problem, in which the points of $P$ are given one after another, and the color of a point must be decided at the moment the point is given.