Automata, Languages and Programming

Holographic circuits are defined here to be circuits in which information is represented as linear superpositions. Holographic circuits when suitably formulated can be emulated on classical computers in polynomial time. The questions we investigate are those of characterizing the complexity classes of computations that can be expressed by holographic circuits.

We describe a cryptographically sound formal logic for proving protocol security properties without explicitly reasoning about probability, asymptotic complexity, or the actions of a malicious attacker. The approach rests on a new probabilistic, polynomial-time semantics for an existing protocol security logic, replacing an earlier semantics that uses nondeterministic symbolic evaluation. While the basic form of the protocol logic remains unchanged from previous work, there are some interesting technical problems involving the difference between efficiently recognizing and efficiently producing a value, and involving a reinterpretation of standard logical connectives that seems necessary to support certain forms of reasoning.

Subtyping relations are usually defined either syntactically by a formal system or semantically by an interpretation of types into an untyped denotational model. This work shows how to define a subtyping relation semantically in the presence of boolean connectives, functional types and dynamic dispatch on types, without the complexity of denotational models, and how to derive a complete subtyping algorithm. The presentation is voluntarily kept informal and discursive and the technical details are reduced to a minimum since we rather insist on the motivations, the intuition, and the guidelines to apply the approach.

Labeled unranked trees are used as a model of XML documents, and logical languages for them have been studied actively over the past several years. Such logics have different purposes: some are better suited for extracting data, some for expressing navigational properties, and some make it easy to relate complex properties of trees to the existence of tree automata for those properties. Furthermore, logics differ significantly in their model-checking properties, their automata models, and their behavior on ordered and unordered trees. In this paper we present a survey of logics for unranked trees.

Motivation-Framework

. Apparently, it is in human’s nature to act selfishly. Game Theory, founded by von Neumann and Morgenstern [39, 40], provides us with

strategic games

, an important mathematical model to describe and analyze such a selfish behavior and its resulting conflicts. In a strategic game, each of a finite set of players aims for an optimal value of its

private objective function

by choosing either a

pure

strategy (a single strategy) or a

mixed

strategy (a probability distribution over all pure strategies) from its

strategy set

. Strategic games in which the strategy sets are finite are called

finite strategic games

. Each player chooses its strategy once and for all, and all players’ choices are made

non-cooperatively and simultaneously

(that is, when choosing a strategy each player is not informed of the strategies chosen by any other player). One of the basic assumption in strategic games is that the players act

rational

, that is, consistently in pursuit of their private objective function. For a concise introduction to contemporary Game Theory we recommend [25].

Given two rooted, ordered, and labeled trees

P

and

T

the tree inclusion problem is to determine if

P

can be obtained from

T

by deleting nodes in

T

. This problem has recently been recognized as an important query primitive in XML databases. Kilpeläinen and Mannila (SIAM J. of Comp. 1995) presented the first polynomial time algorithm using quadratic time and space. Since then several improved results have been obtained for special cases when

P

and

T

have a small number of leaves or small depth. However, in the worst case these algorithms still use quadratic time and space. In this paper we present a new approach to the problem which leads to a new algorithm which uses optimal linear space and has subquadratic running time. Our algorithm improves all previous time and space bounds. Most importantly, the space is improved by a linear factor. This will make it possible to query larger XML databases and speed up the query time since more of the computation can be kept in main memory.

A union-find data structure maintains a collection of disjoint sets under

makeset

,

union

and

find

operations. Kaplan, Shafrir and Tarjan [SODA 2002] designed data structures for an extension of the union-find problem in which elements of the sets maintained may be deleted. The cost of a

delete

operation in their implementations is the same as the cost of a

find

operation. They left open the question whether

delete

operations can be implemented more efficiently than

find

operations. We resolve this open problem by presenting a relatively simple modification of the classical union-find data structure that supports

delete

, as well as

makeset

and

union

, operations in

constant

time, while still supporting

find

operations in

O

(log

n

) worst-case time and

O

(

α

(

n

)) amortized time, where

n

is the number of elements in the set returned by the

find

operation, and

α

(

n

) is a functional inverse of Ackermann’s function.

We study the problem of determining the complexity of optimal comparison-based in-place sorting when the key length,

k

, is not a constant. We present the first algorithm for lexicographically sorting

n

keys in

O

(

nk

+

n

log

n

) time using

O

(1) auxiliary data locations, which is

simultaneously

optimal in time

and

space.

The multiple selection problem asks for the elements of rank

r

1

,

r

2

, ...,

r

k

from a linearly ordered set of

n

elements. Let

B

denote the information theoretic lower bound on the number of element comparisons needed for multiple selection. We first show that a variant of multiple quickselect — a well known, simple, and practical generalization of quicksort — solves this problem with

$B+\mathcal{O}(n)$

expected comparisons. We then develop a deterministic divide-and-conquer algorithm that solves the problem in

$\mathcal{O}(B)$

time and

$B+o(B)+\mathcal{O}(n)$

element comparisons.

Trevisan has shown that constructions of pseudo-random generators from hard functions (the Nisan-Wigderson approach) also produce extractors. We show that constructions of pseudo-random generators from one-way permutations (the Blum-Micali-Yao approach) can be used for building extractors as well. Using this new technique we build extractors that do not use designs and polynomial-based error-correcting codes and that are very simple and efficient. For example, one extractor produces each output bit separately in

O

(log

2

n

) time. These extractors work for weak sources with min entropy λ

n

, for arbitrary constant λ> 0, have seed length

O

(log

2

n

), and their output length is ≈

n

λ

/3

.

Constructions of cryptographic primitives based on general assumptions (e.g., the existence of one-way functions) tend to be less efficient than constructions based on specific (e.g., number-theoretic) assumptions. This has prompted a recent line of research aimed at investigating the best possible efficiency of (black-box) constructions based on general assumptions. Here, we present bounds on the efficiency of statistically-binding commitment schemes constructed using black-box access to one-way permutations; our bounds are tight for the case of

perfectly

-binding schemes. We present the bounds in an extension of the Impagliazzo-Rudich model; that is, we show that any construction beating our bounds would imply the unconditional existence of a one-way function (from which a commitment scheme could be constructed “from scratch”). Our analysis is the first in the area to pertain directly to an information-theoretic component of the security notion.

We consider the problem of constructing round-efficient public-coin argument systems, that is, interactive proof systems that are only computationally sound with a constant number of rounds. We focus on argument systems for

NTime

(T(n))

where either the communication complexity or the verifier’s running time is subpolynomial in

T(n)

, such as Kilian’s argument system for

NP

[Kil92] and universal arguments [BG02,Mic00]. We begin with the observation that under standard complexity assumptions, such argument systems require at least 2 rounds. Next, we relate the existence of non-trivial 2-round argument systems to that of hard-on-average search problems in

NP

and that of efficient public-coin zero-knowledge arguments for

NP

. Finally, we show that the Fiat-Shamir paradigm [FS86] and Babai-Moran round reduction [BM88] fails to preserve computational soundness for some 3-round and 4-round argument systems.

We introduce

hierarchical data processing (HDP)

problems, a class of computations over a collection of values associated with a set of

n

elements, based on a directed acyclic graph (DAG). We present an Ω(log

n

) lower bound on various computational cost measures for HDP problems and we develop an efficient randomized DAG scheme for HDP problems. We apply our results to

data authentication through cryptographic hashing

and

multicast key distribution using key-graphs

. We show that both problems involve HDP and prove logarithmic lower bounds on their computational and communication costs. Using our new DAG scheme, we present a new efficient authenticated dictionary and a new skip-list version with expected search complexity 1.25 log

2

n

+

O

(1).

We study an aspect of the balanced allocation paradigm (also known as the “two-choices paradigm”). Assume there are

n

balls and

m

=(1+

ε

)

n

/

d

bins of capacity

d

each, for a fixed

d

 ≥ 1. To each of the balls two possible bins are assigned at random. We show that

ε

> (2/

e

)

d

 − − 1

is sufficient to guarantee that with high probability each ball can be put into one of the two bins assigned to it, without any bin overflowing. Further, it takes constant time on average for changing the arrangement to accommodate a new ball, if

ε

 > 

γ

·

β

d

, for some constants

γ

 > 0,

β

< 1. The problem may also be described in data structure language. Generalizing cuckoo hashing (Pagh and Rodler, 2001), we consider a hash table with

m

positions, each representing a bucket of capacity

d

≥1. Key

x

may be stored in bucket

h

1

(

x

) or

h

2

(

x

), for two fully random hash functions

h

1

and

h

2

. For arbitrary

ε

> 0, we obtain an implementation of a dynamic dictionary that accommodates

n

keys in

m

=(1+

ε

)

n

/

d

buckets of size

d

=

O

(log(1/

ε

)). For a lookup operation only two hash functions have to be evaluated and two contiguous segments of

d

memory cells have to be inspected. The expected time for inserting a new key is constant.

We consider the problem of evaluating an expression consisting of unions and intersections of some sorted sets. Given the expression and the sizes of the sets, we are interested in the worst-case complexity of evaluating the expression in terms of the sizes of the sets. We assume no set is repeated in the expression. We show a lower bound on this problem and present an algorithm that matches the lower bound asymptotically.

Davis-Putnam-style exponential-time backtracking algorithms are the most common algorithms used for finding exact solutions of NP-hard problems. The analysis of such recursive algorithms is based on the bounded search tree technique: a measure of the size of the subproblems is defined; this measure is used to lower bound the progress made by the algorithm at each branching step.

For the last 30 years the research on exact algorithms has been mainly focused on the design of more and more sophisticated algorithms. However, measures used in the analysis of backtracking algorithms are usually very simple. In this paper we stress that a more careful choice of the measure can lead to significantly better worst case time analysis.

As an example, we consider the minimum dominating set problem. The currently fastest algorithm for this problem has running time

O

(2

0.850n

) on

n

-nodes graphs. By measuring the progress of the (same) algorithm in a different way, we refine the time bound to

O

(2

0.598 n

). A good choice of the measure can provide such a (surprisingly big) improvement; this suggests that the running time of many other exponential-time recursive algorithms is largely overestimated because of a “bad” choice of the measure.

This paper presents a new protocol for atomic broadcast in an

asynchronous

network with a maximal number of

Byzantine

failures. It guarantees both

safety

and

liveness

without making any timing assumptions. Under normal circumstances, the protocol runs in an extremely efficient “optimistic mode,” while in rare circumstances the protocol may briefly switch to a less efficient “pessimistic mode.”

