Automata, Languages and Programming

Advances in data acquisition technology, together with the imminent demise of Moore’s Law, are prompting a rethink of basic algorithm design principles. Computing with massive data sets, data streaming, coping with uncertainty, priced computation, property testing, and sublinear algorithms are all parts of the story. So is the growing trend toward using algorithms as modeling tools for natural phenomena. I will discuss some of these developments; in particular, dimension reduction, sublinear algorithms, online reconstruction, and self-improving algorithms.

In this paper, we identify some issues in the interplay between practice and theory in cryptography, issues that have repeatedly appeared in different incarnations over the years. These issues are related to fundamental concepts in the field, e.g., to what extent we can prove that a system is secure and what theoretic results on security mean for practical applications. We argue that several such issues are often overlooked or misunderstood, and that it may be very productive if both theoreticians and practitioners think more consciously about these issues and act accordingly.

Nexus is a new operating system that runs on computers equipped with tamperproof secure co-processors; it is designed to support the construction of

trustworthy applications-applications

where actions can be attributed with some measure of confidence and where trust assumptions are explicit.

We present a series of techniques for the design of subexponential parameterized algorithms for graph problems. The design of such algorithms usually consists of two main steps: first find a branch- (or tree-) decomposition of the input graph whose width is bounded by a sublinear function of the parameter and, second, use this decomposition to solve the problem in time that is single exponential to this bound. The main tool for the first step is Bidimensionality Theory. Here we present the potential, but also the boundaries, of this theory. For the second step, we describe recent techniques, associating the analysis of sub-exponential algorithms to combinatorial bounds related to Catalan numbers. As a result, we have

$2^{O(\sqrt{k})}\cdot n^{O(1)}$

time algorithms for a wide variety of parameterized problems on graphs, where

n

is the size of the graph and

k

is the parameter.

We consider several online scheduling problems that arise when customers request make-to-order products from a company. At the time of the order, the company must quote a due date to the customer. To satisfy the customer, the company must produce the good by the due date. The company must have an online algorithm with two components: The first component sets the due dates, and the second component schedules the resulting jobs with the goal of meeting the due dates.

The most basic quality of service measure for a job is the

quoted lead time

, which is the difference between the due date and the release time. We first consider the basic problem of minimizing the average quoted lead time. We show that there is a (1 + 

ε

)-speed

$O(\frac{\log k}{\epsilon})$

-competitive algorithm for this problem (here

k

is the ratio of the maximum work of a job to the minimum work of a job), and that this algorithm is essentially optimally competitive. This result extends to the case that each job has a weight and the objective is weighted quoted lead time.

We then introduce the following general setting: there is a non- increasing profit function

p

i

(

t

) associated with each job

J

i

. If the customer for job

J

i

is quoted a due date of

d

i

, then the profit obtained from completing this job by its due date is

p

i

(

d

i

). We consider the objective of maximizing profits. We show that if the company must finish each job by its due date, then there is no

O

(1)-speed poly-log-competitive algorithm. However, if the company can miss the due date of a job, at the cost of forgoing the profits from that job, then we show that there is a (1 + 

ε

)-speed

O

(1 + 1/

ε

)-competitive algorithm, and that this algorithm is essentially optimally competitive.

In this paper, we consider the mechanism design version of the fractional variant of the scheduling problem on unrelated machines. We give a lower bound of 2 − 1/

n

for any fractional truthful mechanism, while we propose a truthful mechanism that achieves approximation of 1 + (

n

 − 1)/2, for

n

machines. We also focus on an interesting family of allocation algorithms, the

task-independent

algorithms. We give a lower bound of 1 + (

n

 − 1)/2, that holds for every (not only monotone) allocation algorithm of this class. Under this consideration, our truthful independent mechanism is the best that we can hope from this family of algorithms.

We study the classic problem of estimating the sum of

n

variables. The traditional uniform sampling approach requires a linear number of samples to provide any non-trivial guarantees on the estimated sum. In this paper we consider various sampling methods besides uniform sampling, in particular sampling a variable with probability proportional to its value, referred to as

linear weighted sampling

. If only linear weighted sampling is allowed, we show an algorithm for estimating sum with

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

samples, and it is almost optimal in the sense that

$\Omega(\sqrt n)$

samples are necessary for any reasonable sum estimator. If both uniform sampling and linear weighted sampling are allowed, we show a sum estimator with

$\tilde{O}(\sqrt[3]n)$

samples. More generally, we may allow general weighted sampling where the probability of sampling a variable is proportional to any function of its value. We prove a lower bound of

$\Omega(\sqrt[3]n)$

samples for any reasonable sum estimator using general weighted sampling, which implies that our algorithm combining uniform and linear weighted sampling is an almost optimal sum estimator.

In this paper we introduce a new lattice problem, the

subspace avoiding problem

(

Sap

). We describe a probabilistic single exponential time algorithm for

Sap

for arbitrary ℓ

p

norms. We also describe polynomial time reductions for four classical problems from the geometry of numbers, the

shortest vector problem

, the

closest vector problem

, the

successive minima problem

, and the

shortest independent vectors problem (

)

to

Sap

, establishing probabilistic single exponential time algorithms for them. The result generalize and extend previous results of Ajtai, Kumar and Sivakumar. The results on

and

are new for all norms. The results on

and

generalize previous results of Ajtai et al. for the ℓ

2

norm to arbitrary ℓ

p

norms.

A

spanner

of an undirected unweighted graph is a subgraph that approximates the distance metric of the original graph with some specified accuracy. Specifically, we say

H

 ⊆ 

G

is an

f

-spanner of

G

if any two vertices

u

,

v

at distance

d

in

G

are at distance at most

f

(

d

) in

H

. There is clearly some tradeoff between the sparsity of

H

and the distortion function

f

, though the nature of this tradeoff is still poorly understood.

In this paper we present a simple, modular framework for constructing sparse spanners that is based on interchangable components called

connection schemes

. By assembling connection schemes in different ways we can recreate the additive 2- and 6-spanners of Aingworth et al. and Baswana et al. and improve on the (1 + 

ε

,

β

)-spanners of Elkin and Peleg, the sublinear additive spanners of Thorup and Zwick, and the (non constant) additive spanners of Baswana et al. Our constructions rival the simplicity of all comparable algorithms and provide substantially better spanners, in some cases reducing the density

doubly

exponentially.

We present a linear time algorithm exactly solving the

2-edge connected spanning subgraph (2-ECSS) problem

in a graph of bounded treewidth. Using this with Klein’s diameter reduction technique [15], we find a linear time PTAS for the problem in unweighted planar graphs, and the first PTAS for the problem in weighted planar graphs.

This paper studies labeling schemes for the vertex connectivity function on general graphs. We consider the problem of labeling the nodes of any

