MFCS 2009 Home Page

MFCS 2009

34th International Symposium on
Mathematical Foundations of Computer Science

August 24 - 28, 2009

Giulio Manzonetto: A general class of models of H*

Abstract: We recently introduced an extensional model of the pure lambda-calculus living in a cartesian closed category of sets and relations. In this paper, we provide sufficient conditions for categorical models living in arbitrary cpo-enriched cartesian closed categories to have H, the maximal consistent sensible lambda-theory, as equational theory. Finally, we prove that our relational model fulfils these conditions.

Bakhadyr Khoussainov, Jiamou Liu and Imran Khaliq: A Dynamic Algorithm for Reachability Games Played on Trees

Abstract: Our goal is to start the investigation of the dynamic content of game determinacy when games are played on finite graphs. We are interested in the dynamic game determinacy problem formulated as follows. Find an algorithm for maintaining the graph of the game that undergoes a sequence of update and query operations in such a way that the algorithm facilitates an efficient solution of the current game. We provide an algorithm that solves the dynamic game determinacy problem when games are played on trees. We show that the amortized time complexity of our algorithm is of order O(log(n)), where n is the number of nodes on the current tree.

Diego Figueira and Luc Segoufin: Future-looking logics on data words and trees

Abstract: In a data word or a data tree each position carries a label from a finite alphabet and a data value from an infinite domain. These models have been considered in the realm of semistructured data, timed automata and extended temporal logics.

Over data words we consider the logic 1-reg-LTL(F), that extends LTL(F) with one register for storing data values for later comparisons. We show that satisfiability over data words of 1-reg-LTL(F) is already not primitive recursive. We also show that the extension of 1-reg-LTL(F) with either the reverse modality F^-1 or with one extra register is undecidable. All those lower bounds were already known for 1-reg-LTL(X,F) and our results essentially show that the X modality was not necessary.

Moreover we show that over data trees similar lower bounds hold for certain fragments of XPATH.

Pawel Gawrychowski and Artur Jez: Hyper-minimising and k-hyper-minimising the automaton in O (|δ| log n)

Abstract: We consider a problem of hyper-minimisation of an automaton \cite{Badr,BadrRAIRO}: given a DFA we want to compute a smallest automaton N such that the language L(M) \simdiff L(N) is finite, where \simdiff denotes the symmetric difference. We improve the previously known O (|Σ|n²) solution by giving an expected O (|δ|log n) time algorithm for this problem, where |δ| is the size of the (potentially partial) transition function. We also give a slightly slower deterministic O(|δ|log² n) version of the algorithm.

Then we introduce a similar problem of k-minimisation: for an automaton M we want to find a smallest automaton N such that L(M) \simdiff L(N) \subseteq Σ^{< k}, i.e. the languages they recognize differ only on words of length less than k. We characterise such minimal automata and give algorithm with a similar complexity for this problem.

Francisco Claude and Gonzalo Navarro: Indexing Straight-Line Programs

Abstract: Straight-line programs (SLPs) offer powerful text compression by representing a text T[1,u] in terms of a restricted context-free grammar of n rules, so that T can be recovered in O(u) time. However, the problem of operating the grammar in compressed form has not been studied much. We present a grammar representation whose size is of the same order of that of a plain SLP representation, and can answer other queries apart from expanding nonterminals. This can be of independent interest. We then extend it to achieve the first grammar representation able of extracting text substrings, and of searching the text for patterns, in time o(n). We also give byproducts on representing binary relations.

Petr Golovach and Pinar Heggernes: Choosability of P₅-free graphs

Abstract: A graph is k-choosable if it admits a proper coloring of its vertices for every assignment of k (possibly different) allowed colors to choose from for each vertex. It is NP-hard to decide whether a given graph is k-choosable for k ≥ 3, and this problem is considered strictly harder than the k-coloring problem. Only few positive results are known on input graphs with a given structure. Here, we prove that the problem is fixed parameter tractable on P₅-free graphs when parameterized by k. This graph class contains the well known and widely studied class of cographs. Our result is surprising since the parameterized complexity of k-coloring is still open on P₅-free graphs. To give a complete picture, we show that the problem remains NP-hard on P₅-free graphs when k is a part of the input.

Sagarmoy Dutta and Piyush P Kurur: Representing groups on graphs

Abstract: In this paper we formulate and study the problem of representing groups on graphs. We show that with respect to polynomial time turing reducibility, both abelian and solvable group representability are all equivalent to graph isomorphism, even when the group is presented as a permutation group via generators. On the other hand, the representability problem for general groups on trees is equivalent to checking, given a group G and n, whether a nontrivial homomorphism from G to S_n exists. There does not seem to be a polynomial time algorithm for this problem, in spite of the fact that tree isomorphism has polynomial time algorithm.

Arturo Carpi and Flavio D'Alessandro: The synchronization problem for locally strongly transitive automata

Abstract: The synchronization problem is investigated for a new class of deterministic automata called locally strongly transitive. An application to synchronizing colorings of aperiodic graphs with a cycle of prime length is also considered.

Rupert Hölzl, Thorsten Kräling and Wolfgang Merkle: Time-bounded Kolmogorov complexity and Solovay functions

Abstract: A Solovay function is a computable upper bound g for prefixfree Kolmogorov complexity K that is nontrivial in the sense that g agrees with K, up to some additive constant, on infinitely many places n. We obtain natural examples of Solovay functions by showing that for any computable superlinear time bound t, the time-bounded version K^t of K is a Solovay function. Letting Ω_g=∑ 2^-g(n), we obtain as a corollary that the Martin-Löf randomness of the various variants of Chaitin's Ω extends to the time-bounded case in so far as for any t as above, Ω_K^t is Martin-Löf random.

By generalizing results of Bienvenu and Downey and of Miller, we show that a right-computable upper bound g of K is a Solovay function if and only if Ω_g is Martin-Löf random.

The problem whether the class of K-trivial sets coincides with the class of sets that are g(n)-jump-traceable for all computable upper bounds g of K has recently received some attention. As a partial answer to this problem, we demonstrate that a set A is K-trivial if and only if A is O(g(n)-K(n))-jump traceable for all Solovay functions g, where by the preceding discussion the equivalence remains true when g is replaced by K^t.

