STACS 2006

The

digital tree

also known as

trie

made its first appearance as a general-purpose data structure in the late 1950’s. Its principle is a recursive partitioning based on successive bits or digits of data items. Under various guises, it has then surfaced in the management of very large data bases, in the design of efficient communication protocols, in quantitative data mining, in the leader election problem of distributed computing, in data compression, as well as in some corners of computational geometry. The algorithms are invariably very simple, easy to implement, and in a number of cases surprisingly efficient. The corresponding quantitative analyses pose challenging mathematical problems and have triggered a flurry of research works. Generating functions and symbolic methods, singularity analysis, the saddle-point method, transfer operators of dynamical systems theory, and the Mellin transform have all been found to have a bearing on the probabilistic behaviour of trie algorithms. We offer here a perspective on the rich algorithmic, analytic, and probabilistic aspects of tries, culminating with a connection between a sorting problem and the Riemann hypothesis.

We consider asynchronous dynamic networks of identical finite (independent of the network size) automata. A useful data structure on such networks is a partial

orientation

of its edges. It needs to be

straight

, i.e. have null holonomy (the difference between the number of up and down edges in each cycle). It also needs to be

centered

, i.e., have a unique node with no down edges. Using such orientation, any feasible computational task can be efficiently implemented with self-stabilization and synchronization. There are (interdependent) self-stabilizing asynchronous finite automata protocols that straighten and centralize any orientation. Such protocols may vary in assorted efficiency parameters and it is desirable to have each replaceable with any alternative responsible for a simple limited task. We describe an efficient reduction of any computational task to any set of such protocols compliant with our interface conditions.

Since programming languages are Turing complete, it is impossible to decide for all programs whether a given non-trivial semantic property is valid or not. The way-out chosen by abstract interpretation is to provide

approximate

methods which may fail to certify a program property on some programs. Precision of the analysis can be measured by providing classes of programs for which the analysis is complete, i.e., decides the property in question. Here, we consider analyses of polynomial identities between integer variables such as

x

1

.

x

2

− 2

x

3 = 0. We describe current approaches and clarify their completeness properties. We also present an extension of our approach based on weakest precondition computations to programs with procedures and equality guards.

We give a randomized algorithm for sorting strings in external memory. For

K

binary strings comprising

N

words in total, our algorithm finds the sorted order and the longest common prefix sequence of the strings using

$O(\frac{K}{B}log_{M/B}(\frac{K}{M})log(\frac{N}{K}) + \frac{N}{B})$

I/Os. This bound is never worse than

$O(\frac{K}{B}log_{M/B}(\frac{K}{M})log log_{M/B}(\frac{K}{M}) + \frac{N}{B})$

I/Os, and improves on the (deterministic) algorithm of Arge et al.

(On sorting strings in external memory, STOC ’97)

. The error probability of the algorithm can be chosen as

O

(

N

$^{\rm -{\it c}}$

) for any positive constant

c

. The algorithm even works in the cache-oblivious model under the tall cache assumption, i.e,, assuming

M

>

B

1 + ε

for some

ε

> 0. An implication of our result is improved construction algorithms for external memory string dictionaries.

Cartesian trees have found numerous applications due to a peculiar rigid structure whose properties can be exploited in various ways. This rigidness, however, is also an obstacle when updating the structure since it can lead to a very unbalanced shape and so up to now most applications either assumed a random distribution of the keys or considered only the static case. In this paper we present a framework for efficiently maintaining a Cartesian tree under insertions and weak deletions in

O

(log

n

) amortized time per operation, using

O

(

n

) space. We show that the amortized cost of updating a Cartesian tree is

$O(1 + \mathcal{H}(T)/n)$

where

$\mathcal{H}(T) = O(nlogn)$

is an entropy-related measure for the partial order encoded by

T

. We also show how to exploit this property by implementing an algorithm which performs these updates in

O

(log

n

) time per operation. No poly-logarithmic update bounds were previously known.

A new method for constructing minimum-redundancy prefix codes is described. This method does not build a Huffman tree; instead it uses a property of optimal codes to find the codeword length of each weight. The running time of the algorithm is shown to be

O

(

nk

), where

n

is the number of weights and

k

is the number of different codeword lengths. When the given sequence of weights is already sorted, it is shown that the codes can be constructed using

O

(log

2k− 1

n

) comparisons, which is sub-linear if the value of

k

is small.

Let w be an infinite fixed point of a binary

k

-uniform morphism

f

, and let

E

(

w

) be the critical exponent of w. We give necessary and sufficient conditions for

E

(

w

) to be bounded, and an explicit formula to compute it when it is. In particular, we show that

E

(

w

) is always rational. We also sketch an extension of our method to non-uniform morphisms over general alphabets.

MSC:

68R15.

We study the isomorphism problem of two “natural” algebraic structures –

$\mathbb{F}$

-algebras and cubic forms. We prove that the

$\mathbb{F}$

-algebra isomorphism problem reduces in polynomial time to the cubic forms equivalence problem. This answers a question asked in [AS05]. For finite fields of the form

