STACS 2007

The sharing of content by communities of users (e.g., scientists) in a P2P context remains cumbersome. We argue that main reasons for this is the lack of calculus and algebra for distributed data management. We present the ActiveXML language that extends the XML language with features to handle distribution. More precisely, ActiveXML documents are XML documents with a special syntax for specifying the embedding of Web service calls, e.g. XML queries such as XQueries. We also present ActiveXML algebra that extends ActiveXML notably with explicit control of data exchanges. ActiveXML algebra allows describing query plans, and exchanging them between peers.

The complementation problem for nondeterministic word automata has numerous applications in formal verification. In particular, the language-containment problem, to which many verification problems are reduced, involves complementation. For automata on finite words, which correspond to safety properties, complementation involves determinization. The 2

n

blow-up that is caused by the subset construction is justified by a tight lower bound. For Büchi automata on infinite words, which are required for the modeling of liveness properties, optimal complementation constructions are quite complicated, as the subset construction is not sufficient. We review here progress on this problem, which dates back to its introduction in Büchi’s seminal 1962 paper.

During the last years, several speed-up techniques for

Dijkstra’s algorithm

have been published that maintain the correctness of the algorithm but reduce its running time for typical instances. They are usually based on a preprocessing that annotates the graph with additional information which can be used to prune or guide the search. Timetable information in public transport is a traditional application domain for such techniques. In this paper, we provide a condensed overview of new developments and extensions of classic results. Furthermore, we discuss how combinations of speed-up techniques can be realized to take advantage from different strategies.

We study labelling schemes for

X

-constrained path problems. Given a graph (

V

,

E

) and

$X\subseteq V$

, a path is

X

-constrained if all intermediate vertices avoid

X

. We study the problem of assigning labels

J

(

x

) to vertices so that given {

J

(

x

):

x

 ∈ 

X

} for any

$X\subseteq V$

, we can route on the shortest

X

-constrained path between

x

,

y

 ∈ 

X

. This problem is motivated by Internet routing, where the presence of routing policies means that shortest-path routing is not appropriate. For graphs of tree width

k

, we give a routing scheme using routing tables of size

O

(

k

2

log

2

n

). We introduce m-clique width, generalizing clique width, to show that graphs of m-clique width

k

also have a routing scheme using size

O

(

k

2

log

2

n

) tables.

We present a new bound for pure greedy hot potato routing on

n

×

n

mesh-connected arrays and

n

×

n

tori. For permutation problems the bound is

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

steps which improves the for a long time known bound of

O

(

n

2

). For the more general link-limited k-destination routing problem the bound is

$O(n \sqrt{kn} \log n)$

. The bound also holds for restricted pure greedy hot potato routing on

n

×

n

meshes with diagonals. The bound could be derived by a new technique where packets may have several identities.

We study computationally hard combinatorial problems arising from the important engineering question of how to maximize the number of connections that can be simultaneously served in a WDM optical network. In such networks, WDM technology can satisfy a set of connections by computing a route and assigning a wavelength to each connection so that no two connections routed through the same fiber are assigned the same wavelength. Each fiber supports a limited number of

w

wavelengths and in order to fully exploit the parallelism provided by the technology, one should select a set connections of maximum cardinality which can be satisfied using the available wavelengths. This is known as the

maximum routing and path coloring

problem (

maxRPC

).

Our main contribution is a general analysis method for a class of iterative algorithms for a more general coloring problem. A lower bound on the benefit of such an algorithm in terms of the optimal benefit and the number of available wavelengths is given by a

benefit-revealing linear program

. We apply this method to

maxRPC

in both undirected and bidirected rings to obtain bounds on the approximability of several algorithms. Our results also apply to the problem

maxPC

where paths instead of connections are given as part of the input. We also study the profit version of

maxPC

in rings where each path has a profit and the objective is to satisfy a set of paths of maximum total profit.

We consider Sturmian trees as a natural generalization of Sturmian words. A Sturmian tree is a tree having

n

 + 1 distinct subtrees of height

n

for each

n

. As for the case of words, Sturmian trees are irrational trees of minimal complexity. We give various examples of Sturmian trees, and we characterize one family of Sturmian trees by means of a structural property of their automata.

The universal automaton of a regular language is the maximal NFA without merging states that recognizes this language. This automaton is directly inspired by the factor matrix defined by Conway thirty years ago. We prove in this paper that a tight bound on its size with respect to the size of the smallest equivalent NFA is given by Dedekind’s numbers. At the end of the paper, we deal with the unary case. Chrobak has proved that the size of the minimal deterministic automaton with respect to the smallest NFA is tightly bounded by the Landau’s function; we show that the size of the universal automaton is in this case an exponential of the Landau’s function.

Partial words

are strings over a finite alphabet that may contain a number of “do not know” symbols. In this paper, we introduce the notions of binary and ternary correlations, which are binary and ternary vectors indicating the periods and weak periods of partial words. Extending a result of Guibas and Odlyzko, we characterize precisely which of these vectors represent the (weak) period sets of partial words and prove that all valid correlations may be taken over the binary alphabet. We show that the sets of all such vectors of a given length form distributive lattices under inclusion. We also show that there is a well defined minimal set of generators for any binary correlation of length

n

and demonstrate that these generating sets are the primitive subsets of {1, 2,...,

n

 − 1}. Finally, we investigate the number of correlations of length

n

.

A coloring of a graph is

convex