Finally, we consider plain Kolmogorov complexity C and its time-bounded variant C^t of initial segments of computationally enumerable sets. Our main theorem here has essentially the main attitude and structure as Kummer's gap theorem, and asserts that every high c.e. Turing degree contains an c.e. set B such that for any computable function t there is a constant c_t>0 such that for all m it holds that C^t(B(0) ... B(m-1)) => c_tm, whereas for any nonhigh c.e. set A there is a computable time bound t and a constant c such that for infinitely many m it holds that C^t(A(0) ... A(m-1)) <= log m + c. By similar methods it can be shown that any high degree contains a set B such that C^t(B(0) ... B(m-1)) =>⁺ m/4. The constructed sets B have high unbounded but much lower time-bounded Kolmogorov complexity, and accordingly we obtain in addition an alternative and somewhat simpler proof of the result due to Juedes, Lathrop, and Lutz that every high degree contains a strongly deep set.

Alexander Kartzow: FO Model Checking on Nested Pushdown Trees

Abstract: Nested Pushdown Trees are unfoldings of pushdown graphs with an additional jump-relation. These graphs are closely related to collapsible pushdown graphs. They enjoy decidable μ-calculus model checking while monadic second-order logic is undecidable on this class. We show that nested pushdown trees are tree-automatic structures, whence first-order model checking is decidable. Furthermore, we prove that the model checking is in 2-EXPSPACE using pumping arguments on runs of pushdown systems. For these arguments we also develop a Gaifman style argument for graphs of small diameter.

Tadao Takaoka: Partial Solution and Entropy

Abstract: If the given problem instance is partially solved, we want to minimize our effort to solve the problem using that information. In this paper we introduce the measure of entropy H(S) for uncertainty in partially solved input data S(X)=(X₁, ..., X_k), where each X_i is already solved. We use the entropy measure to analyze three example problems, sorting, shortest paths and minimum spanning trees. For sorting X_i is an ascending run, and for shortest paths, X_i is an acyclic part in the given graph. For minimum spanning trees, X_i is interpreted as the partially obtained minimum spanning tree for a subgraph. The entropy measure, H(S), is defined by regarding p_i=|X_i|/|X| as a probability measure, that is, H(S)=-nΣ^k_i=1 p_i log p_i, where n=Σ^k_i=1|X_i|. Then we show that we can sort the input data S(X) in O(H(S)) time, and solve the shortest path problem in O(m+H(S)) time where m is the number of edges of the graph. Fianlly we show that the minimum spanning tree is computed in O(m+H(S)) time.

Alessandro Bianco, Marco Faella, Fabio Mogavero and Aniello Murano: Balanced Paths in Colored Graphs

Abstract: Given a finite graph whose edges are labeled with integer colors, we study the problem of determining whether there is an infinite path where either

all colors occur with the same asymptotic frequency, or

there is a constant which bounds the difference between the occurrences of any two colors for all prefixes of the path.

These two notions can be viewed as refinements of the classical notion of fair path, whose simplest form checks whether all colors occur infinitely often. Our notions provide stronger criteria, particularly suitable for scheduling applications based on a coarse-grained model of the jobs involved. We show that both problems are solvable in polynomial time, by reducing them to the feasibility of a linear program.

Irénée Briquel and Pascal Koiran: A Dichotomy Theorem for Polynomial Evaluation

Abstract: A dichotomy theorem for counting problems due to Creignou and Hermann states that or any finite set S of logical relations, the counting problem #SAT(S) is either in FP, or #P-complete.
In the present paper we show a dichotomy theorem for polynomial evaluation. That is, we show that for a given set S, either there exists a VNP-complete family of polynomials associated to S, or the associated family of polynomials are all in VP. We give a concise characterization of the sets S that give rise to "easy" and "hard" polynomials.
We also prove that several problems which were known to be #P-complete under Turing reductions only are in fact #P-complete under many-one reductions.

Lukasz Kaiser: Synthesis for Structure Rewriting Systems

Abstract: The description of a single state of a modelled system is often complex in practice, but few procedures for synthesis address this problem in depth. We study systems in which a state is described by an arbitrary finite structure, and changes of the state are represented by structure rewriting rules, a generalisation of term and graph rewriting. Both the environment and the controller are allowed to change the structure in this way, and the question we ask is how a strategy for the controller that ensures a given property can be synthesised.

We focus on one particular class of structure rewriting rules, namely on separated structure rewriting, a limited syntactic class of rules. To counter this restrictiveness, we allow the property to be ensured by the controller to be specified in a very expressive logic: a combination of monadic second-order logic evaluated on states and the modal mu-calculus for the temporal evolution of the whole system. We show that for the considered class of rules and this logic, it can be decided whether the controller has a strategy ensuring a given property, and in such case a finite-memory strategy can be synthesised. Additionally, we prove that the same holds if the property is given by a monadic second-order formula to be evaluated on the structure being the limit of the evolution of the system. As an example application, we show how a known result on decidability of monadic second-order properties of pushdown graphs is a corollary of this result, and we discuss other possible generalisations.

Tomi Kärki, Anne Lacroix and Michel Rigo: On the recognizability of self-generating sets

Abstract: Let I be a finite set of integers and F be a finite set of maps of the form $n\mapsto k_i n + \ell_i$ with integer coefficients. For an integer base k ≥ 2, we study the k-recognizability of the minimal set X of integers containing I and satisfying f(X) ⊆ X for all f ∈ F. In particular, answering a conjecture of Allouche and Shallit, we show under some technical condition that if two of the constants k_i's are multiplicatively independent, then X is not k-recognizable for any k ≥ 2.

Daniel Kirsten: An Algebraic Characterization of Semirings for which the Support of a Recognizable Series is Always Recognizable

Abstract: We show that for some semiring K, the support of a recognizable series over K is always recognizable if and only if in every finitely generated subsemiring of K there exists a finite congruence such that the zero of K is a singleton congruence class.

Tony Tan: On Pebble Automata for Data Languages with Decidable Emptiness Problem