n

-node graph is such a way that given the labels of two nodes

u

and

v

, one can decide whether

u

and

v

are

k

-vertex connected in

G

, i.e., whether there exist

k

vertex disjoint paths connecting

u

and

v

. The paper establishes an upper bound of

k

2

log

n

on the number of bits used in a label. The best previous upper bound for the label size of such labeling scheme is 2

k

log

n

.

This paper studies the gap between quantum one-way communication complexity

Q

(

f

) and its classical counterpart

C

(

f

), under the

unbounded-error

setting, i.e., it is enough that the success probability is strictly greater than 1/2. It is proved that for

any

(total or partial) Boolean function

f

,

Q

(

f

) = ⌈

C

(

f

)/2 ⌉, i.e., the former is always exactly one half as large as the latter. The result has an application to obtaining an exact bound for the existence of (

m

,

n

,

p

)-QRAC which is the

n

-qubit random access coding that can recover any one of

m

original bits with success probability ≥ 

p

. We can prove that (

m

,

n

, > 1/2)-QRAC exists if and only if

m

 ≤ 2

2

n

− 1. Previously, only the non-existence of (2

2

n

,

n

, > 1/2)-QRAC was known.

We prove a general lower bound on the bounded-error entanglement-assisted quantum communication complexity of Boolean functions. The bound is based on the concept that any classical or quantum protocol to evaluate a function on distributed inputs can be turned into a quantum communication protocol. As an application of this bound, we give a very simple proof of the statement that almost all Boolean functions on

n

 + 

n

bits have communication complexity linear in

n

, even in the presence of unlimited entanglement.

We solve some fundamental problems in the number-on-forehead (NOF)

k

-party communication model. We show that there exists a function which has at most logarithmic communication complexity for randomized protocols with a one-sided error probability of 1/3 but which has linear communication complexity for deterministic protocols. The result is true for

k

 = 

n

O

(1)

players, where

n

is the number of bits on each players’ forehead. This separates the analogues of RP and P in the NOF communication model. We also show that there exists a function which has constant randomized complexity for public coin protocols but at least logarithmic complexity for private coin protocols. No larger gap between private and public coin protocols is possible. Our lower bounds are existential and we do not know of any explicit function which allows such separations. However, for the 3-player case we exhibit an explicit function which has

Ω

(loglog

n

) randomized complexity for private coins but only constant complexity for public coins.

It follows from our existential result that any function that is complete for the class of functions with polylogarithmic nondeterministic

k

-party communication complexity does not have polylogarithmic deterministic complexity. We show that the set intersection function, which is complete in the number-in-hand model, is not complete in the NOF model under cylindrical reductions.

The

edit distance

between two ordered rooted trees with vertex labels is the minimum cost of transforming one tree into the other by a sequence of elementary operations consisting of deleting and relabeling existing nodes, as well as inserting new nodes. In this paper, we present a worst-case

O

(

n

3

)-time algorithm for this problem, improving the previous best

O

(

n

3

log

n

)-time algorithm [7]. Our result requires a novel adaptive strategy for deciding how a dynamic program divides into subproblems, together with a deeper understanding of the previous algorithms for the problem. We prove the optimality of our algorithm among the family of

decomposition strategy

algorithms—which also includes the previous fastest algorithms—by tightening the known lower bound of

Ω

(

n

2

log

2

n

) [4] to

Ω

(

n

3

), matching our algorithm’s running time. Furthermore, we obtain matching upper and lower bounds of

$\Theta(n m^2 (1 + \log \frac{n}{m}))$

when the two trees have sizes

m

and

n

where

m

 < 

n

.

Exploring a graph through search is one of the most basic building blocks of various applications. In a setting with a huge state space, such as in testing and verification, optimizing the search may be crucial. We consider the problem of visiting all states in a graph where edges are generated by actions and the (reachable) states are not known in advance. Some of the actions may commute, i.e., they result in the same state for every order in which they are taken (this is the case when the actions are performed independently by different processes). We show how to use commutativity to achieve full coverage of the states while traversing considerably fewer edges.

We define and study two versions of the bipartite matching problem in the framework of two-stage stochastic optimization with recourse. In one version the uncertainty is in the second stage costs of the edges, in the other version the uncertainty is in the set of vertices that needs to be matched. We prove lower bounds, and analyze efficient strategies for both cases. These problems model real-life stochastic integral planning problems such as commodity trading, reservation systems and scheduling under uncertainty.

We study a fundamental result of Impagliazzo (

FOCS’95

) known as the hard-core set lemma. Consider any function

f

:{0,1}

n

→{0,1} which is “mildly-hard”, in the sense that any circuit of size

s

must disagree with

f

on at least

δ

fraction of inputs. Then the hard-core set lemma says that

f

must have a hard-core set

H

of density

δ

on which it is “extremely hard”, in the sense that any circuit of size

s’=

$ {O} {(s/({{1}\over{\varepsilon^2}}\log(\frac{1}{\varepsilon\delta})))}$

must disagree with

f

on at least (1 − 

ε

)/2 fraction of inputs from

H

.

There are three issues of the lemma which we would like to address: the loss of circuit size, the need of non-uniformity, and its inapplicability to a low-level complexity class. We introduce two models of hard-core set constructions, a strongly black-box one and a weakly black-box one, and show that those issues are unavoidable in such models.

First, we show that in any strongly black-box construction, one can only prove the hardness of a hard-core set for smaller circuits of size at most

$s'=O(s/(\frac{1}{\varepsilon^2}log\frac{1}{\delta}))$

. Next, we show that any weakly black-box construction must be inherently non-uniform — to have a hard-core set for a class

G

of functions, we need to start from the assumption that

f

is hard against a non-uniform complexity class with

$\Omega(\frac{1}{\varepsilon}log|G|)$

bits of advice. Finally, we show that weakly black-box constructions in general cannot be realized in a low-level complexity class such as

AC

0

[

p

] — the assumption that

f

is hard for

AC

0

[

p

] is not sufficient to guarantee the existence of a hard-core set.

Say that

f

:{0,1}

n

→{0,1}

ε

-approximates

g

: {0,1}

n

→{0,1} if the functions disagree on at most an

ε

fraction of points. This paper contains two results about approximation by DNF and other small-depth circuits:

(1) For every constant 0 < 

ε

< 1/2 there is a DNF of size

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

that

ε

-approximates the Majority function on

n

bits, and this is optimal up to the constant in the exponent.

(2) There is a monotone function

$\mathcal{F} : \{{0,1}\}^{n} \rightarrow \{{0,1}\}$

with total influence (AKA average sensitivity)

${\mathbb{I}}({\mathcal{F}}) \leq O(\log n)$

