Automata, Languages, and Programming

We consider the development of computational models for systems involving social networks and large human audiences. In particular, we focus on the spread of information and behavior through such systems, and the ways in which these processes are affected by the underlying network structure.

We revisit classical online makespan minimization which has been studied since the 1960s. In this problem a sequence of jobs has to be scheduled on

m

identical machines so as to minimize the makespan of the constructed schedule. Recent research has focused on settings in which an online algorithm is given extra information or power while processing a job sequence. In this paper we review the various models of resource augmentation and survey important results.

Traditional formal methods are based on a Boolean satisfaction notion: a reactive system satisfies, or not, a given specification. We generalize formal methods to also address the

quality

of systems. As an adequate specification formalism we introduce the linear temporal logic LTL[

${\cal F}$

]. The satisfaction value of an LTL[

${\cal F}$

] formula is a number between 0 and 1, describing the quality of the satisfaction. The logic generalizes traditional LTL by augmenting it with a (parameterized) set

${\cal F}$

of arbitrary functions over the interval [0,1]. For example,

${\cal F}$

may contain the maximum or minimum between the satisfaction values of subformulas, their product, and their average.

The classical decision problems in formal methods, such as satisfiability, model checking, and synthesis, are generalized to search and optimization problems in the quantitative setting. For example, model checking asks for the quality in which a specification is satisfied, and synthesis returns a system satisfying the specification with the highest quality. Reasoning about quality gives rise to other natural questions, like the distance between specifications. We formalize these basic questions and study them for LTL[

${\cal F}$

]. By extending the automata-theoretic approach for LTL to a setting that takes quality into an account, we are able to solve the above problems and show that reasoning about LTL[

${\cal F}$

] has roughly the same complexity as reasoning about traditional LTL.

Most of the classical NP-hard problems remain NP-hard when restricted to planar graphs, and only exponential-time algorithms are known for the exact solution of these planar problems. However, in many cases, the exponential-time algorithms on planar graphs are significantly faster than the algorithms for general graphs: for example,

3-Coloring

can be solved in time

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

in an

n

-vertex planar graph, whereas only 2

O

(

n

)

-time algorithms are known for general graphs. For various planar problems, we often see a square root appearing in the running time of the best algorithms, e.g., the running time is often of the form

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

,

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

, or

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

. By now, we have a good understanding of why this square root appears. On the algorithmic side, most of these algorithms rely on the notion of treewidth and its relation to grid minors in planar graphs (but sometimes this connection is not obvious and takes some work to exploit). On the lower bound side, under a complexity assumption called Exponential Time Hypothesis (ETH), we can show that these algorithms are essentially best possible, and therefore the square root has to appear in the running time.

Random graphs, introduced by P. Erdős and A. Rényi in 1959, still attract a huge amount of research in the communities of Theoretical Computer Science, Algorithms, Graph Theory, Discrete Mathematics and Statistical Physics. This continuing interest is due to the fact that, besides their mathematical beauty, such graphs are very important, since they can model interactions and faults in networks and also serve as typical inputs for an average case analysis of algorithms. The modeling effort concerning random graphs has to show a plethora of random graph models; some of them have quite elaborate definitions and are quite general, in the sense that they can simulate many other known distributions on graphs by carefully tuning their parameters.

Traditionally, combinatorial optimization postulates that an input instance is given with absolute precision and certainty, and it aims at finding an optimum solution for the given instance. In contrast, real world input data are often uncertain, noisy, inaccurate. As a consequence, an optimum solution for a real world instance may not be meaningful or desired. While this unfortunate gap between theory and reality has been recognized for quite some time, it is far from understood, let alone resolved. We advocate to devote more attention to it, in order to develop algorithms that find meaningful solutions for uncertain inputs. We propose an approach towards this goal, and we show that this approach on the one hand creates a wealth of algorithmic problems, while on the other hand it appears to lead to good real world solutions.

This talk is about joint work with Joachim Buhmann, Matus Mihalak, and Rasto Sramek.

Additive Cost Register Automata (ACRA) map strings to integers using a finite set of registers that are updated using assignments of the form “

x

: = 

y

 + 

c

” at every step. The corresponding class of

additive regular functions

has multiple equivalent characterizations, appealing closure properties, and a decidable equivalence problem. In this paper, we solve two decision problems for this model. First, we define the

register complexity

of an additive regular function to be the minimum number of registers that an ACRA needs to compute it. We characterize the register complexity by a necessary and sufficient condition regarding the largest subset of registers whose values can be made far apart from one another. We then use this condition to design a

pspace

algorithm to compute the register complexity of a given ACRA, and establish a matching lower bound. Our results also lead to a machine-independent characterization of the register complexity of additive regular functions. Second, we consider

two-player games over ACRAs

, where the objective of one of the players is to reach a target set while minimizing the cost. We show the corresponding decision problem to be

exptime

-complete when the costs are non-negative integers, but undecidable when the costs are integers.

f

-divergences form a class of measures of distance between probability distributions; they are widely used in areas such as information theory and signal processing. In this paper, we unveil a new connection between

f

-divergences and differential privacy, a confidentiality policy that provides strong privacy guarantees for private data-mining; specifically, we observe that the notion of

α

-distance used to characterize approximate differential privacy is an instance of the family of

f

-divergences. Building on this observation, we generalize to arbitrary

f

-divergences the sequential composition theorem of differential privacy. Then, we propose a relational program logic to prove upper bounds for the

f

-divergence between two probabilistic programs. Our results allow us to revisit the foundations of differential privacy under a new light, and to pave the way for applications that use different instances of

f

-divergences.

