^December January – 2007 ^February

In this talk we will describe the current efforts towards defining a Semantic Web knowledge representation language. The talk will deal with the foundations of the current standard, the Web Ontology Language (OWL), its limitations, and the efforts to extend OWL with a rule-based component. We will describe the problems facing researchers who work in this area as well as their possible resolution.

Verification of safety (e.g., invariance) and liveness (e.g., termination) properties of sequential and concurrent systems has traditionally required significant manual effort. For the case of safety, the method of predicate abstraction, suggested by Graf and Saidi, has become a popular semi-manual solution. However, it is generally too weak to deal with liveness. This talk presents a method known as Ranking Abstraction, which is based on program instrumentation, predicate abstraction, and model checking. The method applies the lessons learned from predicate abstraction to the verification of liveness properties. It is then shown that, just like predicate abstraction, the method can be embedded in an refinement process, resulting in a fully automatic method. Time permitting, I will then show how the method is applied to Shape Analysis, i.e., analysis of programs that destructively manipulate heaps. Joint work with Amir Pnueli and Lenore Zuck.

An important problem in genome rearrangements is sorting permutations by transpositions. Its complexity is still open, and two rather complicated 1.5-approximation algorithms for sorting linear permutations are known (Bafna and Pevzner, Christie). In this talk, we prove that the problem of sorting circular permutations by transpositions is equivalent to the problem of sorting linear permutations by transpositions. Hence, all algorithms for sorting linear permutations by transpositions can be used to sort circular permutations. Then, we derive our main result: A new 1.5-approximation algorithm, which is considerably simpler than the previous ones, and achieves running time which is equal to the best known. The analysis of the algorithm is significantly less involved. Joint work with Ron Shamir

If time permits we will discuss briefly two subsequent studies: "A 1.375-approximation algorithm for sorting by transpositions" (with Isaac Elias), and "Matrix Tightness: A Linear-Algebraic Framework for Sorting by Transpositions" (with Elad Verbin).

The computer industry has been able to keep an exponential improvement in performance for the last few decades. This unbelievable phenomenon is known as "Moore's law". As the computer architecture industry start reaching the "power wall", two new trends are being developed; the first trend calls to trade single thread performance with multithreaded performance and so to increase the overall performance of a processor by accommodate it with large number of small cores. The second trend calls to increase both the single thread performance and the multithreaded performance and so to divide the "transistor budget" of the processor between relatively small number of "large cores".

In this talk I will present the root cause of the "power wall", I will extend the discussion on each of the new trends in computer architectures described above and provide an analysis of what is needed for each of them to succeed. I will conclude the talk with a discussion on few open research topics which I believe are important for the computer architecture industry.

Bio: Avi Mendelson is a principal engineer in Intel’s Mobile Platform Group in Haifa, Israel, and adjunct professor in the CS and EE departments, Technion – Israel Institute of Technology. He received his B.Sc. and M.S.c degrees from the Technion, Israel Institute of Technology and his Ph.D from the University of Massachusetts at Amherst. Avi has been with Intel for 7 years. He started as senior researcher in Intel Labs, later he moved to the Microprocessor group where he served as the CMP architect of Intel Core Duo. Avi's work and research interests are in computer architecture, low power design, parallel systems, OS related issues and virtualization. His e-mail address is avi.mendelson@intel.com

Shape symmetry is an important cue for image understanding. In the absence of more detailed prior shape information, segmentation can be significantly facilitated by symmetry. However, when symmetry is distorted by perspectivity, the detection of symmetry becomes non-trivial,thus complicating symmetry-aided segmentation.

We present a novel approach for segmentation of symmetrical objects accommodating perspective distortion. The key idea is the use of the replicative form induced by the symmetry for challenging segmentation tasks. This is accomplished by dynamic extraction of the object boundaries, based on the image gradients, gray levels or colors, concurrently with registration of the image symmetrical counterpart e.g. reflection) to itself. The symmetrical counterpart of the evolving object contour supports the segmentation by resolving possible ambiguities due to noise, clutter, distortion, shadows, occlusions and assimilation with the background.

The symmetry constraint is integrated in a comprehensive level-set functional for segmentation that determines the evolution of the delineating contour. The proposed framework is exemplified on various images of skew-symmetrical objects and its superiority over state of the art variational segmentation techniques is demonstrated.

Joint work with Nahum Kiryati and Nir Sochen, Tel-Aviv University

In many organizations, private data should be revealed to some people while being concealed from others. In a hospital database system, for instance, a physician should be allowed to see the medical history of her patients; however, such medical data should not be available to the public. Thus, to support research over medical data while protecting privacy, only some of the data should be accessible to researchers. A common approach for protecting privacy is to manipulate sensitive data so that private information would not be revealed (e.g., by changing data values or transforming its structure). But, such manipulations can mislead users who are not aware of them and, thus, cause errors. In my talk, I will present a novel access-control mechanism for XML that protects privacy without misleading users. XML is a primary format for exchanging and publishing data on the Internet, in which data is presented in a hierarchical format. Our model uses the hierarchal nature of XML but also guarantees that private information will not be inferred because of the hierarchy, a challenge that is not required in the relational model. The mechanism employs rules for specifying the private data, and queries are validated with respect to these rules. Only queries that do not reveal private information are authorized and executed. I will talk about the complexity of validating queries, the privacy protection provided by our approach and how to test that a set of rules provides the desired concealment. No prior knowledge of XML or privacy is required. This is a joint work with Alberto Mendelzon, Renee Miller and Zheng Zhang.