such that any DNF or CNF that .01-approximates

${\mathcal{F}}$

requires size 2

Ω

(

n

/ log

n

)

and such that

any

unbounded fan-in AND-OR-NOT circuit that .01-approximates

${\mathcal{F}}$

requires size

Ω

(

n

/ log

n

). This disproves a conjecture of Benjamini, Kalai, and Schramm (appearing in [BKS99,Kal00,KS05]).

We define new complexity classes in the Blum-Shub-Smale theory of computation over the reals, in the spirit of the polynomial hierarchy, with the help of infinitesimal and generic quantifiers. Basic topological properties of semialgebraic sets like boundedness, closedness, compactness, as well as the continuity of semialgebraic functions are shown to be complete in these new classes. All attempts to classify the complexity of these problems in terms of the previously studied complexity classes have failed. We also obtain completeness results in the Turing model for the corresponding discrete problems. In this setting, it turns out that infinitesimal and generic quantifiers can be eliminated, so that the relevant complexity classes can be described in terms of usual quantifiers only.

We provide a framework for online conflict-free coloring (CF-coloring) of any hypergraph. We use this framework to obtain an efficient randomized online algorithm for CF-coloring any

k

-degenerate hypergraph. Our algorithm uses

O

(

k

log

n

) colors with high probability and this bound is asymptotically optimal for any constant

k

. Moreover, our algorithm uses

O

(

k

log

k

log

n

) random bits with high probability. As a corollary, we obtain asymptotically optimal randomized algorithms for online CF-coloring some hypergraphs that arise in geometry. Our algorithm uses exponentially fewer random bits compared to previous results.

We introduce deterministic online CF-coloring algorithms for points on the line with respect to intervals and for points on the plane with respect to halfplanes (or unit discs) that use

Θ

(log

n

) colors and recolor

O

(

n

) points in total.

We study the problem of the amount of information (advice) about a graph that must be given to its nodes in order to achieve fast distributed computations. The required size of the advice enables to measure the information sensitivity of a network problem. A problem is information sensitive if little advice is enough to solve the problem rapidly (i.e., much faster than in the absence of any advice), whereas it is information insensitive if it requires giving a lot of information to the nodes in order to ensure fast computation of the solution. In this paper, we study the information sensitivity of distributed graph coloring.

We consider the problem of private efficient data mining of vertically-partitioned databases. Each of several parties holds a column of a data matrix (a vector) and the parties want to investigate the componentwise combination of their vectors. The parties want to minimize communication and local computation while guaranteeing privacy in the sense that no party learns more than necessary. Sublinear-communication private protocols have been primarily been studied only in the two-party case. We give efficient multiparty protocols for sampling a row of the data matrix and for computing arbitrary functions of a row, where the row index is additively shared among two or more parties. We also give protocols for approximating the componentwise sum, minimum, or maximum of the columns in which the communication and the number of public-key operations are at most polynomial in the size of the small approximation and polylogarithmic in the number of rows.

We consider several private database query problems. The starting point of this work is the

element rank

problem: the server holds a database of

n

integers, and the user an integer

q

; the user wishes to find out how many database records are smaller than

q

, without revealing

q

; nothing else about the database should be disclosed. We show a non-interactive communication-efficient solution to this problem. We then use it to solve more complex private database queries: range queries, range queries in plane and higher-dimensional generalizations of element rank. We also show an improved solution to the

k

th

ranked element

problem [1], and a solution to

private keyword search

[9] using weaker assumptions than those of [9]. All our solutions assume semi-honest adversarial behaviour.

We present algebraic conditions on constraint languages

Γ

that ensure the hardness of the constraint satisfaction problem CSP (

Γ

) for complexity classes L, NL, P, NP and Mod

p

L. These criteria also give non-expressibility results for various restrictions of Datalog. Furthermore, we show that if CSP(

Γ

) is not first-order definable then it is L-hard. Our proofs rely on tame congruence theory and on a fine-grain analysis of the complexity of reductions used in the algebraic study of CSPs. The results pave the way for a refinement of the dichotomy conjecture stating that each CSP(

Γ

) lies in P or is NP-complete and they match the recent classification of [1] for Boolean CSP. We also infer a partial classification theorem for the complexity of CSP(

Γ

) when the associated algebra of

Γ

is the idempotent reduct of a preprimal algebra.

The

k

-consistency algorithm for constraint-satisfaction problems proceeds, roughly, by finding all partial solutions on at most

k

variables and iteratively deleting those that cannot be extended to a partial solution by one more variable. It is known that if the core of the structure encoding the scopes of the constraints has treewidth at most

k

, then the

k

-consistency algorithm is always correct. We prove the exact converse to this: if the core of the structure encoding the scopes of the constraints does not have treewidth at most

k

, then the

k

-consistency algorithm is not always correct. This characterizes the exact power of the

k

-consistency algorithm in structural terms.

We study – within the framework of propositional proof complexity – the problem of certifying unsatisfiability of CNF formulas under the promise that any satisfiable formula has many satisfying assignments, where “many” stands for an explicitly specified function Λ in the number of variables

n

. To this end, we develop propositional proof systems under different measures of promises (that is, different Λ) as extensions of resolution. This is done by augmenting resolution with axioms that, roughly, can eliminate sets of truth assignments defined by Boolean circuits. We then investigate the complexity of such systems, obtaining an exponential separation in the average-case between resolution under different size promises:

(i) Resolution has polynomial-size refutations for all unsatisfiable 3CNF formulas when the promise is

ε

.2

n

, for any constant 0 < 

ε

< 1.

(ii) There are no sub-exponential size resolution refutations for random 3CNF formulas, when the promise is 2

δn

(and the number of clauses is

o

(

n

3/2

)), for any constant 0 < 

δ

< 1.

Motivated by the challenging task of designing “secure” vote storage mechanisms, we deal with information storage mechanisms that operate in extremely hostile environments. In such environments, the majority of existing techniques for information storage and for security are susceptible to powerful adversarial attacks. In this setting, we propose a mechanism for storing a set of at most

K

elements from a large universe of size

N

on write-once memories in a manner that does not reveal the insertion order of the elements. Whereas previously known constructions were either inefficient (required

Θ

(

K

2

) memory), randomized, or employed cryptographic techniques which are unlikely to be available in hostile environments, we eliminate each of these undesirable properties. The total amount of memory used by the mechanism is linear in the number of stored elements and poly-logarithmic in the size of the universe of elements.

In addition, we consider one of the classical distributed computing problems: Conflict resolution in multiple-access channels. By establishing a tight connection with the basic building block of our mechanism, we construct the first deterministic and non-adaptive conflict resolution algorithm whose running time is optimal up to poly-logarithmic factors.