Several ways of assigning probabilities to runs of timed automata (TA) have been proposed recently. When only the TA is given, a relevant question is to design a probability distribution which represents in the best possible way the runs of the TA. This question does not seem to have been studied yet. We give an answer to it using a maximal entropy approach. We introduce our variant of stochastic model, the stochastic process over runs which permits to simulate random runs of any given length with a linear number of atomic operations. We adapt the notion of Shannon (continuous) entropy to such processes. Our main contribution is an explicit formula defining a process

Y

*

which maximizes the entropy. This formula is an adaptation of the so-called Shannon-Parry measure to the timed automata setting. The process

Y

*

has the nice property to be ergodic. As a consequence it has the asymptotic equipartition property and thus the random sampling w.r.t.

Y

*

is quasi uniform.

Verification of properties expressed in the two-variable fragment of first-order logic FO

2

has been investigated in a number of contexts. The satisfiability problem for FO

2

over arbitrary structures is known to be

NEXPTIME

-complete, with satisfiable formulas having exponential-sized models. Over words, where FO

2

is known to have the same expressiveness as unary temporal logic, satisfiability is again

NEXPTIME

-complete. Over finite labelled ordered trees FO

2

has the same expressiveness as navigational XPath, a popular query language for XML documents. Prior work on XPath and FO

2

gives a

2EXPTIME

bound for satisfiability of FO

2

over trees. This work contains a comprehensive analysis of the complexity of FO

2

on trees, and on the size and depth of models. We show that the exact complexity varies according to the vocabulary used, the presence or absence of a schema, and the encoding of labels on trees. We also look at a natural restriction of FO

2

, its guarded version, GF

2

. Our results depend on an analysis of types in models of FO

2

formulas, including techniques for controlling the number of distinct subtrees, the depth, and the size of a witness to satisfiability for FO

2

sentences over finite trees.

Choices made by nondeterministic word automata depend on both the past (the prefix of the word read so far) and the future (the suffix yet to be read). In several applications, most notably synthesis, the future is diverse or unknown, leading to algorithms that are based on deterministic automata. Hoping to retain some of the advantages of nondeterministic automata, researchers have studied restricted classes of nondeterministic automata. Three such classes are nondeterministic automata that are

good for trees

(GFT; i.e., ones that can be expanded to tree automata accepting the derived tree languages, thus whose choices should satisfy diverse futures),

good for games

(GFG; i.e., ones whose choices depend only on the past), and

determinizable by pruning

(DBP; i.e., ones that embody equivalent deterministic automata). The theoretical properties and relative merits of the different classes are still open, having vagueness on whether they really differ from deterministic automata. In particular, while DBP ⊆ GFG ⊆ GFT, it is not known whether every GFT automaton is GFG and whether every GFG automaton is DBP. Also open is the possible succinctness of GFG and GFT automata compared to deterministic automata. We study these problems for

ω

-regular automata with all common acceptance conditions. We show that GFT=GFG⊃DBP, and describe a determinization construction for GFG automata.

In epistemic logic, dynamic operators describe the evolution of the knowledge of participating agents through communication, one of the most basic forms of communication being public announcement. Semantically, dynamic operators correspond to transformations of the underlying model. While metatheoretic results on dynamic epistemic logic so far are largely limited to the setting of Kripke models, there is evident interest in extending its scope to non-relational modalities capturing, e.g., uncertainty or collaboration. We develop a generic framework for non-relational dynamic logic by adding dynamic operators to coalgebraic logic. We discuss a range of examples and establish basic results including bisimulation invariance, complexity, and a small model property.

In this paper we introduce and study a new property of infinite words which is invariant under the action of a morphism: We say an infinite word

$x\in \mathbb{A}^{\mathbb N},$

defined over a finite alphabet

$\mathbb{A}$

, is self-shuffling if

x

admits factorizations:

$x=\prod_{i=1}^\infty U_iV_i=\prod_{i=1}^\infty U_i=\prod_{i=1}^\infty V_i$

with

$U_i,V_i \in \mathbb{A}^+.$

In other words, there exists a shuffle of

x

with itself which reproduces

x

. The morphic image of any self-shuffling word is again self-shuffling. We prove that many important and well studied words are self-shuffling: This includes the Thue-Morse word and all Sturmian words (except those of the form

aC

where

a

 ∈ {0,1} and

C

is a characteristic Sturmian word). We further establish a number of necessary conditions for a word to be self-shuffling, and show that certain other important words (including the paper-folding word and infinite Lyndon words) are not self-shuffling. In addition to its morphic invariance, which can be used to show that one word is not the morphic image of another, this new notion has other unexpected applications: For instance, as a consequence of our characterization of self-shuffling Sturmian words, we recover a number theoretic result, originally due to Yasutomi, which characterizes pure morphic Sturmian words in the orbit of the characteristic.

We study the complexity of model checking in quantified conjunctive logic, that is, the fragment of first-order logic where both quantifiers may be used, but conjunction is the only permitted connective. In particular, we study block-sorted queries, which we define to be prenex sentences in multi-sorted relational first-order logic where two variables having the same sort must appear in the same quantifier block. We establish a complexity classification theorem that describes precisely the sets of block-sorted queries of bounded arity on which model checking is fixed-parameter tractable. This theorem strictly generalizes, for the first time, the corresponding classification for existential conjunctive logic (which is known and due to Grohe) to a logic in which both quantifiers are present.

Formal methods have been very successful in analyzing security protocols for reachability properties such as secrecy or authentication. In contrast, there are very few results for equivalence-based properties, crucial for studying e.g. privacy-like properties such as anonymity or vote secrecy.