The “One-Time Pad” is a fundamental cryptographic protocol as it represents the ideal in secure unidirectional communication (i.e., in cases where there is a designated sender and a designated receiver) both in terms of security (in the presence of eavesdroppers) as well as in terms of computational efficiency. Surprisingly, no modeling and investigation of this protocol has been done in important practical settings, as distributed and asynchronous ones. In this work we introduce an asynchronous model for multidirectional and multi-player One-Time Pad asynchronous communication protocols. In this model the random pad is shared by all players, and there is no designated sender and receiver; in fact any participating player can act as a receiver at any given time, players communicate in a totally asynchronous fashion and may arbitrarily go off-line.

We define the problem of designing One-Time Pad asynchronous communication protocols, where the goal is that of maximizing the amount of the shared pad used before new randomness needs to be generated, with the constraint of mantaining the security property under reasonable adversarial assumptions on the relative behavior of the players and the network. We present lower bounds and protocol solutions for this problem that significantly improve over the obvious scenario where parties use an equal fraction of the pad. Our constructions are

non-interactive

in the sense that they require no additional synchronizing communication beyond the (usual) information that accompanies each ciphertext.

In this paper we study the round complexity of

concurrent zero-knowledge

arguments and show that, for any function

β

(

n

)=

ω

(1), there exists an

unbounded

concurrent zero-knowledge argument system with

β

(

n

) rounds. Our result assumes that the

same

prover is engaged in several concurrent sessions and that the prover has a counter whose value is shared across concurrent executions of the argument. Previous constructions for concurrent zero knowledge required a (almost) logarithmic number of rounds [Prabhakaran et al. – FOCS 2002] in the plain model or seemingly stronger set-up assumptions.

Moreover, we construct two

β

(

n

)-round unbounded concurrent zero-knowledge arguments that are mutually concurrent simulation sound for any

β

(

n

)=

ω

(1). Here we assume that each party has access to a counter and that the two protocols are used by the

same

two parties to play several concurrent sessions of the two protocols.

We present two methods for finding a lowest common ancestor (LCA) for each pair of vertices of a directed acyclic graph (dag) on

n

vertices and

m

edges.

The first method is surprisingly natural and solves the all-pairs LCA problem for the input dag on

n

vertices and

m

edges in time

O

(

nm

). As a corollary, we obtain an

O

(

n

2

)-time algorithm for finding genealogical distances considerably improving the previously known

O

(

n

2.575

) time-bound for this problem.

The second method relies on a novel reduction of the all-pairs LCA problem to the problem of finding maximum witnesses for Boolean matrix product. We solve the latter problem and hence also the all-pairs LCA problem in time

$O(n^{{2}+\frac{1}{4-\omega}})$

, where

ω

=2.376 is the exponent of the fastest known matrix multiplication algorithm. This improves the previously known

$O(n^{\frac{\omega+3}{2}})$

time-bound for the general all-pairs LCA problem in dags.

Let

G

=(

V

,

E

) be a

directed

graph and let

P

be a shortest path from

s

to

t

in

G

. In the

replacement paths

problem we are required to find, for every edge

e

on

P

, a shortest path from

s

to

t

in

G

that avoids

e

. We present the first non-trivial algorithm for computing replacement paths in unweighted directed graphs (and in graphs with small integer weights). Our algorithm is Monte-Carlo and its running time is

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

. Using the improved algorithm for the replacement paths problem we get an improved algorithm for finding the

ksimple

shortest paths between two given vertices.

Thorup and Zwick showed that for any integer

k

≥ 1, it is possible to preprocess any positively weighted undirected graph

G

=(

V

,

E

), with |

E

|=

m

and |

V

|=

n

, in Õ(

kmn

$^{\rm 1/{\it k}}$

)

expected

time and construct a data structure (

a (2k

–1)-approximate distance oracle

) of size

O

(

kn

$^{\rm 1+1/{\it k}}$

) capable of returning in

O

(

k

) time an approximation

$\hat{\delta}(u,v)$

of the distance

δ

(

u

,

v

) from

u

to

v

in

G

that satisfies

$\delta(u,v) \leq \hat{\delta}(u,v) \leq (2k -1)\cdot \delta(u,v)$

, for any two vertices

u

,

v

∈

V

. They also presented a much slower Õ(

kmn

) time

deterministic

algorithm for constructing approximate distance oracle with the slightly larger size of

O

(

kn

$^{\rm 1+1/{\it k}}$

log

n

). We present here a

deterministic

Õ(

kmn

$^{\rm 1/{\it k}}$

) time algorithm for constructing oracles of size

O

(

kn

$^{\rm 1+1/{\it k}}$

). Our deterministic algorithm is slower than the randomized one by only a logarithmic factor.

Using our derandomization technique we also obtain the first deterministic

linear

time algorithm for constructing optimal spanners of weighted graphs. We do that by derandomizing the

O

(

km

) expected time algorithm of Baswana and Sen (ICALP’03) for constructing (2

k

–1)-spanners of size

O

(

kn

$^{\rm 1+1/{\it k}}$

) of weighted undirected graphs without incurring

any

asymptotic loss in the running time or in the size of the spanners produced.

We consider the problem of computing a minimum cycle basis in a directed graph

G

. The input to this problem is a directed graph whose arcs have positive weights. In this problem a {–1,0,1} incidence vector is associated with each cycle and the vector space over

${\mathbb Q}$

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 weights of the cycles is minimum is called a minimum cycle basis of

G

. The current fastest algorithm for computing a minimum cycle basis in a directed graph with

m

arcs and

n

vertices runs in

$\tilde{O}(m{^{\omega+1}}n)$

time (where

ω

< 2.376 is the exponent of matrix multiplication). If one allows randomization, then an Õ(

m

3

n

) algorithm is known for this problem. In this paper we present a simple Õ(

m

2

n

) randomized algorithm for this problem.

The problem of computing a minimum cycle basis in an

undirected

graph has been well-studied. 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 the graph. The fastest known algorithm for computing a minimum cycle basis in an undirected graph runs in

O

(

m

2

n

+

mn

2

log

n

) time and our randomized algorithm for directed graphs almost matches this running time.

In this paper we attempt to formally study two very intuitive physical models: sealed envelopes and locked boxes, often used as illustrations for common cryptographic operations. We relax the security properties usually required from locked boxes (such as in bit-commitment protocols) and require only that a broken lock or torn envelope be identifiable to the original sender. Unlike the completely impregnable locked box, this functionality may be achievable in real life, where containers having this property are called “tamper-evident seals”. Another physical object with this property is the “scratch-off card”, often used in lottery tickets. We show that scratch-off cards can be used to implement bit-commitment and coin flipping, but not oblivious transfer. Of particular interest, we give a strongly-fair coin flipping protocol with bias bounded by

O

(1/

r

) (where

r

is the number of rounds), beating the best known bias in the standard model even with cryptographic assumptions.

We introduce the notion of hybrid trapdoor commitment schemes. Intuitively an hybrid trapdoor commitment scheme is a primitive which can be either an unconditionally binding commitment scheme or a trapdoor commitment scheme depending on the distribution of commitment parameters. Moreover, such two distributions are computationally indistinguishable. Hybrid trapdoor commitments are related but different with respect to

mixed

commitments (introduced by Damgård and Nielsen at Crypto 2002). In particular hybrid trapdoor commitments can either be polynomially trapdoor commitments or unconditionally binding commitments, while mixed commitment can be either trapdoor commitments or extractable commitments. In this paper we show that strong notions (e.g., simulation sound, multi-trapdoor) of hybrid trapdoor commitments admit constructions based on the sole assumption that one-way functions exist as well as efficient constructions based on standard number-theoretic assumptions. To further stress the difference between hybrid and mixed commitments, we remark here that mixed commitments seems to require stronger theoretical assumptions (and the known number-theoretic constructions are less efficient). The main application of our results is that we show how to construct concurrent and simulation-sound zero-knowledge proof (in contrast to the arguments recently presented in [1,2,3]) systems in the common reference string model. We crucially use hybrid commitment since we present general constructions based on the sole assumption that one-way functions exists and very efficient constructions based on number-theoretic assumptions.

At TCC 2005, Backes and Cachin proposed a new and very strong notion of security for public key steganography: secrecy against adaptive chosen covertext attack (

SS-CCA

); and posed the question of whether

SS-CCA

security was achievable for

any

covertext channel. We resolve this question in the affirmative:

SS-CCA

security is possible for any channel that admits a secure stegosystem against the standard and weaker “chosen hiddentext attack” in the standard model of computation. Our construction requires a public-key encryption scheme with ciphertexts that remain indistinguishable from random bits under adaptive chosen-ciphertext attack. We show that a scheme with this property can be constructed under the Decisional Diffie-Hellman assumption. This encryption scheme, which modifies a scheme proposed by Kurosawa and Desmedt, also resolves an open question posed by von Ahn and Hopper at Eurocrypt 2004.

This paper presents an efficient approach to the classification of the affine equivalence classes of cosets of the first order Reed-Muller code with respect to cryptographic properties such as correlation-immunity, resiliency and propagation characteristics. First, we apply the method to completely classify with this respect all the 48 classes into which the general affine group

AGL

(2,5) partitions the cosets of

RM

(1,5). Second, after distinguishing the 34 affine equivalence classes of cosets of

RM

(1,6) in

RM

(3,6) we perform the same classification for these classes.

A finite automaton, simply referred to as a

robot

, has to explore a graph, i.e., visit all the nodes of the graph. The robot has no a priori knowledge of the topology of the graph or of its size. It is known that, for any

k

-state robot, there exists a (

k

+1)-node graph of maximum degree 3 that the robot cannot explore. This paper considers the effects of allowing the system designer to add short labels to the graph nodes in a preprocessing stage, and using these labels to guide the exploration by the robot. We describe an exploration algorithm that given appropriate 2-bit labels (in fact, only 3-valued labels) allows a robot to explore all graphs. Furthermore, we describe a suitable labeling algorithm for generating the required labels, in linear time. We also show how to modify our labeling scheme so that a robot can explore all graphs of bounded degree, given appropriate 1-bit labels. In other words, although there is no robot able to explore all graphs of maximum degree 3, there is a robot

${\mathcal R}$

, and a way to color in black or white the nodes of any bounded-degree graph

G

, so that

${\mathcal R}$

can explore the colored graph

G