Adaptive security, while more realistic as an adversarial model, is typically much harder to achieve compared to static security in cryptographic protocol design. Universal composition (UC) provides a very attractive framework for the modular design of cryptographic protocols that captures both static and adaptive security formulations. In the UC framework, one can design protocols in hybrid worlds that allow access to idealized functionalities and then apply the universal composition theorem to obtain more concrete protocol instances. The zero-knowledge (ZK) ideal functionality is one of the most useful sub-protocols in modular cryptographic design. Given an adaptively secure protocol in the ideal ZK-hybrid-world do we always need an adaptively secure realization of the ZK functionality in order to preserve adaptive security under composition? In this work, perhaps surprisingly, we find that this is not so and in fact there are useful protocol instances that we can “trade static security for adaptive security.”

We investigate the above setting, by introducing a weakened ZK ideal functionality, called the ideal leaking-zero-knowledge functionality (LZK) that leaks some information about the witness to the adversary in a certain prescribed way. We show that while LZK is interchangeable to ZK against static adversaries, ZK is more stringent when adaptive adversaries are considered. We then proceed to characterize a class of protocols in the hybrid-ZK-world that can be “transported” to the LZK-hybrid-world without forfeiting their security against adaptive adversaries. Our results demonstrate that in such settings a static protocol realization of ZK is sufficient for ensuring adaptive security for the parent hybrid protocol something that enables simplified and substantially more efficient UC realizations of such protocols.

We provide a new characterization of certain zero-knowledge protocols as

non-interactive instance-dependent commitment-schemes

(NIC). To obtain this result we consider the notion of V-bit protocols, which are very common, and found many applications in zero-knowledge. Our characterization result states that a protocol has a V-bit zero-knowledge protocol if and only if it has a NIC. The NIC inherits its hiding property from the zero-knowledge property of the protocol, and vice versa.

Our characterization result yields a framework that strengthens and simplifies many zero-knowledge protocols in various settings. For example, applying this framework to the result of Micciancio et al. [18] (who showed that some problems, including

Graph-Nonisomorphism

and

Quadratic-Residuousity

,

unconditionally

have a concurrent zero-knowledge proof) we easily get that arbitrary, monotone boolean formulae over a large class of problems (which contains, e.g., the complement of any random self-reducible problem)

unconditionally

have a concurrent zero-knowledge proof.

We study the problem of finding occurrences of motifs in vertex-colored graphs, where a motif is a multiset of colors, and an occurrence of a motif is a subset of connected vertices whose multiset of colors equals the motif. This problem has applications in metabolic network analysis, an important area in bioinformatics. We give two positive results and three negative results that together draw sharp borderlines between tractable and intractable instances of the problem.

We prove that finding a rooted subtree with at least

k

leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves in digraphs from a wide family

$\cal L$

that includes all strong and acyclic digraphs. This settles completely an open question of Fellows and solves another one for digraphs in

$\cal L$

. Our algorithms are based on the following combinatorial result which can be viewed as a generalization of many results for a ‘spanning tree with many leaves’ in the undirected case, and which is interesting on its own: If a digraph

$D\in \cal L$

of order

n

with minimum in-degree at least 3 contains a rooted spanning tree, then

D

contains one with at least (

n

/2)

1/5

− 1 leaves.

We give an fpt approximation algorithm for the directed vertex disjoint cycle problem. Given a directed graph

G

with

n

vertices and a positive integer

k

, the algorithm constructs a family of at least

k

/

ρ

(

k

) disjoint cycles of

G

if the graph

G

has a family of at least

k

disjoint cycles (and otherwise may still produce a solution, or just report failure). Here

ρ

is a computable function such that

k

/

ρ

(

k

) is nondecreasing and unbounded. The running time of our algorithm is polynomial.

The directed vertex disjoint cycle problem is hard for the parameterized complexity class W1, and to the best of our knowledge our algorithm is the first fpt approximation algorithm for a natural W1-hard problem.

We develop a generic framework for deriving linear-size problem kernels for NP-hard problems on planar graphs. We demonstrate the usefulness of our framework in several concrete case studies, giving new kernelization results for

Connected Vertex Cover

,

Minimum Edge Dominating Set

,

Maximum Triangle Packing

, and

Efficient Dominating Set

on planar graphs. On the route to these results, we present effective, problem-specific data reduction rules that are useful in any approach attacking the computational intractability of these problems.

We consider the problem of constructing efficient locally decodable codes in the presence of a computationally bounded adversary. Assuming the existence of one-way functions, we construct

efficient

locally decodable codes with positive information rate and

low

(almost optimal) query complexity which can correctly decode any given bit of the message from constant channel error rate

ρ

. This compares favorably to our state of knowledge locally-decodable codes without cryptographic assumptions. For all our constructions, the probability for any polynomial-time adversary, that the decoding algorithm incorrectly decodes any bit of the message is negligible in the security parameter.

In the dedicated-key setting, one uses a compression function

f

:{0,1}

k

× {0,1}

n

 + 

d

→{0,1}

n

to build a family of hash functions

${H^ {f}}: \mathcal{K} {\times} \mathcal{M} \{{0,1}\}^{n}$

indexed by a key space

$\mathcal{K}$

. This is different from the more traditional design approach used to build hash functions such as MD5 or SHA-1, in which compression functions and hash functions do not have dedicated key inputs. We explore the benefits and drawbacks of building hash functions in the dedicated-key setting (as compared to the more traditional approach), highlighting several unique features of the former. Should one choose to build hash functions in the dedicated-key setting, we suggest utilizing multi-property-preserving (MPP) domain extension transforms. We analyze seven existing dedicated-key transforms with regard to the MPP goal and propose two simple new MPP transforms.

Secure use of the BGLS [1] aggregate signature schemes is restricted to the aggregation of distinct messages (for the basic scheme) or per-signer distinct messages (for the enhanced, prepend-public-key version of the scheme). We argue that these restrictions preclude interesting applications, make usage of the schemes error-prone and are generally undesirable in practice. Via a new analysis and proof, we show how the restrictions can be lifted, yielding the first truly unrestricted aggregate signature scheme. Via another new analysis and proof, we show that the distinct signer restriction on the sequential aggregate signature schemes of [2] can also be dropped, yielding an unrestricted sequential aggregate signature scheme.

Ring signatures, introduced by Rivest, Shamir and Tauman, enable a user to sign a message anonymously on behalf of a “ring”. A ring is a group of users, which includes the signer. We propose a ring signature scheme that has size

$\mathcal{O}(\sqrt N)$

where

N

is the number of users in the ring. An additional feature of our scheme is that it has perfect anonymity.

Our ring signature like most other schemes uses the common reference string model. We offer a variation of our scheme, where the signer is guaranteed anony- mity even if the common reference string is maliciously generated.