We study the problem of checking equivalence of security protocols for an unbounded number of sessions. Since replication leads very quickly to undecidability (even in the simple case of secrecy), we focus on a limited fragment of protocols (standard primitives but pairs, one variable per protocol’s rules) for which the secrecy preservation problem is known to be decidable. Surprisingly, this fragment turns out to be undecidable for equivalence. Then, restricting our attention to deterministic protocols, we propose the first decidability result for checking equivalence of protocols for an unbounded number of sessions. This result is obtained through a characterization of equivalence of protocols in terms of equality of languages of (generalized, real-time) deterministic pushdown automata.

When can two regular word languages

K

and

L

be separated by a simple language? We investigate this question and consider separation by piecewise- and suffix-testable languages and variants thereof. We give characterizations of when two languages can be separated and present an overview of when these problems can be decided in polynomial time if

K

and

L

are given by nondeterministic automata.

Among the approximation methods for the verification of counter systems, one of them consists in model-checking their flat unfoldings. Unfortunately, the complexity characterization of model-checking problems for such operational models is not always well studied except for reachability queries or for Past LTL. In this paper, we characterize the complexity of model-checking problems on flat counter systems for the specification languages including first-order logic, linear mu-calculus, infinite automata, and related formalisms. Our results span different complexity classes (mainly from PT

ime

to PS

pace

) and they apply to languages in which arithmetical constraints on counter values are systematically allowed. As far as the proof techniques are concerned, we provide a uniform approach that focuses on the main issues.

Multiparty session types are a type system that can ensure the safety and liveness of distributed peers via the global specification of their interactions. To construct a global specification from a set of distributed uncontrolled behaviours, this paper explores the problem of fully characterising multiparty session types in terms of communicating automata. We equip global and local session types with labelled transition systems (LTSs) that faithfully represent asynchronous communications through unbounded buffered channels. Using the equivalence between the two LTSs, we identify a class of communicating automata that exactly correspond to the projected local types. We exhibit an algorithm to synthesise a global type from a collection of communicating automata. The key property of our findings is the notion of

multiparty compatibility

which non-trivially extends the duality condition for binary session types.

Components are traditionally modeled as black-boxes equipped with interfaces that indicate provided/required ports and, often, also conflicts with other components that cannot coexist with them. In modern tools for automatic system management, components become

grey

-boxes that show relevant internal states and the possible actions that can be acted on the components to change such state during the deployment and reconfiguration phases. However, state-of-the-art tools in this field do not support a systematic management of conflicts. In this paper we investigate the impact of conflicts by precisely characterizing the increment of complexity on the reconfiguration problem.

We study the problem of computing the probability that a given stochastic context-free grammar (SCFG),

G

, generates a string in a given regular language

L

(

D

) (given by a DFA,

D

). This basic problem has a number of applications in statistical natural language processing, and it is also a key necessary step towards quantitative

ω

-regular model checking of stochastic context-free processes (equivalently, 1-exit recursive Markov chains, or stateless probabilistic pushdown processes).

We show that the probability that

G

generates a string in

L

(

D

) can be computed to within arbitrary desired precision in polynomial time (in the standard Turing model of computation), under a rather mild assumption about the SCFG,

G

, and with no extra assumption about

D

. We show that this assumption is satisfied for SCFG’s whose rule probabilities are learned via the well-known inside-outside (EM) algorithm for maximum-likelihood estimation (a standard method for constructing SCFGs in statistical NLP and biological sequence analysis). Thus, for these SCFGs the algorithm always runs in P-time.

Haase, Ouaknine, and Worrell have shown that reachability in two-clock timed automata is log-space equivalent to reachability in bounded one-counter automata. We show that reachability in bounded one-counter automata is PSPACE-complete.

Checking whether one formal language is included in another is vital to many verification tasks. In this paper, we provide solutions for checking the inclusion of the languages given by visibly pushdown automata over both finite and infinite words. Visibly pushdown automata are a richer automaton model than the classical finite-state automata, which allows one, e.g., to reason about the nesting of procedure calls in the executions of recursive imperative programs. The highlight of our solutions is that they do not comprise automata constructions for determinization and complementation. Instead, our solutions are more direct and generalize the so-called Ramsey-based inclusion-checking algorithms, which apply to classical finite-state automata and proved effective there, to visibly pushdown automata. We also experimentally evaluate our algorithms thereby demonstrating the virtues of avoiding determinization and complementation constructions.

The decidability of weak bisimilarity on normed BPA is a long standing open problem. It is proved in this paper that branching bisimilarity, a standard refinement of weak bisimilarity, is decidable for normed BPA and that the associated regularity problem is also decidable.

We study the computational complexity of the FO model checking problem on interval graphs, i.e., intersection graphs of intervals on the real line. The main positive result is that this problem can be solved in time

O

(

n

log

n

) for

n

-vertex interval graphs with representations containing only intervals with lengths from a prescribed finite set. We complement this result by showing that the same is not true if the lengths are restricted to any set that is dense in some open subset, e.g., in the set (1, 1 + 

ε

).

When studying games played on finite arenas, the arena is given explicitly, hiding the underlying structure of the arena. We study games where the global arena is a product of several smaller, constituent arenas. We investigate how these “global games” can be solved by playing “component games” on the constituent arenas. To this end, we introduce two kinds of products of arenas. Moreover, we define a suitable notion of strategy composition and show how, for the first notion of product, winning strategies in reachability games can be composed from winning strategies in games on the constituent arenas. For the second kind of product, the complexity of solving the global game shows that a general composition theorem is equivalent to proving P

space

= E

xptime

.

We consider the distributed control problem in the setting of Zielonka asynchronous automata. Such automata are compositions of finite processes communicating via shared actions and evolving asynchronously. Most importantly, processes participating in a shared action can exchange complete information about their causal past. This gives more power to controllers, and avoids simple pathological undecidable cases as in the setting of Pnueli and Rosner. We show the decidability of the control problem for Zielonka automata over acyclic communication architectures. We provide also a matching lower bound, which is