. Finally, we give impossibility results regarding graph exploration by a robot with no internal memory (

i.e.

, a single state automaton).

Radio networks model wireless communication when processing units communicate using one wave frequency. This is captured by the property that multiple messages arriving simultaneously to a node interfere with one another and none of them can be read reliably. We present improved solutions to the problem of waking up such a network. This requires activating all nodes in a scenario when some nodes start to be active spontaneously, while every sleeping node needs to be awaken by receiving successfully a message from a neighbor. Our contributions concern the existence and efficient construction of universal radio synchronizers, which are combinatorial structures introduced in [6] as building blocks of efficient wake-up algorithms. First we show by counting that there are (

n

,

g

)-universal synchronizers for

$g(k)={\mathcal O}(k \ {\rm log}\ k \ {\rm log}\ n)$

. Next we show an explicit construction of (

n

,

g

)-universal-synchronizers for

$g(k) = {\mathcal O}(k^{2}{\rm polylog}\ n)$

. By way of applications, we obtain an existential wake-up algorithm which works in time

${\mathcal O}(n {\rm log}^{2}n)$

and an explicitly instantiated algorithm that works in time

${\mathcal O}(n{\it \Delta} {\rm polylog}\ n)$

, where

n

is the number of nodes and

${\it \Delta}$

is the maximum in-degree in the network. Algorithms for leader-election and synchronization can be developed on top of wake-up ones, as shown in [7], such that they work in time slower by a factor of

${\mathcal O}({\rm log} \ n)$

than the underlying wake-up ones.

We prove that the

L(2,1)-labeling

problem is NP-complete for graphs of treewidth two, thus adding a natural and well studied problem to the short list of problems whose computational complexity separates treewidth one from treewidth two. We prove similar results for other variants of the distance constrained graph labeling problem.

We give an

O

(

n

3

) time algorithm for constructing a minimum-width branch-decomposition of a given planar graph with

n

vertices. This is achieved through a refinement to the previously best known algorithm of Seymour and Thomas, which runs in

O

(

n

4

) time.

The construction of an

ε

-free nondeterministic finite automaton (NFA) from a given NFA is a basic step in the development of compilers and computer systems. The standard conversion may increase the number of transitions quadratically and its optimality with respect to the number of transitions is a long standing open problem. We show that there exist regular languages

L

n

that can be recognized by NFAs with

O

(

n

log

2

n

) transitions, but

ε

-free NFAs need Ω(

n

2

) transitions to accept

L

n

. Hence the standard conversion cannot be improved significantly. However

L

n

requires an alphabet of size

n

, but we also construct regular languages

K

n

over {0,1} with NFAs of size

O

(

n

log

2

n

), whereas

ε

-free NFAs require size

$n \cdot 2^{c \cdot\sqrt{{\rm log}_{2}n}}$

for every

c

< 1/2.

We prove that two automata with multiplicity in

${\mathbb Z}$

are equivalent,

i.e.

define the same rational series, if and only if there is a sequence of

${\mathbb Z}$

-coverings, co-

${\mathbb Z}$

-coverings, and circulations of –1, which transforms one automaton into the other. Moreover, the construction of these transformations is effective.

This is obtained by combining two results: the first one relates coverings to conjugacy of automata, and is modeled after a theorem from symbolic dynamics; the second one is an adaptation of Schützenberger’s reduction algorithm of representations in a field to representations in an Euclidean domain (and thus in

${\mathbb Z}$

).

Reversible cellular automata (RCA) are models of massively parallel computation that preserve information. They consist of an array of identical finite state machines that change their states synchronously according to a local update rule. By selecting the update rule properly the system has been made information preserving, which means that any computation process can be traced back step-by-step using an inverse automaton. We investigate the maximum range in the array that a cell may need to see in order to determine its previous state. We provide a tight upper bound on this inverse neighborhood size in the one-dimensional case: we prove that in a RCA with

n

states the inverse neighborhood is not wider than

n

–1, when the neighborhood in the forward direction consists of two consecutive cells. Examples are known where range

n

–1 is needed, so the bound is tight. If the forward neighborhood consists of

m

consecutive cells then the same technique provides the upper bound

n

m

 − 1

–1 for the inverse direction.

Finite semigroups, i.e. finites sets equipped with a binary associative operation, have played a role in theoretical computer science for fifty years. They were first observed to be closely related to finite automata, hence, by the famous theorem of Kleene, to regular languages. It was later understood that this association is very deep and the theory of pseudo-varieties of Schützenberger and Eilenberg [5] became the accepted framework in which to discuss computations realized by finite-state machines. It is today fair to say that semigroups and automata are so tightly intertwined that it makes little sense to study one without the other.

We present a new primitive – Append-only Signatures (AOS) – with the property that any party given an AOS signature

Sig

[

M

1

] on message

M

1

can compute

Sig

[

M

1

||

M

2

] for any message

M

2

, where

M

1

||

M

2

is the concatenation of

M

1

and

M

2

. We define the security of AOS, present concrete AOS schemes, and prove their security under standard assumptions. In addition, we find that despite its simple definition, AOS is equivalent to Hierarchical Identity-based Signatures (HIBS) through efficient and security-preserving reductions. Finally, we show direct applications of AOS to problems in network security. Our investigations indicate that AOS is both useful in practical applications and worthy of further study as a cryptographic primitive.

We introduce the notion of

hierarchical group signatures

. This is a proper generalization of group signatures, which allows multiple group managers organized in a tree with the signers as leaves. When opening a signature a group manager only learns to which of its subtrees, if any, the signer belongs.

We provide definitions for the new notion and construct a scheme that is provably secure given the existence of a family of trapdoor permutations. We also present a construction which is relatively practical, and prove its security in the random oracle model under the strong RSA assumption and the DDH assumption.

We show that the signer can abuse the disavowal protocol in the Jakobsson-Sako-Impagliazzo designated-verifier signature scheme. In addition, we identify a new security property—non-delegatability—that is essential for designated-verifier signatures, and show that several previously proposed designated-verifier schemes are delegatable. We give a rigorous formalisation of the security for designated-verifier signature schemes, and propose a new and efficient designated-verifier signature scheme that is provably unforgeable under a tight reduction to the Decisional Diffie-Hellman problem in the non-programmable random oracle model, and non-delegatable under a loose reduction in the programmable random oracle model. As a direct corollary, we also get a new efficient conventional signature scheme that is provably unforgeable under a tight reduction to the Decisional Diffie-Hellman problem in the non-programmable random oracle plus common reference string model.

We investigate a general paradigm for constructing arbitrary-input-length (AIL) MACs from fixed-input-length (FIL) MACs, define the waste as the relevant efficiency parameter of such constructions, and give a simple and general security proof technique applicable to very general constructions. We propose concrete, essentially optimal constructions for practical use, Chain-Shift (CS) and Chain-Rotate (CR), and prove their security. They are superior to the best previously known construction, the NI-construction proposed by An and Bellare: Only one rather than two secret keys are required, the efficiency is improved, and the message space is truly AIL, i.e., there is no upper bound on the message length. The generality of our proof technique is also illustrated by giving a simple security proof of the NI-construction and several improvements thereof.

We study the resource allocation game in which price anticipating players compete for multiple divisible resources. In the scheme, each player submits a bid to a resource and receives a share of the resource according to the proportion of his bid to the total bids. Unlike the previous study (e.g.[5]), we consider the case when the players have budget constraints, i.e. each player’s total bids is fixed. We show that there always exists a Nash equilibrium when the players’ utility functions are strongly competitive. We study the efficiency and fairness at the Nash equilibrium. We show the tight efficiency bound of

$\theta(1/\sqrt{m})$

for the

m

player balanced game. For the special cases when there is only one resource or when there are two players with linear utility functions, the efficiency is 3/4. We extend the classical notion of envy-freeness to measure fairness. We show that despite a possibly large utility gap, any Nash equilibrium is 0.828-approximately envy-free in this game.

We give the first analyses in multicommodity networks of both the worst-case severity of Braess’s Paradox and the price of anarchy of selfish routing with respect to the maximum latency. Our first main result is a construction of an infinite family of two-commodity networks, related to the Fibonacci numbers, in which both of these quantities grow exponentially with the size of the network. This construction has wide implications, and demonstrates that numerous existing analyses of selfish routing in single-commodity networks have no analogues in multicommodity networks, even in those with only two commodities. This dichotomy between single- and two-commodity networks is arguably quite unexpected, given the negligible dependence on the number of commodities of previous work on selfish routing.

Our second main result is an exponential upper bound on the worst-possible severity of Braess’s Paradox and on the price of anarchy for the maximum latency, which essentially matches the lower bound when the number of commodities is constant.

Finally, we use our family of two-commodity networks to exhibit a natural network design problem with intrinsically exponential (in)approximability: while there is a polynomial-time algorithm with an exponential approximation ratio, subexponential approximation is unachievable in polynomial time (assuming

P

≠

NP

).

Weighted automata are used to describe quantitative properties in various areas such as probabilistic systems, image compression, speech-to-text processing. The behaviour of such an automaton is a mapping, called a formal power series, assigning to each word a weight in some semiring. We generalize Büchi’s and Elgot’s fundamental theorems to this quantitative setting. We introduce a weighted version of MSO logic and prove that, for commutative semirings, the behaviours of weighted automata are precisely the formal power series definable with our weighted logic. We also consider weighted first-order logic and show that aperiodic series coincide with the first-order definable ones, if the semiring is locally finite, commutative and has some aperiodicity property.

We obtain a logical characterization of an important class of regular languages, denoted

${\mathcal DO}$

, and of its most important subclasses in terms of two-variable sentences with ordinary and modular quantifiers but in which all modular quantifiers lie outside the scope of ordinary quantifiers. The result stems from a new decomposition of the variety of monoids

DO

in terms of iterated block products.

This decomposition and the ensuing logical characterization allows us to shed new light on recent results on regular languages which are recognized by bounded-depth circuits with a linear number of wires and regular languages with small communication complexity.

Computing the order of the Jacobian group of a hyperelliptic curve over a finite field is very important to construct a hyperelliptic curve cryptosystem (HCC), because to construct secure HCC, we need Jacobian groups of order in the form

l

c

where

l

is a prime greater than about 2

160

and

c

is a very small integer. But even in the case of genus two, known algorithms to compute the order of a Jacobian group for a general curve need a very long running time over a large prime field. In this article, we give explicit formulae of the order of Jacobian groups for hyperelliptic curves over a finite prime field of type

