^November December – 2007 ^January

In this talk we present BP-QL, a novel system for querying and monitoring business processes. The BP-QL query language is based on an intuitive model of business processes, an abstraction of the emerging BPEL (Business Process Execution Language) standard. It allows users to query business processes specifications, as well as their run time behavior, visually, in a manner very analogous to how such processes are typically specified, and can be employed in a distributed setting, where process components may be provided by distinct providers (peers).

We describe here the query language as well as its underlying formal model. We consider the properties of the various language components and explain how they influenced the language design. In particular we distinguish features that can be efficiently supported, and those that incur a prohibitively high cost, or cannot be computed at all. We also present our implementation which complies with real life standards for business process specifications, XML, and Web services, and is used in the BPQL system.

One of the surprising developments in the area of program verification is how several ideas introduced by logicians in the first part of the 20th century ended up yielding at the start of the 21st century an industrial-standard property-specification language called PSL. This development was enabled by the equally unlikely transformation of the mathematical machinery of automata on infinite words, introduced in the early 1960s for second-order arithmetics, into effective algorithms for model-checking tools. This talk attempts to trace the tangled threads of this development.

This research concerns the image deblurring and noise removal problem in a variational framework. Energy functionals in this study consist of a fidelity term and a regularizer that is based on Mumford-Shah segmentation, such that the recovered image and its discontinuities set are simultaneously extracted in the course of the deblurring process. The functionals are formulated using the Gamma-convergence approximation and are iteratively optimized via the alternate minimization method. We first consider the image deblurring problem in the presence of Gaussian/impulsive noise. The suggested approach integrates and extends the robust statistics, anisotropic diffusion and line process (half quadratic) points of view. Then, we extend the deblurring and denoising problem to vectorvalued images. Further, we present the shift-variant deblurring case following by simultaneous motion estimation and restoration of motion-blurred video.

In this talk, I will give an overview of several recent results of mine in computer vision and computational geometry. Within the realm of computer vision, I will focus on applications of partial differential equations (curve and surface flows) and combinatorial optimization to segmentation, tracking, and optical flow. Within computational geometry, I will discuss results on manifold reconstruction from unorganized points, as well as computational algebraic topology, in particular the measurement of homology. These results may be applied to the study of shape.

The field of Augmentative and Alternative Communication (AAC) is concerned with studying methods of communication that can be added to natural communication (speech and writing), especially when an individual lacks some of the skills to achieve it. Natural language processing techniques have been used for AAC applications to enhance the rate of communication and extend the range of expressions that can be generated. The key applications include message generation, abbreviation expansion, word prediction and text simplification. In my talk I will present the world of AAC, the usage of NLP within AAC, and specifically natural language generation systems including the one developed in BGU.

There is an intrinsic connection between computational geometry and networking. In this talk I will describe theoretical results in computational geometry with practical implications in networking. More specifically, I will first present a new construction of geometric spanners that allows optimal routing between points in the plane. In the second part of the talk I will describe the first construction ever of a disk graph spanner. The practical importance of the later is enormous as it can serve as a topology for ad-hoc networks whose nodes have a *variable* transmission range.

The talk is based on the following papers:

1. Improved Algorithms for Fully Dynamic Geometric Spanners Lee-Ad Gottlieb (NYU) and Liam Roditty

2. Spanners for Ad Hoc Networks with Variable Transmission Range David Peleg (Weizmann) and Liam Roditty

The most popular object-oriented programming (OOP) languages nowadays - Java, C++, C# - are statically-typed and based on a static model. They do not allow to manipulate their classes at run-time. As a result, many programmers view OOP as a methodology with limited flexibility and expressiveness. OOP languages do not have to be static. Several new scripting languages break this rule by implementing a highly dynamic and flexible version of OOP. These are dynamically-typed languages that allow to manipulate objects and classes at run-time. This ability gives a lot of flexibility to the programmer, and those languages are gaining much popularity.

One of the more impressive and useful usages of this approach is the implementation of a meta-classes system in Python. Meta-classes are classes that create other classes as their instances. Using meta-classes lets programmers implement design patterns and aspect-oriented programming by using the programming language itself, giving a higher level of expressiveness and code re-use. In this talk I will give a short introduction to those new approaches in OOP, and present meta-OOP programming in Python, with its powers and problems.

Revenue from electronic commerce and Internet-based advertising has been growing exponentially in the last decade, hand in hand with the birth of large-scale marketplaces (e.g., eBay and Amazon), information providers ( e.g., Google and Yahoo) and web-based social networks (e.g., MySpace and Facebook). Participants in such systems have access to information that is known only to them (like how much buyers are willing to pay for commodities), and economic mechanisms are designed to gather sufficient information for computing the desired outcomes. Complex communication protocols are often required in order to achieve good results, whereas practical and behavioral reasons encourage the use of simple communication exchanges.

This talk will survey several results characterizing tradeoffs between the simplicity of markets and their achievable economic properties. On the positive side, nearly optimal markets exist even when the agents have restricted expressive power. On the negative side, we show that the communication overhead of computing equilibrium-supporting prices may be significant. Finally, we show that simple pricing schemes cannot support close-to-optimal results in ascending-price multi-unit auctions.

Based on joint works with Moshe Babaioff, Michal Feldman, Moni Naor, Noam Nisan, Michael Schapira and Ilya Segal.

We study the round complexity of various cryptographic protocols. Our main result is a tight lower bound on the round complexity of any fully-black-box construction of a statistically-hiding commitment scheme from one-way permutations, and even from trapdoor permutations. This lower bound matches the round complexity of the statistically-hiding commitment scheme due to Naor, Ostrovsky, Venkatesan and Yung (CRYPTO '92). As a corollary, we derive similar tight lower bounds for several other cryptographic protocols, such as single-server private information retrieval, interactive hashing, and oblivious transfer that guarantees statistical security for one of the parties. Our techniques extend the collision-finding oracle due to Simon (EUROCRYPT '98) to the setting of interactive protocols (our extension also implies an alternative proof for the main property of the original oracle). In addition, we substantially extend the reconstruction paradigm of Gennaro and Trevisan (FOCS `00). In both cases, our extensions are quite delicate and may be found useful in proving additional black-box separation results. Joint work with Jonathan J. Hoch, Gil Segev and Omer Reingold

The Computational Geometry Algorithms Library, CGAL, is the largest software collection of algorithms and data structures in Computational Geometry available today. It started a little over a decade ago as a European research project with a small number of partners and has grown over the years to be a huge open source project. The arrangement package of CGAL, developed at Tel Aviv University, constructs, maintains, traverses, and answers queries on two-dimensional arrangements (subdivisions) of general curves. We will start with a bird's eye view of the overall project, and then briefly present the underlying design principles of the arrangement package. The talk will mostly focus on recent innovations and applications of the arrangement package, including the construction of: general 2D Voronoi diagrams, envelopes of surfaces in three-dimensional space, Boolean set operations for generalized (curved) polygons, and more.

The new components that we will review were developed by Efi Fogel, Michal Meyerovitch, Ophir Setter, Ron Wein, and Baruch Zukerman.