l

-fold exponential,

l

being the height of the architecture tree.

We study the problem of answering a union of Boolean conjunctive queries

q

against a database Δ, and a logical theory

ϕ

which falls in the guarded fragment with transitive guards (GF + TG). We trace the frontier between decidability and undecidability of the problem under consideration. Surprisingly, we show that query answering under GF

2

+ TG, i.e., the two-variable fragment of GF + TG, is already undecidable (even without equality), whereas its monadic fragment is decidable; in fact, it is 2

exptime

-complete in combined complexity and coNP-complete in data complexity. We also show that for a restricted class of queries, query answering under GF+TG is decidable.

Although theories of equivalence or subtyping for recursive types have been extensively investigated, sophisticated interaction between recursive types and abstract types has gained little attention. The key idea behind type theories for recursive types is to use syntactic contractiveness, meaning every

μ

-bound variable occurs only under a type constructor such as → or ∗. This syntactic contractiveness guarantees the existence of the unique solution of recursive equations and thus has been considered necessary for designing a sound theory for recursive types. However, in an advanced type system, such as OCaml, with recursive types, type parameters, and abstract types, we cannot easily define the syntactic contractiveness of types. In this paper, we investigate a sound type system for recursive types, type parameters, and abstract types. In particular, we develop a new semantic notion of contractiveness for types and signatures using mixed induction and coinduction, and show that our type system is sound with respect to the standard call-by-value operational semantics, which eliminates signature sealings. Moreover we show that while non-contractive types in signatures lead to unsoundness of the type system, they may be allowed in modules. We have also formalized the whole system and its type soundness proof in Coq.

In this paper, we study the languages of labeled finite birooted trees: Munn’s birooted trees extended with vertex labeling. We define a notion of finite state birooted tree automata that is shown to capture the class of languages that are upward closed w.r.t. the natural order and definable in Monadic Second Order Logic. Then, relying on the inverse monoid structure of labeled birooted trees, we derive a notion of recognizable languages by means of (adequate) premorphisms into finite (adequately) ordered monoids. This notion is shown to capture finite boolean combinations of languages as above. We also provide a simple encoding of finite (mono-rooted) labeled trees in an antichain of labeled birooted trees that shows that classical regular languages of finite (mono-rooted) trees are also recognized by such premorphisms and finite ordered monoids.

In this paper we consider word equations with one variable (and arbitrary many appearances of it). A recent technique of recompression, which is applicable to general word equations, is shown to be suitable also in this case. While in general case it is non-deterministic, it determinises in case of one variable and the obtained running time is

$\mathcal{O}(n)$

(in RAM model).

We study languages of

λ

-terms generated by IO and OI unsafe grammars. These languages can be used to model meaning representations in the formal semantics of natural languages following the tradition of Montague [19]. Using techniques pertaining to the denotational semantics of the simply typed

λ

-calculus, we show that the emptiness and membership problems for both types of grammars are decidable. In the course of the proof of the decidability results for OI, we identify a decidable variant of the

λ

-definability problem, and prove a stronger form of Statman’s finite completeness Theorem [28].

Dynamic data-structures are ubiquitous in programming, and they use extensively underlying directed multi-graph structures, such as labeled trees, DAGs, and objects. This paper adapts well-established static analysis methods, namely data ramification and language-based information flow security, to programs over such graph structures. Our programs support the creation, deletion, and updates of both vertices and edges, and are related to pointer machines. The main result states that a function over graph-structures is computable in polynomial time if it is computed by a terminating program whose graph manipulation is ramified, provided all edges that are both created and read in a loop have the same label.

It is shown that membership in rational subsets of wreath products

H

 ≀ 

V

with

H

a finite group and

V

a virtually free group is decidable. On the other hand, it is shown that there exists a fixed finitely generated submonoid in the wreath product ℤ ≀ ℤ with an undecidable membership problem.

Fair subtyping is a liveness-preserving refinement relation for session types akin to (but coarser than) the well-known should-testing precongruence. The behavioral characterization of fair subtyping is challenging essentially because fair subtyping is context-sensitive: two session types may or may not be related depending on the context in which they occur, hence the traditional coinductive argument for dealing with recursive types is unsound in general. In this paper we develop complete behavioral and axiomatic characterizations of fair subtyping and we give a polynomial algorithm to decide it.

Monadic effect systems provide a unified way of tracking effects of computations, but there is no unified mechanism for tracking how computations rely on the environment in which they are executed. This is becoming an important problem for modern software – we need to track where distributed computations run, which resources a program uses and how they use other capabilities of the environment.

We consider three examples of context-dependence analysis:

liveness

analysis, tracking the use of

implicit parameters

(similar to tracking of

resource usage

in distributed computation), and calculating caching requirements for

dataflow

programs. Informed by these cases, we present a unified calculus for tracking context dependence in functional languages together with a categorical semantics based on

indexed comonads

. We believe that indexed comonads are the right foundation for constructing context-aware languages and type systems and that following an approach akin to monads can lead to a widespread use of the concept.

This paper concerns retracts in simply typed lambda calculus assuming

βη

-equality. We provide a simple tableau proof system which characterises when a type is a retract of another type and which leads to an exponential decision procedure.

A Presburger formula is a Boolean formula with variables in ℕ that can be written using addition, comparison (≤, =, etc.), Boolean operations (and, or, not), and quantifiers (∀ and ∃). We characterize sets that can be defined by a Presburger formula as exactly the sets whose characteristic functions can be represented by rational generating functions; a geometric characterization of such sets is also given. In addition, if

p

 = (

p

1

,…,

p

n

) are a subset of the free variables in a Presburger formula, we can define a counting function

g

(

p

) to be the number of solutions to the formula, for a given

p