if it induces a partition of the vertices into connected subgraphs. Besides being an interesting property from a theoretical point of view, tests for convexity have applications in various areas involving large graphs. Our results concern the important subcase of testing for convexity in trees. This problem is linked, among other possible applications, with the study of phylogenetic trees, which are central in genetic research, and are used in linguistics and other areas. We give a 1-sided, non-adaptive, distribution-free

ε

-test for the convexity of tree colorings. The query complexity of our test is

$O\left(\frac{k}{\epsilon}\right)$

, where

k

is the number of colors, and the additional computational complexity is

O

(

n

). On the other hand, we prove a lower bound of

$\Omega(\sqrt{k/\epsilon})$

on the query complexity of tests for convexity in the standard model, which applies even for (unweighted) paths. We also consider whether the dependency on

k

can be reduced in some cases, and provide an alternative testing algorithm for the case of paths. Then we investigate a variant of convexity, namely

quasi-convexity

, in which all but one of the colors are required to induce connected components. For this problem we provide a 1-sided, non-adaptive

ε

-test with query complexity

$O\left(\frac{k}{\epsilon^2}\right)$

and time complexity

O

(

n

). For both our convexity and quasi-convexity tests, we show that, assuming that a query takes constant time, the time complexity can be reduced to a constant independent of

n

if we allow a preprocessing stage of time

O

(

n

). Finally, we show how to test for a variation of convexity and quasi-convexity where the maximum number of connectivity classes of each color is allowed to be a constant value other than 1.

Coloring a

k

-colorable graph using

k

colors (

k

 ≥ 3) is a notoriously hard problem. Considering average case analysis allows for better results. In this work we consider the uniform distribution over

k

-colorable graphs with

n

vertices and exactly

cn

edges,

c

greater than some sufficiently large constant. We rigorously show that all proper

k

-colorings of most such graphs are clustered in one cluster, and agree on all but a small, though constant, number of vertices. We also describe a polynomial time algorithm that finds a proper

k

-coloring for (1 − 

o

(1))-fraction of such random

k

-colorable graphs, thus asserting that most of them are “easy”. This should be contrasted with the setting of very sparse random graphs (which are

k

-colorable

whp

), where experimental results show some regime of edge density to be difficult for many coloring heuristics. One explanation for this phenomena, backed up by partially non-rigorous analytical tools from statistical physics, is the complicated clustering of the solution space at that regime, unlike the more “regular” structure that denser graphs possess. Thus in some sense, our result rigorously supports this explanation.

Let

τ

(

n

) denote the minimum number of arithmetic operations sufficient to build the integer

n

from the constant 1. We prove that if there are arithmetic circuits for computing the permanent of

n

by

n

matrices having size polynomial in

n

, then

τ

(

n

!) is polynomially bounded in log

n

. Under the same assumption on the permanent, we conclude that the Pochhammer-Wilkinson polynomials

$\prod_{k=1}^n (X-k)$

and the Taylor approximations

$\sum_{k=0}^n \frac1{k!} X^k$

and

$\sum_{k=1}^n \frac1{k} X^k$

of exp and log, respectively, can be computed by arithmetic circuits of size polynomial in log

n

(allowing divisions). This connects several so far unrelated conjectures in algebraic complexity.

We introduce a new technique for proving formula size lower bounds based on matrix rank. A simple form of this technique gives bounds at least as large as those given by the method of Khrapchenko, originally used to prove an

n

2

lower bound on the parity function. Applying our method to the parity function, we are able to give an exact expression for the formula size of parity: if

n

 = 2

ℓ

 + 

k

, where 0 ≤ 

k

 < 2

ℓ

, then the formula size of parity on

n

bits is exactly 2

ℓ

(2

ℓ

 + 3

k

) = 

n

2

 + 

k

2

ℓ

 − 

k

2

. Such a bound cannot be proven by any of the lower bound techniques of Khrapchenko, Nečiporuk, Koutsoupias, or the quantum adversary method, which are limited by

n

2

.

Hard metrics are the class of extremal metrics with respect to embedding into Euclidean Spaces: their distortion is as bad as it possibly gets, which is

Ω

(log

n

). Besides being very interesting objects akin to expanders and good codes, with rich structure of independent interest, such metrics are important for obtaining lower bounds in Combinatorial Optimization, e.g., on the value of MinCut/MaxFlow ratio for multicommodity flows.

For more than a decade, a single family of hard metrics was known (see [10,3]). Recently, a different such family was found (see [8]), causing a certain excitement among the researchers in the area.

In this paper we present another construction of hard metrics, different from [10,3], and more general yet clearer and simpler than [8]. Our results naturally extend to NEG and to ℓ

1

.

One frequently studied problem in the context of information dissemination in communication networks is the broadcasting problem. In this paper, we study the following randomized broadcasting protocol: At some time

t

an information

r

is placed at one of the nodes of a graph

G

. In the succeeding steps, each informed node chooses one neighbor, independently and uniformly at random, and informs this neighbor by sending a copy of

r

to it.

First, we consider the relationship between randomized broadcasting and random walks on graphs. In particular, we prove that the runtime of the algorithm described above is upper bounded by the corresponding mixing time, up to a logarithmic factor. One key ingredient of our proofs is the analysis of a continuous-type version of the afore mentioned algorithm, which might be of independent interest. Then, we introduce a general class of Cayley graphs, including (among others) Star graphs, Transposition graphs, and Pancake graphs. We show that randomized broadcasting has optimal runtime on all graphs belonging to this class. Finally, we develop a new proof technique by combining martingale tail estimates with combinatorial methods. Using this approach, we show the optimality of our algorithm on another Cayley graph and obtain new knowledge about the runtime distribution on several Cayley graphs.

