^October November – 2006 ^December

A mediator can help non-cooperative agents obtain an equilibrium that may otherwise not be possible. We give matching upper and lower bounds on the ability of rational agents to obtain the same equilibrium without a mediator, simply by engaging in non-binding pre-play communication, known as ``cheap talk''. Our upper bounds are based on k-resilient Nash equilibria for the secret sharing game, joint strategies where no member of a coalition of size up to k can do better, even if the whole coalition defects. Our results on implementing mediators with ``cheap talk'' reveal some connections between game theory, cryptography and distributed computing. Our upper bounds require both known and new tools in secure multi party computation. Our lower bounds require both known and new results in Byzantine fault tolerance and distributed computing. Joint work with Danny Dolev, Rica Gonen and Joe Halpern

The paradigm of Service Oriented Architectures provides a framework for dynamic Business Processes and for the emerging ideas of "programming-in-the-large". This talk addresses fundamental notions of services, in particular their proper termination and their composition, as well as the construction of (most liberal) partners, operating guidelines, (most abstract) substitutes, adapters, etc.

Finally, a feature complete semantics of the WS-BPEL language is glanced, together with techniques to analyze properties of WS-BPEL program

Combinatorial optimization heuristics are often compared with each other to determine which one performs best by means of worst-case performance ratio which reflects the quality of returned solution in the worst case. The domination number is a complement parameter indicating the > quality of the heuristic in hand by determining how many feasible solutions are dominated by the heuristic solution. We prove that the Max-Regret heuristic introduced by Balas and Saltzman finds the unique worst possible solution for some instances of the s-dimensional ($s \ge 3$) assignment problem (s-AP) and the asymmetric traveling salesman problems (ATSP) of each possible size. It was proved earlier that Greedy has the same property for ATSP and it's not difficult to show that Greedy has the same property for s-AP ($s \ge 2$). This means that the domination number of all above mentioned heuristics (for ATSP and s-AP) is 1. We show that the Triple Interchange heuristic (for $s = 3$) also introduced by Balas and Saltzman and two new heuristics (Part and Recursive Opt Matching) have factorial domination numbers for s-AP ($s \ge 3$). ATSP heuristics of factorial domination number will also be discussed

We show that unless $\NP \subseteq \RTIME (2^{\poly(\log{n})})$, the Shortest Vector Problem (SVP) on n-dimensional lattices in the $l_p$ norm is hard to approximate in polynomial-time to within almost polynomial factors. This improves the previous best factor of $2^{(\log{n})^{1/2-\eps}}$ under the same complexity assumption due to Khot [Khot05]. Our proof starts with SVP instances from [Khot05] that are hard to approximate to within some constant. To boost the hardness factor we simply apply the standard tensor product of lattices. The main novel part is in the analysis, where we show that the lattices of [Khot05] behave nicely under tensorization. At the heart of the analysis is a certain matrix inequality which was first used in the context of lattices by de Shalit [deShalit06].

Joint work with Oded Regev.

In this talk we give upper bounds for the number of vertices of the polyhedron $P(A,b)=\{x\in \mathbb{R}^d~:~Ax\leq b\}$ when the $m\times d$ constraint matrix $A$ is subjected to certain restriction. For instance, if $A$ is a 0/1-matrix, then there can be at most $d!$ vertices and this bound is tight, or if the entries of $A$ are non-negative integers so that each row sums to at most $C$, then there can be at most $C^d$ vertices. These bounds are consequences of a more general theorem that the number of vertices of $P(A,b)$ is at most $d!\cdot W/D$, where $W$ is the volume of the convex hull of the zero vector and the row vectors of $A$, and $D$ is the smallest absolute value of any non-zero $d\times d$ subdeterminant of $A$.