^November December – 2009 ^January

In 1951, John Nash proved that every game has an equilibrium, i.e. a set of strategies such that no player has an incentive to change her strategy. Nash's proof is non-constructive in nature, since it relies on Brouwer's fixed point theorem. This raises the following question - given a game, what is the computational complexity of finding a Nash equilibrium?

In this talk I will give an introduction to the area of Computing Equilibria in Algorithmic Game Theory and overview a breakthrough result suggesting that the problem of finding a Nash equilibrium is hard – Daskalakis et al. prove it is complete for the complexity class PPAD. The proof is based on a reduction from fixed point problems to finding equilibria, using small “gadget games” as means of performing arithmetic computations.

No prior knowledge is assumed.

References: C. Daskalakis, P. W. Goldberg and C. H. Papadimitriou. - The Complexity of Computing a Nash Equilibrium, SIAM Journal on Computing, 1:195-259, 2009. K. Etessami and M. Yannakakis. On the Complexity of Nash Equilibria and Other Fixed Points, - In the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007.

This talk attempts to glimpse into the field of Computational Biology, specifically through the topic of constrained sequence alignment and its applications. Introducing constraints into alignment processes facilitates improved speed and allows for fine-tuning of the alignment results. Constraints are usually a formulation of a priory knowledge regarding the expected alignment result and often originate from biological studies. We survey different types of constraints, the central approaches to constrained sequence alignment and discuss several algorithms and their applications.

A secret-sharing scheme is a mechanism for sharing data among a set of participants such that only pre-defined authorized subsets of participants can reconstruct the data, while any other subset has absolutely no information on the data. The talk will have 2 parts. In the first part, I will give some background on secret sharing schemes and introduce several simple schemes. In addition, I will discuss the connection between secret sharing and information theory. (This part is really simple) In the second part I will briefly show some results from my thesis. Specifically, the result from the paper Secret Sharing and Non-Shannon Information Inequalities  Amos Beimel and Ilan Orlov [TCC09]

the abstract of this paper follows The known secret-sharing schemes for most access structures are not efficient; even for a one-bit secret the length of the shares in the schemes is $2^{O(n)}$, where $n$ is the number of participants in the access structure. It is a long standing open problem to improve these schemes or prove that they cannot be improved. The best known lower bound is by Csirmaz (J. Cryptology 97), who proved that there exist access structures with $n$ participants such that the size of the share of at least one party is $n/ log n$ times the secret size. Csirmaz's proof uses Shannon information inequalities, which were the only information inequalities known when Csirmaz published his result. On the negative side, Csirmaz proved that by only using Shannon information inequalities one cannot prove a lower bound of $omega(n)$ on the share size. In the last decade, a sequence of non- Shannon information inequalities were discovered. This raises the hope that these inequalities can help in improving the lower bounds beyond $n$. However, in this paper we show that all the inequalities known to date cannot prove a lower bound of $omega(n)$ on the share size.

Modern software engineering heavily relies on clearly specified interfaces for separation of concerns among designers implementing components and programmers using those components. The interface of a component describes the functionality and constraints on the correct usage in a succinct manner. The need for interfaces is evident for assembling complex systems from components, but more so in modern control applications where a network of sensors and actuators is deployed to achieve complex control objectives. The notion of an interface for a control component must incorporate information about timing and resource needs, information that is not represented in current programming interfaces.

In the talk, I'll propose formal languages as an interface for resource sharing and timing. For example, imagine two components that share some resource (e.g. CPU), allocated in a time-triggered manner. With the proposed interface, each component specifies a formal language over the alphabet ${0,1}$ of ``safe schedules", i.e., if $w=w(1),w(2),…$ is in this languages, and the component gets the resource in every time slot t for which $w(t)=1$, then the component meets its performance requirements. The main advantage of this interface is that it allows modular analysis of each component and, then, constraints can be combined using languages intersection.

I'll present theoretical results concerning applications of the above approach to software control systems (where controllers are implemented by a software that shares resources). I'll also introduce a Real-Time-Java based tool, called RTComposer, that supports the proposed methodology. In RTComposer, scheduling specifications can be given as periodic tasks, or using temporal logic, or as omega-automata, or stability requirements. Components can be added dynamically, and non-real-time components are allowed. The benefits of the approach will be demonstrated and applications to wireless sensor/actuator networks based on the WirelessHART protocol and to distributed control systems based on the Control Area Network (CAN) bus (used, e.g., in automotive applications) will be discussed.