An orthogonal network for a given set of

n

points in the plane is an axis-aligned planar straight line graph that connects all input points. We show that for any set of

n

points in the plane, there is an orthogonal network that (i) is

short

having a total edge length of

O

(|

T

|), where |

T

| denotes the length of a minimum Euclidean spanning tree for the point set; (ii) is

small

having

O

(

n

) vertices and edges; and (iii) has

constant geometric dilation

, which means that for any two points

u

and

v

in the network, the shortest path in the network between

u

and

v

is at most constant times longer than the (Euclidean) distance between

u

and

v

.

We analyse the notion of iterated admissibility, i.e., avoidance of weakly dominated strategies, as a solution concept for extensive games of infinite horizon. This concept is known to provide a valuable criterion for selecting among multiple equilibria and to yield sharp predictions in finite games. However, generalisations to the infinite are inherently problematic, due to unbounded dominance chains and the requirement of transfinite induction.

In a multi-player non-zero-sum setting, we show that for infinite extensive games of perfect information with only two possible payoffs (win or lose), the concept of iterated admissibility is sound and robust: all iteration stages are dominated by admissible strategies, the iteration is non-stagnating, and, under regular winning conditions, strategies that survive iterated elimination of dominated strategies form a regular set.

Markov decision processes (MDPs) are controllable discrete event systems with stochastic transitions. Performances of an MDP are evaluated by a payoff function. The controller of the MDP seeks to optimize those performances, using optimal strategies.

There exists various ways of measuring performances, i.e. various classes of payoff functions. For example, average performances can be evaluated by a mean-payoff function, peak performances by a limsup payoff function, and the parity payoff function can be used to encode logical specifications.

Surprisingly, all the MDPs equipped with mean, limsup or parity payoff functions share a common non-trivial property: they admit

pure stationary

optimal strategies.

In this paper, we introduce the class of

prefix-independent

and

submixing

payoff functions, and we prove that any MDP equipped with such a payoff function admits pure stationary optimal strategies.

This result unifies and simplifies several existing proofs. Moreover, it is a key tool for generating new examples of MDPs with pure stationary optimal strategies.

Strategic games may exhibit symmetries in a variety of ways. A common aspect, enabling the compact representation of games even when the number of players is unbounded, is that players cannot (or need not) distinguish between the other players. We define four classes of symmetric games by considering two additional properties:

identical payoff functions

for all players and the ability to

distinguish oneself

from the other players. Based on these varying notions of symmetry, we investigate the computational complexity of pure Nash equilibria. It turns out that in all four classes of games Nash equilibria can be computed in TC

0

when only a constant number of actions is available to each player, a problem that has been shown intractable for other succinct representations of multi-player games. We further show that identical payoff functions make the difference between TC

0

-completeness and membership in AC

0

, while a growing number of actions renders the equilibrium problem NP-complete for three of the classes and PLS-complete for the most restricted class for which the existence of a pure Nash equilibrium is guaranteed. Finally, our results extend to wider classes of

threshold symmetric

games where players are unable to determine the exact number of players playing a certain action.

For every

k

 ≥ 1 and two finite fields

${\mathbb F}$

and

${\mathbb F}'$

, we design a polynomial-time algorithm that given a matroid

${\mathcal M}$

of branch-width at most

k

represented over

${\mathbb F}$

decides whether

${\mathcal M}$

is representable over

${\mathbb F}'$

and if so, it computes a representation of

${\mathcal M}$

over

${\mathbb F}'$

. The algorithm also counts the number of non-isomorphic representations of

${\mathcal M}$

over

${\mathbb F}'$

. Moreover, it can be modified to list all such non-isomorphic representations.

Minimal interval completions of graphs are central in understanding two important and widely studied graph parameters: profile and pathwidth. Such understanding seems necessary to be able to attack the problem of computing these parameters. An interval completion of a given graph is an interval supergraph of it on the same vertex set, obtained by adding edges. If no subset of the added edges can be removed without destroying the interval property, we call it a minimal interval completion. In this paper, we give the first characterization of minimal interval completions. We present a polynomial time algorithm, for deciding whether a given interval completion of an arbitrary graph is minimal. If the interval completion is not minimal the algorithm can be used to extract a minimal interval completion that is a subgraph of the given interval completion.

This paper is motivated by the open question whether the union of two disjoint NP-complete sets always is NP-complete. We discover that such unions retain much of the complexity of their single components. More precisely, they are complete with respect to more general reducibilities.

Moreover, we approach the main question in a more general way: We analyze the scope of the complexity of unions of m-equivalent disjoint sets. Under the hypothesis that NE ≠ coNE, we construct degrees in NP where our main question has a positive answer, i.e., these degrees are closed under unions of disjoint sets.

Merkle et al. [11] that all Kolmogorov-Loveland stochastic infinite binary sequences have constructive Hausdorff dimension 1. In this paper, we go even further, showing that from an infinite sequence of dimension less than

$\mathcal{H}({1\over2}+\delta)$

(

$\mathcal{H}$

being the Shannon entropy function) one can extract by a selection rule a biased subsequence with bias at least

δ

. We also prove an analogous result for finite strings.

We consider the problem of assigning powers to nodes of a wireless network in the plane such that a message from a source node

s

reaches all other nodes within a bounded number

k

of transmissions and the total amount of assigned energy is minimized. By showing the existence of a