$3 \Lambda(\#\mathbb{F} - 1)$

, this result implies that the two problems are infact equivalent. This result also has the following interesting consequence:

Graph Isomorphism

${\leq}^P_m$

$\mathbb{F}$

-algebra Isomorphism

${\leq}^P_m$

Cubic Form Equivalence.

We define a code in a sofic shift as a set of blocks of symbols of the shift such that any block of the shift has at most one decomposition in code words. It is maximal if it is not strictly included in another one. Such a code is complete in the sofic shift if any block of the shift occurs within some concatenation of code words. We prove that a maximal code in an irreducible sofic shift is complete in this shift. We give an explicit construction of a regular completion of a regular code in a sofic shift. This extends the well known result of Ehrenfeucht and Rozenberg to the case of codes in sofic systems. We also give a combinatorial proof of a result concerning the polynomial of a code in a sofic shift.

We introduce the study of Kolmogorov complexity with error. For a metric

d

, we define

C

a

(

x

) to be the length of a shortest program

p

which prints a string

y

such that

d

(

x

,

y

) ≤

a

. We also study a conditional version of this measure

C

a

,

b

(

x

|

y

) where the task is, given a string

y

′ such that

d

(

y

,

y

′) ≤

b

, print a string

x

′ such that

d

(

x

,

x

′) ≤

a

. This definition admits both a uniform measure, where the

same

program should work given any

y

′ such that

d

(

y

,

y

′) ≤

b

, and a nonuniform measure, where we take the length of a program for the worst case

y

′. We study the relation of these measures in the case where

d

is Hamming distance, and show an example where the uniform measure is exponentially larger than the nonuniform one. We also show an example where symmetry of information does not hold for complexity with error under either notion of conditional complexity.

We introduce the concepts of complex and autocomplex sets, where a set

A

is complex if there is a recursive, nondecreasing and unbounded lower bound on the Kolmogorov complexity of the prefixes (of the characteristic sequence) of

A

, and autocomplex is defined likewise with recursive replaced by

A

-recursive. We observe that exactly the autocomplex sets allow to compute words of given Kolmogorov complexity and demonstrate that a set computes a diagonally nonrecursive (DNR) function if and only if the set is autocomplex. The class of sets that compute DNR functions is intensively studied in recursion theory and is known to coincide with the class of sets that compute fixed-point free functions. Consequently, the Recursion Theorem fails relative to a set if and only if the set is autocomplex, that is, we have a characterization of a fundamental concept of theoretical computer science in terms of Kolmogorov complexity. Moreover, we obtain that recursively enumerable sets are autocomplex if and only if they are complete, which yields an alternate proof of the well-known completeness criterion for recursively enumerable sets in terms of computing DNR functions.

All results on autocomplex sets mentioned in the last paragraph extend to complex sets if the oracle computations are restricted to truth-table or weak truth-table computations, for example, a set is complex if and only if it wtt-computes a DNR function. Moreover, we obtain a set that is complex but does not compute a Martin-Löf random set, which gives a partial answer to the open problem whether all sets of positive constructive Hausdorff dimension compute Martin-Löf random sets.

Furthermore, the following questions are addressed: Given

n

, how difficult is it to find a word of length

n

that (a) has at least prefix-free Kolmogorov complexity

n

, (b) has at least plain Kolmogorov complexity

n

or (c) has the maximum possible prefix-free Kolmogorov complexity among all words of length

n

. All these questions are investigated with respect to the oracles needed to carry out this task and it is shown that (a) is easier than (b) and (b) is easier than (c). In particular, we argue that for plain Kolmogorov complexity exactly the PA-complete sets compute incompressible words, while the class of sets that compute words of maximum complexity depends on the choice of the universal Turing machine, whereas for prefix-free Kolmogorov complexity exactly the complete sets allow to compute words of maximum complexity.

If two classical provers share an entangled state, the resulting interactive proof system is significantly weakened [6]. We show that for the case where the verifier computes the XOR of two binary answers, the resulting proof system is in fact no more powerful than a system based on a single quantum prover:

$\rm \bigoplus MIP^*[2] \subseteq QIP(2)$

. This also implies that

$\rm \bigoplus MIP^*[2] \subseteq EXP$

which was previously shown using a different method [7]. This contrasts with an interactive proof system where the two provers do not share entanglement. In that case,

$\rm \bigoplus MIP[2] = NEXP$

for certain soundness and completeness parameters[6].

We present quantum algorithms for some graph problems: finding a maximal bipartite matching in time

$O(n\sqrt{m}logn)$

, finding a maximal non-bipartite matching in time

$O(n^2(\sqrt{m/n}+log n)log n)$

, and finding a maximal flow in an integer network in time

$O(min(n^{7/6} \sqrt{m} \cdot U^{1/3},\sqrt{nU}m)log n)$

, where

n

is the number of vertices,

m

is the number of edges, and

U

≤

n

1/4

is an upper bound on the capacity of an edge.

A

run

(or a

maximal repetition

) in a string is an inclusion-maximal periodic segment in a string. Let

ρ

(

n

) be the maximal number of runs in a string of length

n

. It has been shown in [8] that

ρ

(

n

)=

O

(

n

), the proof was very complicated and the constant coefficient in

O

(

n

) has not been given explicitly. We propose a new approach to the analysis of runs based on the properties of subperiods: the periods of periodic parts of the runs. We show that

ρ

(

n

) ≤ 5

n

. Our proof is inspired by the results of [4], where the role of new periodicity lemmas has been emphasized.

We consider the problem of computing information theoretic functions such as entropy on a data stream, using sublinear space.

Our first result deals with a measure we call the “entropy norm” of an input stream: it is closely related to entropy but is structurally similar to the well-studied notion of frequency moments. We give a polylogarithmic space one-pass algorithm for estimating this norm under certain conditions on the input stream. We also prove a lower bound that rules out such an algorithm if these conditions do not hold.

Our second group of results are for estimating the empirical entropy of an input stream. We first present a sublinear space one-pass algorithm for this problem. For a stream of

m

items and a given real parameter

α

, our algorithm uses space

$\tilde{O}(m^{2\alpha})$

and provides an approximation of 1/

α

in the worst case and (1 + 

ε

) in “most” cases. We then present a two-pass polylogarithmic space (1 + 

ε

)-approximation algorithm. All our algorithms are quite simple.

Demand-robust versions of common optimization problems were recently introduced by Dhamdhere et al. [4] motivated by the worst-case considerations of two-stage stochastic optimization models. We study the demand robust min-cut and shortest path problems, and exploit the nature of the robust objective to give improved approximation factors. Specifically, we give a

$(1 + \sqrt{2})$

approximation for robust min-cut and a 7.1 approximation for robust shortest path. Previously, the best approximation factors were

O

(log

n

) for robust min-cut and 16 for robust shortest paths, both due to Dhamdhere et al.[4].

Our main technique can be summarized as follows: We investigate each of the second stage scenarios individually, checking if it can be independently serviced in the second stage within an acceptable cost (namely, a guess of the optimal second stage costs). For the costly scenarios that cannot be serviced in this way (“rainy days”), we show that they can be fully taken care of in a near-optimal first stage solution (i.e., by ”paying today”).

We also consider “hitting-set” extensions of the robust min-cut and shortest path problems and show that our techniques can be combined with algorithms for Steiner multicut and group Steiner tree problems to give similar approximation guarantees for the hitting-set versions of robust min-cut and shortest path problems respectively.

We show exact values for the price of anarchy of weighted and unweighted congestion games with polynomial latency functions. The given values also hold for weighted and unweighted

network

congestion games.

We introduce a new class

$\rm {O}^p_2$

as a subclass of the symmetric alternation class

$\rm {S}^p_2$

. An

$\rm {O}^p_2$

proof system has the flavor of an

$\rm {S}^p_2$

proof system, but it is more restrictive in nature. In an

$\rm {S}^p_2$

proof system, we have two competing provers and a verifier such that for any input, the honest prover has an irrefutable certificate. In an

$\rm {O}^p_2$

proof system, we require that the irrefutable certificates depend only on the length of the input, not on the input itself. In other words, the irrefutable proofs are oblivious of the input. For this reason, we call the new class

oblivious symmetric alternation

. While this might seem slightly contrived, it turns out that this class helps us improve some existing results. For instance, we show that if NP ⊂ P/poly then

$\rm PH = {O}^p_2$

, whereas the best known collapse under the same hypothesis was

$\rm PH = {S}^p_2$

.

We also define classes

$\rm Y{O}^p_2$

and

$\rm N{O}^p_2$

, bearing relations to

$\rm {O}^p_2$

as NP and coNP are to P, and show that these along with

$\rm {O}^p_2$

form a hierarchy, similar to the polynomial hierarchy. We investigate other inclusions involving these classes and strengthen some known results. For example, we show that

$\rm MA \subseteq N{O}^p_2$

which sharpens the known result

$\rm MA \subseteq {S}^p_2$

[16]. Another example is our result that

$\rm AM \subseteq O_2 \cdot NP \subseteq {\prod}^p_2$

, which is an improved upper bound on AM. Finally, we also prove better collapses for the 2-queries problem as discussed by [12,1,7]. We prove that

$\rm P^{NP[1]} = P^{NP[2]} \Longrightarrow PH = {NO}^p_2 \cap Y{O}^p_2$

.

In this work we introduce and study the question of combining multiple heuristics. Given a problem instance, each of the multiple heuristics is capable of computing the correct solution, but has a different cost. In our models the user executes multiple heuristics until one of them terminates with a solution. Given a set of problem instances, we show how to efficiently compute an optimal fixed schedule for a constant number of heuristics, and show that in general, the problem is computationally hard even to approximate (to within a constant factor). We also discuss a probabilistic configuration, in which the problem instances are drawn from some unknown fixed distribution, and show how to compute a near optimal schedule for this setup.

Given the range space (

$P,\mathcal{R}$

), where

P

is a set of

n

points in ℝ

2

and

$\mathcal{R}$

is the family of subsets of

P

induced by all axis-parallel rectangles, the conflict-free coloring problem asks for a coloring of

P

with the minimum number of colors such that (

$P,\mathcal{R}$

) is

conflict-free

. We study the following question: Given

P

, is it possible to add a small set of points

Q

such that (

$P \cup Q,\mathcal{R}$

) can be colored with fewer colors than (

$P,\mathcal{R}$

)? Our main result is the following: given

P

, and any

ε

 ≥ 0, one can always add a set

Q

of

O

(

n

1 − 

ε

) points such that

P

∪

Q

can be conflict-free colored using

$\tilde{O}(n^{\frac{3}{8}(1+\varepsilon)})$

colors. Moreover, the set

Q

and the conflict-free coloring can be computed in polynomial time, with high probability. Our result is obtained by introducing a general probabilistic re-coloring technique, which we call

quasi-conflict-free

coloring, and which may be of independent interest. A further application of this technique is also given.

An

edge-unfolding

of a polyhedron is produced by cutting along edges and flattening the faces to a

net

, a connected planar piece with no overlaps. A

grid unfolding

allows additional cuts along grid edges induced by coordinate planes passing through every vertex. A

vertex-unfolding

permits faces in the net to be connected at single vertices, not necessarily along edges. We show that any orthogonal polyhedra of genus zero has a grid vertex-unfolding. (There are orthogonal polyhedra that cannot be vertex-unfolded, so some type of “gridding” of the faces is necessary.) For any orthogonal polyhedron

P

with

n

vertices, we describe an algorithm that vertex-unfolds

P

in

O

(

n

2

) time. Enroute to explaining this algorithm, we present a simpler vertex-unfolding algorithm that requires a 3 × 1 refinement of the vertex grid.

We introduce the notion of the width bounded geometric separator and develop the techniques for the existence of the width bounded separator in any

d

-dimensional Euclidean space. The separator is applied in obtaining

$2^{O(\sqrt{n})}$

time exact algorithms for a class of NP-complete geometric problems, whose previous algorithms take

$n^{O(\sqrt{n})}$

time[2][5][1]. One of those problems is the well known disk covering problem, which seeks to determine the minimal number of fixed size disks to cover

n

points on a plane[10]. They also include some NP-hard problems on disk graphs such as the maximum independent set problem, the vertex cover problem, and the minimum dominating set problem.

Automatic structures are countable structures finitely presentable by a collection of automata. We study questions related to properties invariant with respect to the choice of an automatic presentation. We give a negative answer to a question of Rubin concerning definability of intrinsically regular relations by showing that order-invariant first-order logic can be stronger than first-order logic with counting on automatic structures. We introduce a notion of equivalence of automatic presentations, define semi-synchronous transductions, and show how these concepts correspond. Our main result is that a one-to-one function on words preserves regularity as well as non-regularity of all relations iff it is a semi-synchronous transduction. We also characterize automatic presentations of the complete structures of Blumensath and Grädel.

We show that, from a topological point of view, 2-tape Büchi automata have the same accepting power than Turing machines equipped with a Büchi acceptance condition. In particular, for every non null recursive ordinal

α

, there exist some Σ

$^{\rm 0}_{\alpha}$

-complete and some Π

$^{\rm 0}_{\alpha}$

-complete infinitary rational relations accepted by 2-tape Büchi automata. This surprising result gives answers to questions of Simonnet [Sim92] and of Lescow and Thomas [Tho90, LT94].

The theory of two-dimensional languages, generalizing formal string languages, was motivated by problems arising from image processing and models of parallel computing. Weighted automata and series over pictures map pictures to some semiring and provide an extension to a quantitative setting. We establish a notion of a weighted MSO logics over pictures. The semantics of a weighted formula will be a picture series. We introduce weighted 2-dimensional online tessellation automata (W2OTA) extending the common automata-theoretic model for picture languages. We prove that the class of picture series defined by sentences of the weighted logics coincides with the family of picture series that are computable by W2OTA. Moreover, behaviours of W2OTA coincide precisely with the recognizable picture series characterized in [18].

We consider Markov decision processes (MDPs) with multiple discounted reward objectives. Such MDPs occur in design problems where one wishes to simultaneously optimize several criteria, for example, latency and power. The possible trade-offs between the different objectives are characterized by the Pareto curve. We show that every Pareto-optimal point can be achieved by a memoryless strategy; however, unlike in the single-objective case, the memoryless strategy may require randomization. Moreover, we show that the Pareto curve can be approximated in polynomial time in the size of the MDP. Additionally, we study the problem if a given value vector is realizable by any strategy, and show that it can be decided in polynomial time; but the question whether it is realizable by a deterministic memoryless strategy is NP-complete. These results provide efficient algorithms for design exploration in MDP models with multiple objectives.

We study mechanisms for

cooperative

cost-sharing games satisfying:

voluntary participation

(i.e., no user is forced to pay more her valuation of the service),

consumer sovereignty

(i.e, every user can get the service if her valuation is large enough),

no positive transfer

(i.e., no user receives money from the mechanism),

budget balance

(i.e., the total amount of money that users pay is equal to the cost of servicing them), and

group strategyproofness

(i.e., the mechanism is resistant to coalitions).

We show that mechanisms satisfying all these requirements must obey certain

algorithmic properties

(which basically specify how the serviced users are selected). Our results yield a

characterization of upper continuous mechanisms

(this class is interesting as all known general techniques yield mechanisms of this type). Finally, we extend some of our negative results and obtain the first negative results on the existence of mechanisms satisfying all requirements above. We apply these results to an interesting generalization of cost-sharing games in which the mechanism cannot service certain “forbidden” subsets of users. These

generalized cost-sharing games

correspond to natural variants of known cost-sharing games and have interesting practical applications (e.g., sharing the cost of multicast transmissions which cannot be encrypted).

We study the speed of convergence to approximately optimal states in two classes of potential games. We provide bounds in terms of the number of

rounds

, where a round consists of a sequence of movements, with each player appearing at least once in each round. We model the sequential interaction between players by a

best-response walk

in the state graph, where every transition in the walk corresponds to a best response of a player. Our goal is to bound the social value of the states at the end of such walks. In this paper, we focus on two classes of potential games: selfish routing games, and cut games (or party affiliation games [7]).

We consider the problem that, given a graph

G

and a parameter

k

, asks whether the edit distance of

G

and a rectangular grid is at most

k

. We examine the general case where the edit operations are vertex/edge removals and additions. If the dimensions of the grid are given in advance, we give a parameterized algorithm that runs in 2

O

(

log

k

·

k

)

+

O

(

n

3

) steps. In the case where the dimensions of the grid are not given we give a parameterized algorithm that runs in 2

O

(

log

k

·

k

)

+

O

(

k

2

·

n

3

) steps. We insist on parameterized algorithms with running times where the relation between the polynomial and the non-polynomial part is additive. Our algorithm is based on the technique of kernelization. In particular we prove that for each version of the above problem there exists a kernel of size

O

(

k

4

).

An

N

-

superconcentrator

is a directed graph with

N

input vertices and

N

output vertices and some intermediate vertices, such that for

k

=1, 2, ...,

N

, between any set of

k

input vertices and any set of

k

output vertices, there are

k

vertex disjoint paths. In a

depth-twoN

-superconcentrator each edge either connects an input vertex to an intermediate vertex or an intermediate vertex to an output vertex. We consider tradeoffs between the number of edges incident on the input vertices and the number of edges incident on the output vertices in a depth-two

N

-superconcentrator. For an

N

-superconcentrator

G

, let

a

(

G

) be the average degree of the input vertices and

b

(

G

) be the average degree of the output vertices. Assume that

b

(

G

) ≥

a

(

G

). We show that there is a constant

k

1

> 0 such that

$a(G)log (\frac{2b(G)}{a(G)}) log b(G) \geq k_1 \cdot log^2 N$

.

Using logspace counting classes we study the computational complexity of hypergraph and graph isomorphism where the vertex sets have bounded color classes for certain specific bounds. We also give a polynomial-time algorithm for hypergraph isomorphism for bounded color classes of arbitrary size.

Assume that for some

α

< 1 and for all nutural

n

a set

F

n

of at most 2

αn

“forbidden” binary strings of length

n

is fixed. Then there exists an infinite binary sequence

ω

that does not have (long) forbidden substrings.

We prove this combinatorial statement by translating it into a statement about Kolmogorov complexity and compare this proofl with a combinatorial one based on Laslo Lovasz local lemma.

Then we construct an almost periodic sequence with the same property (thus combines the results from [1] and[2]).

Both the combinatorial proof and Kolmogorov complexity argument can be generalized to the multidimensional case.

We establish a relationship between the online mistake-bound model of learning and resource-bounded dimension. This connection is combined with the Winnow algorithm to obtain new results about the density of hard sets under adaptive reductions. This improves previous work of Fu (1995) and Lutz and Zhao (2000), and solves one of Lutz and Mayordomo’s “Twelve Problems in Resource-Bounded Measure” (1999).

Visibly pushdown automata are special pushdown automata whose stack behavior is driven by the input symbols according to a partition of the alphabet. We show that it is decidable for a given visibly pushdown automaton whether it is equivalent to a visibly counter automaton, i.e. an automaton that uses its stack only as counter. In particular, this allows to decide whether a given visibly pushdown language is a regular restriction of the set of well-matched words, meaning that the language can be accepted by a finite automaton if only well-matched words are considered as input.

We consider the problem of converting regular expressions of length

n

over an alphabet of size

k

into

ε

-free NFAs with as few transitions as possible. Whereas the previously best construction uses

O

(

n

·

min

{

k

,

log

2

n

} ·

log

2

n

) transitions, we show that

O

(

n

· log

2

2

k

· log

2

n

) transitions suffice. For small alphabets we further improve the upper bound to

$O(n \cdot log_2 2k \cdot k^{L_k (n)+1})$

, where

L

k

(

n

) =

O

(log

$_{\rm 2}^{\rm *}$

n

). In particular,

$n \cdot 2^{O({log}^*_2 n)}$

transitions and hence almost linear size suffice for the binary alphabet! Finally we show the lower bound Ω(

n

· log

$_{\rm 2}^{\rm 2}$

2

k

) and as a consequence the upper bound

O

(

n

· log

$_{\rm 2}^{\rm 2}$

n

) of [7] for general alphabets is best possible. Thus the conversion problem is solved for large alphabets (

k

=

n

Ω(1)

) and almost solved for small alphabets (

k

=

O

(1)).

Classification.

Automata and formal languages, descriptional complexity, nondeterministic automata, regular expressions.

We show that a set is m-autoreducible if and only if it is m-mitotic. This solves a long standing open question in a surprising way. As a consequence of this unconditional result and recent work by Glaßer et al. [12], complete sets for all of the following complexity classes are m-mitotic: NP, coNP,

$\bigoplus$

P, PSPACE, and NEXP, as well as all levels of PH, MODPH, and the Boolean hierarchy over NP. In the cases of NP, PSPACE, NEXP, and PH, this at once answers several well-studied open questions. These results tell us that complete sets share a redundancy that was not known before. In particular, every NP-complete set

A

splits into two NP-complete sets

A

1

and

A

2

.

It is well-known that the class of sets that can be computed by polynomial size circuits is equal to the class of sets that are polynomial time reducible to a sparse set. It is widely believed, but unfortunately up to now unproven, that there are sets in EXP

NP

, or even in EXP that are not computable by polynomial size circuits and hence are not reducible to a sparse set. In this paper we study this question in a more restricted setting: what is the computational complexity of sparse sets that are

selfreducible

? It follows from earlier work of Lozano and Toran [10] that EXP

NP

does not have sparse selfreducible hard sets. We define a natural version of selfreduction, tree-selfreducibility, and show that NEXP does not have sparse tree-selfreducible hard sets. We also show that this result is optimal with respect to relativizing proofs, by exhibiting an oracle relative to which all of EXP is reducible to a sparse tree-selfreducible set. These lower bounds are corollaries of more general results about the computational complexity of sparse sets that are selfreducible, and can be interpreted as super-polynomial circuit lower bounds for NEXP.

We show that

RL

⊆

L/O

(

n

), i.e., any language computable in randomized logarithmic space can be computed in deterministic logarithmic space with a linear amount of non-uniform advice. To prove our result we use an ultra-low space walk on the Gabber-Galil expander graph due to Gutfreund and Viola.

First-order logic with

k

-ary deterministic transitive closure has the same power as two-way

k

-head deterministic automata that use a finite set of nested pebbles. This result is valid for strings, ranked trees, and in general for families of graphs having a fixed automaton that can be used to traverse the nodes of each of the graphs in the family. Other examples of such families are grids, toruses, and rectangular mazes.

We consider an extension of first-order logic by modular quantifiers of a fixed modulus

q

. Drawing on collapse results from finite model theory and techniques of finite semigroup theory, we show that if the only available numerical predicate is addition, then sentences in this logic cannot define the set of bit strings in which the number of 1’s is divisible by a prime

p

that does not divide

q

. More generally, we completely characterize the regular languages definable in this logic. The corresponding statement, with addition replaced by arbitrary numerical predicates, is equivalent to the conjectured separation of the circuit complexity class

ACC

from

NC

1

. Thus our theorem can be viewed as proving a highly uniform version of the conjecture.

It is well-known that modal satisfiability is PSPACE-complete [Lad77]. However, the complexity may decrease if we restrict the set of propositional operators used. Note that there exist an infinite number of propositional operators, since a propositional operator is simply a Boolean function. We completely classify the complexity of modal satisfiability for every finite set of propositional operators, i.e., in contrast to previous work, we classify an infinite number of problems. We show that, depending on the set of propositional operators, modal satisfiability is PSPACE-complete, coNP-complete, or in P. We obtain this trichotomy not only for modal formulas, but also for their more succinct representation using modal circuits.

A stochastic graph game is played by two players on a game graph with probabilistic transitions. We consider stochastic graph games with

ω

-regular winning conditions specified as parity objectives. These games lie in NP ∩ coNP. We present a strategy improvement algorithm for stochastic parity games; this is the first non-brute-force algorithm for solving these games. From the strategy improvement algorithm we obtain a randomized subexponential-time algorithm to solve such games.

Tree-width is a well-known metric on undirected graphs that measures how tree-like a graph is and gives a notion of graph decomposition that proves useful in algorithm development. Tree-width is characterised by a game known as the cops-and-robber game where a number of cops chase a robber on the graph. We consider the natural adaptation of this game to directed graphs and show that monotone strategies in the game yield a measure with an associated notion of graph decomposition that can be seen to describe how close a directed graph is to a directed acyclic graph (DAG). This promises to be useful in developing algorithms on directed graphs. In particular, we show that the problem of determining the winner of a parity game is solvable in polynomial time on graphs of bounded DAG-width. We also consider the relationship between DAG-width and other measures such as entanglement and directed tree-width. One consequence we obtain is that certain NP-complete problems such as Hamiltonicity and disjoint paths are polynomial-time computable on graphs of bounded DAG-width.

We investigate the coded model of fault-tolerant computations introduced by D. Spielman. In this model the input and the output of a computational circuit is treated as words in some error-correcting code. A circuit is said to compute some function correctly if for an input which is a encoded argument of the function, the output, been decoded, is the value of the function on the given argument.

We consider two models of faults. In the first one we suppose that an elementary processor at each step can be corrupted with some small probability, and faults of different processors are independent. For this model, we prove that a parallel computation running on

n

elementary non-faulty processors in time

t

= poly(

n

) can be simulated on

O

(

n

log

n

/ log log

n

) faulty processors in time

O

(

t

log log

n

). Note that we get a sub-logarithmic blow up of the memory, which cannot be achieved in the classic model of faulty boolean circuit, where the input is not encoded.

In the second model, we assume that at each step some fixed fraction of elementary processors can be corrupted by an adversary, who is free to chose these processors arbitrarily. We show that in this model any computation can be made reliable with an exponential blow up of the memory.

Our method employs a sort of

mixing mappings

, which enjoy some properties of expanders. Based on mixing mappings, we implement an effective self-correcting procedure for an array of faulty processors.

The common theoretical model adopted in recent studies on algorithms for systems of autonomous mobile robots assumes that the positional input of the robots is obtained by perfectly accurate visual sensors, that robot movements are accurate, and that internal calculations performed by the robots on (real) coordinates are perfectly accurate as well. The current paper concentrates on the effect of weakening this rather strong set of assumptions, and replacing it with the more realistic assumption that the robot sensors, movement and internal calculations may have slight inaccuracies. Specifically, the paper concentrates on the ability of robot systems with inaccurate sensors, movements and calculations to carry out the task of convergence. The paper presents several impossibility results, limiting the inaccuracy allowing convergence. The main positive result is an algorithm for convergence under bounded measurement, movement and calculation errors.

For decades, the algorithm providing the smallest proven worst-case running time (with respect to the number of terminals) for the Steiner tree problem has been the one by Dreyfus and Wagner. In this paper, a new algorithm is developed, which improves the running time from

O

(3

k

n

+2

k

n

2

+

n

3

) to (2+

δ

)

k

·

poly

(

n

) for arbitrary but fixed

δ

> 0. Like its predecessor, this algorithm follows the dynamic programming paradigm. Whereas in effect the Dreyfus–Wagner recursion splits the optimal Steiner tree in two parts of arbitrary sizes, our approach looks for a set of nodes that separate the tree into parts containing only few terminals. It is then possible to solve an instance of the Steiner tree problem more efficiently by combining partial solutions.

We provide a general method to generate randomized roundings that satisfy cardinality constraints. Our approach is different from the one taken by Srinivasan (FOCS 2001) and Gandhi et al. (FOCS 2002) for one global constraint and the bipartite edge weight rounding problem.

Also for these special cases, our approach is the first that can be derandomized. For the bipartite edge weight rounding problem, in addition, we gain an

$\tilde{O}(|V|)$

factor run-time improvement for generating the randomized solution.

We also improve the current best result on the general problem of derandomizing randomized roundings. Here we obtain a simple

O

(

mn

log

n

) time algorithm that works in the RAM model for arbitrary matrices with entries in ℚ

 ≥ 0

. This improves over the

O

(

mn

2

log(

mn

)) time solution of Srivastav and Stangier.

We consider the online scheduling problem for sorting buffers on a line metric, motivated by an application to disc scheduling. Input is an online sequence of requests. Each request is a block of data to be written on a specified track of the disc. To write a block on a particular track, the scheduler has to bring the disc head to that track. The cost of moving the disc head from a track to another is the distance between those tracks. A sorting buffer that can store at most

k

requests at a time is available to the scheduler. This buffer can be used to rearrange the input sequence. The objective is to minimize the total cost of head movement while serving the requests. On a disc with

n

uniformly-spaced tracks, we give a randomized online algorithm with a competitive ratio of

O

(log

2

n

) in expectation against an oblivious adversary. We show that any deterministic strategy which makes scheduling decisions based only on the contents of the buffer has a competitive ratio of Ω(

k

) or Ω(log

n

/loglog

n

).

We study route selection for packet switching in the competitive throughput model. In contrast to previous papers which considered competitive algorithms for packet scheduling, we consider the packet routing problem (output port selection in a node). We model the node routing problem as follows: a node has an arbitrary number of input ports and an arbitrary number of output queues. At each time unit, an arbitrary number of new packets may arrive, each packet is associated with a subset of the output ports (which correspond to the next edges on the allowed paths for the packet). Each output queue transmits packets in some arbitrary manner. Arrival and transmission are arbitrary and controlled by an adversary. The node routing algorithm has to route each packet to one of the allowed output ports, without exceeding the size of the queues. The goal is to maximize the number of the transmitted packets. In this paper, we show that all non-refusal algorithms are 2-competitive. Our main result is an almost optimal

$\frac{e}{e-1} \approx 1.58$

-competitive algorithm, for a large enough queue size. For packets with arbitrary values (allowing preemption) we present a 2-competitive algorithm for any queue size.

We present the first one-pass memoryless algorithm for metric Facility Location which maintains a set of facilities approximating the optimal facility configuration within a constant factor. The algorithm considers the demand points one-by-one in arbitrary order, is randomized and very simple to state and implement. It runs in linear time and keeps in memory only the facility locations currently open. We prove that its competitive ratio is less than 14 in the special case of uniform facility costs and less than 49 in the general case of non-uniform facility costs.

We study scheduling problems in battery-operated computing devices, aiming at schedules with low total energy consumption. While most of the previous work has focused on finding feasible schedules in deadline-based settings, in this paper we are interested in schedules that guarantee good response times. More specifically, our goal is to schedule a sequence of jobs on a variable speed processor so as to minimize the total cost consisting of the power consumption and the total flow time of all the jobs. We first show that when the amount of work, for any job, may take an arbitrary value, then no online algorithm can achieve a constant competitive ratio. Therefore, most of the paper is concerned with unit-size jobs. We devise a deterministic constant competitive online algorithm and show that the offline problem can be solved in polynomial time.

Recursive Markov Decision Processes (RMDPs) and Recursive Simple Stochastic Games (RSSGs) are natural models for recursive systems involving both probabilistic and non-probabilistic actions. As shown recently [10], fundamental problems about such models, e.g., termination, are undecidable in general, but decidable for the important class of 1-exit RMDPs and RSSGs. These capture controlled and game versions of multi-type Branching Processes, an important and well-studied class of stochastic processes. In this paper we provide efficient algorithms for the

qualitative termination

problem for these models: does the process terminate almost surely when the players use their optimal strategies? Polynomial time algorithms are given for both maximizing and minimizing 1-exit RMDPs (the two cases are not symmetric). For 1-exit RSSGs the problem is in NP∩coNP, and furthermore, it is at least as hard as other well-known NP∩coNP problems on games, e.g., Condon’s

quantitative

termination problem for finite SSGs ([3]). For the class of linearly-recursive 1-exit RSSGs, we show that the problem can be solved in polynomial time.

We relate the expressive power of Datalog and constraint satisfaction with infinite templates. The relationship is twofold: On the one hand, we prove that every non-empty problem that is closed under disjoint unions and has Datalog width one can be formulated as a constraint satisfaction problem (CSP) with a countable template that is

ω-categorical

. Structures with this property are of central interest in classical model theory. On the other hand, we identify classes of CSPs that can be solved in polynomial time with a Datalog program. For that, we generalise the notion of the

canonical Datalog program

of a CSP, which was previously defined only for CSPs with finite templates by Feder and Vardi. We show that if the template Γ is

ω

-categorical, then CSP(Γ) can be solved by an (

l

,

k

)-Datalog program if and only if the problem is solved by the canonical (

l

,

k

)-Datalog program for Γ. Finally, we prove algebraic characterisations for those

ω

-categorical templates whose CSP has Datalog width (1,

k

), and for those whose CSP has strict Datalog width

l

.

Topic:

Logic in Computer Science, Computational Complexity.

We revisit monotone planar circuits MPCVP, with special attention to circuits with cylindrical embeddings. MPCVP is known to be in

NC

3

in general, and in

L

og

DCFL

for the special case of upward stratified circuits. We characterize cylindricality, which is stronger than planarity but strictly generalizes upward planarity, and make the characterization partially constructive. We use this construction, and four key reduction lemmas, to obtain several improvements. We show that monotone circuits with embeddings that are stratified cylindrical, cylindrical, planar one-input-face and focused can be evaluated in

L

og

DCFL

,

AC

1

(

L

og

DCFL

),

L

og

CFL

and

AC

1

(

L

og

DCFL

) respectively. We note that the

NC

3

algorithm for general MPCVP is in

AC

1

(

L

og

CFL

) =

SAC

2

. Finally, we show that monotone circuits with toroidal embeddings can, given such an embedding, be evaluated in

NC

.

We study the complexity of arithmetic in finite fields of characteristic two,

$\mathbb{F}_{2^n}$

. We concentrate on the following two problems:

– Iterated Multiplication: Given

$\alpha_1,...,\alpha_t \in \mathbb{F}_{2^n}$

, compute

α

1

⋯

α

t

.

– Exponentiation: Given

$\alpha \in \mathbb{F}_{2^n}$

and a

t

-bit integer

k

, compute

α

k

.

We study weighted distributed systems whose behavior is described as a formal power series over a free partially commutative or trace monoid. We characterize the behavior of such systems both, in the deterministic and in the non-deterministic case. As a consequence, we obtain a particularly simple class of sequential weighted automata that have already the full expressive power.

We show that if a minimal-time solution exists for a fundamental distributed computation primitive, synchronizing a general directed network of finite-state processors, then there must exist an extraordinarily fast

$O(ED log_2 D (log_2 n)^2)$

algorithm in the RAM model of computation for exactly determining the diameter of a general directed graph. The proof is constructive.

This result interconnects two very distinct areas of computer science: distributed protocols on networks of intercommunicating finite-state machines and standard algorithms on the usual RAM model of computation.