. We show that every counting function obtained in this way may be represented as, equivalently, either a piecewise quasi-polynomial or a rational generating function. In the full version of this paper, we also translate known computational complexity results into this setting and discuss open directions.

The decidability of determining equivalence of deterministic multitape automata (or transducers) was a longstanding open problem until it was resolved by Harju and Karhumäki in the early 1990s. Their proof of decidability yields a

co-NP

upper bound, but apparently not much more is known about the complexity of the problem. In this paper we give an alternative proof of decidability, which follows the basic strategy of Harju and Karhumäki but replaces their use of group theory with results on matrix algebras. From our proof we obtain a simple randomised algorithm for deciding equivalence of deterministic multitape automata, as well as automata with transition weights in the field of rational numbers. The algorithm involves only matrix exponentiation and runs in polynomial time for each fixed number of tapes. If the two input automata are inequivalent then the algorithm outputs a word on which they differ.

We consider the computational power of silent transitions in one-way automata with storage. Specifically, we ask which storage mechanisms admit a transformation of a given automaton into one that accepts the same language and reads at least one input symbol in each step. We study this question using the model of valence automata. Here, a finite automaton is equipped with a storage mechanism that is given by a monoid. This work presents generalizations of known results on silent transitions. For two classes of monoids, it provides characterizations of those monoids that allow the removal of silent transitions. Both classes are defined by graph products of copies of the bicyclic monoid and the group of integers. The first class contains pushdown storages as well as the blind counters while the second class contains the blind and the partially blind counters.

We study

storyboarding

where advertisers wish to present sequences of ads (stories) uninterruptedly on a major ad position of a web page. These jobs/stories arrive online and are triggered by the browsing history of a user who at any time continues surfing with probability

β

. The goal of an ad server is to construct a schedule maximizing the expected reward. The problem was introduced by Dasgupta, Ghosh, Nazerzadeh and Raghavan (SODA’09) who presented a 7-competitive online algorithm. They also showed that no deterministic online strategy can achieve a competitiveness smaller than 2, for general

β

.

We present improved algorithms for storyboarding. First we give a simple online strategy that achieves a competitive ratio of 4/(2 − 

β

), which is upper bounded by 4 for any

β

. The algorithm is also 1/(1 − 

β

)-competitive, which gives better bounds for small

β

. As the main result of this paper we devise a refined algorithm that attains a competitive ratio of

c

 = 1 + 

φ

, where

$\phi=(1+\sqrt{5})/2$

is the Golden Ratio. This performance guarantee of

c

 ≈ 2.618 is close to the lower bound of 2. Additionally, we study for the first time a problem extension where stories may be presented simultaneously on several ad positions of a web page. For this parallel setting we provide an algorithm whose competitive ratio is upper bounded by

$1/(3-2\sqrt{2})\approx 5.828$

, for any

β

. All our algorithms work in phases and have to make scheduling decisions only every once in a while.

A key building block for collaborative filtering recommender systems is finding users with similar consumption patterns. Given access to the full data regarding the items consumed by each user, one can directly compute the similarity between any two users. However, for massive recommender systems such a naive approach requires a high running time and may be intractable in terms of the space required to store the full data. One way to overcome this is using sketching, a technique that represents massive datasets concisely, while still allowing calculating properties of these datasets. Sketching methods maintain very short fingerprints of the item sets of users, which allow approximately computing the similarity between sets of different users.

The state of the art sketch [22] has a very low space complexity, and a recent technique [14] shows how to exponentially speed up the computation time involved in building the fingerprints. Unfortunately, these methods are incompatible, forcing a choice between low running time or a small sketch size. We propose an alternative sketching approach, which achieves both a low space complexity similar to that of [22] and a low time complexity similar to [14]. We empirically evaluate our algorithm using the Netflix dataset. We analyze the running time and the sketch size of our approach and compare them to alternatives. Further, we show that in practice the accuracy achieved by our approach is even better than the accuracy guaranteed by the theoretical bounds, so it suffices to use even shorter fingerprints to obtain high quality results.

Physarum polycephalum

is a slime mold that is apparently able to solve shortest path problems. A mathematical model for the slime’s behavior in the form of a coupled system of differential equations was proposed by Tero, Kobayashi and Nakagaki [TKN07]. We prove that a discretization of the model (Euler integration) computes a (1 + 

ε

)-approximation of the shortest path in

O

(

m

L

(log

n

 + log

L

)/

ε

3

) iterations, with arithmetic on numbers of

O

(log(

nL

/

ε

)) bits; here,

n

and

m

are the number of nodes and edges of the graph, respectively, and

L

is the largest length of an edge. We also obtain two results for a directed Physarum model proposed by Ito et al. [IJNT11]: convergence in the general, nonuniform case and convergence and complexity bounds for the discretization of the uniform case.

A prevalent assumption in traditional mechanism design is that buyers know their precise value for an item; however, this assumption is rarely true in practice. In most settings, buyers can “deliberate”, i.e., spend money or time, in order improve their estimate of an item’s value. It is known that the deliberative setting is fundamentally different than the classical one, and desirable properties of a mechanism such as equilibria, revenue maximization, or truthfulness, may no longer hold.

In this paper we introduce a new general deliberative model in which users have independent private values that are a-priori unknown, but can be learned. We consider the design of dominant-strategy revenue-optimal auctions in this setting. Surprisingly, for a wide class of environments, we show the optimal revenue is attained with a sequential posted price mechanism (SPP). While this result is not constructive, we show how to construct approximately optimal SPPs in polynomial time. We also consider the design of Bayes-Nash incentive compatible auctions for a simple deliberative model.

The Price of Anarchy in congestion games has attracted a lot of research over the last decade. This resulted in a thorough understanding of this concept. In contrast the Price of Stability, which is an equally interesting concept, is much less understood.