coreset

of size

$O(\left({{1}\over{\epsilon}}\right)^{4k})$

we are able to (1 + 

ε

)-approximate the bounded-hop broadcast problem in time

linear

in

n

which is a drastic improvement upon the previously best known algorithm.

While actual network deployments often are in a planar setting, the experienced metric for several reasons is typically not exactly of the Euclidean type, but in some sense ’close’. Our algorithm (and others) also work for non-Euclidean metrics provided they exhibit a certain similarity to the Euclidean metric which is known in the literature as

bounded doubling dimension

. We give a novel characterization of such metrics also pointing out other applications such as space-efficient routing schemes.

The problem of image matching is to find for two given digital images

A

and

B

an admissible transformation that converts image

A

as close as possible to

B

. This problem becomes hard if the space of admissible transformations is too complex. Consequently, in many real applications, like the ones allowing nonlinear elastic transformations, the known algorithms solving the problem either work in exponential worst-case time or can only guarantee to find a local optimum. Recently Keysers and Unger have proved that the image matching problem for this class of transformations is NP-complete, thus giving evidence that the known exponential time algorithms are justified. On the other hand, allowing only such transformations as translations, rotations, or scalings the problem becomes tractable. In this paper we analyse the computational complexity of image matching for a larger space of admissible transformations, namely for all affine transformations. In signal processing there are no efficient algorithms known for this class. Similarly, the research in combinatorial pattern matching does not cover this set of transformations neither providing efficient algorithms nor proving intractability of the problem, although it is a basic one and of high practical importance. The main result of this paper is that the image matching problem can be solved in polynomial time even allowing all affine transformations.

Fixed point equations

x = f(x)

over

ω

-continuous semirings can be seen as the mathematical foundation of interprocedural program analysis. The sequence

0, f

(

0

),

f

2

(

0

),... converges to the least fixed point

μ

f

. The convergence can be accelerated if the underlying semiring is commutative. We show that accelerations in the literature, namely Newton’s method for the arithmetic semiring [4] and an acceleration for commutative Kleene algebras due to Hopkins and Kozen [5], are instances of a general algorithm for arbitrary commutative

ω

-continuous semirings. In a second contribution, we improve the

$\mathcal{O}(3^n)$

bound of [5] and show that their acceleration reaches

μ

f

after

n

iterations, where

n

is the number of equations. Finally, we apply the Hopkins-Kozen acceleration to itself and study the resulting hierarchy of increasingly fast accelerations.

We show by an example that the number of reduction steps needed to compute a prefix Gröbner basis in a free monoid ring by interreduction can in fact be exponential in the size of the input. This answers an open question posed by Zeckzer in [Ze00].

In this paper, it is shown that the

Feedback Vertex Set

problem on unweighted, undirected graphs has a kernel of cubic size. I.e., a polynomial time algorithm is described, that, when given a graph

G

and an integer

k

, finds a graph

H

and integer

k

′ ≤ 

k

, such that

H

has a feedback vertex set with at most

k

′ vertices, if and only if

G

has a feedback vertex set with at most

k

vertices, and

H

has at most

O

(

k

3

) vertices and edges. This improves upon a result by Burrage et al. [8] who gave a kernel for

Feedback Vertex Set

of size

O

(

k

11

).

One can easily make the algorithm constructive, and transform a minimum size feedback vertex set of

H

with at most

k

′ vertices into a minimum size feedback vertex set of

G

. The kernelization algorithm can be used as a first step of an FPT algorithm for

Feedback Vertex Set

, but also as a preprocessing heuristic for the problem.

We study how many vertices in a rank-

r

hypergraph can belong to the union of all inclusion-minimal hitting sets of at most

k

vertices. This union is interesting in certain combinatorial inference problems with hitting sets as hypotheses, as it provides a problem kernel for likelihood computations (which are essentially counting problems) and contains the most likely elements of hypotheses. We give worst-case bounds on the size of the union, depending on parameters

r

,

k

and the size

k

*

of a minimum hitting set. (Note that

k

 ≥ 

k

*

is allowed.) Our result for

r

 = 2 is tight. The exact worst-case size for any

r

 ≥ 3 remains widely open. By several hypergraph decompositions we achieve nontrivial bounds with potential for further improvements.

The problem of dynamically recognizing a class of graphs has received much attention recently. Given an input graph and a sequence of operations (vertex and edge additions and deletions) to be performed on that graph, the algorithm must determine after each operation if the resulting graph is still a member of the class in question. This paper presents the first dynamic recognition algorithm for distance-hereditary graphs. The algorithm handles edge additions and deletions, and is optimal in that each operation can be performed in constant time. In doing so, the paper completely characterizes when an edge can be added to and removed from a distance-hereditary graph with the result remaining distance-hereditary, and develops a new representation for these graphs in terms of cographs.

We present an algorithm that finds the maximal attractor (limit set) of those cellular automata whose maximal attractor is a sofic subshift.

Wang tiles are unit size squares with colored edges. To know if a given finite set of Wang tiles can tile the plane while respecting colors on edges is undecidable. Berger’s proof of this result shows the equivalence between tilings and Turing machines and thus tilings can be seen as a computing model. We thus have tilings that are Turing-universal, but there lacks a proper notion of universality for tilings. In this paper, we introduce natural notions of universality and completeness for tilings. We construct some universal tilings and try to make a first hierarchy of tile sets with a universality criteria.

We give a characterization, in terms of computational complexity, of the family

Rec