Abstract: In this paper we study a subclass of pebble automata (PA) for data languages for which the emptiness problem is decidable. Namely, we show that the emptiness problem for weak 2-pebble automata is decidable, while the same problem for weak 3-pebble automata is undecidable. We also introduce the so-called top view weak PA. Roughly speaking, top view weak PA are weak PA where the equality test is performed only between the data values seen by the two most recently placed pebbles. The emptiness problem for this model is still decidable.

Arne Meier, Martin Mundhenk, Thomas Schneider, Michael Thomas, Volker Weber and Felix Weiss: The Complexity of Satisfiability for Fragments of Hybrid Logic --- Part I

Abstract: The satisfiability problem of hybrid logics with the downarrow binder is known to be undecidable. This initiated a research program on decidable and tractable fragments.

In this paper, we investigate the effect of restricting the propositional part of the language on decidability and on the complexity of the satisfiability problem over arbitrary, transitive, total frames, and frames based on equivalence relations. We also consider different sets of temporal and hybrid operators.

We trace the border of decidability and give the precise complexity of most fragments, in particular for all fragments including negation. For the monotone fragments, we are able to distinguish the easy from the hard cases, depending on the allowed set of operators.

Stanislav Zivny, David A. Cohen and Peter G. Jeavons: The Expressive Power of Binary Submodular Functions

Abstract: We investigate whether all Boolean submodular functions can be decomposed into a sum of binary submodular functions over a possibly larger set of variables. This question has been considered within several different contexts in computer science, including computer vision, artificial intelligence, and pseudo-Boolean optimisation. Using a connection between the expressive power of valued constraints and certain algebraic properties of functions, we answer this question negatively.

Our results have several corollaries. First, we characterise precisely which submodular polynomials of degree 4 can be expressed by quadratic submodular polynomials. Next, we identify a novel class of submodular functions of arbitrary arities which can be expressed by binary submodular functions, and therefore minimised efficiently using a so-called expressibility reduction to the Min-Cut problem. More importantly, our results imply limitations on this kind of reduction and establish for the first time that it cannot be used in general to minimise arbitrary submodular functions. Finally, we refute a conjecture of Promislow and Young on the structure of the extreme rays of the cone of Boolean submodular functions.

Xizhong Zheng and Robert Rettinger: Points on Computable Curves of Computable Lengths

Abstract: In this paper we show that the set of points covered by computable curves in IR² is a proper superset of the set of points covered by computable curves with computable length, where a plan curve C computable if there exists an injective, computable function f:[0;1] → IR² such that C is the range of f. More precisely, we construct a computable curve K and a points z on K such that no computable curve of computable length contains this point z. This gives a positive answer to a recent open question of Gu, Lutz and Mayordomo.

Marco Gaboardi, Luca Roversi and Luca Vercelli: Multiplicative Exponential Linear Logic can be levelled

Abstract: We study the relations between Multiplicative Exponential Linear Logic (meLL) and Baillot-Mazza Linear Logic by Levels (mL³). We design a decoration-based translation between propositional meLL and propositional mL³. The translation preserves the cut elimination. Moreover, we show that there is a proof net Π of second order meLL that cannot have a representative Π' in second order mL³ under any decoration. Every such a representative should identify two distinct indices. This suggests that levels can be an analytical tool in understanding the complexity of second order quantifier.

Anuj Dawar and Yuguo He: Parameterized Complexity Classes under Logical Reductions

Abstract: The parameterized complexity classes of the W-hierarchy are usually defined as the problems reducible to certain natural complete problems by means of fixed-parameter tractable (fpt) reductions. We investigate whether the classes can be characterised by means of weaker, logical reductions. We show that each class W[t] has complete problems under slicewise bounded-variable first-order reductions. These are a natural weakening of the slicewise bounded-variable LFP reductions which, by a result of Flum and Grohe are known to be equivalent to fpt reductions. If we relax the restriction on having a bounded number of variables, we obtain reductions that are too strong in that there are problems in W[t+1] that reduce to problems in W[t] under slicewise firts-order reductions. On the other hand, we show that if we consider slicewise quantifier-free first-order reductions, they are considerably weaker in that there are problems in W[t+1] that provably cannot reduce to any problem in W[t] under such reductions.

Periklis Papakonstantinou: On the Structure of Optimal Greedy Computation (for Job Scheduling)

Abstract: The model of Priority Algorithm syntactically formulates the concept of greedy algorithm [BNR03]. In this paper we investigate properties of the computation of optimal priority algorithms. The approximation power of priority algorithms for Job Scheduling is well-understood. A Job Scheduling subproblem is determined by a set of jobs, every finite subset of which forms an input. To the best of our knowledge there is no previous work about such arbitrary subproblems of Job Scheduling. An algorithm is optimal on a set determining the subproblem if it gains optimal profit on every input. Although there is strong evidence [PR07] that meaningful characterizations for arbitrary subproblems are not possible, we are able to ask about features of optimal priority algorithms. We ask these questions in the general setting of an arbitrary Job Scheduling subproblem and an arbitrary optimal priority algorithm. Our study shows that there is rich and interesting structure in the computation of such algorithms.

Kei Uchizawa, Eiji Takimoto and Takao Nishizeki: Size and Energy of Threshold Circuits Computing Mod Functions

Abstract: Let C be a threshold logic circuit computing a Boolean function MOD_m: {0, 1}ⁿ → {0, 1}, where n ≥ 1 and m ≥ 2. Then C outputs "0" if the number of "1"s in an input \Vec{x} ∈ {0, 1}ⁿ to C is a multiple of m and, otherwise, C outputs "1". The function MOD₂ is the so-called PARITY function, and MOD_n+1 is the OR function. Let s be the size of the circuit C, that is, C consists of s threshold gates, and let e be the energy complexity of C, that is, at most e gates in C output "1" for any input \Vec{x} ∈ {0, 1}ⁿ. In the paper, we prove that a very simple inequality n/(m-1) ≤ s^e holds for every circuit C computing MOD_m. The inequality implies that there is a tradeoff between the size s and energy complexity e of a threshold circuit C computing MOD_m, and yields a lower bound e = Ω ((log n - log m)/log log n) on e if s=O(polylog(n)).
We actually obtain a general result on the so-called generalized mod function, from which the result on the ordinary mod function MOD_m immediately follows.

