^May June – 2006 ^July

This talk presents BPQL, a novel graphical query language for querying Business Processes, implemented as a set of cooperating web services. BPQL 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 visually, in a manner 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). The talk describes the query language as well as its underlying formal model. Special emphasis is given to the following subjects: (a) The analogy between the specification and querying of business processes, and (b) the use of graph grammars to represent potentially infinite query results by a finite and concise representation. The current implementation, using Active XML and Web services is briefly described.

We study the problem of the amount of information about a network that must be known in order to efficiently accomplish an exploration or communication task. While previous results about exploration and communication in networks assumed particular partial information, such as the knowledge of the neighborhood, the knowledge of the network topology within some radius, or a partial map of the network, our approach is quantitative: we investigate the minimum total number of bits of information (minimum oracle size) that has to be known in order to perform efficient exploration or communication.

We present the approach by oracles on the examples of two problems. The first is exploration, a fundamental problem in mobile computing: a mobile agent has to traverse all edges of a network. The second is information dissemination, one of the basic communication primitives: a message held in one node of the network, called the source, has to be transmitted to all other nodes. If no restrictions are imposed, information dissemination is called broadcast. If only nodes that already got the source message can transmit, it is called wakeup.

For the exploration task we establish the minimum oracle size permitting exploration with competitive ratio below 2. For communication we show that the minimum oracle size to perform wakeup with a linear number of messages in an $n$-node network, is $\Theta (n \log n)$, while the broadcast with a linear number of messages can be achieved with an oracle of size $O(n)$. Thus an efficient wakeup requires strictly more information about the network than an efficient broadcast.

This is joint work with Pierre Fraigniaud and David Ilcinkas

It is often useful to formulate problems in vision and in computational biology as energy minimization problems. For many of these problems, finding the global optimum is NP hard and researchers have focused on approximation methods. From an application standpoint, using approximations is problematic because when things fail we don't know whom to blame - the energy function or the approximate minimization.

In this talk I will describe our recent successes in finding the GLOBAL optimum for energy functions in stereo vision, side chain prediction and protein design. Our approach is based on a classical technique - linear programming (LP) relaxations, but with a novel twist - we use a variant of belief propagation to solve the LP relaxation. By using belief propagation, we can find the global optimum for large, real-world problems in a few minutes.

Joint work with Talya Meltzer and Chen Yanover

We show that several discrete random processes, which arise in diverse disciplines can be asymptotically analyzed via the notion of a causal set which is a discrete analogue of a spacetime (Lorentzian) geometry. We then consider applicatiions to airplane boarding and some problems in pattern recognition.

Some of this work is joint with D. Berend, L. Sapir, S. Skiena and M. Elkin.