In this paper, we consider congestion games with polynomial cost functions with nonnegative coefficients and maximum degree

d

. We give matching bounds for the Price of Stability in such games, i.e., our technique provides the exact value for any degree

d

.

For linear congestion games, tight bounds were previously known. Those bounds hold even for the more restricted case of dominant equilibria, which may not exist. We give a separation result showing that already for congestion games with quadratic cost functions this is not possible; that is, the Price of Anarchy for the subclass of games that admit a dominant strategy equilibrium is strictly smaller than the Price of Stability for the general class.

We study the

localization problem

in the ring: a collection of

n

anonymous mobile robots are deployed in a continuous ring of perimeter one. All robots start moving at the same time along the ring with arbitrary velocity, starting in clockwise or counterclockwise direction around the ring. The robots bounce against each other when they meet. The task of each robot is to find out, in finite time, the initial position and the initial velocity of every deployed robot. The only way that robots perceive the information about the environment is by colliding with their neighbors; any type of communication among robots is not possible.

We assume the principle of momentum conservation as well as the conservation of energy, so robots exchange velocities when they collide. The capabilities of each robot are limited to: observing the times of its collisions, being aware of its velocity at any time, and processing the collected information. Robots have no control of their walks or velocities. Robots’ walks depend on their initial positions, velocities, and the sequence of collisions. They are not equipped with any visibility mechanism.

The localization problem for bouncing robots has been studied previously in [1,2] in which robots are assumed to move at the same velocity. The configuration of initial positions of robots and their speeds is considered

feasible

, if there is a finite time, after which every robot starting at this configuration knows initial positions and velocities of all other robots. Authors of [1] conjectured that if robots have arbitrary velocities, the problem might be solvable, if the momentum conservation and energy preservation principles are assumed.

In this paper we prove that the conjecture in [1] is false. We show that the feasibility of any configuration and the required time for solving it under such stronger constraints depend only on the collection of velocities of the robots. More specifically, if

v

0

,

v

1

,…,

v

n

 − 1

are the velocities of a given robot configuration

$\mathcal{S}$

, we prove that

$\mathcal{S}$

is feasible if and only if

$v_i\neq \bar{v}$

for all 0 ≤ 

i

 ≤ 

n

 − 1, where

$\bar{v} = \frac{v_0+\ldots+v_{n-1}}{n}$

. To figure out the initial positions of all robots no more than

$\frac{2}{min_{0\leq i\leq n-1} |v_i-\bar{v}|}$

time is required.

We study the following scenario of online graph exploration. A team of

k

agents is initially located at a distinguished vertex

r

of an undirected graph. At every time step, each agent can traverse an edge of the graph. All vertices have unique identifiers, and upon entering a vertex, an agent obtains the list of identifiers of all its neighbors. We ask how many time steps are required to complete exploration, i.e., to make sure that every vertex has been visited by some agent.

We consider two communication models: one in which all agents have global knowledge of the state of the exploration, and one in which agents may only exchange information when simultaneously located at the same vertex. As our main result, we provide the first strategy which performs exploration of a graph with

n

vertices at a distance of at most

D

from

r

in time

O

(

D

), using a team of agents of polynomial size

k

 = 

D

n

1 + 

ε

 < 

n

2 + 

ε

, for any

ε

 > 0. Our strategy works in the local communication model, without knowledge of global parameters such as

n

or

D

.

We also obtain almost-tight bounds on the asymptotic relation between exploration time and team size, for large

k

. For any constant

c

 > 1, we show that in the global communication model, a team of

k

 = 

D

n

c

agents can always complete exploration in

$D(1+ \frac{1}{c-1} +o(1))$

time steps, whereas at least

$D(1+ \frac{1}{c} -o(1))$

steps are sometimes required. In the local communication model,

$D(1+ \frac{2}{c-1} +o(1))$

steps always suffice to complete exploration, and at least

$D(1+ \frac{2}{c} -o(1))$

steps are sometimes required. This shows a clear separation between the global and local communication models.

Two mobile agents with range of vision 1 start at arbitrary points in the plane and have to accomplish the task of

approach

, which consists in getting at distance at most one from each other, i.e., in getting within each other’s range of vision. An adversary chooses the initial positions of the agents, their possibly different starting times, and assigns a different positive integer label and a possibly different speed to each of them. Each agent is equipped with a compass showing the cardinal directions, with a measure of length and a clock. Each agent knows its label and speed but not those of the other agent and it does not know the initial position of the other agent relative to its own. Agents do not have any global system of coordinates and they cannot communicate. Our main result is a deterministic algorithm to accomplish the task of approach, working in time polynomial in the unknown initial distance between the agents, in the length of the smaller label and in the inverse of the larger speed. The distance travelled by each agent until approach is polynomial in the first two parameters and does not depend on the third. The problem of approach in the plane reduces to a network problem: that of rendezvous in an infinite grid.

In secure delegatable computation, computationally weak devices (or clients) wish to outsource their computation and data to an

untrusted

server in the cloud. While most earlier work considers the general question of how to securely outsource

any

computation to the cloud server, we focus on

concrete

and

important

functionalities and give the first protocol for the

pattern matching

problem in the cloud. Loosely speaking, this problem considers a text

T

that is outsourced to the cloud

S

by a client

C

T

. In a query phase, clients

C

1

, …,

C

l

run an efficient protocol with the server

S

and the client

C

T

in order to learn the positions at which a pattern of length

m

matches the text (and nothing beyond that). This is called the

outsourced pattern matching

problem and is highly motivated in the context of delegatable computing since it offers storage alternatives for massive databases that contain confidential data (e.g., health related data about patient history). Our constructions offer

simulation-based security