Kyriaki Ioannidou, George Mertzios and Stavros Nikolopoulos: The Longest Path Problem is Polynomial on Interval Graphs

Abstract: The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamiltonian path problem. Motivated by the work of Uehara and Uno in~\cite{Ueh04}, where they left the longest path problem open for the class of interval graphs, in this paper we show that the problem can be solved in polynomial time on interval graphs. The proposed algorithm runs in O(n⁴) time, where n is the number of vertices of the input graph, and bases on a dynamic programming approach.

Kai Plociennik: A Probabilistic PTAS for Shortest Common Superstring

Abstract: We consider approximation algorithms for the shortest common superstring problem (SCS). It is well-known that there exists a constant f>1 such that there is no efficient approximation algorithm for SCS achieving a factor of at most f in the worst case, unless P=NP. We study SCS on random inputs and present an approximation scheme that achieves, for every eps>0, a 1+eps-approximation in expected polynomial time. This result applies not only if the letters are chosen independently at random, but also to the more realistic mixing model, which allows dependencies among the letters of the random strings. Our result is based on a sharp tail bound on the optimal compression, which improves a previous result by Frieze and Szpankowski.

Vincenzo Auletta, Paolo Penna and Giuseppe Persiano: Private capacities in mechanism design

Abstract: Algorithmic mechanism design considers distributed settings where the participants, termed agents, cannot be assumed to follow the protocol but rather their own interests. The protocol can be regarded as an algorithm augmented with a suitable payment rule and the desired condition is termed *truthfulness*, meaning that it is never convenient for an agent to report false information.