1

of the unary picture languages that are tiling recognizable. We introduce quasi-unary strings to represent unary pictures and we prove that any unary picture language

L

is in

Rec

1

if and only if the set of all quasi-unary strings encoding the elements of

L

is recognizable by a one-tape nondeterministic Turing machine that is space and head-reversal linearly bounded. In particular, the result implies that the family of binary string languages corresponding to tiling-recognizable square languages lies between

NTime

(2

n

) and

NTime

(4

n

). This also implies the existence of a nontiling-recognizable unary square language that corresponds to a binary string language recognizable in nondeterministic time

O

(4

n

log

n

).

Classification:

automata and formal languages, computational complexity.

In this paper, we consider Kearns’ [4] Statistical Query Model of learning. It is well known [3] that the number of statistical queries, needed for “weakly learning” an unknown target concept (i.e. for gaining significant advantage over random guessing) is polynomially related to the so-called Statistical Query dimension of the concept class. In this paper, we provide a similar characterization for “strong learning” where the learners final hypothesis is required to approximate the unknown target concept up to a small rate of misclassification. The quantity that characterizes strong learnability in the Statistical Query model is a surprisingly close relative of (though not identical to) the Statistical Query dimension. For the purpose of proving the main result, we provide other characterizations of strong learnability which are given in terms of covering numbers and related notions. These results might find some interest in their own right. All characterizations are purely information-theoretical and ignore computational issues.

This paper accomplishes the last step in a series of consistency theorems for Bayesian learners based on discree hypothesis class, being initiated by Solomonoff’s 1978 work. Precisely, we show the generalization of a performance guarantee for Bayesian stochastic model selection, which has been proven very recently by the author for finite observation space, to countable and continuous observation space as well as mixtures. This strong result is (to the author’s knowledge) the first of this kind for stochastic model selection. It states almost sure consistency of the learner in the realizable case, that is, where one of the hypotheses/models considered coincides with the truth. Moreover, it implies error bounds on the difference of the predictive distribution to the true one, and even loss bounds w.r.t. arbitrary loss functions. The set of consistency theorems for the three natural variants of discrete Bayesian prediction, namely marginalization, MAP, and stochastic model selection, is thus being completed for general observation space. Hence, this is the right time to recapitulate all these results, to present them in a unified context, and to discuss the different situations of Bayesian learning and its different methods.

We introduce a new class

VPSPACE

of families of polynomials. Roughly speaking, a family of polynomials is in

VPSPACE

if its coefficients can be computed in polynomial space. Our main theorem is that if (uniform, constant-free)

VPSPACE

families can be evaluated efficiently then the class

${\sf PAR}_{\mathbb{R}}$

of decision problems that can be solved in parallel polynomial time over the real numbers collapses to

P

ℝ

. As a result, one must first be able to show that there are

${\sf VPSPACE}$

families which are hard to evaluate in order to separate

$\sf{P}_{\mathbb{R}}$

from

$\sf{NP}_{\mathbb{R}}$

, or even from

$\sf{PAR}_{\mathbb{R}}$

.

In holographic algorithms,

symmetric signatures

have been particularly useful. We give a complete characterization of these symmetric signatures over all bases of size 1. These improve previous results [4] where only symmetric signatures over the Hadamard basis (special basis of size 1) were obtained. In particular, we give a complete list of Boolean symmetric signatures over bases of size 1.

It is an open problem whether signatures over bases of higher dimensions are strictly more powerful. The recent result by Valiant [18] seems to suggest that bases of size 2 might be indeed more powerful than bases of size 1. This result is with regard to a restrictive counting version of #SAT called #Pl-Rtw-Mon-3CNF. It is known that the problem is #P-hard, and its mod 2 version is ⊕P-hard. Yet its mod 7 version is solvable in polynomial time by holographic algorithms. This was accomplished by a suitable symmetric signature over a basis of size 2 [18]. We show that the same unexpected holographic algorithm can be realized over a basis of size 1. Furthermore we prove that 7 is the only modulus for which such an “accidental algorithm” exists.

We show how to generate randomized roundings of rational vectors that satisfy hard cardinality constraints and allow large deviations bounds. This improves and extends earlier results by Srinivasan (FOCS 2001), Gandhi et al. (FOCS 2002) and the author (STACS 2006). Roughly speaking, we show that also for rounding arbitrary rational vectors randomly or deterministically, it suffices to understand the problem for

$\{0,\tfrac 12\}$

vectors (which typically is much easier). So far, this was only known for vectors with entries in 2

 − ℓ

ℤ, ℓ ∈ ℕ.

To prove the general case, we exhibit a number of results of independent interest, in particular, a quite useful lemma on negatively correlated random variables, an extension of de Werra’s (RAIRO 1971) coloring result for unimodular hypergraphs and a sufficient condition for a unimodular hypergraph to have a perfectly balanced non-trivial partial coloring.

We also show a new solution for the general derandomization problem for rational matrices.

This paper addresses strategies for the stable roommates problem, assuming that a stable matching is chosen at random. We investigate how a cheating man should permute his preference list so that he has a higher-ranking roommate probabilistically.

In the first part of the paper, we identify a necessary condition for creating a new stable roommate for the cheating man. This condition precludes any possibility of his getting a new roommate ranking higher than all his stable roommates when everyone is truthful. Generalizing to the case that multiple men collude, we derive another impossibility result: given any stable matching in which a subset of men get their best possible roommates, they cannot cheat to create a new stable matching in which they all get strictly better roommates than in the given matching.

