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

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.

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

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.

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.