Motivated by the applications, we extend the usual one-parameter and multi-parameter settings by considering agents with *private capacities*: each agent can misreport her cost for `executing'' a single unit of work *and* the maximum amount of work that each agent can actually execute (i.e., the capacity of the agent). We show that truthfulness in this setting is equivalent to a simple condition on the underlying algorithm. By applying this result to various problems considered in the literature (e.g., makespan minimization on related machines) we show that only some of the existing approaches to the case "without capacities" can be adapted to the case with private capacities. This poses new interesting algorithmic challenges.

Bernd Borchert, Pierre McKenzie and Klaus Reinhardt: Few Product Gates but Many Zeros

Abstract: A d-gem is a {+,-,×}-circuit having very few ×-gates and computing from {x}∪Z a univariate polynomial of degree d having d distinct integer roots. We introduce d-gems because they could help factoring integers and because their existence for infinitely many d would blatantly disprove a variant of the Blum-Cucker-Shub-Smale conjecture. A natural step towards validating the conjecture would thus be to rule out d-gems for large d. Here we construct d-gems for several values of d up to 55. Our 2ⁿ-gems for n ≤ 4 are skew, that is, each {+,-}-gate adds an integer. We prove that skew 2ⁿ-gems if they exist require n {+,-}-gates, and that these for n ≥ 5 would imply new solutions to the Prouhet-Tarry-Escott problem in number theory. By contrast, skew d-gems over the real numbers are shown to exist for every d.

Sotiris Nikoletseas, Christoforos Raptopoulos and Paul Spirakis: Colouring Non-Sparse Random Intersection Graphs

Abstract: An intersection graph of n vertices assumes that each vertex is equipped with a subset of a global label set. Two vertices share an edge when their label sets intersect. Random Intersection Graphs (RIGs) (as defined in \cite{KSS99,S95}) consider label sets formed by the following experiment: each vertex, independently and uniformly, examines all the labels (m in total) one by one. Each examination is independent and the vertex succeeds to put the label in her set with probability p. Such graphs nicely capture interactions in networks due to sharing of resources among nodes. We study here the problem of efficiently coloring (and of finding upper bounds to the chromatic number) of RIGs. We concentrate in a range of parameters not examined in the literature, namely:

m = n^-α for α less than 1 (in this range, RIGs differ substantially from the Erdös-Renyi random graphs) and

the selection probability p is quite high (e.g. at least $\frac{\ln²n}{m}$ in our algorithm) and disallows direct greedy colouring methods.

We manage to get the following results:

For the case mp ≤ β ln n, for any constant β < 1 - α, we prove that np colours are enough to colour most of the vertices of the graph with high probability (whp). This means that even for quite dense graphs, using the same number of colours as those needed to properly colour the clique induced by any label suffices to colour almost all of the vertices of the graph. Note also that this range of values of m, p is quite wider than the one studied in \cite{BTU05}.
We propose and analyze an algorithm CliqueColour for finding a proper colouring of a random instance of G_{n, m, p}, for any mp ≥ ln²n. The algorithm uses information of the label sets assigned to the vertices of G_{n, m, p} and runs in $O\left(\frac{n²mp²}{ln n} \right)$ time, which is polynomial in n and m. We also show by a reduction to the uniform random intersection graphs model that the number of colours required by the algorithm are of the correct order of magnitude with the actual chromatic number of G_{n, m, p}.
We finally compare the problem of finding a proper colouring for G_{n, m, p} to that of colouring hypergraphs so that no edge is monochromatic. We show how one can find in polynomial time a k-colouring of the vertices of G_{n, m, p}, for any integer k, such that no clique induced by only one label in G_{n, m, p} is monochromatic.

Our techniques are novel and try to exploit as much as possible the hidden structure of random intersection graphs in this interesting range.

Feodor Dragan and Yang Xiang: How to use spanning trees to navigate in graphs

Abstract: In this paper, we investigate three strategies of how to use a spanning tree T of a graph G to navigate in G, i.e., to move from a current vertex x towards a destination vertex y via a path that is close to optimal. In each strategy, each vertex v has full knowledge of its neighborhood N_G[v] in G (or, k-neighborhood D_k(v,G), where k is a small integer) and uses a small piece of global information from spanning tree T (e.g., distance or ancestry information in T), available locally at v, to navigate in G. We investigate advantages and limitations of these strategies on particular families of graphs such as graphs with locally connected spanning trees, graphs with bounded length of largest induced cycle, graphs with bounded tree-length, graphs with bounded hyperbolicity. For most of these families of graphs, the ancestry information from a Breadth-First-Search-tree guarantees short enough routing paths. In many cases, the obtained results are optimal up to a constant factor.

Julien Degorre, Marc Kaplan, Sophie Laplante and Jérémie Roland: The communication complexity of non-signaling distributions

Abstract: We study a model of communication complexity that encompasses many well-studied problems, including classical and quantum communication complexity, the complexity of simulating distributions arising from bipartite measurements of shared quantum states, and XOR games. In this model, Alice gets an input x, Bob gets an input y, and their goal is to each produce an output a,b distributed according to some pre-specified joint distribution p(a,b|x,y). Our results apply to any non-signaling distribution, that is, those where Alice's marginal distribution does not depend on Bob's input, and vice versa, therefore our techniques apply to any communication problem that can be reduced to a non-signaling distribution, including quantum distributions, Boolean and non-Boolean functions, most relations, partial (promise) problems, in the two-player and multipartite settings.

By introducing a simple new technique based on affine combinations of lower-complexity distributions, we give elementary proofs and very intuitive interpretations of the recent lower bounds of Linial and Shraibman, which we generalize to the problem of simulating any non-signaling distribution. The lower bounds we obtain are also expressed as linear programs (or SDPs for quantum communication). We show that the dual formulations have a striking interpretation, since they coincide with maximum violations of Bell and Tsirelson inequalities. The dual expressions are closely related to the winning probability of XOR games.

We show that as in the case of Boolean functions, the gap between the quantum and classical lower bounds is at most linear in size of the support of the distribution, and does not depend on the size of the inputs. This translates into a bound on the gap between maximal Bell and Tsirelson inequalities, which was previously known only for the case of distributions with Boolean outcomes and uniform marginals.

Finally, we give an exponential upper bound on quantum and classical communication complexity in the simultaneous messages model, for any non-signaling distribution. One new consequence is that any quantum distribution can be simulated with a logarithmic number of qubits in the simultaneous messages model, independently of the amount of entanglement in the bipartite state measured by the two parties.

Ivona Bezakova and William A. Rummler: Sampling and Counting Edge Covers in 3-Regular Graphs

Abstract: An edge cover C is a set of edges of an undirected graph such that every vertex has an adjacent edge in C. We show that a Glauber dynamics Markov chain for edge covers mixes rapidly for three-regular graphs (or graphs with degrees at most three). Glauber dynamics have been studied extensively in the statistical physics community, with special emphasis on lattice graphs. Our results apply, for example, to the hexagonal lattice. Our proof of rapid mixing introduces a new cycle/path decomposition for the canonical flow argument.

Manfred Kufleitner and Pascal Weil: On FO2 quantifier alternation over words

Abstract: We show that each level of the quantifier alternation hierarchy within FO²[<] - the 2-variable fragment of the first order logic of order on words -- is a variety of languages. We then use the notion of condensed rankers, a refinement of the rankers defined by Weis and Immerman, to produce a decidable hierarchy of varieties which is interwoven with the quantifier alternation hierarchy -- and conjecturally equal to it. It follows that the latter hierarchy is decidable within one unit: given a formula alpha in FO²[<], one can effectively compute an integer m such that alpha is equivalent to a formula with at most m+1 alternating blocks of quantifiers, but not to a formula with only m-1 blocks. This is a much more precise result than what is known about the quantifier alternation hierarchy within FO[<], where no decidability result is known beyond the very first levels.

Vikraman Arvind and Pushkar Joglekar: Arithmetic Circuits, Monomial Algebras and Finite Automata

Abstract: The main motivation of this paper is to study lower bounds for circuit and branching program size over monomial algebras. both in the noncommutative and commutative setting. Our main results are:

An extension of Nisan's noncommutative algebraic branching program size lower bounds over the free noncommutative ring $F\angle{x₁,x₂,...,x_n}$ to similar lower bounds over the noncommutative monomial algebras $F\angle{x₁,x₂,...,x_n}/I$ for a monomial ideal I generated by subexponential number of monomials.

An extension of the exponential size lower bounds for monotone commutative circuits \cite{JS82,Ra08} for monotone commutative circuits over the ring Q[x₁,x₂,...,x_n] to monotone commutative circuits over the monomial algebra Q[x₁,x₂,...,x_n]/I, where I is a monomial ideal that is generated by o(n/lg n) monomials.

The main tool we use is some basic automata theory applied to arithmetic circuits. Let $F\angle{x₁,x₂,...,x_n}$ be the noncommutative polynomial ring over a field F, where the X={x₁,x₂,...,x_n} is a set of free noncommuting formal variables. Let f=∑_{m∈ M} c_m, m∈ FX be a polynomial, where c_m ≠ 0 is the coefficient of monomial m in f. For a finite automaton A over input alphabet X we define the polynomial fA=∑_{m∈ M ∩ L(\A)} c_m m which we call the intersection of f by A. If A is a DFA we show bounds on the circuit and algebraic branching program (ABP) complexities of the polynomial fA in terms of the corresponding complexity of f and size of the automaton A.

These bounds also have some consequences in polynomial identity testing. For example, we give a randomized NC² algorithm for finding a nonzero monomial in both noncommutative and commutative ABPs.

Delia Kesner and Fabien Renaud: The prismoid of resources

Abstract: We define a framework called the prismoid of resources where each vertex is a lambda calculus with the possibility of having different explicit resources and/or explicit cut elimination based on a different choice to make explicit or implicit (meta-level) the definition of the contraction, weakening, substitution operations. For all the calculi in the prismoid we show simulation of beta reduction, confluence, preservation of beta-strong normalisation and strong normalisation for typed terms. Full composition also holds for the prismoid base handling explicit substitutions. The whole development of the prismoid is done by making the set of resources a parameter, so that the properties for each vertex are obtained as a particular case of the general abstract proofs.

Violetta Lonati and Matteo Pradella: Snake-Deterministic Tiling Systems

Abstract: The concept of determinism, while clear and well assessed for string languages, is still matter of research as far as picture languages are concerned. We introduce here a new kind of determinism, called snake, based on the boustrophedonic scanning strategy, that is a natural scanning strategy used by many algorithm on 2D arrays and pictures. We consider a snake-deterministic variant of tiling systems, which defines the so-called snake-DREC class of languages. Snake-DREC properly extends the more traditional approach of diagonal-based determinism, used e.g. by Deterministic tiling systems, and by online tessellation automata. Our main result is showing that the concept of snake-determinism of tiles coincides with row (or column) unambiguity.

Jarkko Kari, Pascal Vanier and Thomas Zeume: Bounds on non-surjective cellular automata

Abstract: Cellular automata (CA) are discrete, homogeneous dynamical systems. Non-surjective one-dimensional CA have finite words with no preimage (called orphans), pairs of different words starting and ending identically and having the same image (diamonds) and words with more/fewer preimages than the average number (unbalanced words). Using a linear algebra approach, we obtain new upper bounds on the lengths of the shortest such objects. In the case of an n-state, non-surjective CA with neighborhood range 2 our bounds are of the orders O(n²), O(n^3/2) and O(n) for the shortest orphan, diamond and unbalanced word, respectively.

P. Madhusudan and Mahesh Viswanathan: Query Automata for Nested Words

Abstract: We study visibly pushdown automata (VPA) models for expressing and evaluating queries on words with a nesting structure. We define a query VPA model, which is a 2-way deterministic VPA that can mark in one run \emph{all} positions in a document that satisfy a query, and show that it is equi-expressive as unary monadic queries.
This surprising result parallels a classic result by Hopcroft and Ullman for queries on regular word languages. We also compare our model to query models on unranked trees, and show that our result is fundamentally different from those known for automata on trees.

Gaétan Richard: (Un)decidability of injectivity and surjectivity in one-dimensional sand automaton

Abstract: Originated from sand pile model, one-dimensional sand automata are a discrete dynamical system which is an intermediate between one dimensional cellular automata and two-dimensional cellular automata. In this paper, we shall study the decidability of the global behavior of this system according to his local definition. In particular, we shall focus on the problem of injectivity and surjectivity which have the property of being decidable for one-dimensional cellular automata and undecidable for two-dimensional one. We prove the following quite surprising property that one (surjectivity) is undecidable whereas the other one (injectivity) is decidable. For completeness, we also study this question for some classical restriction of configurations (finite, periodic and bounded ones).

Wouter Gelade, Marc Gyssens and Wim Martens: Regular Expressions with Counting: Weak versus Strong Determinism

Abstract: We study deterministic regular expressions extended with the counting operator. There exist two notions of determinism, strong and weak determinism, which almost coincide for standard regular expressions. This, however, changes dramatically in the presence of counting. In particular, we show that weakly deterministic expressions with counting are exponentially more succinct and strictly more expressive than strongly deterministic ones, even though they still do not capture all regular languages. In addition, we present a finite automaton model with counters, study its properties and investigate the natural extension of the Glushkov construction translating expressions with counting into such counting automata. This translation yields a deterministic automaton if and only if the expression is strongly deterministic. These results then also allow to derive upper bounds for decision problems for strongly deterministic expressions with counting.

Nadja Betzler and Britta Dorn: Towards a Dichotomy of Finding Possible Winners in Elections Based on Scoring Rules

Abstract: To make a joint decision, agents (or voters) are often required to provide their preferences as linear orders. To determine a winner, the given linear orders can be aggregated according to a voting protocol. However, in realistic settings, the voters may often only provide partial orders. This directly leads to the Possible Winner problem that asks, given a set of partial votes, if a distinguished candidate can stil become a winner. In this work, we consider the computational complexity of Possible Winner for the broad class of voting protocols defined by scoring rules. Generally, a scoring rule provides a score value for every position which a candidate can have in a linear order. Prominent examples include plurality, k-approval, and Borda. Generalizing previous NP-hardness results for some special cases and providing new many-one reductions, we settle the computational complexity for all but one scoring rule. More precisely, for an unbounded number of candidates and unweigthed voters, we show that Possible Winner is NP-complete for all scoring rules except plurality, veto, and the scoring rule defined by the scoring vector (2,1,...,1,0), and that it is solvable in polynomial time for plurality and veto.

Marco Faella: Admissible Strategies in Infinite Games over Graphs

Abstract: We consider games played on finite graphs, whose objective is to obtain a trace belonging to a given set of accepting traces. We focus on the states from which Player 1 cannot force a win. We compare several criteria for establishing what is the preferable behavior of Player 1 from those states, eventually settling on the notion of admissible strategy.

As the main result, we provide a characterization of the goals admitting positional admissible strategies. In addition, we derive a simple algorithm for computing such strategies for various common goals, and we prove the equivalence between the existence of positional winning strategies and the existence of positional subgame perfect strategies.

Michael Fellows, Jiong Guo, Hannes Moser and Rolf Niedermeier: A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems

Abstract: We investigate the computational complexity of a general "compression task" centrally occurring in the recently developed technique of iterative compression for exactly solving NP-hard minimization problems. The core issue (particularly but not only motivated by iterative compression) is to determine the computational complexity of, given an already inclusion-minimal solution for an underlying (typically NP-hard) vertex deletion problem, to find a better disjoint solution. The complexity of this task is so far lacking a systematic study. We show that, except for few cases where it is polynomial-time solvable, it is otherwise NP-complete. Our result applies to a large class of vertex deletion problems on undirected graphs, including problems such as Vertex Cover (here the corresponding compression task is decidable in polynomial time) or Undirected Feedback Vertex Set (here the corresponding compression task is NP-complete).

Adrian Kosowski and Alfredo Navarra: Graph Decomposition for Improving Memoryless Periodic Exploration

Abstract: We consider a general framework in which a memoryless robot periodically explores all the nodes of a connected anonymous graph by following local information available at each vertex. For each vertex v, the endpoints of all edges adjacent to v are assigned unique labels from the range 1 to deg(v) (the degree of v). The generic exploration strategy is implemented using a right-hand-rule transition function: after entering vertex v via the edge labeled i, the robot proceeds with its exploration, leaving via the edge having label [(i+1) mod deg(v)] at v.

A lot of attention has recently been given to the problem of labeling the graph so as to achieve a periodic exploration having the minimum possible length π. It has recently been shown [Czyzowicz at al., Proc. SIROCCO'09] that π ≤ 4 \frac13 n holds for all graphs of n vertices. Herein, we provide a new labeling scheme which leads to shorter exploration cycles, improving the general bound to π ≤ 4 n - 2. This main result is shown to be tight with respect to the class of labelings admitting certain connectivity properties. The labeling scheme is based on a new graph decomposition which may be of independent interest.

Mathieu Chapelle, Frédéric Mazoit and Ioan Todinca: Constructing Brambles

Abstract: Given an arbitrary graph G and a number k, it is well-known by a result of Seymour and Thomas \cite{SeTo93} that G has treewidth strictly larger than k if and only if it has a bramble of order k+2. Brambles are used in combinatorics as certificates proving that the treewidth of a graph is large. From an algorithmic point of view, there are several algorithms computing tree-decompositions of G of width at most k, if such decompositions exist and the running time is polynomial for constant k. Nevertheless, when the treewidth of the input graph is larger than k, to our knowledge there is no algorithm constructing a bramble of order k+2. We give here such an algorithm, running in O(n^k+4) time. Moreover, for classes of graphs with polynomial number of minimal separators, we define a notion of compact brambles and show how to compute compact brambles of order k+2 in polynomial time, not depending on k.

Paolo D'Arco, Alfredo De Santis, Anna Lisa Ferrara and Barbara Masucci: Security and Tradeoffs of the Akl-Taylor Scheme and its Variants

Abstract: In 1983 Akl and Taylor [Cryptographic Solution to a Problem of Access Control in a Hierarchy, ACM Transactions on Computer Systems, 1(3), 239--248, 1983] first suggested the use of cryptographic techniques to enforce access control in hierarchical structures. Due to its simplicity and versatility, the scheme has been used, for more than twenty years, to implement access control in several different domains, including mobile agent environments and XML documents. However, despite of its use over the time, the scheme has never been fully analyzed with respect to security and efficiency requirements. In this paper we provide new results on the Akl-Taylor scheme and its variants. More precisely:

We provide a rigorous analysis of the Akl-Taylor scheme. We consider different key assignment strategies and prove that the corresponding schemes are secure against key recovery.

We show how to obtain different tradeoffs between the amount of public information and the number of steps required to perform key derivation in the proposed schemes.

We also look at the MacKinnon et al. and Harn and Lin schemes and prove they are secure against key recovery.

We describe an Akl-Taylor based key assignment scheme with time-dependent constraints and prove the scheme efficient, flexible and secure.

We propose a general construction, which is of independent interest, yielding a key assignment scheme offering security w.r.t. key indistinguishability, given any key assignment scheme which guarantees security against key recovery.

Finally, we show how to use our construction, along with our assignment strategies and tradeoffs, to obtain an Akl-Taylor scheme, secure w.r.t. key indistinguishability, requiring a constant amount of public information.

Ahmet Kara, Volker Weber, Martin Lange and Thomas Schwentick: On the Hybrid Extension of CTL and CTL+

Abstract: The paper studies the expressivity, relative succinctness and complexity of satisfiability for hybrid extensions of the branching-time logics CTL and CTL+ by variables. Previous complexity results show that only fragments with one variable do have elementary complexity. It is shown that H1CTL+ and H1CTL are expressively equivalent but H1CTL+ is exponentially more succinct than H1CTL. On the other hand, H1CTL1 does not capture CTL*, even with arbitrarily many variables, as it cannot express the simple CTL* property EGFp. The satisfiability problem for H1CTL+ is complete for triply exponential time, this remains true for quite weak fragments and quite strong extensions of the logic.

Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis and Maria Kyropoulou: An improved approximation bound for spanning star forest and color saving

Abstract: We present a simple algorithm for the maximum spanning star forest problem. We take advantage of the fact that the problem is a special case of complementary set cover and we adapt an algorithm of Duh and Fürer in order to solve it. We prove that this algorithm computes 193/240 ≈ 0.804-approximate spanning star forests; this result improves a previous lower bound of 0.71 by Chen et al. Although the algorithm is purely combinatorial, our analysis defines a linear program that uses a parameter f and which is feasible for values of the parameter f not smaller than the approximation ratio of the algorithm. The analysis is tight and, interestingly, it also applies to complementary versions of set cover such as color saving; it yields the same approximation guarantee of 193/240 that marginally improves the previously known upper bound of Duh and Fürer. We also show that, in general, a natural class of local search algorithms do not provide better than 1/2-approximate spanning star forests.

Kohtaro Tadaki: Partial Randomness and Dimension of Recursively Enumerable Reals

Abstract: A real α is called recursively enumerable ("r.e." for short) if there exists a computable, increasing sequence of rationals which converges to α. It is known that the randomness of an r.e. real α can be characterized in various ways using each of the notions; program-size complexity, Martin-Löf test, Chaitin Ω number, the domination and Ω-likeness of α, the universality of a computable, increasing sequence of rationals which converges to α, and universal probability. These equivalent characterizations are a central result of algorithmic randomness and a current focus of the research. In this paper, we generalize these characterizations of randomness over the notion of partial randomness by parameterizing each of the notions above by a real T in (0,1], where the notion of partial randomness is a stronger representation of the compression rate by means of program-size complexity. As a result, we present ten equivalent characterizations of the partial randomness of an r.e. real. The resultant characterizations of partial randomness are powerful and have many important applications. One of them is to present equivalent characterizations of the dimension of an individual r.e. real. The equivalence between the notion of Hausdorff dimension and compression rate by program-size complexity (or partial randomness) has been established at present by a series of works of many researchers over the last two decades. The subject of the equivalence is one of the most active areas of the current research of algorithmic randomness. In this paper, we present ten equivalent characterizations of the dimension of an r.e. real.

Sven Schewe: From Parity and Payoff Games to Linear Programming

Abstract: This paper establishes a surprising reduction from parity and mean payoff games to linear programming problems. While such a connection is trivial for solitary games, it is surprising for two player games, because the players have opposing objectives, whose natural translations into an optimisation problem are minimisation and maximisation, respectively. Our reduction to linear programming circumvents the need for concurrent minimisation and maximisation by replacing one of them, the maximisation, by approximation. The resulting optimisation problem can be translated to a linear programme by a simple space transformation, which is inexpensive in the unit cost model, but results in an exponential growth of the coefficients. The discovered connection opens up unexpected applications - like μ-calculus model checking - of linear programming in the unit cost model and thus turns the intriguing academic problem of finding a polynomial time algorithm for linear programming in this model of computation (and subsequently a strongly polynomial algorithm) into a problem of paramount practical importance: All advancements in this area can immediately be applied to accelerate solving parity and payoff games, or to improve their complexity analysis.

Stavros Athanassopoulos, Ioannis Caragiannis, Christos Kaklamanis and Evi Papaioannou: Energy-efficient communication in multi-interface wireless networks

Abstract: We study communication problems in wireless networks supporting multiple interfaces. In such networks, two nodes can communicate if they are close and share a common interface. The activation of each interface has a cost reflecting the energy consumed when a node uses this interface. We distinguish between the symmetric and non-symmetric case, depending on whether all nodes have the same activation cost for each interface or not. For the symmetric case, we present a 3/2+ε-approximation algorithm for the problem of achieving connectivity with minimum activation cost, improving a previous bound of 2. For the non-symmetric case, we show that the connectivity problem is not approximable within a sublogarithmic factor in the number of nodes and present a logarithmic approximation algorithm for a more general problem that models group communication.

Mark Braverman, Stephen Cook, Pierre McKenzie, Rahul Santhanam and Dustin Wehr: Branching Programs for Tree Evaluation

Abstract: The problem FT^t_d consists in computing the value in [k]={1,...,k} taken by the root of a balanced d-ary tree of height h whose internal nodes are labelled with d-ary functions on [k] and whose leaves are labelled with elements of [k]. We propose FT^t_d as a good candidate for witnessing lspace \subsetneq logdcfl. We observe that the latter would follow from a proof that k-way branching programs solving FT^t_d require Ω(k^{unbounded function(h)}) size. We introduce a "state sequence" method that can match the size lower bounds on FT^t_d obtained by the Neciporuk method and can yield slightly better (yet still subquadratic) bounds for some nonboolean functions. Both methods yield the tight bounds Θ(k³) and Θ(k^5/2) for deterministic and nondeterministic branching programs solving FT³₂ respectively. We propose as a challenge to break the quadratic barrier inherent in the Neciporuk method by adapting the state sequence method to handle FT⁴_d.

Johannes Köbler and Sebastian Kuhnert: The k-tree isomorphism problem is complete for logspace

Abstract: We show that k-tree isomorphism can be decided in logarithmic space by giving a logspace canonical labeling algorithm. This improves over the previous StUL upper bound and matches the lower bound. As a consequence, the isomorphism, the automorphism, as well as the canonization problem for k-trees are all complete for deterministic logspace.

Martin Roetteler: Quantum algorithms for hidden shift problems: quadratics and functions of large Gowers norm

Abstract: Most quantum algorithms that give an exponential speedup over classical algorithms exploit the Fourier transform in some way. In Shor's algorithm, the Fourier transform is used to discover periodicity which is accomplished by sampling from the Fourier spectrum of a function. In a generalization of this idea, quantum Fourier sampling can be used to discover hidden subgroup structures of some functions much more efficiently than it is possible classically. Another problem for which the Fourier transform has been recruited successfully on a quantum computer is the hidden shift problem. Quantum algorithms for hidden shift problems usually have a slightly different flavor from hidden subgroup algorithms, as they use the Fourier transform to perform a correlation with a given reference function, instead of sampling from the Fourier spectrum directly. In this paper we show that hidden shifts can be extracted efficiently from Boolean functions that are quadratic forms. We also show how to identify an unknown quadratic form on n variables using a linear number of queries, in contrast to the classical case were this takes Θ(n²) many queries to a black box. What is more, we show that our quantum algorithm is robust in the sense that it can also infer the shift if the function is close to a quadratic, where we consider a Boolean function to be close to a quadratic if it has a large Gowers U₃ norm.

Ezra Resnick, Yoram Bachrach, Reshef Meir and Jeffrey Rosenschein: The Cost of Stability in Network Flow Games

Abstract: Cooperative game theory solution concepts define ways of dividing a coalition's gains among its members ("imputations"). A prominent solution concept is the core, focusing on stable imputations where no subset of agents has an incentive to leave the grand coalition. However, some games have empty cores.
We consider stabilizing cooperative games by having an external party offer a supplemental payment to the grand coalition. The adjusted gains, the sum of this payment and the original gains of the coalition, may be divided among agents in a stable manner. Such a division of the adjusted gains is called a superimputation, and the minimal sum of payments that stabilizes a game is called the cost of stability (CoS).
We examine the CoS in threshold network flow games, where each player controls an edge in the network flow graph, and a coalition of player succeeds if the maximal flow it can send from the source to the sink exceeds a certain threshold. We show that it is coNP-complete to determine whether a given super-imputation in such a game is stable. We give bounds on the CoS in general network flow games, and provide efficient algorithms for computing the CoS and finding stable super-imputations in several restricted cases. We also consider the relation between the CoS in Network Flow Games and the CoS in another known game theoretic domain, weighted voting games.

Yi Cao, Joseph Culberson and Lorna Stewart: DP-complete Problems Derived from Extremal NP-complete Properties

Abstract: In contrast to extremal coNP-complete problems, which are frequently DP-complete, many extremal NP-complete problems are in P. We investigate two extremal NP-complete problems, the extremal colorability problem with restricted degree and the extremal unfrozen non-implicant problem, and show that both of them are DP-complete.

MFCS 2009 home

Last modified: June 3, 2009