The construction of perfect hash functions is a well-studied topic. In this paper, this concept is generalized with the following definition. We say that a family of functions from [

n

] to [

k

] is a

δ

-balanced (

n

,

k

)-family of perfect hash functions if for every

S

 ⊆ [

n

], |

S

| = 

k

, the number of functions that are 1-1 on

S

is between

T

/

δ

and

δT

for some constant

T

 > 0. The standard definition of a family of perfect hash functions requires that there will be at least one function that is 1-1 on

S

, for each

S

of size

k

. In the new notion of balanced families, we require the number of 1-1 functions to be almost the same (taking

δ

to be close to 1) for every such

S

. Our main result is that for any constant

δ

> 1, a

δ

-balanced (

n

,

k

)-family of perfect hash functions of size 2

O

(

k

loglog

k

)

log

n

can be constructed in time 2

O

(

k

loglog

k

)

n

log

n

. Using the technique of color-coding we can apply our explicit constructions to devise approximation algorithms for various counting problems in graphs. In particular, we exhibit a deterministic polynomial time algorithm for approximating both the number of simple paths of length

k

and the number of simple cycles of size

k

for any

$k \leq O(\frac{\log n}{\log \log \log n})$

in a graph with

n

vertices. The approximation is up to any fixed desirable relative error.

In this paper we present a new approximation algorithm for the

Minimum Energy Broadcast Routing

(MEBR) problem in ad hoc wireless networks that has exponentially better approximation factor than the well-known Minimum Spanning Tree (MST) heuristic. Namely, for any instance where a minimum spanning tree of the set of stations is guaranteed to cost at most

ρ

times the cost of an optimal solution for MEBR, we prove that our algorithm achieves an approximation ratio bounded by 2ln

ρ

 − 2 ln 2 + 2. This result is particularly relevant for its consequences on Euclidean instances where we significantly improve previous results.

State-based systems and modal logics for reasoning about them often heterogeneously combine a number of features such as non-determinism and probabilities. Here, we show that the combination of features can be reflected algorithmically and develop modular decision procedures for heterogeneous modal logics. The modularity is achieved by formalising the underlying state-based systems as multi-sorted coalgebras and associating both a logical and an algorithmic description to a number of basic building blocks. Our main result is that logics arising as combinations of these building blocks can be decided in polynomial space provided that this is the case for the components. By instantiating the general framework to concrete cases, we obtain

PSPACE

decision procedures for a wide variety of structurally different logics, describing e.g. Segala systems and games with uncertain information.

In this paper we present the theory and practice of

co-logic programming

(co-LP for brevity), a paradigm that combines both inductive and coinductive logic programming. Co-LP is a natural generalization of logic programming and coinductive logic programming, which in turn generalizes other extensions of logic programming, such as infinite trees, lazy predicates, and concurrent communicating predicates. Co-LP has applications to rational trees, verifying infinitary properties, lazy evaluation, concurrent LP, model checking, bisimilarity proofs, etc.

We introduce an offline precomputation technique for mix-nets that drastically reduces the amount of online computation needed. Our method can be based on any additively homomorphic cryptosystem and is applicable when the number of senders and the maximal bit-size of messages are relatively small.

Broadcast encryption schemes enable senders to efficiently broadcast ciphertexts to a large set of receivers in a way that only non-revoked receivers can decrypt them. Black-box traitor revocable broadcast encryption schemes are broadcast encryption schemes that enable a tracer, who is given a pirate decoder, to identify traitors by black-box accessing the given pirated decoder and to revoke traitors so identified. In this paper, we propose a fully collusion resistant black-box traitor revocable broadcast encryption scheme in which the size of each private key is constant, the size of the public key is proportional to the number of receivers, and the sizes of ciphertexts are sub-linear with respect to the number of receivers. The encryption procedure in our scheme requires only a public key. The tracing procedure in it requires only a public key and black-box access to a resettable pirate decoder. The security of our scheme is proved in the generic bilinear group model if the subgroup decision assumption holds.

Various methods have been used to represent a tree of

n

nodes in essentially the information-theoretic minimum space while supporting various navigational operations in constant time, but different representations usually support different operations. Our main contribution is a succinct representation of ordinal trees, based on that of Geary et al. (7), that supports all the navigational operations supported by various succinct tree representations while requiring only 2

n

 + 

o

(

n

) bits. It also supports efficient level-order traversal, a useful ordering previously supported only with a very limited set of operations (8).

Our second contribution expands on the notion of a single succinct representation supporting more than one traversal ordering, by showing that our method supports two other encoding schemes as abstract data types. In particular, it supports extracting a word (

$O(\lg n)$

bits) of the balanced parenthesis sequence (11) or depth first unary degree sequence (3;4) in

O

(

f

(

n

)) time, using at most

n

/

f

(

n

) + 

o

(

n

) additional bits, for any

f

(

n

) in

$O(\lg n)$

and

Ω

(1).

We present a framework to dynamize succinct data structures, to encourage their use over non-succinct versions in a wide variety of important application areas. Our framework can dynamize most state-of-the-art succinct data structures for dictionaries, ordinal trees, labeled trees, and text collections. Of particular note is its direct application to XML indexing structures that answer

subpath

queries [2]. Our framework focuses on achieving information-theoretically optimal space along with near-optimal update/query bounds.

As the main part of our work, we consider the following problem central to text indexing: Given a text

T

over an alphabet

Σ

, construct a compressed data structure answering the queries

char

(

i

),

rank

s

(

i

), and

select

s

(

i

) for a symbol

s

 ∈ 

Σ

. Many data structures consider these queries for static text

T

[5,3,16,4]. We build on these results and give the best known query bounds for the dynamic version of this problem, supporting arbitrary insertions and deletions of symbols in

T

.

Specifically, with an amortized update time of

O

(

n

ε

), any static succinct data structure

D

for

T

, taking

t

(

n

) time for queries, can be converted by our framework into a dynamic succinct data structure that supports

rank

s

(

i

),

select

s

(

i

), and

char

(

i

) queries in

O

(

t

(

n

) + loglog

n

) time, for any constant

ε

> 0. When |

Σ

| = polylog(n), we achieve

O

(1) query times. Our update/query bounds are near-optimal with respect to the lower bounds from [13].

Given string

T

 = 

T

[1,...,

n

], the

suffix sorting

problem is to lexicographically sort the suffixes

T

[

i

,...,

n

] for all

i

. This problem is central to the construction of suffix arrays and trees with many applications in string processing, computational biology and compression. A bottleneck in these applications is the amount of

workspace

needed to perform suffix sorting beyond the space needed to store the input as well as the output. In particular, emphasis is even on the constant