y

2

=

x

$^{\rm 2{\it k}+1}$

+

ax

, which allows us to search suitable curves for HCC. By using these formulae, we can find many suitable curves for genus-4 HCC and show some examples.

We investigate the complexity of the following polynomial solvability problem: Given a finite field

${\mathbb F}_{q}$

and a set of polynomials

$$f_{1}(x,y),f_{2}(x,y),...,f_{n}(x,y),g(x,y) \ \epsilon \ {\mathbb F}_{q} [x,y]$$

determine the

${\mathbb F}_{q}$

-solvability of the system

$$f_{1}(x,y)=f_{2}(x,y)=...=f_{n}(x,y)=0 \ {\rm and} \ {\it g}(x,y) \neq 0$$

We give a

deterministic

polynomial-time algorithm for this problem.

We present an efficient cache-oblivious implementation of the shortest-path algorithm for planar graphs by Klein et al., and prove that it incurs no more than

${\mathcal O}(\frac{N}{B^{1/2 - \epsilon}} + \frac{N}{B}{\rm log}N$

) block transfers on a graph with

N

vertices. This is the first cache-oblivious algorithm for this problem that incurs

o

(

N

) block transfers.

Two new adaptive sorting algorithms are introduced which perform an optimal number of comparisons with respect to the number of inversions in the input. The first algorithm is based on a new linear time reduction to (non-adaptive) sorting. The second algorithm is based on a new division protocol for the GenericSort algorithm by Estivill-Castro and Wood. From both algorithms we derive I/O-optimal cache-aware and cache-oblivious adaptive sorting algorithms. These are the first I/O-optimal adaptive sorting algorithms.

The Metropolis algorithm is simulated annealing with a fixed temperature. Surprisingly enough, many problems cannot be solved more efficiently by simulated annealing than by the Metropolis algorithm with the best temperature. The problem of finding a natural example (artificial examples are known) where simulated annealing outperforms the Metropolis algorithm for all temperatures has been discussed by Jerrum and Sinclair (1996) as “an outstanding open problem.” This problem is solved here. The examples are instances of the well-known minimum spanning tree problem. Moreover, it is investigated which instances of the minimum spanning tree problem can be solved efficiently by simulated annealing. This is motivated by the aim to develop further methods to analyze the simulated annealing process.

We study interval coloring problems and present new upper and lower bounds for several variants. We are interested in four problems, online coloring of intervals with and without bandwidth and a new problem called lazy online coloring again with and without bandwidth. We consider both general interval graphs and unit interval graphs. Specifically, we establish the difference between the two main problems which are interval coloring with and without bandwidth. We present the first non-trivial lower bound of

3.2609

for the problem with bandwidth. This improves the lower bound of 3 that follows from the tight results for interval coloring without bandwidth presented in [9].

This paper studies the dynamic bin packing problem, in which items arrive and depart at arbitrary time. We want to pack a sequence of unit fractions items (i.e., items with sizes 1/

w

for some integer

w

≥ 1) into unit-size bins such that the maximum number of bins used over all time is minimized. Tight and almost-tight performance bounds are found for the family of any-fit algorithms, including first-fit, best-fit, and worst-fit. We show that the competitive ratio of best-fit and worst-fit is 3, which is tight, and the competitive ratio of first-fit lies between 2.45 and 2.4985. We also show that no on-line algorithm is better than 2.428-competitive. This result improves the lower bound of dynamic bin packing problem even for general items.

A sequence of objects which are characterized by their color has to be processed. Their processing order influences how efficiently they can be processed: Each color change between two consecutive objects produces non-uniform cost. A reordering buffer which is a random access buffer with storage capacity for

k

objects can be used to rearrange this sequence in such a way that the total cost are minimized. This concept is useful for many applications in computer science and economics.

We show that a reordering buffer reduces the cost of each sequence by a factor of at most 2

k

–1. This result even holds for cost functions modeled by arbitrary metric spaces. In addition, a matching lower bound is presented. From this bound follows that each strategy that does not increase the cost of a sequence is at least (2

k

–1)-competitive.

As main result, we present the deterministic Maximum Adjusted Penalty (MAP) strategy which is

O

(log

k

)-competitive. Previous strategies only achieve a competitive ratio of

k

in the non-uniform model. For the upper bound on MAP, we introduce a basic proof technique. We believe that this technique can be interesting for other problems.

Most of the decision procedures for symbolic analysis of protocols are limited to a fixed set of algebraic operators associated with a fixed intruder theory. Examples of such sets of operators comprise XOR, multiplication/exponentiation, abstract encryption/decryption. In this paper we give an algorithm for combining decision procedures for arbitrary intruder theories with disjoint sets of operators, provided that solvability of ordered intruder constraints, a slight generalization of intruder constraints, can be decided in each theory. This is the case for most of the intruder theories for which a decision procedure has been given. In particular our result allows us to decide trace-based security properties of protocols that employ any combination of the above mentioned operators with a bounded number of sessions.

In this paper we study the link between formal and cryptographic models for security protocols in the presence of a passive adversary. In contrast to other works, we do not consider a fixed set of primitives but aim at results for an arbitrary equational theory. We define a framework for comparing a cryptographic implementation and its idealization

w.r.t.

various security notions. In particular, we concentrate on the computational soundness of static equivalence, a standard tool in cryptographic pi calculi. We present a soundness criterion, which for many theories is not only sufficient but also necessary. Finally, we establish new soundness results for the exclusive OR and a theory of ciphers and lists.

The use of passwords in security protocols is particularly delicate because of the possibility of off-line guessing attacks. We study password-based protocols in the context of a recent line of research that aims to justify symbolic models in terms of more concrete, computational ones. We offer two models for reasoning about the concurrent use of symmetric, asymmetric, and passwordbased encryption in protocol messages. In each of the models we define a notion of equivalence between messages and also characterize when passwords are used securely in a message or in a set of messages. Our new definition for the computational security of password-based encryption may be of independent interest. The main results of this paper are two soundness theorems. We show that under certain (standard) assumptions about the computational implementation of the cryptographic primitives, symbolic equivalence implies computational equivalence. More importantly, we prove that symbolically secure uses of passwords are also computationally secure.

The cover time of graphs has much relevance to algorithmic applications and has been extensively investigated. Recently, with the advent of ad-hoc and sensor networks, an interesting class of random graphs, namely

random geometric graphs

, has gained new relevance and its properties have been the subject of much study. A random geometric graph

${\mathcal G}(n,r)$

is obtained by placing

n

points uniformly at random on the unit square and connecting two points iff their Euclidean distance is at most

r

. The phase transition behavior with respect to the radius

r

of such graphs has been of special interest. We show that there exists a critical radius

r

opt

such that for any

$r \geq r_{\rm opt} {\mathcal G}(n,r)$

has optimal cover time of Θ(

n

log

n

) with high probability, and, importantly,

r

opt

 = Θ(

r

con

) where

r

con

denotes the critical radius guaranteeing asymptotic connectivity. Moreover, since a disconnected graph has infinite cover time, there is a phase transition and the corresponding threshold width is

O

(

r

con

). We are able to draw our results by giving a tight bound on the electrical resistance of

${\mathcal G}(n,r)$

via the power of certain constructed flows.

Random Intersection Graphs is a new class of random graphs introduced in [5], in which each of

n

vertices randomly and independently chooses some elements from a universal set, of cardinality

m

. Each element is chosen with probability

p

. Two vertices are joined by an edge iff their chosen element sets intersect. Given

n

,

m

so that

m

=

n

α

, for any real

α

different than one, we establish here, for the first time, tight lower bounds

p

0

(

n

,

m

), on the value of p, as a function of

n

and

m

, above which the graph

G

n

,

m

,

p

is almost certainly Hamiltonian, i.e. it contains a Hamilton Cycle almost certainly. Our bounds are tight in the sense that when

p

is asymptotically smaller than

p

0

(

n

,

m

) then

G

n

,

m

,

p

almost surely has a vertex of degree less than 2. Our proof involves new, nontrivial, coupling techniques that allow us to circumvent the edge dependencies in the random intersection model. Interestingly, Hamiltonicity appears well below the general thresholds, of [4], at which

G

n

,

m

,

p

looks like a usual random graph. Thus our bounds are much stronger than the trivial bounds implied by those thresholds.

Our results strongly support the existence of a threshold for Hamiltonicity in

G

n

,

m

,

p

.

In this paper we study the following covering process defined over an arbitrary directed graph. Each node is initially uncovered and is assigned a random integer rank drawn from a suitable range. The process then proceeds in rounds. In each round, a uniformly random node is selected and its lowest-ranked uncovered outgoing neighbor, if any, is covered. We prove that if each node has in-degree

$\theta({\it d})$

and out-degree

O

(

d

), then with high probability, every node is covered within

$O(n+ \frac{n \ {\rm log}\ n}{d})$

rounds, matching a lower bound due to Alon. Alon has also shown that, for a certain class of

d

-regular expander graphs, the upper bound holds no matter what method is used to choose the uncovered neighbor. In contrast, we show that for arbitrary

d

-regular graphs, the method used to choose the uncovered neighbor can affect the cover time by more than a constant factor.

Recently, there has been a surge of research activity in the area of

Link Analysis Ranking

, where hyperlink structures are used to determine the relative

authority

of Web pages. One of the seminal works in this area is that of Kleinberg [15], who proposed the

Hits

algorithm. In this paper, we undertake a theoretical analysis of the properties of the

Hits

algorithm on a broad class of random graphs. Working within the framework of Borodin et al.[7], we prove that on this class (a) the

Hits

algorithm is stable with high probability, and (b) the

Hits

algorithm is similar to the

InDegree

heuristic that assigns to each node weight proportional to the number of incoming links. We demonstrate that our results go through for the case that the expected in-degrees of the graph follow a power-law distribution, a situation observed in the actual Web graph [9]. We also study experimentally the similarity between

Hits

and

InDegree

, and we investigate the general conditions under which the two algorithms are similar.

Up-to techniques have been introduced to enhance the bisimulation proof method for establishing bisimilarity results. While up-to techniques for strong bisimilarity are well understood, in the weak case they come as a collection of unrelated results, and lack a unified presentation. We propose a uniform and modular theory of up-to techniques for weak bisimulation that captures existing proof technology and introduces new techniques. Some proofs rely on non trivial – and new – commutation results based on termination guarantees.

