Catálogo de publicaciones - libros

In the last couple of decades, network connected systems have gradually replaced centralized parallel computing machines. To provide smooth operation of network applications, the underlying system has to provide so-called . One of the most crucial services is to provide a transparent access to data like variables, databases, memory pages, or .les, which are shared by the instances of programs running at nodes of the network.

Knot theory emerged in the nineteenth century for needs of physics and chemistry as these needs were understood those days. After that the interest of physicists and chemists was lost for about a century. Nowadays knot theory has made a comeback. Knot theory and other areas of topology are no more considered as abstract areas of classical mathematics remote from anything of practical interest. They have made deep impact on quantum field theory, quantum computation and complexity of computation.

A sequential algorithm just follows its instructions and thus cannot make a nondeterministic choice all by itself, but it can be instructed to solicit outside help to make a choice. Similarly, an object-oriented program cannot create a new object all by itself; a create-a-new-object command solicits outside help. These are but two examples of intra-step interaction of an algorithm with its environment. Here we motivate and survey recent work on interactive algorithms within the Behavioral Computation Theory project.

Membrane computing is a branch of molecular computing that aims to develop models and paradigms that are biologically motivated. It identifies an unconventional computing model, namely a P system, from natural phenomena of cell evolutions and chemical reactions. Because of the nature of maximal parallelism inherent in the model, P systems have a great potential for implementing massively concurrent systems in an efficient way that would allow us to solve currently intractable problems (in much the same way as the promise of quantum and DNA computing) once future bio-technology (or silicon-technology) gives way to a practical bio-realization (or chip realization). Here we report on recent results that answer some interesting and fundamental open questions in the field. These concern computational issues such as determinism versus nondeterminism, membrane and alphabet-size hierarchies, and various notions of parallelism.

A substantial amount of research in graph theory continues to concentrate on the existence of hamiltonian cycles and perfect matchings. A classic theorem of Dirac states that a sufficient condition for an -vertex graph to be hamiltonian, and thus, for even, to have a perfect matching, is that the minimum degree is at least /2. Moreover, there are obvious counterexamples showing that this is best possible.

In the -party simultaneous message model, –1 parties holding respectively ,, ⋯, wish to compute the value of some boolean function (,,..., ), by each sending a stochastically chosen message to a -th party, the , who then decides on the value of with probability at least 2/3 of being correct. Let () be the minimum number of total communication bits needed to compute by any such algorithm.

The (,)- is defined by (,,...,) = 1, if and only if ⊕=0 (where are -bit strings). It is well known that, for any fixed ≥ 3, , and that the bound is tight for =3. It is an interesting open question whether the bound is tight for >3. In this talk we present some new results on this question. Specifically, we prove that the above bound is tight in the , in which all the transmitted message bits are linear functions of the input bits. We also discuss ’s quantum communication complexity, which also has received considerable attention in recent years.

Parity games and their subclasses and variants pop up in various contexts: -calculus, tree automata, program verification [3,1,8]. Such games provide only binary information indicating the winning player. However, in classical games theory [12] the emphasis is rather on how much we win or lose. Can we incorporate the information about the profits and losses into parity games?

Schaefer proved in 1978 that the Boolean constraint satisfaction problem for a given constraint language is either in P or is NP-complete, and identified all tractable cases. Schaefer’s dichotomy theorem actually shows that there are at most two constraint satisfaction problems, up to polynomial-time isomorphism (and these isomorphism types are distinct if and only if P ≠ NP). We show that if one considers AC isomorphisms, then there are exactly six isomorphism types (assuming that the complexity classes NP, P, ⊕L, NL, and L are all distinct).

Semi-algebraic objects are subsets or functions that can be described by finite boolean combinations of polynomials with real coefficients. In this paper we provide sharp estimates for the the precision and the number of trials needed in the MonteCarlo integration method to achieve a given error with a fixed confidence when approximating the mean value of semi-algebraic functions. Our study extends to the functional case the results of P. Koiran ([7]) for approximating the volume of semi-algebraic sets.

We study the computational complexity of deciding the existence of a Pure Nash Equilibrium in multi-player strategic games. We address two fundamental questions: how can we represent a game? and how can we represent a game with polynomial pay-off functions? Our results show that the computational complexity of deciding the existence of a pure Nash equilibrium in a strategic game depends on two parameters: the number of players and the size of the sets of strategies. In particular we show that deciding the existence of a Nash equilibrium in a strategic game is NP-complete when the number of players is large and the number of strategies for each player is constant, while the problem is Σ-complete when the number of players is a constant and the size of the sets of strategies is exponential (with respect to the length of the strategies).