c

in the

O

(

n

) = 

cn

space algorithms known for this problem,

Currently the best previous result [5] takes

time and

extra space, for any

$v\in [1,\sqrt{n}]$

for strings from a general alphabet. We improve this and present the first known in-place suffix sorting algorithm. Our algorithm takes

time using

O

(1) workspace and is optimal in the worst case for the general alphabet.

We systematically investigate the computational complexity of constraint satisfaction problems for constraint languages over an infinite domain. In particular, we study a generalization of the wellestablished notion of

maximal constraint languages

from finite to infinite domains. If the constraint language can be defined with an ù-categorical structure, then maximal constraint languages are in one-to-one correspondence to minimal oligomorphic clones. Based on this correspondence, we derive general tractability and hardness criteria for the corresponding constraint satisfaction problems.

We study the definability of constraint satisfaction problems (CSP) in various fixed-point and infinitary logics. We show that testing the solvability of systems of equations over a finite Abelian group, a tractable CSP that was previously known not to be definable in Datalog, is not definable in an infinitary logic with counting and hence that it is not definable in least fixed point logic or its extension with counting. We relate definability of CSPs to their classification obtained from tame congruence theory of the varieties generated by the algebra of polymorphisms of the template structure. In particular, we show that if this variety admits either the unary or affine type, the corresponding CSP is not definable in the infinitary logic with counting. We also study the complexity of determining whether a CSP omits unary and affine types.

We study the boundedness problem for monadic least fixed points as a decision problem. While this problem is known to be undecidable in general and even for syntactically very restricted classes of underlying first-order formulae, we here obtain a decidability result for the boundedness issue for monadic fixed points over arbitrary first-order formulae in restriction to acyclic structures.

As defined by Aumann in 1959, a strong equilibrium is a Nash equilibrium that is resilient to deviations by coalitions. We give tight bounds on the strong price of anarchy for load balancing on related machines. We also give tight bounds for

k

-strong equilibria, where the size of a deviating coalition is at most

k

.

In this work we study the tractability of well supported approximate Nash Equilibria (SuppNE in short) in bimatrix games. In view of the apparent intractability of constructing Nash Equilibria (NE in short) in polynomial time, even for bimatrix games, understanding the limitations of the approximability of the problem is of great importance.

We initially prove that SuppNE are immune to the addition of arbitrary real vectors to the rows (columns) of the row (column) player’s payoff matrix. Consequently we propose a polynomial time algorithm (based on linear programming) that constructs a 0.5 −SuppNE for arbitrary win lose games.

We then parameterize our technique for win lose games, in order to apply it to arbitrary (normalized) bimatrix games. Indeed, this new technique leads to a

weaker

φ

−SuppNE for win lose games, where

$\phi=\frac{\sqrt{5}-1}{2}$

is the

golden ratio

. Nevertheless, this parameterized technique extends nicely to a technique for arbitrary [0,1] −bimatrix games, which assures a 0.658 −SuppNE in polynomial time.

To our knowledge, these are the

first

polynomial time algorithms providing

ε

−SuppNE of normalized or win lose bimatrix games, for some nontrivial

constant

ε

 ∈ [0,1), bounded away from 1.

The purpose of this paper is threefold: to present a general abstract, yet practical, notion of equational system; to investigate and develop a theory of free constructions for such equational systems; and to illustrate the use of equational systems as needed in modern applications, specifically to the theory of substitution in the presence of variable binding and to models of name-passing process calculi.

Computations on trees form a classical topic in computing. These computations can be described in terms of machines (typically called tree transducers), or in terms of functions. This paper focuses on three flavors of bottom-up computations, of increasing generality. It brings categorical clarity by identifying a category of tree transducers together with two different behavior functors. The first sends a tree transducer to a coKleisli or biKleisli map (describing the contribution of each local node in an input tree to the global transformation) and the second to a tree function (the global tree transformation). The first behavior functor has an adjoint realization functor, like in Goguen’s early work on automata. Further categorical structure, in the form of Hughes’s Arrows, appears in properly parameterized versions of these structures.

Valiant’s theory of holographic algorithms is a novel methodology to achieve exponential speed-ups in computation. A fundamental parameter in holographic algorithms is the dimension of the linear basis vectors. We completely resolve the problem of the power of higher dimensional bases. We prove that 2-dimensional bases are universal for holographic algorithms.

While data compression and Kolmogorov complexity are both about effective coding of words, the two settings differ in the following respect. A compression algorithm or compressor, for short, has to map a word to a unique code for this word in one shot, whereas with the standard notions of Kolmogorov complexity a word has many different codes and the minimum code for a given word cannot be found effectively. This gap is bridged by introducing decidable Turing machines and a corresponding notion of Kolmogorov complexity, where compressors and suitably normalized decidable machines are essentially the same concept.

Kolmogorov complexity defined via decidable machines yields characterizations in terms of the intial segment complexity of sequences of the concepts of Martin-Löf randomness, Schnorr randomness, Kurtz randomness, and computable dimension. These results can also be reformulated in terms of time-bounded Kolmogorov complexity. Other applications of decidable machines are presented, such as a simplified proof of the Miller-Yu theorem (characterizing Martin-Löf randomness by the plain complexity of the initial segments) and a new characterization of computably traceable sequences via a natural lowness notion for decidable machines.

We present a new meshing algorithm for the plane, Overlay Stitch Meshing (OSM), accepting as input an arbitrary Planar Straight Line Graph and producing a triangulation with all angles smaller than 170°. The output triangulation has competitive size with any optimal size mesh having equally bounded largest angle. The competitive ratio is

O

(log(

L

/

s

)) where

L

and

s

are respectively the largest and smallest features in the input. OSM runs in

O

(

n

log(

L

/

s

) + 

m

) time/work where

n

is the input size and

m

is the output size. The algorithm first uses Sparse Voronoi Refinement to compute a quality overlay mesh of the input points alone. This triangulation is then combined with the input edges to give the final mesh.

We describe a fully abstract trace semantics for a functional language with locally declared general references (a fragment of Standard ML). It is based on a bipartite LTS in which states alternate between program and environment configurations and labels carry only (sets of) basic values, location and pointer names. Interaction between programs and environments is either direct (initiating or terminating subprocedures) or indirect (by the overwriting of shared locations): actions reflect this by carrying updates to the shared part of the store.

The trace-sets of programs and contexts may be viewed as deterministic strategies and counter-strategies in the sense of game semantics: we prove soundness of the semantics by showing that the evaluation of a program in an environment tracks the interaction between the corresponding strategies. We establish full abstraction by proving a definability result: every bounded deterministic strategy of a given type is the trace-set of a configuration of that type.