The firing rule of Petri nets relies on a residuation operation for the commutative monoid of natural numbers. We identify a class of residuated commutative monoids, called Petri algebras, for which one can mimic the token game of Petri nets to define the behaviour of generalized Petri net whose flow relation and place contents are valued in such algebraic structures. We show that Petri algebras coincide with the positive cones of lattice-ordered commutative groups and constitute the subvariety of the (duals of) residuated lattices generated by the commutative monoid of natural numbers. We introduce a class of nets, termed lexicographic Petri nets, that are associated with the positive cones of the lexicographic powers of the additive group of real numbers. This class of nets is universal in the sense that any net associated with some Petri algebras can be simulated by a lexicographic Petri net. All the classical decidable properties of Petri nets however are undecidable on the class of lexicographic Petri nets. Finally we turn our attention to bounded nets associated with Petri algebras and show that their dynamics can be reformulated in term of MV-algebras.

We present a finite

ω

-complete axiomatization for the process algebra BCCSP modulo failure semantics, in case of a finite alphabet. This solves an open question by Groote [12] .

Bigraphs are emerging as an interesting model for concurrent calculi, like CCS, pi-calculus, and Petri nets. Bigraphs are built orthogonally on two structures: a hierarchical place graph for locations and a link (hyper-)graph for connections. With the aim of describing bigraphical structures, we introduce a general framework for logics whose terms represent arrows in monoidal categories. We then instantiate the framework to bigraphical structures and obtain a logic that is a natural composition of a place graph logic and a link graph logic. We explore the concepts of separation and sharing in these logics and we prove that they generalise some known spatial logics for trees, graphs and tree contexts.

An encryption scheme is non-malleable if the adversary cannot transform a ciphertext into one of a related message under the given public key. Although providing a very strong security property, some application scenarios like the recently proposed key-substitution attacks yet show the limitations of this notion. In such settings the adversary may have the power to transform the ciphertext

and

the given public key, possibly without knowing the corresponding secret key of her own public key. In this paper we therefore introduce the notion of completely non-malleable cryptographic schemes withstanding such attacks. We show that classical schemes like the well-known Cramer-Shoup DDH encryption scheme become indeed insecure against this stronger kind of attack, implying that the notion is a strict extension of chosen-ciphertext security. We also prove that, unless one puts further restrictions on the adversary’s success goals, completely non-malleable schemes are hard to construct (as in the case of encryption) or even impossible (as in the case of signatures). Identifying the appropriate restrictions we then show how to modify well-known constructions like RSA-OAEP and Fiat-Shamir signatures yielding practical solutions for the problem in the random oracle model.

The first practical identity based encryption (IBE) scheme was proposed by Boneh and Franklin in [BF03]. In this work we point out that there is a flawed step in the security reduction exhibited by the authors. Fortunately, it is possible to fix it without changing the scheme or the underlying assumption.

In the second place, we introduce a variant of the seminal IBE scheme which allows a more efficient security reduction. This variant is simpler, and has more compact ciphertexts than Boneh-Franklin’s proposal, while keeping the computational cost.

Finally, we observe that the flawed step pointed out here is present in several works, and that our techniques can be applied to obtain tighter reductions for previous relevant schemes.

We present a single-database private information retrieval (PIR) scheme with communication complexity

${\mathcal O}(k+d)$

, where

k

≥ log

n

is a security parameter that depends on the database size

n

and

d

is the bit-length of the retrieved database block. This communication complexity is better asymptotically than previous single-database PIR schemes. The scheme also gives improved performance for practical parameter settings whether the user is retrieving a single bit or very large blocks. For large blocks, our scheme achieves a constant “rate” (e.g., 0.2), even when the user-side communication is very low (e.g., two 1024-bit numbers). Our scheme and security analysis is presented using general groups with hidden smooth subgroups; the scheme can be instantiated using composite moduli, in which case the security of our scheme is based on a simple variant of the “Φ-hiding” assumption by Cachin, Micali and Stadler [2].

The concurrent setting for Zero-Knowledge protocols is very challenging as it requires protocols to remain secure even when several parties execute the same protocol concurrently. Indeed, it has been proved that achieving concurrent security for (black-box-simulation) zero-knowledge protocols in standard models requires a non-constant number of rounds, thus severely limiting efficiency. As a result, a few models with additional setup or network assumptions have been introduced to present constant-round concurrently-secure zero-knowledge protocols for all languages in

${\mathcal NP}$

.

In this paper we consider the bare public-key model, which is known to have very minimal setup assumptions, and we present the first constant round and concurrently secure zero-knowledge argument for any languages in

${\mathcal NP}$

, under standard intractability assumptions. In fact, our protocol requires 4 rounds and is therefore round-optimal, is a proof of knowledge, and is time-efficient, in the sense that it is based on a tranformation that does not require any expensive

${\mathcal NP}$

reduction from prover or verifier. One 5-round variant of our protocol can be based on the minimal assumption of the existence of a one-way function.

We consider the problem of scheduling

n

independent jobs on

m

unrelated parallel machines without preemption. Job

i

takes processing time

p

ij

on machine

j

, and the total time used by a machine is the sum of the processing times for the jobs assigned to it. The objective is to minimize makespan. The best known approximation algorithms for this problem compute an optimum fractional solution and then use rounding techniques to get an integral 2-approximation.

In this paper we present a combinatorial approximation algorithm that matches this approximation quality. It is much simpler than the previously known algorithms and its running time is better. This is the first time that a combinatorial algorithm always beats the interior point approach for this problem. Our algorithm is a generic minimum cost flow algorithm, without any complex enhancements, tailored to handle unsplittable flow. It pushes unsplittable jobs through a two-layered bipartite generalized network defined by the scheduling problem. In our analysis, we take advantage from addressing the approximation problem directly. In particular, we replace the classical technique of solving the LP-relaxation and rounding afterwards by a completely integral approach. We feel that this approach will be helpful also for other applications.

The

preemptive Sum-Multicoloring (pSMC)

problem is a scheduling problem where pairwise conflicting jobs are represented by a conflict graph. The time demands of jobs are given by integer weights on the nodes. The goal is to schedule the jobs in such a way that the

sum

of their finish times is minimized. We give an

${\mathcal O}(n \cdot {\rm min}(n,{\rm log}\ p))$

time algorithm for pSMC on paths and cycles, where

n

is the number of nodes and

p

is the largest time demand. This is the first polynomial algorithm for this problem. It answers the question raised in [8] about the hardness of this problem. In this respect our result identifies a gap between binary-tree conflict graphs – where the question is NP-hard – and paths. Furthermore, our time bound gets very close to that of

${\mathcal O}(n\cdot {\rm log} \ p/{\rm log log} \ p)$

for the

non-preemptive

SMC on paths [8] . A detailed version of this paper is available at [3].

In this paper we initiate the study of the AND-OR directed feedback vertex set problem from the viewpoint of approximation algorithms. This AND-OR feedback vertex set problem is motivated by a practical deadlock resolution problem that appears in the development of distributed database systems. This problem also turns out be a natural generalization of the directed feedback vertex set problem. Awerbuch and Micali [1] gave a polynomial time algorithm to find a minimal solution for this problem. Unfortunately, a minimal solution can be arbitrarily more expensive than the minimum cost solution. We show that finding the minimum cost solution is as hard as the directed Steiner tree problem (and thus Ω(

log

2

n

) hard to approximate). On the positive side, we give algorithms which work well when the number of writers (AND nodes) or the number of readers (OR nodes) are small.

We also consider a variant that we call

permanent deadlock resolution

where we cannot specify an execution order for the surviving processes; they should get completed even if they were scheduled adversarially. When all processes are writers (AND nodes), we give an

O

(log

n

log log

n

) approximation for this problem.

Finally we give an LP-rounding approach and discuss some other natural variants.

In this paper we present a randomized constant factor approximation algorithm for the problem of computing the optimal

cost

of the metric Minimum Facility Location problem, in the case of uniform costs and uniform demands, and in which every point can open a facility. By exploiting the fact that we are approximating the optimal cost without computing an actual solution, we give the first algorithm for this problem with running time

O

(

n

log

2

n

), where

n

is the number of metric space points. Since the size of the representation of an

n

-point metric space is Θ(

n

2

), the complexity of our algorithm is

sublinear

with respect to the input size.

We consider also the general version of the metric Minimum Facility Location problem and we show that there is no

o

(

n

2

)-time algorithm, even a randomized one, that approximates the optimal solution to within any factor. This result can be generalized to some related problems, and in particular, the cost of minimum-cost matching, the cost of bi-chromatic matching, or the cost of

n

/2-median cannot be approximated in

o

(

n

2

)-time.

The theory of graph games with

ω

-regular winning conditions is the foundation for modeling and synthesizing reactive processes. In the case of stochastic reactive processes, the corresponding stochastic graph games have three players, two of them (System and Environment) behaving adversarially, and the third (Uncertainty) behaving probabilistically. We consider two problems for stochastic graph games: the

qualitative

problem asks for the set of states from which a player can win with probability 1 (

almost-sure winning

); the

quantitative

problem asks for the maximal probability of winning (

optimal winning

) from each state. We show that for Rabin winning conditions, both problems are in NP. As these problems were known to be NP-hard, it follows that they are NP-complete for Rabin conditions, and dually, coNP-complete for Streett conditions. The proof proceeds by showing that pure memoryless strategies suffice for qualitatively and quantitatively winning stochastic graph games with Rabin conditions. This insight is of interest in its own right, as it implies that controllers for Rabin objectives have simple implementations. We also prove that for every

ω

-regular condition, optimal winning strategies are no more complex than almost-sure winning strategies.

We introduce Recursive Markov Decision Processes (RMDPs) and Recursive Simple Stochastic Games (RSSGs), and study the decidability and complexity of algorithms for their analysis and verification. These models extend Recursive Markov Chains (RMCs), introduced in [EY05a, EY05b] as a natural model for verification of probabilistic procedural programs and related systems involving both recursion and probabilistic behavior. RMCs define a class of denumerable Markov chains with a rich theory generalizing that of stochastic context-free grammars and multi-type branching processes, and they are also intimately related to probabilistic pushdown systems. RMDPs & RSSGs extend RMCs with one controller or two adversarial players, respectively. Such extensions are useful for modeling nondeterministic and concurrent behavior, as well as modeling a system’s interactions with an environment.

We provide upper and lower bounds for deciding, given an RMDP (or RSSG)

A

and probability

p

