Catálogo de publicaciones - libros

The paper investigates the complexity of depth-two circuits with threshold gates and consisting of two parts.

First, we develop a method for deriving a lower bound on the size of depth two circuits with a threshold gate at the top and a certain type of gates at the bottom. We apply the method for circuits with symmetric gates at the bottom that compute the “inner product mod 2”, and obtain a lower bound of 1.3638. Although our lower bound is slightly weaker than the best known lower bound of Ω(2/), which was recently proved by Forster et al. [5,6], our method has unique features: A lower bound is obtained by solving a certain linear program, and solving larger linear programs yield higher lower bounds. We also discuss the generalization of the proposed method.

Second, we develop a simplified simulation of a depth-one threshold circuit with unbounded weights by a depth-two threshold circuit with small weights. Precisely, we give an explicit construction of depth-two circuits with small weights consist of Õ gates that compute an arbitrary threshold function. We also give the construction of such circuits with (/log ) gates computing the COMPARISON and CARRY functions, and that with (/log ) gates computing the ADDITION function. These improve the previously known constructions on its size and simplicity.

We study the isomorphic implication problem for Boolean constraints. We show that this is a natural analog of the subgraph isomorphism problem. We prove that, depending on the set of constraints, this problem is in P, NP-complete, or NP-hard, coNP-hard, and in . We show how to extend the NP-hardness and coNP-hardness to -hardness for some cases, and conjecture that this can be done in all cases.

An abstract numeration system is a triple = (,Σ,<) where (Σ,<) is a totally ordered alphabet and a regular language over Σ; the associated numeration is defined as follows: by enumerating the words of the regular language over Σ with respect to the induced genealogical ordering, one obtains a one-to-one correspondence between ℕ and . Furthermore, when the language is assumed to be exponential, real numbers can also be expanded. The aim of the present paper is to associate with a self-replicating multiple tiling of ăthe space, under the following assumption: the adjacency matrix of the trimmed minimal automaton recognizing is primitive with a dominant eigenvalue being a Pisot unit. This construction generalizes the classical constructions performed for Rauzy fractals associated with Pisot substitutions [16], and for central tiles associated with a Pisot beta-numeration [23] .

In this paper we start the study of generalizing the Adversarial Queueing Theory model towards a continuous scenario in which the usually assumed synchronicity of the evolution is not required anymore. We consider a model, named (), in which packets can have arbitrary lengths, and the network links may have different speeds (or bandwidths) and propagation delays. We show that, in such a general model, having bounded queues implies bounded end-to-end packet delays and vice versa. From the network point of view, we show that networks with directed acyclic topologies are universally stable, i.e., stable independently of the protocols and the traffic patterns used in it, and that this even holds for traffic patterns that make links to be fully loaded. Concerning packet scheduling protocols, we show that the well-known , , and protocols remain universally stable in our model. We also show that the model is strictly stronger than the model by presenting scheduling policies that are unstable under the former while they are universally stable under the latter.

Feige and Kilian [5] showed that finding reasonable approximative solutions to the coloring problem on graphs is hard. This motivates the quest for algorithms that either solve the problem in most but not all cases, but are of polynomial time complexity, or that give a correct solution on all input graphs while guaranteeing a polynomial running time on average only. An algorithm of the first kind was suggested by Alon and Kahale in [1] for the following type of random -colorable graphs: Construct a graph on vertex set of cardinality by first partitioning into equally sized sets and then adding each edge between these sets with probability independently from each other. Alon and Kahale showed that graphs from can be -colored in polynomial time with high probability as long as ≥ / for some sufficiently large constant . In this paper, we construct an algorithm with polynomial expected running time for = 3 on the same type of graphs and for the same range of . To obtain this result we modify the ideas developed by Alon and Kahale and combine them with techniques from semidefinite programming. The calculations carry over to general .

It is a well-known result that the set of reachable stack contents in a pushdown automaton is a regular set of words. We consider the more general case of higher-order pushdown automata and investigate, with a particular stress on effectiveness and complexity, the natural notion of regularity for higher-order stacks: a set of level stacks is regular if it is obtained by a regular sequence of level operations. We prove that any regular set of level stacks admits a normalized representation and we use it to show that the regular sets of a given level form an effective Boolean algebra. In fact, this notion of regularity coincides with the notion of monadic second order definability over the canonical structure associated to level stacks. Finally, we consider the link between regular sets of stacks and families of infinite graphs defined by higher-order pushdown systems.

Linearly bounded Turing machines have been mainly studied as acceptors for context-sensitive languages. We define a natural family of canonical infinite automata representing their observable computational behavior, called linearly bounded graphs. These automata naturally accept the same languages as the linearly bounded machines defining them. We present some of their structural properties as well as alternative characterizations in terms of rewriting systems and context-sensitive transductions. Finally, we compare these graphs to rational graphs, which are another family of automata accepting the context-sensitive languages, and prove that in the bounded-degree case, rational graphs are a strict sub-family of linearly bounded graphs.

We prove several results about the relations between injectivity and surjectivity for sand automata. Moreover, we begin the exploration of the dynamical behavior of sand automata proving that the property of ultimate periodicity is undecidable. We believe that the proof technique used for this last result might turn out to be useful for many other results in the same context.

A distributed system is a collection of processes that can interact. Three major process interaction models in distributed systems have principally been considered: – the message passing model, – the shared memory model, – the local computation model. In each model the processes are represented by vertices of a graph and the interactions are represented by edges. In the message passing model and the shared memory model, processes interact by communication primitives: messages can be sent along edges or atomic read/write operations can be performed on registers associated with edges. In the local computation model interactions are defined by labelled graph rewriting rules; supports of rules are edges or stars. These models (and their sub-models) reflect different system architectures, different levels of synchronization and different levels of abstraction. Understanding the power of various models, the role of structural network properties and the role of the initial knowledge enhances our understanding of basic distributed algorithms. This is done with some typical problems in distributed computing: election, naming, spanning tree construction, termination detection, network topology recognition, consensus, mutual exclusion. Furthermore, solutions to these problems constitute primitive building blocks for many other distributed algorithms. A survey may be found in [FR03], this survey presents some links with several parameters of the models including synchrony, communication media and randomization. An important goal in the study of these models is to understand some relationships between them. This paper is a contribution to this goal; more precisely we establish a bridge between tools and results presented in [YK96] for the message passing model and tools and results presented in [Ang80, BCG+96, Maz97, CM04, CMZ04, Cha05] for the local computation model.

Given a distance matrix  that specifies the pairwise evolutionary distances between species, the phylogenetic reconstruction problem asks for an edge-weighted phylogenetic tree that satisfies , if one exists. We study some extensions of this problem to rooted phylogenetic . Our main result is an ( log )-time algorithm for determining whether there is an ultrametric galled network that satisfies , and if so, constructing one. In fact, if such an ultrametric galled network exists, our algorithm is guaranteed to construct one containing the minimum possible number of nodes with more than one parent ( nodes). We also prove that finding a largest possible submatrix ′ of  such that there exists an ultrametric galled network that satisfies ′ is NP-hard. Furthermore, we show that given an incomplete distance matrix (i.e., where some matrix entries are missing), it is also NP-hard to determine whether there exists an ultrametric galled network which satisfies it.