Register allocation is NP-complete in general but can be solved in linear time for straight-line programs where each variable has at most one definition point if the bank of registers is homogeneous. In this paper we study registers which may alias: an aliased register can be used both independently or in combination with an adjacent register. Such registers are found in commonly-used architectures such as x86, the HP PA-RISC, the Sun SPARC processor, and MIPS floating point. In 2004, Smith, Ramsey, and Holloway presented the best algorithm for aliased register allocation so far; their algorithm is based on a heuristic for coloring of general graphs. Most architectures with register aliasing allow only

aligned

registers to be combined: for example, the low-address register must have an even number. Open until now is the question of whether working with restricted classes of programs can improve the complexity of aliased register allocation with alignment restrictions. In this paper we show that aliased register allocation with alignment restrictions for straight-line programs is NP-complete.

The ability to detect ambiguities in context-free grammars is vital for their use in several fields, but the problem is undecidable in the general case. We present a safe, conservative approach, where the approximations cannot result in overlooked ambiguous cases . We analyze the complexity of the verification, and provide formal comparisons with several other ambiguity detection methods.

We present lower bounds on the space required to estimate the quantiles of a stream of numerical values. Quantile estimation is perhaps the most studied problem in the data stream model and it is relatively well understood in the basic single-pass data stream model in which the values are ordered adversarially. Natural extensions of this basic model include the

random-order model

in which the values are ordered randomly (e.g. [21,5,13,11,12]) and the

multi-pass model

in which an algorithm is permitted a limited number of passes over the stream (e.g. [6,7,1,19,2,6,7,19,2]). We present lower bounds that complement existing upper bounds [21,11] in both models. One consequence is an exponential separation between the random-order and adversarial-order models: using

space, exact selection requires

Ω

(log

n

) passes in the adversarial-order model while

O

(loglog

n

) passes are sufficient in the random-order model.

We present a streaming algorithm for constructing sparse spanners and show that our algorithm out-performs significantly the state-of-the-art algorithm for this task [20]. Specifically, the

processing time-per-edge

of our algorithm is drastically smaller than that of the algorithm of [20], and all other efficiency parameters of our algorithm are no greater (and some of them are strictly smaller) than the respective parameters for the state-of-the-art algorithm.

We also devise a fully dynamic centralized algorithm maintaining sparse spanners. This algorithm has a very small incremental update time, and a non-trivial decremental update time. To our knowledge, this is the first fully dynamic centralized algorithm for maintaining sparse spanners that provides non-trivial bounds on both incremental and decremental update time for a wide range of stretch parameter

t

.

We revisit the problem of memory checking considered by Blum et al. [3]. In this model, a checker monitors the behavior of a data structure residing in unreliable memory given an arbitrary sequence of user defined operations. The checker is permitted a small amount of separate reliable memory and must fail a data structure if it is not behaving as specified and pass it otherwise. How much additional reliable memory is required by the checker? First, we present a checker for an implementation of a priority queue. The checker uses

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

space where

n

is the number of operations performed. We then present a

spot-checker

using only

O

(

ε

− 1

log

δ

− 1

log

n

) space, that, with probability at least 1 − 

δ

, will fail the priority queue if it is

ε

-far (defined appropriately) from operating like a priority queue and pass the priority queue if it operates correctly. Finally, we then prove a range of lower bounds that complement our checkers.

The trace equivalence of BPP was shown to be undecidable by Hirshfeld. We show that the trace equivalence remains undecidable even if the number of labels is restricted to two. The undecidability result holds also for the simulation of two-label BPP processes. These results imply undecidability of some behavioral type systems for the

Π

-calculus.

This paper provides new insight into the connection between the trace-based lower part of van Glabbeek’s linear-time, branching-time spectrum and its simulation-based upper part. We establish that ready simulation is fully abstract with respect to failures inclusion, when adding the conjunction operator that was proposed by the authors in [TCS 373(1–2):19–40] to the standard setting of labelled transition systems with (CSP-style) parallel composition. More precisely, we actually prove a stronger result by considering a coarser relation than failures inclusion, namely a preorder that relates processes with respect to inconsistencies that may arise under conjunctive composition. Ready simulation is also shown to satisfy standard logic properties and thus commends itself for studying mixed operational and logic languages.

We propose axiomatizing some stochastic games, in a continuous state space setting, using continuous belief functions, resp. plausibilities, instead of measures. Then, stochastic games are just variations on continuous Markov chains. We argue that drawing at random along a belief function is the same as letting the probabilistic player

P

play first, then letting the non-deterministic player

C

play demonically. The same holds for an angelic

C

, using plausibilities instead. We then define a simple modal logic, and characterize simulation in terms of formulae of this logic. Finally, we show that (discounted) payoffs are defined and unique, where in the demonic case,

P

maximizes payoff, while

C

minimizes it.

In this paper we study the chromatic number

χ

(

G

n

,

p

) of the binomial random graph

G

n

,

p

, where

p

 = 

p

(

n

) ≤ 

n

 − 3/4 − 

δ

, for every fixed

δ

> 0. We prove that a.a.s.

χ

(

G

n

,

p

) is ℓ, ℓ + 1, or ℓ + 2, where ℓ is the maximum integer satisfying 2(ℓ − 1)log(ℓ − 1) ≤ 

np

.

We deal with two very related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to measure how much a given graph “resembles” a random one. Moreover, a regular partition approximates a given graph by a bounded number of quasi-random graphs. Regarding quasi-randomness, we present a new spectral characterization of low discrepancy, which extends to sparse graphs. Concerning regular partitions, we present a novel concept of regularity that takes into account the graph’s degree distribution, and show that if

G

 = (

V

,

E

) satisfies a certain boundedness condition, then

G

admits a regular partition. In addition, building on the work of Alon and Naor [4], we provide an algorithm that computes a regular partition of a given (possibly sparse) graph

G

in polynomial time.

The cover polynomial introduced by Chung and Graham is a two-variate graph polynomial for directed graphs. It counts the (weighted) number of ways to cover a graph with disjoint directed cycles and paths, it is an interpolation between determinant and permanent, and it is believed to be a directed analogue of the Tutte polynomial. Jaeger, Vertigan, and Welsh showed that the Tutte polynomial is

$\sharp$

-hard to evaluate at all but a few special points and curves. It turns out that the same holds for the cover polynomial: We prove that, in almost the whole plane, the problem of evaluating the cover polynomial is

$\sharp$

-hard under polynomial-time Turing reductions, while only three points are easy. Our construction uses a gadget which is easier to analyze and more general than the XOR-gadget used by Valiant in his proof that the permanent is

$\sharp$

-complete.