, whether player 1 has a strategy to force termination at a desired exit with probability at least

p

. We also address “qualitative” termination, where

p

=1, and model checking questions.

We investigate the decidability of observational equivalence and approximation in “Syntactic Control of Interference” (SCI). By associating denotations of terms in an inequationally fully abstract model of finitary basic SCI with multitape finite state automata, we show that observational approximation is not decidable (even at first order), but that observational equivalence is decidable for all terms. We then consider the same problems for basic SCI extended with non-local control in the form of backwards jumps. We show that both observational approximation and observational equivalence are decidable in this language by describing a fully abstract games model in which strategies are regular languages.

We prove that observational equivalence of

IA

3

+

Y

0

(3rd-order Idealized Algol with 0th-order recursion) is equivalent to the DPDA Equivalence Problem, and hence decidable. This completes the classification of decidable fragments of Idealized Algol. We also prove that observational approximation of

IA

1

+

Y

0

is undecidable by reducing the DPDA Containment Problem to it.

We consider a game-theoretical variant of the Steiner forest problem, in which each of

k

users

i

strives to connect his terminal pair (

s

i

,

t

i

) of vertices in an undirected, edge-weighted graph

G

. In [1] a natural primal-dual algorithm was shown which achieved a 2-approximate budget balanced cross-monotonic cost sharing method for this game.

We derive a new linear programming relaxation from the techniques of [1] which allows for a simpler proof of the budget balancedness of the algorithm from [1]. Furthermore we show that this new relaxation is strictly stronger than the well-known

undirected cut relaxation

for the Steiner forest problem.

We conclude the paper with a negative result, arguing that no cross-monotonic cost sharing method can achieve a budget balance factor of less than 2 for the Steiner tree and Steiner forest games. This shows that the results of [1,2] are essentially tight.

We define an algorithmic paradigm, the stack model, that captures most primal-dual and local-ratio algorithms for approximating covering and packing problems. The stack model is defined syntactically and without any complexity limitations. Hence our approximation bounds are independent of the

P

vs

NP

question. We provide tools to bound the performance of primal dual and local ratio algorithms and supply a (log

n

+1)/2 inapproximability result for set-cover, a 4/3 inapproximability for min steiner tree, and a 0.913 inapproximability for interval scheduling on two machines.

An instance of

Max

k

CSP consists of weighted

k

-ary constraints acting over a set of Boolean variables. The objective is to find an assignment to the Boolean variables such that the total weight of satisfied constraints is maximized. In this paper we provide a probabilistical polynomial time approximation algorithm that

c

0

k

(log

k

)

− 1

2

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

-approximates

Max

k

CSP, for a constant

c

0

>0.

This paper presents several advances in the understanding of dynamic data structures in the bit-probe model:

We improve the lower bound record for dynamic language membership problems to

$\Omega((\frac{{\rm lg}\ n}{\rm lg \ lg \ {\it n}})^{2})$

. Surpassing

$\Omega({\rm lg} \ {\it n})$

was listed as the first open problem in a survey by Miltersen.

We prove a bound of

$\Omega(\frac{{\rm lg}\ n}{\rm lg \ lg \ lg \ {\it n}})$

for maintaining partial sums in

${\mathbb Z}/2{\mathbb Z}$

. Previously, the known bounds were

$\Omega(\frac{{\rm lg}\ n}{\rm lg \ lg \ {\it n}})$

and

$O({\rm lg}\ n)$

.

We prove a surprising and tight upper bound of

$O(\frac{{\rm lg} \ {\it n}}{\rm lg \ lg \ {\it n}})$

for predecessor problems. We use this to obtain the same upper bound for dynamic word and prefix problems in group-free monoids.

We establish the first polynomial-strength time-space lower bounds for problems in the linear-time hierarchy on randomized machines with bounded two-sided error. We show that for any integer ℓ > 1 and constant

c

< ℓ, there exists a positive constant

d

such that QSAT

ℓ

cannot be computed by such machines in time

n

c

and space

n

d

, where QSAT

ℓ

denotes the problem of deciding the validity of a Boolean first-order formula with at most ℓ–1 quantifier alternations. Corresponding to ℓ = 1, we prove that for any constant

c

<

φ

≈ 1.618, there exists a positive constant

d

such that the set of Boolean tautologies cannot be decided by a randomized machine with one-sided error in time

n

c

and space

n

d

.

We consider constant depth circuits augmented with few modular, or more generally, arbitrary symmetric gates. We prove that circuits augmented with

o

(log

2

n

) symmetric gates must have size

n

$^{\Omega({\rm log}\ {\it n})}$

to compute a certain (complicated) function in

ACC

0

.

This function is also hard on the average for circuits of size

n

$^{\epsilon log {\it n}}$

augmented with

o

(log

n

) symmetric gates, and as a consequence we can get a pseudorandom generator for circuits of size

m

containing

$o(\sqrt{{\rm log} \ m})$

symmetric gates.

For a composite integer

m

having

r

distinct prime factors, we prove that circuits augmented with

s

MOD

m

gates must have size

${\it n}^{\Omega(\frac{1}{s}{\rm log}^{\frac{1}{r-1}}n)}$

to compute MAJORITY or MOD

l

, if

l

has a prime factor not dividing

m

. For proving the latter result we introduce a new notion of representation of boolean function by polynomials, for which we obtain degree lower bounds that are of independent interest.

In this paper we explore discrete random variables over domains. We show that these lead to a continuous endofunctor on the categories

RB

(domains that are retracts of bifinite domains), and

FS

(domains where the identity map is the directed supremum of deflations finitely separated from the identity). The significance of this result lies in the fact that there is no known category of continuous domains that is closed under the probabilistic power domain, which forms the standard approach to modeling probabilistic choice over domains. The fact that

RB

and

FS

are cartesian closed and also are closed under the discrete random variables power domain means we can now model, e.g., the untyped lambda calculus extended with a probabilistic choice operator, implemented via random variables.

Behavioural pseudometrics are a quantitative analogue of behavioural equivalences. They provide robust models for those concurrent systems in which quantitative data plays a crucial role. In this paper, we show how behavioural pseudometrics can be defined coalgebraically. Our results rely on the theory of accessible categories. We apply our results to obtain a robust model for probabilistic systems.

Turing machines exposed to a small stochastic noise are considered. An exact characterisation of their (≈

${\it \Pi}$

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

) computational power (as noise level tends to 0) is obtained. From a probabilistic standpoint this is a theory of large deviations for Turing machines.

We reduce the approximation factor for Vertex Cover to

$2 - \theta(\frac{1}{\sqrt{{\rm log} n}})$

(instead of the previous

$2- \theta(\frac{{\rm log log} n}{{\rm log}\ n})$

, obtained by Bar-Yehuda and Even [3], and by Monien and Speckenmeyer[11]). The improvement of the vanishing factor comes as an application of the recent results of Arora, Rao, and Vazirani [2] that improved the approximation factor of the sparsest cut and balanced cut problems. In particular, we use the existence of two big and well-separated sets of nodes in the solution of the semidefinite relaxation for balanced cut, proven in [2]. We observe that a solution of the semidefinite relaxation for vertex cover, when strengthened with the triangle inequalities, can be transformed into a solution of a balanced cut problem, and therefore the existence of big well-separated sets in the sense of [2] translates into the existence of a big independent set.

This paper considers the Steiner tree problem in the model of

two-stage stochastic optimization with recourse

. This model, the focus of much recent research [11, 16, 8, 18], tries to capture the fact that many infrastructure planning problems have to be solved in the presence of uncertainty, and that we have make decisions knowing merely market forecasts (and not the precise set of demands); by the time the actual demands arrive, the costs may be higher due to inflation.

In the context of the Stochastic Steiner Tree problem on a graph

G

= (

V

,

E

), the model can be paraphrased thus: on Monday, we are given a probability distribution

π

on subsets of vertices, and can build some subset

E

M

of edges. On Tuesday, a set of terminals

D

materializes (drawn from the same distribution

π

). We now have to buy edges

E

T

so that the set

E

M

∪

E

T

forms a Steiner tree on

D

. The goal is to minimize the expected cost of the solution.

We give the first constant-factor approximation algorithm for this problem. To the best of our knowledge, this is the first

O

(1)-approximation for the stochastic version of a

non sub-additive problem

. In fact, algorithms for the

unrooted

stochastic Steiner tree problem we consider are powerful enough to solve the Multicommodity Rent-or-Buy problem, itself a topic of recent interest [3, 7, 15].

Given a graph

G

= (

V

,

E

) and positive integral vertex weights

w

:

V

→

N

, the

max-coloring problem

seeks to find a proper vertex coloring of

G

whose color classes

C

1

,

C

2

, ...,

C

k

, minimize

${\sum_{i=1}^{k}}{\it max}_{v\epsilon C{_{i}} {\it w}(v)}$

. The problem arises in scheduling conflicting jobs in batches and in minimizing buffer size in dedicated memory managers.

In this paper we present three approximation algorithms and one inapproximability result for the max-coloring problem. We show that if for a class of graphs

${\mathcal G}$

, the classical problem of finding a proper vertex coloring with fewest colors has a

c

-approximation, then for that class

${\mathcal G}$

of graphs, max-coloring has a 4

c

-approximation algorithm. As a consequence, we obtain a 4-approximation algorithm to solve max-coloring on perfect graphs, and well-known subclasses such as chordal graphs, and permutation graphs. We also obtain constant-factor algorithms for max-coloring on classes of graphs such as circle graphs, circular arc graphs, and unit disk graphs, which are not perfect, but do have a constant-factor approximation for the usual coloring problem. As far as we know, these are the first constant-factor algorithms for all of these classes of graphs. For bipartite graphs we present an approximation algorithm and a matching inapproximability result. Our approximation algorithm returns a coloring whose weight is within

$\frac{8}{7}$

times the optimal. We then show that for any

ε

> 0, it is impossible to approximate max-coloring on bipartite graphs to within a factor of

$(\frac{8}{7} - \epsilon)$

unless

P

=

NP

. Thus our approximation algorithm yields an optimum approximation factor. Finally, we also present an exact sub-exponential algorithm and a PTAS for max-coloring on trees.

We study a clean machine model for external memory and stream processing. We show that the number of scans of the external data induces a strict hierarchy (as long as work space is sufficiently small, e.g., polylogarithmic in the size of the input). We also show that neither joins nor sorting are feasible if the product of the number

r