in the presence of semi-honest and malicious adversaries (in the random oracle model) and limit the communication in the query phase to

O

(

m

) bits plus the number of occurrences — which is optimal. In contrast to generic solutions for delegatable computation, our schemes do not rely on fully homomorphic encryption but instead uses novel ideas for solving pattern matching, based on efficiently solvable instances of the subset sum problem.

We consider the task of learning a ring in a distributed way: each node of an unknown ring has to construct a labeled map of it. Nodes are equipped with unique labels. Communication proceeds in synchronous rounds. In every round every node can send arbitrary messages to its neighbors and perform arbitrary local computations. We study tradeoffs between the time (number of rounds) and the cost (number of messages) of completing this task in a deterministic way: for a given time

T

we seek bounds on the smallest number of messages needed for learning the ring in time

T

. Our bounds depend on the diameter

D

of the ring and on the

delay

θ

 = 

T

 − 

D

above the least possible time

D

in which this task can be performed. We prove a lower bound Ω(

D

2

/

θ

) on the number of messages used by any algorithm with delay

θ

, and we design a class of algorithms that give an almost matching upper bound: for any positive constant 0 < 

ε

 < 1 there is an algorithm working with delay

θ

 ≤ 

D

and using

O

(

D

2

(log

*

D

)/

θ

1 − 

ε

) messages.

In digital goods auctions, the auctioneer sells an item in unlimited supply to a set of potential buyers. The objective is to design a truthful auction that maximizes the auctioneer’s total profit. Motivated by the observation that the buyers’ valuation of the good might be interconnected through a social network, we study digital goods auctions with positive externalities among buyers. This defines a multi-parameter auction design problem where the private valuation of every buyer is a function of the set of other winning buyers. The main contribution of this paper is a truthful competitive mechanism for subadditive valuations. Our competitive result is with respect to a new solution benchmark

$\mathcal{F}^{(3)}$

. On the other hand, we show a surprising impossibility result if comparing to the stronger benchmark

$\mathcal{F}^{(2)}$

, where the latter has been used quite successfully in digital goods auctions without externalities [16].

Basic graph structures such as maximal independent sets (MIS’s) have spurred much theoretical research in distributed algorithms, and have several applications in networking and distributed computing as well. However, the extant (distributed) algorithms for these problems do not necessarily guarantee fault-tolerance or load-balance properties: For example, in a star-graph, the central vertex, as well as the set of leaves, are both MIS’s, with the latter being much more fault-tolerant and balanced — existing distributed algorithms do not handle this distinction. We propose and study “low-average degree” or “balanced” versions of such structures. Interestingly, in sharp contrast to, say, MIS’s, it can be shown that checking whether a structure is balanced, will take substantial time. Nevertheless, we are able to develop good sequential and distributed algorithms for such “balanced” versions. We also complement our algorithms with several lower bounds.

Motivated by a strongly growing interest in graph anonymization in the data mining and databases communities, we study the NP-hard problem of making a graph

k

-anonymous by adding as few edges as possible. Herein, a graph is

k

-anonymous if for every vertex in the graph there are at least

k

 − 1 other vertices of the same degree. Our algorithmic results shed light on the performance quality of a popular heuristic due to Liu and Terzi [ACM SIGMOD 2008]; in particular, we show that the heuristic provides optimal solutions in case that many edges need to be added. Based on this, we develop a polynomial-time data reduction, yielding a polynomial-size problem kernel for the problem parameterized by the maximum vertex degree. This result is in a sense tight since we also show that the problem is already NP-hard for H-index three, implying NP-hardness for smaller parameters such as average degree and degeneracy.

We study the problem of maintaining a

breadth-first spanning tree

(BFS tree) in

partially dynamic

distributed networks modeling a sequence of either failures or additions of communication links (but not both). We show (1 + 

ε

)-approximation algorithms whose amortized time (over some number of link changes) is

sublinear

in

D

, the

maximum diameter

of the network. This breaks the Θ(

D

) time bound of recomputing “from scratch”.

Our technique also leads to a (1 + 

ε

)-approximate incremental algorithm for single-source shortest paths (SSSP) in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic

exact

algorithm of [9] that is optimal under some assumptions [27]. Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if a small approximation is allowed.

We study two-sided matching markets with locality of information and control. Each male (female) agent has an arbitrary strict preference list over all female (male) agents. In addition, each agent is a node in a fixed network. Agents learn about possible partners dynamically based on their current network neighborhood. We consider convergence of dynamics to locally stable matchings that are stable with respect to their imposed information structure in the network. While existence of such states is guaranteed, we show that reachability becomes

NP

-hard to decide. This holds even when the network exists only among one side. In contrast, if only one side has no network and agents remember a previous match every round, reachability is guaranteed and random dynamics converge with probability 1. We characterize this positive result in various ways. For instance, it holds for random memory and for memory with the most recent partner, but not for memory with the best partner. Also, it is crucial which partition of the agents has memory. Finally, we conclude with results on approximating maximum locally stable matchings.

Many futuristic technologies, such as Internet of Things or nano-communication, assume that a large number of simple devices of very limited energy and computational power will be able to communicate efficiently via wireless medium. Motivated by this, we study broadcasting in the model of ad-hoc wireless networks of weak devices with uniform transmission powers. We compare two settings: with and without local knowledge about immediate neighborhood. In the latter setting, we prove Ω(

n

log

n

)-round lower bound and develop an algorithm matching this formula. This result could be made more accurate with respect to network density, or more precisely, the maximum node degree Δ in the communication graph. If Δ is known to the nodes, it is possible to broadcast in

O

(

D

Δlog

2

n

) rounds, which is almost optimal in the class of networks parametrized by

D

and Δ due to the lower bound Ω(

D

Δ). In the setting with local knowledge, we design a scalable and almost optimal algorithm accomplishing broadcast in