Our impossibility result, considered in the context of the stable marriage problem, easily re-establishes the celebrated Dubins-Freedman Theorem. The more generalized Demange-Gale-Sotomayor Theorem states that a coalition of men and women cannot cheat to create a stable matching in which everyone of them gets a strictly better partner than in the Gale-Shapley algorithm (with men proposing). We give a sharper result: a coalition of men and women cannot cheat together so that, in a newly-created stable matching, every man in the coalition gets a strictly better partner than in the Gale-Shapley algorithm while none of the women in the coalition is worse off.

In the second part of the paper, we present two cheating strategies that guarantee that the cheating man’s new probability distribution over stable roommates majorizes the original one. These two strategies do not require the knowledge of the probability distribution of the cheating man. This is important because the problem of counting stable matchings is #P-complete. Our strategies only require knowing the set of stable roommates that the cheating man has and can be formulated in polynomial time. Our second cheating strategy has an interesting corollary in the context of stable marriage with the Gale-Shapley algorithm. Any woman-optimal strategy will ensure that every woman, cheating or otherwise, ends up with a partner at least as good as when everyone is truthful.

We consider the problem of maintaining aggregates over recent elements of a massive data stream. Motivated by applications involving network data, we consider

asynchronous

data streams, where the observed order of data may be different from the order in which the data was generated. The set of recent elements is modeled as a

sliding timestamp window

of the stream, whose elements are changing continuously with time. We present the first

deterministic

algorithms for maintaining a small space summary of elements in a sliding timestamp window of an asynchronous data stream. The summary can return approximate answers for the following fundamental aggregates:

basic count

, the number of elements within the sliding window, and

sum

, the sum of all element values within the sliding window. For basic counting, the space taken by our summary is

O

(log

W

·log

B

·(log

W

 + log

B

)/

ε

) bits, where

B

is an upper bound on the value of the basic count,

W

is an upper bound on the width of the timestamp window, and

ε

is the desired relative error. Our algorithms are based on a novel data structure called

splittable histogram

. Prior to this work, randomized algorithms were known for this problem, which provide weaker guarantees than those provided by our deterministic algorithms.

The parallel complexity class

NC

1

has many equivalent models such as bounded width branching programs. Caussinus et.al [10] considered arithmetizations of two of these classes,

#NC

1

and

#BWBP

. We further this study to include arithmetization of other classes. In particular, we show that counting paths in branching programs over visibly pushdown automata has the same power as

#BWBP

, while counting proof-trees in logarithmic width formulae has the same power as

#NC

1

. We also consider polynomial-degree restrictions of

${\sf SC}^{i}$

, denoted

${\sf sSC}^{i}$

, and show that the Boolean class

${\sf sSC}{^1}$

lies between

NC

1

and

L

, whereas

${\sf sSC}^0$

equals

${\sf NC}^1$

. On the other hand,