(

n

) of scans of the external memory and the size

s

(

n

) of the internal memory buffers is sufficiently small, e.g., of size

$o(\sqrt[n]{5})$

. We also establish tight bounds for the complexity of XPath evaluation and filtering.

This paper is concerned with the language inclusion problem for timed automata: given timed automata

${\mathcal A}$

and

${\mathcal B}$

, is every word accepted by

${\mathcal B}$

also accepted by

${\mathcal A}$

? Alur and Dill [3] showed that the language inclusion problem is decidable if

${\mathcal A}$

has no clocks and undecidable if

${\mathcal A}$

has two clocks (with no restriction on

${\mathcal B}$

). However, the status of the problem when

${\mathcal A}$

has one clock is not determined by [3]. In this paper we close this gap for timed automata over infinite words by showing that the one-clock language inclusion problem is undecidable. For timed automata over finite words, building on our earlier paper [20], we show that the one-clock language inclusion problem is decidable with non-primitive recursive complexity. This reveals a surprising divergence between the theory of timed automata over finite words and over infinite words. Finally, we show that if

ε

-transitions or non-singular postconditions are allowed, then the one-clock language inclusion problem is undecidable over both finite and infinite words.

We study congruences on words in order to characterize the class of visibly pushdown languages (

Vpl

), a subclass of context-free languages. For any language

L

, we define a natural congruence on words that resembles the syntactic congruence for regular languages, such that this congruence is of finite index if, and only if,

L

is a

Vpl

. We then study the problem of finding canonical minimal deterministic automata for

Vpl

s. Though

Vpl

s in general do not have unique minimal automata, we consider a subclass of VPAs called

k

-module single-entry VPAs that correspond to programs with recursive procedures without input parameters, and show that the class of well-matched

Vpl

s do indeed have unique minimal

k

-module single-entry automata. We also give a polynomial time algorithm that minimizes such

k

-module single-entry VPAs.

In the Euclidean group

Traveling Salesman Problem

(TSP), we are given a set of points

P

in the plane and a set of

m

connected regions, each containing at least one point of

P

. We want to find a tour of minimum length that visits at least one point in each region. This unifies the TSP with Neighborhoods and the Group Steiner Tree problem. We give a (9.1

α

+1)-approximation algorithm for the case when the regions are disjoint

α

-fat objects with possibly varying size. This considerably improves the best results known, in this case, for both the group Steiner tree problem and the TSP with Neighborhoods problem. We also give the first

O

(1)-approximation algorithm for the problem with intersecting regions.

We study the problem of maximizing the expected spread of an innovation or behavior within a social network, in the presence of “word-of-mouth” referral. Our work builds on the observation that individuals’ decisions to purchase a product or adopt an innovation are strongly influenced by recommendations from their friends and acquaintances. Understanding and leveraging this influence may thus lead to a much larger spread of the innovation than the traditional view of marketing to individuals in isolation.

In this paper, we define a natural and general model of influence propagation that we term the

decreasing cascade model

, generalizing models used in the sociology and economics communities. In this model, as in related ones, a behavior spreads in a cascading fashion according to a probabilistic rule, beginning with a set of initially “active” nodes. We study the

target set selection

problem: we wish to choose a set of individuals to target for initial activation, such that the cascade beginning with this active set is as large as possible in expectation. We show that in the decreasing cascade model, a natural greedy algorithm is a 1-1/ e-

ε

approximation for selecting a target set of size

k

.

Computing energy efficient broadcast trees is one of the most prominent operations in wireless networks. For stations embedded in the Euclidean plane, the best analytic result known to date is a 6.33-approximation algorithm based on computing an Euclidean minimum spanning tree. We improve the analysis of this algorithm and show that its approximation ratio is 6, which matches a previously known lower bound for this algorithm.

Virtual private network design

is the following NP-hard problem. We are given a communication network, represented as a weighted graph with thresholds on the nodes which represent the amount of flow that a node can send to and receive from the network. The task is to reserve capacities at minimum cost and to specify paths between every ordered pair of nodes such that all valid traffic-matrices can be routed along the corresponding paths.

Recently, this network design problem has received considerable attention in the literature. It is motivated by the fact that the exact amount of flow which is exchanged between terminals is not known in advance and prediction is often illusive. The main contributions of this paper are as follows:

Using Hu’s 2-commodity flow theorem, we provide a new lower bound on the cost of an optimum solution.

Using this lower bound we reanalyze a simple routing scheme which has been described in the literature many times and provide a considerably stronger upper bound on its approximation ratio.

We present a new randomized approximation algorithm for which, in contrast to earlier approaches from the literature, the resulting solution does not have tree structure.

Finally we show that a combination of our new algorithm with the simple routing scheme yields a randomized algorithm with expected performance ratio 3.55 for virtual private network design. This is a considerable improvement of the previously best known approximation results (5.55 STOC’03, 4.74 SODA’05).

We develop a new method for estimating the discrepancy of tensors associated with multiparty communication problems in the “Number on the Forehead” model of Chandra, Furst and Lipton. We define an analogue of the Hadamard property of matrices for tensors in multiple dimensions and show that any

k

-party communication problem represented by a Hadamard tensor must have Ω(

n

/2

k

) multiparty communication complexity. We also exhibit constructions of Hadamard tensors, giving Ω(

n

/2

k

) lower bounds on multiparty communication complexity for a new class of explicitly defined Boolean functions.

We prove that an

ω

(log

3

n

) lower bound for the three-party number-on-the-forehead (NOF) communication complexity of the set-disjointness function implies an

n

ω

(1)

size lower bound for tree-like Lovász-Schrijver systems that refute unsatisfiable CNFs. More generally, we prove that an

n

Ω(1)

lower bound for the (

k

+1)-party NOF communication complexity of set-disjointness implies a

$2^{n^{\Omega(1)}}$

size lower bound for all tree-like proof systems whose formulas are degree

k

polynomial inequalities.

We give an

l

-ary greatest common divisor algorithm in the ring of integers of any number field with class number 1, i.e., factorial rings of integers. The algorithm has a quadratic running time in the bit-size of the input using naive integer arithmetic.

The

π

-calculus with data terms (

π

T) extends the pure

π

-calculus by data constructors and destructors and allows data to be transmitted between agents. It has long been known how to encode such data types in

π

, but until now it has been open how to make the encoding

fully abstract

, meaning that two encodings (in

π

) are semantically equivalent precisely when the original

π

T agents are semantically equivalent. We present a new type of encoding and prove it to be fully abstract with respect to may-testing equivalence. To our knowledge this is the first result of its kind, for any calculus enriched with data terms. It has particular importance when representing security properties since attackers can be regarded as may-test observers. Full abstraction proves that it does not matter whether such observers are formulated in

π

or

π

T, both are equally expressive in this respect. The technical new idea consists of achieving full abstraction by encoding data as table entries rather than active processes, and using a firewalled central integrity manager to ensure data security.

In this paper, we give novel and more liberal notions of operational and equational conservativity for language extensions. We motivate these notions by showing their practical application in existing formalisms. Based on our notions, we formulate and prove meta-theorems that establish conservative extensions for languages defined using Structural Operational Semantics (SOS).

We introduce a foundational language for modelling applications over global computers whose interconnection structure can be explicitly manipulated. Together with process distribution, mobility, remote operations and asynchronous communication through distributed data spaces, the language provides constructs for explicitly modelling inter-node connections and for dynamically establishing and removing them. For the proposed language, we define natural notions of extensional observations and study their closure under operational reductions and/or language contexts to obtain

barbed congruence

and

may testing

equivalence. For such equivalences, we provide alternative characterizations in terms of a labelled

bisimulation

and a

trace

equivalence that can be used for actual proofs.

We investigate the foundations of a constraint-based compositional verification method for infinite-state systems. We first consider an asynchronous process calculus which is an abstract formalization of several existing languages based on the blackboard model. For this calculus we define a constraint-based symbolic representation of finite computations of a compositional model based on traces. The constraint system we use combines formulas of integer arithmetics with equalities over uninterpreted functions in which satisfiability is decidable. The translation is inductively defined via a CLP program. Execution traces of a process can be compositionally obtained from the solutions of the answer constraints of the CLP encoding. This way, the task of compositional verification can be reduced to constraint computing and solving.

Filtering

is a standard technique for fast approximate string matching in practice.In filtering, a quick first step is used to rule out almost all positions of a text as possible starting positions for a pattern. Typically this step consists of finding the exact matches of small parts of the pattern. In the followup step, a slow method is used to verify or eliminate each remaining position. The running time of such a method depends largely on the quality of the filtering step, as measured by its false positives rate. The quality of such a method depends on the number of true matches that it misses, that is, on its false negative rate.

A

spaced seed

is a recently introduced type of filter pattern that allows gaps (i.e. don’t cares) in the small sub-pattern to be searched for. Spaced seeds promise to yield a much lower false positives rate, and thus have been extensively studied, though heretofore only heuristically or statistically.

In this paper, we show how to optimally design spaced seeds that yield no false negatives.

Reconstructing the evolutionary history of a set of species is a fundamental problem in biology and methods for solving this problem are gaged based on two characteristics: accuracy and efficiency. Neighbor Joining (NJ) is a so-called distance-based method that, thanks to its good accuracy and speed, has been embraced by the phylogeny community. It takes the distances between

n

taxa and produces in Θ(

n

3

) time a phylogenetic tree, i.e., a tree which aims to describe the evolutionary history of the taxa. In addition to performing well in practice, the NJ algorithm has optimal reconstruction radius.

The contribution of this paper is twofold: (1) we present an algorithm called Fast Neighbor Joining (FNJ) with optimal reconstruction radius and optimal run time complexity

O

(

n

2

) and (2) we present a greatly simplified proof for the correctness of NJ. Initial experiments show that FNJ in practice has almost the same accuracy as NJ, indicating that the property of optimal reconstruction radius has great importance to their good performance. Moreover, we show how improved running time can be achieved for computing the so-called correction formulas.

We consider the problem of efficiently designing sets (codes) of equal-length DNA strings (words) that satisfy certain combinatorial constraints. This problem has numerous motivations including DNA computing and DNA self-assembly. Previous work has extended results from coding theory to obtain bounds on code size for new biologically motivated constraints and has applied heuristic local search and genetic algorithm techniques for code design. This paper proposes a natural optimization formulation of the DNA code design problem in which the goal is to design

n