O

(

D

log

2

n

) communication rounds, where

n

is the number of nodes and

D

is the eccentricity of a network. This can be improved to

O

(

D

log

g

) if network granularity

g

is known to the nodes. Our results imply that the cost of “local communication” is a dominating component in the complexity of wireless broadcasting by weak devices, unlike in traditional models with non-weak devices in which well-scalable solutions can be obtained even without local knowledge.

Secure multiparty computation (MPC) allows multiple parties to evaluate functions without disclosing the private inputs. Secure comparisons (testing equality and greater-than) are important primitives required by many MPC applications. We propose two equality tests for ℓ-bit values with

O

(1) online communication that require

O

(ℓ) respectively

O

(

κ

) total work, where

κ

is a correctness parameter.

Combining these with ideas of Toft [16], we obtain (i) a greater-than protocol with sublinear online complexity in the arithmetic black-box model (

O

(

c

) rounds and

O

(

c

·ℓ

1/

c

) work online, with

c

 = logℓ resulting in logarithmic online work). In difference to Toft, we do not assume two mutually incorruptible parties, but

O

(ℓ) offline work is required, and (ii) two greater-than protocols with the same online complexity as the above, but with overall complexity reduced to

O

(logℓ(

κ

 + loglogℓ)) and

O

(

c

·ℓ

1/

c

(

κ

 + logℓ)); these require two mutually incorruptible parties, but are highly competitive with respect to online complexity when compared to existing protocols.

In this work we consider

temporal networks

, i.e. networks defined by a

labeling

λ

assigning to each edge of an

underlying graph

G

a set of

discrete

time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at which the edge is available. We focus on

path problems

of temporal networks. In particular, we consider

time-respecting

paths, i.e. paths whose edges are assigned by

λ

a strictly increasing sequence of labels. We begin by giving two efficient algorithms for computing shortest time-respecting paths on a temporal network. We then prove that there is a

natural analogue of Menger’s theorem

holding for arbitrary temporal networks. Finally, we propose two

cost minimization parameters

for temporal network design. One is the

temporality

of

G

, in which the goal is to minimize the maximum number of labels of an edge, and the other is the

temporal cost

of

G

, in which the goal is to minimize the total number of labels used. Optimization of these parameters is performed subject to some

connectivity constraint

. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graph families such as rings, directed acyclic graphs, and trees.

This work extends what is known so far for a basic model of evolutionary antagonism in undirected networks (graphs). More specifically, this work studies the generalized Moran process, as introduced by Lieberman, Hauert, and Nowak [Nature, 433:312-316, 2005], where the individuals of a population reside on the vertices of an undirected connected graph. The initial population has a single

mutant

of a

fitness

value

r

(typically

r

 > 1), residing at some vertex

v

of the graph, while every other vertex is initially occupied by an individual of fitness 1. At every step of this process, an individual (i.e. vertex) is randomly chosen for reproduction with probability proportional to its fitness, and then it places a copy of itself on a random neighbor, thus replacing the individual that was residing there. The main quantity of interest is the

fixation probability

, i.e. the probability that eventually the whole graph is occupied by descendants of the mutant. In this work we concentrate on the fixation probability when the mutant is initially on a specific vertex

v

, thus refining the older notion of Lieberman et al. which studied the fixation probability when the initial mutant is placed at a random vertex. We then aim at finding graphs that have many “strong starts” (or many “weak starts”) for the mutant. Thus we introduce a parameterized notion of

selective amplifiers

(resp.

selective suppressors

) of evolution. We prove the existence of

strong

selective amplifiers (i.e. for

h

(

n

) = Θ(

n

) vertices

v

the fixation probability of

v

is at least

$1-\frac{c(r)}{n}$

for a function

c

(

r

) that depends only on

r

), and the existence of quite strong selective suppressors. Regarding the traditional notion of fixation probability from a random start, we provide strong upper and lower bounds: first we demonstrate the non-existence of “strong universal” amplifiers, and second we prove the

Thermal Theorem

which states that for any undirected graph, when the mutant starts at vertex

v

, the fixation probability at least

$(r-1) / (r+\frac{\deg v}{\deg_{\min}})$

. This theorem (which extends the “Isothermal Theorem” of Lieberman et al. for regular graphs) implies an almost tight lower bound for the usual notion of fixation probability. Our proof techniques are original and are based on new domination arguments which may be of general interest in Markov Processes that are of the general birth-death type.

Vertex coloring

is a central concept in graph theory and an important symmetry-breaking primitive in distributed computing. Whereas degree-Δ graphs may require palettes of Δ + 1 colors in the worst case, it is well known that the chromatic number of many natural graph classes can be much smaller. In this paper we give new distributed algorithms to find (Δ/

k

)-coloring in graphs of girth 4 (triangle-free graphs), girth 5, and trees, where

k

is at most

$(\frac{1}{4}-o(1))\ln\Delta$

in triangle-free graphs and at most (1 − 

o

(1))ln Δ in girth-5 graphs and trees, and

o

(1) is a function of Δ. Specifically, for Δ sufficiently large we can find such a coloring in

O

(

k

 + log

*

n

) time. Moreover, for

any

Δ we can compute such colorings in roughly logarithmic time for triangle-free and girth-5 graphs, and in

O

(logΔ + log

Δ

log

n

) time on trees. As a byproduct, our algorithm shows that the chromatic number of triangle-free graphs is at most

$(4+o(1))\frac{\Delta}{\ln\Delta}$

, which improves on Jamall’s recent bound of

$(67+o(1))\frac{\Delta}{\ln\Delta}$

. Also, we show that (Δ + 1)-coloring for triangle-free graphs can be obtained in sublogarithmic time for any Δ.