This paper studies the expressive power of finite-state automata recognizing sets of real numbers encoded positionally. It is known that the sets that are definable in the first-order additive theory of real and integer variables 〈ℝ, ℤ, + , < 〉 can all be recognized by weak deterministic Büchi automata, regardless of the encoding base

r

 > 1. In this paper, we prove the reciprocal property, i.e., that a subset of ℝ that is recognizable by weak deterministic automata in every base

r

 > 1 is necessarily definable in 〈ℝ, ℤ, + , < 〉. This result generalizes to real numbers the well-known Cobham’s theorem on the finite-state recognizability of sets of integers. Our proof gives interesting insight into the internal structure of automata recognizing sets of real numbers, which may lead to efficient data structures for handling these sets.

We consider the minimum-time reachability problem in concurrent two-player timed automaton game structures. We show how to compute the minimum time needed by a player to reach a target location against all possible choices of the opponent. We do not put any syntactic restriction on the game structure, nor do we require any player to guarantee time divergence. We only require players to use receptive strategies which do not block time. The minimal time is computed in part using a fixpoint expression, which we show can be evaluated on equivalence classes of a non-trivial extension of the clock-region equivalence relation for timed automata.

In a reachability-time game, players Min and Max choose moves so that the time to reach a final state in a timed automaton is minimised or maximised, respectively. Asarin and Maler showed decidability of reachability-time games on strongly non-Zeno timed automata using a value iteration algorithm. This paper complements their work by providing a strategy improvement algorithm for the problem. It also generalizes their decidability result because the proposed strategy improvement algorithm solves reachability-time games on all timed automata. The exact computational complexity of solving reachability-time games is also established: the problem is EXPTIME-complete for timed automata with at least two clocks.

We introduce stochastic priority games — a new class of perfect information stochastic games. These games can take two different, but equivalent, forms. In stopping priority games a play can be stopped by the environment after a finite number of stages, however, infinite plays are also possible. In discounted priority games only infinite plays are possible and the payoff is a linear combination of the classical discount payoff and of a limit payoff evaluating the performance at infinity. Shapley games [1] and parity games [2] are special extreme cases of priority games.

A data tree is a tree where each node has a label from a finite set, and a data value from a possibly infinite set. We consider data trees whose depth is bounded beforehand. By developing an appropriate automaton model, we show that under this assumption various formalisms, including a two variable first-order logic and a subset of XPath, have decidable emptiness problems.

We propose an extension of the tree automata with constraints between direct subtrees (Bogaert and Tison, 1992) to unranked trees. Our approach uses MSO-formulas to capture the possibility of comparing unboundedly many direct subtrees. Our main result is that the nonemptiness problem for the deterministic automata, as in the ranked setting, is decidable. Furthermore, we show that the nondeterministic automata are more expressive than the deterministic ones.

Nested words are a restriction of the class of visibly pushdown languages that provide a natural model of runs of programs with recursive procedure calls. The usual connection between monadic second-order logic (MSO) and automata extends from words to nested words and gives us a natural notion of regular languages of nested words.

In this paper we look at some well-known aspects of regular languages – their characterization via fixed points, deterministic and alternating automata for them, and synchronization for defining regular relations – and extend them to nested words. We show that mu-calculus is as expressive as MSO over finite and infinite nested words, and the equivalence holds, more generally, for mu-calculus with past modalities evaluated in arbitrary positions in a word, not only in the first position. We introduce the notion of alternating automata for nested words, show that they are as expressive as the usual automata, and also prove that Muller automata can be determinized (unlike in the case of visibly pushdown languages). Finally we look at synchronization over nested words. We show that the usual letter-to-letter synchronization is completely incompatible with nested words (in the sense that even the weakest form of it leads to an undecidable formalism) and present an alternative form of synchronization that gives us decidable notions of regular relations.

Following the idea developed by I. Simon in his theorem of Ramseyan factorisation forests, we develop a result of ‘deterministic factorisations’. This extra determinism property makes it usable on trees (finite or infinite).

We apply our result for proving that,

over trees

, every monadic interpretation is equivalent to the composition of a first-order interpretation (with access to the ancestor relation) and a monadic marking. Using this remark, we give new characterisations for prefix-recognisable structures and for the Caucal hierarchy.

Furthermore, we believe that this approach has other potential applications.

Gaifman’s locality theorem states that every first-order sentence is equivalent to a local sentence. We show that there is no elementary bound on the length of the local sentence in terms of the original.

The classical Łoś-Tarski theorem states that every first-order sentence preserved under extensions is equivalent to an existential sentence. We show that there is no elementary bound on the length of the existential sentence in terms of the original. Recently, variants of the Łoś-Tarski theorem have been proved for certain classes of finite structures, among them the class of finite acyclic structures and more generally classes of structures of bounded tree width. Our lower bound also applies to these variants.

We further prove that a version of the Feferman-Vaught theorem based on a restriction by formula length necessarily entails a non-elementary blow-up in formula size.

All these results are based on a similar technique of encoding large numbers by trees of small height in such a way that small formulas can speak about these numbers. Notably, our lower bounds do not apply to restrictions of the results to structures of bounded degree. For such structures, we obtain elementary upper bounds in all cases. However, even there we can prove at least doubly exponential lower bounds.

We investigate a class of parametric timed automata, called lower bound/upper bound (L/U) automata, where each parameter occurs in the timing constraints either as a lower bound or as un upper bound. For such automata, we show that checking if for a parameter valuation (resp., all parameter valuations) there is an infinite accepting run is

Pspace

-complete. We extend these results by allowing the specification of constraints on parameters as a linear system. We show that the considered decision problems are still

Pspace

-complete, if the lower bound parameters are not compared to the upper bound parameters in the linear system, and are undecidable in general. Finally, we consider a parametric extension of

, and prove that the related satisfiability and model checking (w.r.t. L/U automata) problems are

Pspace

-complete.

Recursive state machines (

rsm

s) are models for programs with recursive procedural calls. While

Ltl

model-checking is

Exptime

-complete on such models, on finite-state machines, it is

Pspace

-complete in general and becomes

Np

-complete for interesting fragments. In this paper, we systematically study the computational complexity of model-checking

rsm

s against several syntactic fragments of

Ltl

. Our main result shows that if in the specification we disallow

next

and

until

, and retain only the

box

and

diamond

operators, model-checking is in

Np

. Thus, differently from the full logic, for this fragment the abstract complexity of model-checking does not change moving from finite-state machines to

rsm

s. Our results on the other studied fragments confirm this trend, in the sense that, moving from finite-state machines to

rsm

s, the complexity of model-checking either rises from

Pspace

-complete to

Exptime

-complete, or stays within

Np

.

We regret to report that we have found an error in our paper “On the Hardness of Embeddings Between Two Finite Metrics,” which appeared in the Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP), Lisboa, Portugal, July 2005.