strings that satisfy a given set of constraints while minimizing the length of the strings. For multiple sets of constraints, we provide high-probability algorithms that run in time polynomial in

n

and any given constraint parameters, and output strings of length within a constant factor of the optimal. To the best of our knowledge, this work is the first to consider this type of optimization problem in the context of DNA code design.

Simon in his FOCS’94 paper was the first to show an exponential gap between classical and quantum computation. The problem he dealt with is now part of a well-studied class of problems, the hidden subgroup problems. We study Simon’s problem from the point of view of quantum query complexity and give here a first nontrivial lower bound on the query complexity of a hidden subgroup problem, namely Simon’s problem. More generally, we give a lower bound which is optimal up to a constant factor for any Abelian group.

The quantum adversary method is one of the most versatile lower-bound methods for quantum algorithms. We show that all known variants of this method are equal: spectral adversary [1], weighted adversary [2], strong weighted adversary [3], and the Kolmogorov complexity adversary [4]. We also present a few new equivalent formulations of the method. This shows that there is essentially

one

quantum adversary method. From our approach, all known limitations of all versions of the quantum adversary method easily follow.

We consider the problem of testing the commutativity of a black-box group specified by its

k

generators. The complexity (in terms of

k

) of this problem was first considered by Pak, who gave a randomized algorithm involving

O

(

k

) group operations. We construct a quite optimal quantum algorithm for this problem whose complexity is in Õ(

k

2/3

). The algorithm uses and highlights the power of the quantization method of Szegedy. For the lower bound of Ω(

k

2/3

), we introduce a new technique of reduction for quantum query complexity. Along the way, we prove the optimality of the algorithm of Pak for the randomized model.

In this paper we introduce a semantic-based approach for code obfuscation. The aim of code obfuscation is to prevent malicious users to disclose properties of the original source program. This goal can be precisely modeled by abstract interpretation, where the hiding of properties corresponds to abstract the semantics. We derive a general theory based on abstract interpretation, where the potency of code obfuscation can be measured by comparing hidden properties in the lattice of abstract interpretations. Semantic-based code obfuscation is applied to show that well known program transformation methods, such as constant propagation, can be seen as code obfuscation.

We present a Hoare logic for a simple imperative while-language with stored commands, ie. stored parameterless procedures. Stores that may contain procedures are called higher-order. Soundness of our logic is established by using denotational rather than operational semantics. The former is employed to elegantly account for an inherent difficulty of higher-order store, namely that assertions necessarily describe recursive predicates on a recursive domain. In order to obtain proof rules for mutually recursive procedures, assertions have to explicitly refer to the code of the procedures.

Although every terminating loop has a ranking function, not every loop has a ranking function of a restricted form, such as a lexicographic tuple of polynomials over program variables. The

polyranking principle

is proposed as a generalization of polynomial ranking for analyzing termination of loops. We define

lexicographic polyranking functions

in the context of loops with parallel transitions consisting of polynomial assertions, including inequalities, over primed and unprimed variables. Next, we address

synthesis

of these functions with a complete and automatic method for synthesizing

lexicographic linear polyranking functions

with supporting linear invariants over linear loops.

We show a constant factor approximation algorithm for interior guarding of monotone polygons. Using this algorithm we obtain an approximation algorithm for interior guarding rectilinear polygons that has an approximation factor independent of the number of vertices of the polygon. If the size of the smallest interior guard cover is

OPT

for a rectilinear polygon, our algorithm produces a guard set of size

O

(

OPT

2

).

We generalize the

k

-means algorithm presented by the authors [14] and show that the resulting algorithm can solve a larger class of clustering problems that satisfy certain properties (

existence of a random sampling procedure

and

tightness

). We prove these properties for the

k

-median and the discrete

k

-means clustering problems, resulting in

O

(2

(

k

/

ε

)

O

(1)

dn

) time (1+

ε

)-approximation algorithms for these problems. These are the first algorithms for these problems linear in the size of the input (

nd

for

n

points in

d

dimensions), independent of dimensions in the exponent, assuming

k

and

ε

to be fixed. A key ingredient of the

k

-median result is a (1+

ε

)-approximation algorithm for the 1-median problem which has running time

O

(2

(1/

ε

)

O

(1)

d

). The previous best known algorithm for this problem had linear running time.

We consider the problem of dynamic load balancing in arbitrary (connected) networks on

n

nodes. Our load generation model is such that during each round,

n

tasks are generated on arbitrary nodes, and then (possibly after some balancing) one task is deleted from every non-empty node. Notice that this model

fully saturates

the resources of the network in the sense that we generate just as many new tasks per round as the network is able to delete. We show that even in this situation the system is

stable

, in that the total load remains bounded (as a function of

n

alone) over time. Our proof only requires that the underlying “communication” graph be connected. (It of course also works if we generate less than

n

new tasks per round, but the major contribution of this paper is the fully saturated case.) We further show that the upper bound we obtain is asymptotically tight (up to a moderate multiplicative constant) by demonstrating a corresponding lower bound on the system load for the particular example of a linear array (or path). We also show some simple negative results (i.e., instability) for work-stealing based diffusion-type algorithms in this setting.

The hidden subgroup problem (HSP) offers a unified framework to study problems of group-theoretical nature in quantum computing such as order finding and the discrete logarithm problem. While it is known that Fourier sampling provides an efficient solution in the abelian case, not much is known for general non-abelian groups. Recently, some authors raised the question as to whether post-processing the Fourier spectrum by measuring in a random orthonormal basis helps for solving the HSP. Several negative results on the shortcomings of this

random strong

method are known. In this paper however, we show that the random strong method can be quite powerful under certain conditions on the group

G

. We define a parameter

r

(

G

) and show that

O

((log |

G

| /

r

(

G

))

2

) iterations of the random strong method give enough classical information to solve the HSP. We illustrate the power of the random strong method via a concrete example of the HSP over finite Heisenberg groups. We show that

r

(

G

) = Ω(1) for these groups; hence the HSP can be solved using polynomially many random strong Fourier samplings followed by a possibly exponential classical post-processing without further queries. The quantum part of our algorithm consists of a polynomial computation followed by measuring in a random orthonormal basis. As an interesting by-product of our work, we get an algorithm for solving the

state identification problem

for a set of nearly orthogonal pure quantum states.

We improve hardness results for the problem of embedding one finite metric into another with minimum distortion. This problem is equivalent to optimally embedding one weighted graph into another under the shortest path metric. We show that unless

P

=

NP

, the minimum distortion of embedding one such graph into another cannot be efficiently approximated within a factor less than 9/4 even when the two graphs are unweighted trees. For weighted trees with the ratio of maximum edge weight to the minimum edge weight of

α

2

(

α

≥ 1) and all but one node of constant degree, we improve this factor to 1+

α

. We also obtain similar hardness results for extremely simple line graphs (weighted). This improves and complements recent results of Kenyon et al.[13] and Papadimitriou and Safra [18].

We prove new lower bounds for

locally decodable codes

and

private information retrieval

. We show that a 2-query LDC encoding

n

-bit strings over an ℓ-bit alphabet, where the decoder only uses

b

bits of each queried position, needs code length

$m=exp\left(\Omega\left(\frac{n}{2^{b}{\sum_{i=0}^{b}}(^{l}_{i})}\right)\right)$

Similarly, a 2-server PIR scheme with an

n

-bit database and

t

-bit queries, where the user only needs

b

bits from each of the two ℓ-bit answers, unknown to the servers, satisfies

$t=\Omega \left(\frac{n}{2^{b}\sum_{i=0}^{b}(^{l}_{i})}\right)$

This implies that several known PIR schemes are close to optimal. Our results generalize those of Goldreich et al. [8], who proved roughly the same bounds for

linear

LDCs and PIRs. Like earlier work by Kerenidis and de Wolf [12], our classical bounds are proved using quantum computational techniques. In particular, we give a tight analysis of how well a 2-input function can be computed from a quantum superposition of both inputs.

A class of relational structures is said to have the extension preservation property if every first-order sentence that is preserved under extensions on the class is equivalent to an existential sentence. The class of all finite structures does not have the extension preservation property. We study the property on classes of finite structures that are better behaved. We show that the property holds of classes of acyclic structures, structures of bounded degree and more generally structures that are

wide

in a sense we make precise. We also show that the preservation property holds for the class of structures of treewidth at most

k

, for any

k

. In contrast, we show that the property fails for the class of planar graphs.

We show that the problem of checking if an infinite tree generated by a higher-order grammar of level 2 (hyperalgebraic) satisfies a given

μ

-calculus formula (or, equivalently, if it is accepted by an alternating parity automaton) is decidable, actually 2-

Exptime

-complete. Consequently, the monadic second-order theory of any hyperalgebraic tree is decidable, so that the safety restriction can be removed from our previous decidability result. The last result has been independently obtained by Aehlig, de Miranda and Ong. Our proof goes

via

a characterization of possibly unsafe second-order grammars by a new variant of higher-order pushdown automata, which we call

panic automata

. In addition to the standard

pop

1

and

pop

2

operations, these automata have an option of a destructive move called

panic

. The model-checking problem is then reduced to the problem of deciding the winner in a parity game over a suitable 2nd order pushdown system.

We introduce a new model of membrane computing system (or P system), called signaling P system. It turns out that signaling systems are a form of P systems with promoters that have been studied earlier in the literature. However, unlike non-cooperative P systems with promoters, which are known to be universal, non-cooperative signaling systems have decidable reachability properties. Our focus in this paper is on verification problems of signaling systems; i.e., algorithmic solutions to a verification query on whether a given signaling system satisfies some desired behavioral property. Such solutions not only help us understand the power of “maximal parallelism” in P systems but also would provide a way to validate a (signaling) P system in vitro through digital computers when the P system is intended to simulate living cells. We present decidable and undecidable properties of the model of non-cooperative signaling systems using proof techniques that we believe are new in the P system area. For the positive results, we use a form of “upper-closed sets” to serve as a symbolic representation for configuration sets of the system, and prove decidable symbolic model-checking properties about them using backward reachability analysis. For the negative results, we use a reduction via the undecidability of Hilbert’s Tenth Problem. This is in contrast to previous proofs of universality in P systems where almost always the reduction is via matrix grammar with appearance checking or through Minsky’s two-counter machines. Here, we employ a new tool using Diophantine equations, which facilitates elegant proofs of the undecidable results. With multiplication being easily implemented under maximal parallelism, we feel that our new technique is of interest in its own right and might find additional applications in P systems.