^April May – 2004 ^June

The atomic snapshot object is an important and well-studied primitive in distributed computing. This talk will describe applications of this object, present some implementations from registers in both asycnhronous and synchronous systems, and discuss some recent lower lower bounds.

Arithmetic formulas for computing the determinant and the permanent of a matrix have been studied since the 19th century. Are there polynomial size formulas for these functions ? Although the determinant and the permanent are among the most extensively studied computational problems, polynomial size formulas for these functions are not known. An outstanding open problem in complexity theory is to prove that polynomial size formulas for these functions do not exist. Note, however, that super-polynomial lower bounds for the size of arithmetic formulas are not known for any explicit function and that questions of this type are considered to be among the most challenging open problems in theoretical computer science. I will talk about a recent solution of this problem for the subclass of multi-linear formulas.

An arithmetic formula is multi-linear if the polynomial computed by each of its sub-formulas is multi-linear, that is, in each of its monomials the power of every input variable is at most one. Multi-linear formulas are restricted, as they do not allow the intermediate use of higher powers of variables in order to finally compute a certain multi-linear function. Note, however, that for many multi-linear functions, formulas that are not multi-linear are very counter-intuitive. Note also that both the determinant and the permanent are multi-linear functions and that many of the well known formulas for these functions are multi-linear formulas.

We prove that any multi-linear arithmetic formula for the determinant or the permanent of an $n$ dimensional matrix is of size super-polynomial in $n$.

Previously, no lower bound was known (for any explicit function) even for the special case of multi-linear formulas of constant depth.

Decentralized control of a cooperative system is the problem faced by a group of decision makers who share a single global objective function. Examples of such systems include multiple-rovers missions, flexible manufacturing, collaborative robots systems, distributed systems. The difficulty in solving optimally such problems arises when the agents lack full observability of the global state of the system at execution time.

In my talk, I will identify classes of decentralized control problems whose complexity ranges between NEXP (known for the general problem) and P. No algorithms were known so far short of full search of the policy space. I will introduce the first algorithms that solve optimally certain classes of problems, where transitions and observations are independent and the system behavior may be goal-oriented.

The second part of the talk will focus on information sharing among the decision-makers, which can improve their performance. Agents can exchange information in three different ways: indirect communication, direct communication and sharing common features that are uncontrollable by the agents. The decentralized control problem is then to optimize over actions and communication. The decision makers trade-off the cost of communication with the value of the information acquired computing when it is beneficial to communicate and what information they should exchange.

Finally, I will present a general approximation scheme based on mechanism design to solve decentralized control problems with direct communication. Empirical results will be shown for two polynomial algorithms tested: myopic-greedy and backward induction. These results offer one of the first practical approaches to address the complexity of decentralized control with communication.

We consider the multilevel paradigm and its potential to aid the solution of combinatorial optimisation problems. The multilevel paradigm is a simple one, which involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found (sometimes for the original problem, sometimes the coarsest) and then iteratively refined at each level. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas. However multilevel techniques have not been widely applied to combinatorial optimisation problems. Inthis seminar we address the issue of multilevel algorithms for such problems. We have developed the multiscale algorithm for the Minimum Linear Arrangement Problem.

The Minimum Linear Arrangement problem is widely used and studied in many practical and theoretical applications. We will present a linear-time heuristics (without giving lower and upper bounds) for the problem inspired by the Algebraic Multigrid approach which is based on weighted edge contraction rather than simple contraction. Our results turned out to be better than every known result in almost all cases, while the short running time of the algorithm enabled experiments with very large graphs. Joint work with Dr. Dorit Ron and Prof. Achi Brandt.

This is the first of 2 talks presenting Wick's formula which relates matrix integrals and asymptotics of eigenvalues to simple graph based combinatorial objects which are called maps.