${\sf \#}{\sf sSC}^0$

contains

#BWBP

and is contained in

FL

, and

#sSC

1

contains

#NC

1

and is in

${\sf SC}^{2}$

. We also investigate some closure properties of the newly defined arithmetic classes.

The

perfect matching problem

is known to be in

P

, in randomized

NC

, and it is hard for

NL

. Whether the perfect matching problem is in

NC

is one of the most prominent open questions in complexity theory regarding parallel computations.

Grigoriev and Karpinski [GK87] studied the perfect matching problem for bipartite graphs with polynomially bounded permanent. They showed that for such bipartite graphs the problem of deciding the existence of a perfect matchings is in

NC

2

, and counting and enumerating all perfect matchings is in

NC

3

. For general graphs with a polynomially bounded number of perfect matchings, they show both problems to be in

NC

3

.

In this paper we extend and improve these results. We show that for any graph that has a polynomially bounded number of perfect matchings, we can construct all perfect matchings in

NC

2

. We extend the result to weighted graphs.

We study languages with bounded communication complexity in the multiparty “input on the forehead model” with worst-case partition. In the two-party case, languages with bounded complexity are exactly those recognized by programs over commutative monoids [19]. This can be used to show that these languages all lie in shallow ACC

0

.

In contrast, we use coding techniques to show that there are languages of arbitrarily large circuit complexity which can be recognized in constant communication by

k

players for

k

 ≥ 3. However, we show that if a language has a neutral letter and bounded communication complexity in the

k

-party game for some fixed

k

then the language is in fact regular. We give an algebraic characterization of regular languages with this property. We also prove that a symmetric language has bounded

k

-party complexity for some fixed

k

iff it has bounded two party complexity.

We consider the problem of computing an approximate minimum cycle basis of an undirected edge-weighted graph

G

with

m

edges and

n

vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over

$\mathbb{F}_2$

generated by these vectors is the cycle space of

G

. A set of cycles is called a cycle basis of

G

if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of

G

. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction.

We present two new algorithms to compute an approximate minimum cycle basis. For any integer

k

 ≥ 1, we give (2

k

 − 1)-approximation algorithms with expected running time

O

(

k

m

n

1 + 2/

k

 + 

m

n

(1 + 1/

k

)(

ω

 − 1)

) and deterministic running time

O

(

n

3 + 2/

k

), respectively. Here

ω

is the best exponent of matrix multiplication. It is presently known that

ω

 < 2.376. Both algorithms are

o

(

m

ω

) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the

Θ

(

m

ω

) bound.

We also present a 2-approximation algorithm with

$O(m^{\omega}\sqrt{n\log n})$

expected running time, a linear time 2-approximation algorithm for planar graphs and an

O

(

n

3

) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

We present a

$(\frac{2}{3}-\epsilon)$

-approximation algorithm for the partial latin square extension (PLSE) problem. This improves the current best bound of

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

due to Gomes, Regis, and Shmoys [5]. We also show that PLSE is APX-hard.

We then consider two new and natural variants of PLSE. In the first, there is an added restriction that at most

k

colors are to be used in the extension; for this problem, we prove a tight approximation threshold of

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

. In the second, the goal is to find the largest partial Latin square embedded in the given partial Latin square that can be extended to completion; we obtain a

$\frac{1}{4}$

-approximation algorithm in this case.

The

min-sum k

-clustering

problem is to partition a metric space (

P

,

d

) into

k

clusters

$C_1, \ldots,C_k \subseteq P$

such that

$\sum_{i=1}^k \sum_{p,q \in C_i} d(p,q)$

is minimized. We show the first efficient construction of a

coreset

for this problem. Our coreset construction is based on a new adaptive sampling algorithm. Using our coresets we obtain three main algorithmic results.

The first result is a sublinear time (4 + 

ε

)-approximation algorithm for the min-sum

k

-clustering problem in metric spaces. The running time of this algorithm is

$\widetilde{O}(n)$

for any constant

k

and

ε

, and it is

o

(

n

2

) for all

k

 = 

o

(log

n

/loglog

n

). Since the description size of the input is

Θ

(

n

2

), this is

sublinear

in the input size.

Our second result is the first

pass-efficient data streaming algorithm

for min-sum

k

-clustering in the distance oracle model, i.e., an algorithm that uses

${\mathit{poly}}(\log n, k)$

space and makes 2 passes over the input point set arriving as a data stream.

Our third result is a

sublinear-time

polylogarithmic-factor- approximation algorithm for the min-sum

k

-clustering problem for arbitrary values of

k

.

To develop the coresets, we introduce the concept of

α-preserving metric embeddings

. Such an embedding satisfies properties that (a the distance between any pair of points does not decrease, and (b) the cost of an optimal solution for the considered problem on input (

P

,

d

′) is within a constant factor of the optimal solution on input (

P

,

d

). In other words, the idea is find a metric embedding into a (structurally simpler) metric space that approximates the original metric up to a factor of

α

with respect to a certain problem

. We believe that this concept is an interesting generalization of coresets.

In this paper we focus our attention on the decision problem for Propositional Neighborhood Logic (PNL for short). PNL is the proper subset of Halpern and Shoham’s modal logic of intervals whose modalities correspond to Allen’s relations

meets

and

met by

. We show that the satisfiability problem for PNL over the integers is NEXPTIME-complete. Then, we develop a sound and complete tableau-based decision procedure and we prove its optimality.

Hybrid logics extend modal logics by first-order concepts, in particular they allow a limited use of variables. Unfortunately, in general, satisfiability for hybrid formulas is undecidable and model checking is

PSPACE

-hard. It is shown here that on the linear frame (

ω

, < ), the restriction to one name, although expressively complete, has

EXPSPACE

-complete satisfiability and polynomial time model-checking.

For the upper bound, a result of independent interest is found: Non-emptiness for alternating two-way Büchi automata with one pebble is

EXPSPACE

-complete.

Coalgebras provide a unifying semantic framework for a wide variety of modal logics. It has previously been shown that the class of coalgebras for an endofunctor can always be axiomatised in rank 1. Here we establish the converse, i.e. every rank 1 modal logic has a sound and

strongly

complete coalgebraic semantics. As a consequence, recent results on coalgebraic modal logic, in particular generic decision procedures and upper complexity bounds, become applicable to arbitrary rank 1 modal logics, without regard to their semantic status; we thus obtain purely syntactic versions of these results. As an extended example, we apply our framework to recently defined deontic logics.

Extraspecial groups form a remarkable subclass of

p

-groups. They are also present in quantum information theory, in particular in quantum error correction. We give here a polynomial time quantum algorithm for finding hidden subgroups in extraspecial groups. Our approach is quite different from the recent algorithms presented in [17] and [2] for the Heisenberg group, the extraspecial

p

-group of size

p

3

and exponent

p

. Exploiting certain nice automorphisms of the extraspecial groups we define specific group actions which are used to reduce the problem to hidden subgroup instances in abelian groups that can be dealt with directly.

Schur duality decomposes many copies of a quantum state into subspaces labeled by partitions, a decomposition with applications throughout quantum information theory. Here we consider applying Schur duality to the problem of distinguishing coset states in the standard approach to the hidden subgroup problem. We observe that simply measuring the partition (a procedure we call

weak Schur sampling

) provides very little information about the hidden subgroup. Furthermore, we show that under quite general assumptions, even a combination of weak Fourier sampling and weak Schur sampling fails to identify the hidden subgroup. We also prove tight bounds on how many coset states are required to solve the hidden subgroup problem by weak Schur sampling, and we relate this question to a quantum version of the collision problem.

Since quantum information is continuous, its handling is sometimes surprisingly harder than the classical counterpart. A typical example is cloning; making a copy of digital information is straightforward but it is not possible exactly for quantum information. The question in this paper is whether or not

quantum

network coding is possible. Its classical counterpart is another good example to show that digital information flow can be done much more efficiently than conventional (say, liquid) flow.

Our answer to the question is similar to the case of cloning, namely, it is shown that quantum network coding is possible if approximation is allowed, by using a simple network model called Butterfly. In this network, there are two flow paths,

s

1

to

t

1

and

s

2

to

t

2

, which shares a single bottleneck channel of capacity one. In the classical case, we can send two bits simultaneously, one for each path, in spite of the bottleneck. Our results for quantum network coding include: (i) We can send any quantum state

$|\psi_1\rangle$

from

s

1

to

t

1

and

$|\psi_2\rangle$

from

s

2

to

t

2

simultaneously with a fidelity strictly greater than 1/2. (ii) If one of

$|\psi_1\rangle$

and

$|\psi_2\rangle$

is classical, then the fidelity can be improved to 2/3. (iii) Similar improvement is also possible if

$|\psi_1\rangle$

and

$|\psi_2\rangle$

are restricted to only a finite number of (previously known) states. (iv) Several impossibility results including the general upper bound of the fidelity are also given.

We consider commutative string rewriting systems (Vector Addition Systems, Petri nets), i.e., string rewriting systems in which all pairs of letters commute. We are interested in reachability: given a rewriting system

R

and words

v

and

w

, can

v

be rewritten to

w

by applying rules from

R

? A famous result states that reachability is decidable for commutative string rewriting systems. We show that reachability is decidable for a union of two such systems as well. We obtain, as a special case, that if

h

:

U

→

S

and

g

:

U

→

T

are homomorphisms of commutative monoids, then their pushout has a decidable word problem. Finally, we show that, given commutative monoids

U

,

S

and

T

satisfying

S

 ∩ 

T

 = 

U

, it is decidable whether there exists a monoid

M

such that

$S\cup T\subseteq M$

; we also show that the problem remains decidable if we require

M

to be commutative, too.

We consider deducibility constraints, which are equivalent to particular Diophantine systems, arising in the automatic verification of security protocols, in presence of associative and commutative symbols. We show that deciding such Diophantine systems is, in general, undecidable. Then, we consider a simple subclass, which we show decidable. Though the solutions of these problems are not necessarily semi-linear sets, we show that there are (computable) semi-linear sets whose minimal solutions are not too far from the minimal solutions of the system. Finally, we consider a small variant of the problem, for which there is a much simpler decision algorithm.

In many security protocols, such as group protocols, principals have to perform iterative or recursive computations. We call such protocols

recursive protocols

. Recently, first results on the decidability of the security of such protocols have been obtained. While recursive protocols often employ operators with algebraic, security relevant properties, such as the exclusive OR (XOR), the existing decision procedures, however, cannot deal with such operators and their properties. In this paper, we show that the security of recursive protocols with XOR is decidable (w.r.t. a bounded number of sessions) for a class of protocols in which recursive computations of principals are modeled by certain Horn theories. Interestingly, this result can be obtained by a reduction to the case without XOR. We also show that relaxing certain assumptions of our model lead to undecidability.

An instance of the

sorting buffer

problem consists of a metric space and a server, equipped with a finite-capacity buffer capable of holding a limited number of requests. An additional ingredient of the input is an online sequence of requests, each of which is characterized by a destination in the given metric; whenever a request arrives, it must be stored in the sorting buffer. At any point in time, a currently pending request can be served by drawing it out of the buffer and moving the server to its corresponding destination. The objective is to serve all input requests in a way that minimizes the total distance traveled by the server.

In this paper, we focus our attention on instances of the problem in which the underlying metric is either an

evenly-spaced

or a

continuous

line metric. Our main findings can be briefly summarized as follows:

1. We present a

deterministic

O

(log

n

) competitive algorithm for

n

-point evenly-spaced line metrics. This result improves on a randomized

O

(log

2

n

) competitive algorithm due to Khandekar and Pandit.

2. We devise a

deterministic

O

(log

N

loglog

N

) competitive algorithm for continuous line metrics, where

N

is the input sequence length.

3. We establish the first non-trivial lower bound for the evenly-spaced case, by proving that the competitive ratio of any deterministic algorithm is at least

$\frac{ 2 + \sqrt{3} }{ \sqrt{3}} \approx 2.154$

.

Roughgarden and Sundararajan recently introduced an alternative measure of efficiency for cost sharing mechanisms. We study cost sharing methods for combinatorial optimization problems using this novel efficiency measure, with a particular focus on scheduling problems. While we prove a lower bound of

Ω

(log

n

) for a very general class of problems, we give a best possible cost sharing method for minimum makespan scheduling. Finally, we show that no budget balanced cost sharing methods for completion or flow time objectives exist.

We prove that every triconnected planar graph on

n

vertices is definable by a first order sentence that uses at most 15 variables and has quantifier depth at most 11 log

2

n

 + 45. As a consequence, a canonic form of such graphs is computable in AC

1

by the 14-dimensional Weisfeiler-Lehman algorithm. This gives us another AC

1

algorithm for the planar graph isomorphism.

We contribute to the study of efficient enumeration algorithms for all solutions of constraint satisfaction problems. The only algorithm known so far, presented by Creignou and Hébrard [CH97] and generalized by Cohen [Coh04], reduces the enumeration problem for a constraint language

Γ

to the decision problem for a slightly enlarged constraint language

Γ

 + 

, i.e., it yields an efficient enumeration algorithm for the case where

${\sf CSP}(\it \Gamma^+)$

is tractable. We develop a new class of algorithms, yielding efficient enumeration algorithms for a broad class of constraint languages. For the three-element domain, we achieve a first step towards a dichotomy theorem for the enumeration problem.