List of accepted papers (with abstracts)

Jens M. Schmidt. A Planarity Test via Construction Sequences
Abstract: Linear-time algorithms for testing the planarity of a graph are well known for over $35$ years. However, these algorithms are quite involved and recent publications still try to give simpler linear-time tests. We give a conceptually simple reduction from planarity testing to the problem of computing a certain construction of a $3$-connected graph. This implies a linear-time planarity test. Our approach is radically different from all previous linear-time planarity tests; as key concept, we maintain a planar embedding that is $3$-connected at each point in time. The algorithm computes a planar embedding if the input graph is planar and a Kuratowski-subdivision otherwise.
Leah Epstein and Hanan Zebedat-Haider. Rent or buy problems with a fixed time horizon
Abstract: We study several variants of a fixed length ski rental problem and related scheduling problems with rejection. A ski season consists of m days, and an equipment of cost 1 is to be used during these days. The equipment can be bought on any day, in which case it can be used without any additional cost starting that day and until the vacation ends. On each day, the algorithm is informed with the current non-negative cost of renting the equipment. As long as the algorithm did not buy the equipment, it must rent it every day of the vacation, paying the rental cost of each day of rental. We consider the case of arbitrary, non-increasing, and non-decreasing rental costs. We consider the case where the season cannot end before the m-th day, and the case that it can end without prior notice. We propose optimal online algorithms for all values of m for all variants. The optimal competitive ratios are either defined by solutions of equations (closed formulas or finite recurrences) or sets of mathematical programs, and tend to 2 as m grows.
Michal Kunc and Alexander Okhotin. Reversibility of computations in graph-walking automata
Abstract: The paper proposes a general notation for deterministic automata traversing finite undirected structures: the graph-walking automata. This abstract notion covers such models as two-way finite automata, including their multi-tape and multi-head variants, tree-walking automata and their extension with pebbles, picture-walking automata, space-bounded Turing machines, etc. It is then demonstrated that every graph-walking automaton can be transformed to an equivalent reversible graph-walking automaton, so that every step of its computation is logically reversible. This is done with a linear blow-up in the number of states, where the linear factor depends on the degree of graphs being traversed. The construction directly applies to all basic models covered by this abstract notion.
Meirav Zehavi. Parameterized Algorithms for Module Motif
Abstract: Student paper. Module Motif is a pattern matching problem that was introduced in the context of biological networks. Informally, given a multiset of colors $P$ and a graph $H$ whose nodes have sets of colors, it asks if $P$ occurs in a module of $H$ (i.e. in a set of nodes that have the same neighborhood outside the set). We present three parameterized algorithms for this problem that measure similarity between matched colors and handle deletions and insertions of colors to $P$. We observe that the running time of two of them might be essentially tight and prove that the problem is unlikely to admit a polynomial kernel.
Alexander Souza. Approximation Algorithms for Generalized Plant Location
Abstract: We consider the following Generalized Plant Location problem: There are $m$ possible plant locations and $n$ customers. Each customer $j$ has a demand $d_j$ of some utility. A plant $i$ can be constructed at cost $c_i$. Serving a customer $j$ with plant $i$ incurs cost $s_{i,j}$ and yields that the plant produces $u_{i,j}$ of the demanded utility. The goal is to serve all demands at minimal total cost. In Budgeted Plant Location each customer has a budget of $b_j$ and serving this customer with plant $i$ charges the budget an amount~$a_{i,j}$.

We give a unified randomized algorithm which is $(4 + \eps) \cdot \ln n$-approximate for both versions of the problem for any $\eps > 0$. This result is best possible up to a constant factor. In the budgeted version, we will violate the budgets by factors of at most $2 \cdot (4 + \eps) \cdot \ln n$. Our approach is based on LP-relaxations of the problems strengthened by additional \alg{Knapsack Cover} inequalities. This allows us to round the LP by rounding some ``large'' variables deterministically and the other ``small'' ones randomly.
Nicolas Bedon. Logic and branching automata
Abstract: The first result presented in this paper is the closure under complementation of the class or languages of finite N-free posets recognized by branching automata.
Relying on this, we propose a logic, named \emph{Presburger-MSO} or \emph{P-MSO} for short, precisely as expressive as branching automata.
The P-MSO theory of the class of all finite N-free posets is decidable.
Michael Soltys and Ariel German Fernandez. Feasible combinatorial matrix theory
Abstract: We show that the well-known K{\"o}nig's Min-Max Theorem (KMM), a fundamental result in combinatorial matrix theory, can be proven in the first order theory $\LA$ with induction restricted to $\Sigma_1^B$ formulas. This is an improvement over the standard textbook proof of KMM which requires $\Pi_2^B$ induction, and hence does not yield feasible proofs --- while our new approach does. $\LA$ is a weak theory that essentially captures the ring properties of matrices; however, equipped with $\Sigma_1^B$ induction $\LA$ is capable of proving KMM, and a host of other combinatorial properties such as Menger's, Hall's and Dilworth's Theorems. Therefore, our result formalizes Min-Max type of reasoning within a feasible framework.
Dietrich Kuske. Logical aspects of the lexicographic order on 1-counter languages
Abstract: We prove two results to the effect that 1-counter languages give
rise to the full complexity of context-free and even recursively
enumerable languages: (1) There are pairs of disjoint deterministic
one-counter languages whose union, ordered lexicographically, has an
undecidable $\Sigma_3$-theory and, alternatively, true arithmetic
can be reduced to its first-order theory. (2) It is undecidable
whether the union of two disjoint deterministic 1-counter languages,
ordered lexicographically, is dense.

In several aspects, these results cannot be sharpened any further:
(a) they do not hold for single deterministic 1-counter languages
(Caucal 2002, 2003), (b) they do not hold for the $\Sigma_2$-theory
(Corollary 1.2 of this paper), and (c) the first-order theory can always be
reduced to true arithmetic (since these linear orders are computable
Alexander Heußner and Alexander Kartzow. Reachability in Higher-Order Counters
Abstract: Higher-order counter automata (\HOCS) can be either seen as a restriction of higher-order pushdown automata (\HOPS) to a unary stack alphabet, or as an extension of counter automata to higher levels. We distinguish two principal kinds
of \HOCS: those that can test whether the topmost counter value is zero and those which cannot.

We show that control-state reachability for level $k$ \HOCS with $0$-test is complete for \mbox{$(k-2)$}-fold exponential space; leaving out the $0$-test leads to completeness for \mbox{$(k-2)$}-fold exponential time. Restricting \HOCS (without $0$-test) to level $2$, we prove that global (forward or backward) reachability analysis is $\PTIME$-complete. This enhances the known result for pushdown systems which are subsumed by level $2$ \HOCS without $0$-test.

We transfer our results to the formal language setting. Assuming that
$\DTIME(b(n))\subsetneq \DSPACE(b(n)) \subsetneq \DTIME(\exp(b(n)))$,
we apply proof ideas of Engelfriet and conclude that the hierarchies of languages of \HOPS and of \HOCS form strictly interleaving hierarchies. Interestingly, Engelfriet's constructions also allow to conclude immediately that the hierarchy of collapsible pushdown languages is strict level-by-level due to the existing complexity results for reachability on collapsible pushdown graphs. This answers an open question asked by Parys and by Kobayashi.
Andreas Brandstädt, Martin Milanic and Ragnar Nevries. New Polynomial Cases of the Weighted Efficient Domination Problem
Abstract: Let G be a finite undirected graph. A vertex dominates itself and all its neighbors in G. A vertex set D is an efficient dominating set (e.d. for short) of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination (ED) problem, which asks for the existence of an e.d. in G, is known to be NP-complete even for very restricted graph classes.

In particular, the ED problem remains NP-complete for 2P3-free graphs and thus for P7-free graphs. We show that the weighted version of the problem (abbreviated WED) is solvable in polynomial time on various subclasses of 2P3-free and P7-free graphs, including (P2+P4)-free graphs, P5-free graphs and other classes.

Furthermore, we show that a minimum weight e.d. consisting only of vertices of degree at most 2 (if one exists) can be found in polynomial time. This contrasts with our NP-completeness result for the ED problem on planar bipartite graphs with maximum degree 3.
Vince Barany, Michael Benedikt and Balder Ten Cate. Rewriting Guarded Negation Queries
Abstract: The Guarded Negation Fragment (GNFO) is a fragment of first-order logic
that contains all unions of conjunctive queries, a restricted form of negation
that suffices for expressing some common uses of negation in SQL queries,
and a large class of integrity constraints.
At the same time, as was recently shown, the syntax of GNFO is restrictive enough so that static
analysis problems such as query containment
are still decidable. This suggests that,
in spite of its expressive power, GNFO queries are amenable to novel
optimizations. In this paper we provide further evidence for this,
establishing that GNFO queries have distinctive features with respect to
query rewriting.Our results include effective preservation theorems for GNFO,
Craig Interpolation and Beth Definability results, and the ability to
express the certain answers of queries with respect
to GNFO constraints within very restricted logics.

Stephane Durocher and Saeed Mehrabi. Guarding Orthogonal Art Galleries using Sliding Cameras: Algorithmic and Hardness Results
Abstract: Let $P$ be an orthogonal polygon. Consider a sliding camera that
travels back and forth along an orthogonal line segment $s\in P$ as
its \emph{trajectory}. The camera can see a point $p\in P$ if there
exists a point $q\in s$ such that $pq$ is a line segment normal to
$s$ that is completely contained in $P$. In the
\emph{minimum-cardinality sliding cameras problem}, the objective is
to find a set $S$ of sliding cameras of minimum cardinality to guard
$P$ (i.e., every point in $P$ can be seen by some sliding camera in
$S$) while in the \emph{minimum-length sliding cameras problem} the
goal is to find such a set $S$ so as to minimize the total length of
trajectories along which the cameras in $S$ travel.

In this paper, we first settle the complexity of the minimum-length
sliding cameras problem by showing that it is polynomial tractable
even for orthogonal polygons with holes, answering a question posed
by Katz and Morgenstern (2011). Next we show that the
minimum-cardinality sliding cameras problem is \textsc{NP}-hard when
$P$ is allowed to have holes, which partially answers another
question posed by Katz and Morgenstern (2011). Finally, we
give a 5-approximation algorithm to the minimum-cardinality sliding
cameras problem for $[w]$-star-shaped polygons, a subclass of simple
orthogonal polygons, introduced by Lingas et al. (2008).
Yuan Feng, Nengkun Yu and Mingsheng Ying. Reachability analysis of recursive quantum Markov chains
Abstract: We introduce the notion of recursive quantum Markov chain (RQMC) for analysing recursive quantum programs with procedure calls. RQMCs are natural extension of Etessami and Yannakakis's recursive Markov chains where the probabilities along transitions are replaced by completely positive and trace-nonincreasing super-operators on a state Hilbert space of a quantum system.

We study the reachability problem for RQMCs and establish a reduction from it to computing the least solution of a system of polynomial equations in the semiring of super-operators. It is shown that for an important subclass of RQMCs, namely linear RQMCs, the reachability problem can be solved in polynomial time. For general case, technique of Newtonian program analysis recently developed by Esparza, Kiefer and Luttenberger is employed to approximate reachability super-operators. A polynomial time algorithm that computes the support subspaces of the reachability super-operators in general case is also proposed.
Nadia Creignou, Arne Meier, Julian-Steffen Müller, Johannes Schmidt and Heribert Vollmer. Paradigms for Parameterized Enumeration
Abstract: The aim of the paper is to examine the computational complexity and algorithmics of enumeration, the task to output all solutions of a given problem, from the point of view of parameterized complexity.
First we define formally different notions of efficient enumeration in the context of parameterized complexity. Second we show how different algorithmic paradigms can be used in order to get parameter-efficient enumeration algorithms in a
number of examples.
These paradigms use well-known principles from the design of parameterized decision as well as enumeration techniques, like for instance kernelization and self-reducibility.
The technique of kernelization, in particular, leads to a characterization of fixed-parameter tractable enumeration problems.
Stefan Mengel. Arithmetic Branching Programs with Memory
Abstract: We extend the well known characterization of the arithmetic
circuit class VPws as the class of polynomials computed by polynomial
size arithmetic branching programs to other complexity classes. In order
to do so we add additional memory to the computation of branching
programs to make them more expressive. We show that allowing differ-
ent types of memory in branching programs increases the computational
power even for constant width programs. In particular, this leads to very
natural and robust characterizations of VP and VNP by branching pro-
grams with memory.
Sébastien Tavenas. Improved bounds for reduction to depth 4 and depth 3 [Best paper award (joint) + Best student paper award]
Abstract: Koiran showed that if a polynomial of degree d is computed by a circuit of size s, then it is also computed by a homogeneous circuit of depth four and of size exp(O(sqrt(d)log(d)log(s))). Using this result, Gupta, Kamath, Kayal and Saptharishi gave a exp(O(sqrt(d log(d) log(n) log(s)))) upper bound for the size of the smallest depth three circuit computing a n-variate polynomial of degree d given by a circuit of size s.

We improve here Koiran's bound. Indeed, we show that if we reduce an arithmetic circuit to depth four, then the size becomes exp(O(sqrt(d log(ds)log(n)))). It also implies the same upper bound for depth three circuits.

This new bound is not far from optimal in the sense that Gupta, Kamath, Kayal and Saptharishi also showed a exp(Omega(sqrt(d))) lower bound for the size of homogeneous depth four circuits such that gates at the bottom have fan-in at most sqrt(d). Finally, we show that this last lower bound also holds if the fan-in is at least sqrt(d).
Rohit Chadha, A. Prasad Sistla and Mahesh Viswanathan. Probabilistic Automata with Isolated Cut-points
Abstract: We consider various decision problems for probabilistic
finite automata ({\PFA}) with isolated cut-points. Recall that a
cut-point $x$ is said to be isolated for a probabilistic finite
automaton ({\PFA}) if the acceptance probability of all finite strings
is bounded away from $x$. First we establish the exact level of undecidability of
the problem of determining if a cut-point is isolated; we show this
problem to be $\mathbf{\Sigma^0_2}$-complete. Next we introduce a new
class of {\PFA}s called eventually weakly ergodic {\PFA}s that
generalize ergodic and weakly ergodic {\PFA}s. We show that the
emptiness and universality problem for these {\PFA}s is decidable
provided the cut-point is isolated.
Christoph Berkholz and Oleg Verbitsky. On the speed of constraint propagation and the time complexity of arc consistency testing
Abstract: Establishing arc consistency on two relational structures
is one of the most popular heuristics for the constraint satisfaction problem.
We aim at determining the time complexity of arc consistency testing.
The input structures G and H can be supposed to be connected
colored graphs, as the general problem reduces to this particular case.
We first observe the upper bound O(e(G)v(H)+v(G)e(H)), which implies
the bound O(e(G)e(H)) in terms of the number of edges and
the bound O((v(G)+v(H))^3) in terms of the number of vertices.
We then show that both bounds are tight
up to a constant factor as long as an arc consistency algorithm is based
on constraint propagation (like any algorithm currently known).

Our argument for the lower bounds is based on examples of slow constraint
propagation. We measure the speed of constraint propagation
observed on a pair G,H by the size of a proof, in a natural combinatorial proof system,
that Spoiler wins the existential 2-pebble game on G,H.
The proof size is bounded from below by the game length D(G,H), and
a crucial ingredient of our analysis is the existence of G, H
with D(G,H)=\Omega(v(G)v(H)).
We find one such example among old benchmark instances
for the arc consistency problem and also suggest a new, different construction.
Stephane Durocher, Rahul Shah, Matthew Skala and Sharma V. Thankachan. Linear-Space Data Structures for Range Frequency Queries on Arrays and Trees
Abstract: We present O(n)-space data structures to support various range frequency queries on a given array A[0:n-1] or tree T with n nodes. Given a query consisting of an arbitrary pair of pre-order rank indices (i,j), our data structures return a least frequent element, mode, or alpha-minority of the multiset of elements in the unique path with endpoints at indices i and j in A or T. We describe a data structure that supports range least frequent element queries on arrays in O(sqrt{n / w}) time, improving the Theta(sqrt{n}) worst-case time required by the data structure of Chan et al. (SWAT 2012), where w \in Omega(log n) is the word size in bits. We describe a data structure that supports range mode queries on trees in O(log log n sqrt{n / w}) time, improving the Theta(sqrt{n} log n) worst-case time required by the data structure of Krizanc et al. (ISAAC 2003). Finally, we describe a data structure that supports range alpha-minority queries on trees in O(alpha^{-1} log log n) time, where alpha \in [0,1] can be specified at query time.
Stefan Felsner, George Mertzios and Irina Mustata. On the Recognition of Four-Directional Orthogonal Ray Graphs
Abstract: Orthogonal ray graphs are the intersection graphs of horizontal and vertical rays (i.e. half-lines) in the plane. If the rays can have any possible orientation (left/right/up/down) then the graph is a $4$-directional orthogonal ray graph (4-DORG). Otherwise, if all rays are only pointing into the positive $x$ and $y$ directions, the intersection graph is a 2-DORG. Similarly, for 3-DORGs, the horizontal rays can have any direction but the vertical ones can only have the positive direction. The recognition problem of 2-DORGs, which are a nice subclass of bipartite comparability graphs, is known to be polynomial, while the recognition problems for 3-DORGs and 4-DORGs are open. Recently is has been shown that the recognition of unit grid intersection graphs, a superclass of 4-DORGs, is NP-complete. In this paper we prove that the recognition problem of $4$-DORGs is polynomial, given a partition $\{L,R,U,D\}$ of the vertices of $G$ (which corresponds to the four possible ray directions). For the proof, given the graph $G$, we first construct two cliques $G_{1},G_{2}$ with both directed and undirected edges. Then we successively augment these two graphs, constructing eventually a graph $\widetilde{G}$ with both directed and undirected edges, such that $G$ has a 4-DORG representation if and only if $\widetilde{G}$ has a transitive orientation respecting its directed edges. As a crucial tool for our analysis we introduce the notion of an $S$-orientation of a graph, which extends the notion of a transitive orientation. We expect that our proof ideas will be useful also in other situations. Using an independent approach we show that, given a permutation $\pi$ of the vertices of $U$ ($\pi$ is the order of $y$-coordinates of ray endpoints for $U$), while the partition $\{L,R\}$ of $V\setminus U$ is not given, we can still efficiently check whether $G$ has a 3-DORG representation.
Alexander Golovnev, Alexander Kulikov and Ivan Mihajlin. Solving 3-superstring in 3^{n/3} Time
Abstract: In the shortest common superstring problem one is given a set s_1, ..., s_n of n strings and the goal is to find a shortest string containing each s_i as a substring. While many approximation algorithms for this problem have been developed, it is still not known whether it can be solved exactly in less than 2^n steps. In this paper we present an algorithm solving a special case when all the strings have length 3 in time 3^{n/3} and polynomial space.
The approach is based on finding a shortest directed rural postman path in the de Bruijn graph of the given set of strings (such graphs are widely used in genome assembly, but have only few applications in theoretical investigations of SCS).
Yasuhiro Takahashi, Takeshi Yamazaki and Kazuyuki Tanaka. Hardness of Classically Simulating Quantum Circuits with Unbounded Toffoli and Fan-Out Gates
Abstract: We study the classical simulatability of constant-depth quantum circuits followed by only one single-qubit measurement, where they consist of universal gates on at most two qubits and additional gates on an unbounded number of qubits. First, we consider unbounded Toffoli gates as the additional gates and deal with the weak simulation, i.e., sampling the output probability distribution. We show that there exists a constant-depth quantum circuit with only one unbounded Toffoli gate that is not weakly simulatable, unless BQP \subseteq PostBPP \cap AM. Then, we consider unbounded fan-out gates as the additional gates and deal with the strong simulation, i.e., computing the output probability. We show that there exists a constant-depth quantum circuit with only two unbounded fan-out gates that is not strongly simulatable, unless P = PP. These results are in contrast to the fact that any constant-depth quantum circuit without the additional gates is strongly and weakly simulatable.
Fedor Fomin, Petr Golovach and Janne H. Korhonen. On the parameterized complexity of cutting a few vertices from a graph
Abstract: We study the parameterized complexity of separating a small set of vertices from a graph by a small vertex-separator. That is, given a graph $G$ and integers $k$, $t$, the task is to find a vertex set $X$ with $|X| \le k$ and $|N(X)| \le t$. We show that

- the problem is fixed-parameter tractable (FPT) when parameterized by $t$ but W[1]-hard when parameterized by $k$, and

- a terminal variant of the problem, where $X$ must contain a given vertex $s$, is W[1]-hard when parameterized either by $k$ or by $t$ alone, but is FPT when parameterized by $k + t$.

We also show that if we consider edge cuts instead of vertex cuts, the terminal variant is NP-hard and FPT parameterized by $k+t$.
Karl Bringmann, Christian Engels, Bodo Manthey and Raghavendra Rao B V. Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems
Abstract: Probabilistic analyses for metric optimization problems have mostly been conducted on random Euclidean instances, but little is known about metric instances drawn from distributions other than the Euclidean.

This motivates our study of random metric instances for optimization problems obtained as follows: Every edge of a complete graph gets a weight drawn independently at random. The length of an edge is then the length of a shortest path (with respect to the weights drawn) that connects its two endpoints.

We prove structural properties of the random shortest path metrics generated in this way. Our main structural contribution is the construction of a good clustering. Then we apply these findings to analyze the approximation ratios of heuristics for matching, the traveling salesman problem (TSP), and the k-center problem, as well as the running-time of the 2-opt heuristic for the TSP. The bounds that we obtain are considerably better than the respective worst-case bounds. This suggests that random shortest path metrics are easy instances, similar to random Euclidean instances, albeit for completely different structural reasons.
Thomas Zeume and Thomas Schwentick. On the quantifier-free dynamic complexity of Reachability
Abstract: The dynamic complexity of the reachability query is studied in the dynamic complexity framework of Patnaik and Immerman, restricted to quantifier-free update formulas.

It is shown that, with this restriction, the reachability query cannot be dynamically maintained, neither with binary auxiliary relations nor with unary auxiliary functions, and that ternary auxiliary relations are more powerful with respect to graph queries than binary auxiliary relations. Further results are obtained including more inexpressibility results for reachability in a different setting, inexpressibility results results for some other queries and normal forms for quantifier-free update programs.
Marco Bender, Clemens Thielen and Stephan Westphal. A Constant Factor Approximation for the Generalized Assignment Problem with Minimum Quantities and Unit Size Items
Abstract: We consider a variant of the generalized assignment problem (GAP) where the items have unit size and the amount of space used in each bin is restricted to be either zero (if the bin is not opened) or above a given lower bound (a minimum quantity). This problem is known to be strongly NP-complete and does not admit a polynomial time approximation scheme (PTAS).

By using randomized rounding, we obtain a randomized 3.93-approximation algorithm, thereby providing the first nontrivial approximation result for this problem.
Moritz Müller and Stefan Szeider. Revisiting Space in Proof Complexity: Treewidth and Pathwidth
Abstract: So-called ordered variants of the classical notions of pathwidth and treewidth are introduced and proposed as proof theoretically meaningful complexity measures for the directed acyclic graphs underlying proofs. The ordered pathwidth of a proof is shown to be roughly the same as its formula space. Length-space lower bounds for R(k)-refutations are generalized to arbitrary infinity axioms and strengthened in that the space measure is relaxed to ordered treewidth.

Amr Elmasry and Jyrki Katajainen. In-Place Binary Counters
Abstract: We introduce a binary counter that supports increments and decrements in $O(1)$ worst-case time per operation. (We assume that arithmetic operations on an index variable that is stored in one computer word can be performed in $O(1)$ time each.) To represent any integer in the range from $0$ to $2^n -1$, our counter uses an array of $n$ bits plus few words of $\lceil \lg (1 + n) \rceil$ bits each. Extended regular and strictly regular counters are known to also support increments and decrements in $O(1)$ worst-case time per operation, but the implementation of these counters would require $\Theta(n)$ words of extra space, whereas our counter only needs $O(1)$ words of extra space. Compared to other space-efficient counters, which rely on Gray codes, our counter utilizes codes with binary weights allowing the usage of the counter in data-structural applications.
Francesco Ranzato. A More Efficient Simulation Algorithm on Kripke Structures
Abstract: A number of algorithms for computing the simulation preorder (and equivalence) on Kripke structures are available. Let Sigma denote the state space, -> the transition relation and Psim the partition of Sigma induced by simulation equivalence. While some algorithms are designed to reach the best space bounds, whose leading additive term is |Psim|^2, other algorithms are devised to attain the best time complexity O(|Psim||->|). We present a novel simulation algorithm which is both space and time efficient: it runs in O(|Psim|^2 log|Psim| + |Sigma|log|Sigma|) space and O(|Psim||->|log|Sigma|) time. Our simulation algorithm thus reaches the best space bounds while closely approaching the best time complexity.
Kristoffer Arnsfelt Hansen and Vladimir Podolskii. Polynomial threshold functions and Boolean threshold circuits
Abstract: We initiate a comprehensive study of the complexity of computing
Boolean functions by polynomial threshold functions (PTFs) on general
Boolean domains. A typical example of a general Boolean domain is
{1,2}^n. We are mainly interested in the length (the number of
monomials) of PTFs, with their degree and weight being of secondary

First we motivate the study of PTFs over the {1,2}^n domain by showing
their close relation to depth two threshold circuits. In particular we
show that PTFs of polynomial length and polynomial degree compute
exactly the functions computed by polynomial size THRoMAJ circuits.
We note that known lower bounds for THRoMAJ circuits extends to the
likely strictly stronger model of PTFs. We also show that a
``max-plus'' version of PTFs are related to AC^0oTHR circuits.

We exploit this connection to gain a better understanding of threshold
circuits. In particular, we show that (super-logarithmic) lower bounds
for 3-player randomized communication protocols with unbounded error
would yield (super-polynomial) size lower bounds for THRoTHR

Finally, having thus motivated the model, we initiate structural
studies of PTFs. These include relationships between weight and degree
of PTFs, and a degree lower bound for PTFs of constant length.
Michael Benedikt, Joost Engelfriet and Sebastian Maneth. Determinacy and Rewriting of Top-Down and MSO Tree Transformations
Abstract: A query is determined by a view, if the result to the query can be reconstructed
from the result of the view. We consider the problem of deciding for
two given tree transformations, whether one is determined by the other. If the
view transformation is induced by a tree transducer that may copy, then determinacy
is undecidable, even for identity queries. For a large class of non-copying
views, namely compositions of functional extended linear top-down tree transducers
with regular look-ahead, we show that determinacy is decidable, where
queries are given by deterministic top-down tree transducers with regular look-ahead
or by MSO tree transducers. We also show that if a query is determined,
then it can be rewritten into a query that works directly over the view and is in the
same class as the given query. The proof relies on the decidability of equivalence
for the two considered classes of queries, and on their closure under composition.
Radu Mardare, Dexter Kozen and Prakash Panangaden. Strong Completeness for Markovian Logics
Abstract: In this paper we present Hilbert-style axiomatizations for three logics
for reasoning about continuous-space Markov processes (MPs): (i) a logic for
MPs defined for probability distributions on measurable state spaces, (ii) a logic
for MPs defined for sub-probability distributions and (iii) a logic defined for arbitrary
distributions. These logics are not compact so one needs infinitary rules in
order to obtain strong completeness results.
We propose a new infinitary rule that replaces the so-called Countable Additivity
Rule (CAR) currently used in the literature to address the problem of proving
strong completeness for these and similar logics. Unlike the CAR, our rule has
a countable set of instances; consequently it allows us to apply the Rasiowa-
Sikorski lemma for establishing strong completeness. Our proof method is novel
and it can be used for other logics as well.
Neeldhara Misra, Fahad Panolan and Saket Saurabh. Subexponential Algorithm for d-Cluster Edge Deletion: Exception or Rule?
Abstract: The correlation clustering problem is a fundamental problem in both theory and practice, and it involves identifying clusters of objects in a data set based on their similarity. A traditional modeling of this question as a graph theoretic problem involves associating vertices with data points and indicating similarity by adjacency. Clusters then correspond to cliques in the graph. The resulting optimization problem, Cluster Editing (and several variants) are very well-studied algorithmically. In many situations, however, translating clusters to cliques can be somewhat restrictive. A more flexible notion would be that of a structure where the vertices are mutually "not too far apart", without necessarily being adjacent.

One such generalization is realized by structures called s-clubs}, which are graphs of diameter at most s. In this work, we study the question of finding a set of at most k edges whose removal leaves us with a graph whose components are s-clubs. Recently, it has been shown that unless the Exponential Time Hypothesis (ETH) fails Cluster Editing (whose components are 1-clubs) does not admit sub-exponential time algorithm [STACS, 2013]. That is, there is no algorithm solving the problem in time 2^{o(k)}n^{O(1)}. However, surprisingly they show that when the number of cliques in the output graph is restricted to $d$, then the problem can be solved in time O(2^{O(\sqrt{dk})}+m+n). We show that this sub-exponential time algorithm for the fixed number of cliques is an exception rather than a rule.

Our first result shows that assuming the ETH, there is no algorithm solving the s-Club Cluster Edge Deletion problem in time 2^{o(k)}n^{O(1)}. We show, further, that even the problem of deleting edges to obtain a graph with d s-clusters cannot be solved in time 2^{o(k)}n^{O(1)} for any fixed s,d \geq 2. This is a radical contrast from the situation established for cliques, where sub-exponential algorithms are known.
Andrea Pietracaprina, Geppino Pucci, Francesco Silvestri and Fabio Vandin. Space-Efficient Parallel Algorithms for Combinatorial Search Problems
Abstract: In this paper we present space-efficient parallel strategies for two fundamental combinatorial search problems, namely, \emph{backtrack search} and \emph{branch-and-bound}, both involving the visit of an $n$-node tree of height $h$ under the assumption that a node can be accessed only through its father or its children. For both problems we propose efficient algorithms that run on a distributed-memory machine with $p$ processors. For backtrack search, we give a deterministic algorithm running in $\BO{n/p+h\log p}$ time, and a Las Vegas algorithm requiring optimal $\BO{n/p+h}$ time, with high probability. Building on the backtrack search algorithm, we also derive a Las Vegas algorithm for branch-and-bound which runs in $\BO{(n/p+h\log p \log n)h\log n}$ time, with high probability. All of the algorithms use constant space per processor. Our results represent a significant improvement with respect to the state of the art, since the space requirements per processor of previously known algorithms are nonconstant (i.e., $\BOM{h}$ for backtrack search and $\BOM{n/p}$ for branch-and-bound) and indeed depend on the (possibly huge) tree to be explored.
Hervé Fournier, Sylvain Perifel and Rémi de Verclos. On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
Abstract: We consider the problem of fixed-polynomial lower bounds on the size of arithmetic circuits computing uniform families of polynomials. Assuming the Generalised Riemann Hypothesis (GRH), we show that for all $k$, there exist polynomials with coefficients in $\MA$ having no arithmetic circuits of size $O(n^k)$ over $\IC$ (allowing any complex constant). We also build a family of polynomials that can be evaluated in $\AM$ having no arithmetic circuits of size $O(n^k)$. Then we investigate the link between fixed-polynomial size circuit bounds in the Boolean and arithmetic settings. In characteristic zero, it is proved that $\NP \not\subset \size(n^k)$, or $\MA \subset \size(n^k)$, or $\NP=\MA$ imply lower bounds on the circuit size of uniform polynomials in $n$ variables from the class $\VNP$ over~$\IC$, assuming GRH. In positive characteristic $p$, uniform polynomials in $\VNP$ have circuits of fixed-polynomial size if and only if both $\VP = \VNP$ over $\IF_p$ and $\ModpP$ has circuits of fixed-polynomial size.
Sebastian Eggert, Henning Schnoor and Thomas Wilke. Noninterference with Local Policies
Abstract: We develop a theory for state-based noninterference in a setting where different security policies-we call them local policies-apply in different parts of a given system.
Our theory comprises appropriate security definitions, characterizations of these definitions, for instance in terms of unwindings, algorithms for analyzing the security of systems with local policies, and corresponding complexity results.
Antonios Antoniadis, Chien-Chung Huang, Sebastian Ott and José Verschae. How to pack your items when you have to buy your knapsack
Abstract: In this paper we consider a generalization of the classical knapsack problem. While in the standard setting a fixed capacity may not be exceeded by the weight of the chosen items, we replace this hard constraint by a weight-dependent cost function. The objective is to maximize the total profit of the chosen items minus the cost induced by their total weight. We study two natural classes of cost functions, namely convex and concave functions. For the concave case, we show that the problem can be solved in polynomial time; for the convex case we present an FPTAS and a 2-approximation algorithm with the running time of O(n logn), where n is the number of items.

We note that our problem with a convex cost function is a special case of maximizing a non-monotone,
possibly negative submodular function. Prior to our result, only a 3-approximation is known.
Piero Bonatti, Marco Faella, Clemente Galdi and Luigi Sauro. Auctions for Partial Heterogeneous Preferences
Abstract: Online privacy provides fresh motivations to generalized auctions where: (i) preferences over bids may be partial, because of lack of knowledge and formalization difficulties; (ii) the preferences of auctioneers and bidders may be heterogeneous and unrelated.
We tackle these generalized scenarios by introducing a few natural generalizations of second-price auctions, and by investigating which of their classical properties are preserved under which conditions.
Henrik Björklund, Wim Martens and Thomas Schwentick. Validity of Tree Pattern Queries With Respect to Schema Information
Abstract: We prove that various containment and validity problems for tree
pattern queries with respect to a schema are Exptime-complete.
When one does not require the root of a tree pattern query to match
the root of a tree, validity of a non-branching tree pattern query
with respect to a Relax NG schema or W3C XML Schema is already
Exptime-hard when the query does not branch and uses only child
axes. These hardness results already hold when the alphabet size is
fixed. Validity with respect to a DTD is proved to be Exptime-hard
already when the query only uses child axes and is allowed to
branch only once.
Anca Muscholl and Sven Schewe. Unlimited decidability of distributed synthesis with limited missing knowledge
Abstract: We study the problem of controller synthesis for distributed systems modelled by Zielonka automata. While the decidability of this problem in full generality remains open and challenging, we suggest here to seek controllers from a parametrised family: we are interested in controllers that ensure frequent communication between the processes, where frequency is determined by the parameter. We show that this restricted controller synthesis version is affordable for synthesis standards: fixing the parameter, the problem is EXPTIME-complete.
Martin Fink and Sergey Pupyrev. Ordering Metro Lines by Block Crossings
Abstract: A problem that arises in drawings of transportation networks is to
minimize the number of crossings between different transportation
lines. While this can be done efficiently under specific constraints,
not all solutions are visually equivalent. We suggest to
merge crossings into \emph{block crossings}, that is, crossings
of two neighboring groups of consecutive lines. Unfortunately,
minimizing the total number of block
crossings is NP-hard even for very simple graphs. We
give approximation algorithms for special classes of graphs and
an asymptotically worst-case optimal algorithm for block crossings
on general graphs. That is, we bound the number of block crossings
that our algorithm needs and construct worst-case instances on which the
number of block crossings that is necessary
in any solution is asymptotically the same as our bound.
Vincent Froese, René Van Bevern, Rolf Niedermeier and Manuel Sorge. A Refined Computational Complexity Analysis of Combinatorial Feature Selection Problems
Abstract: We examine the algorithmic tractability of NP-hard combinatorial
feature selection problems in terms of parameterized complexity
theory. In combinatorial feature selection, one seeks to discard
dimensions from high-dimensional data such that the resulting
instances fulfill a desired property. In parameterized complexity
analysis, one seeks to identify relevant problem-specific quantities
and tries to determine their influence on the computational complexity
of the considered problem. In this paper, for various combinatorial
feature selection problems, we identify parameterizations and reveal
to what extent these govern computational complexity. We provide
tractability as well as intractability results; for example, we show
that the Distinct Vectors problem on binary points is polynomial-time
solvable if each pair of points differs in at most three dimensions,
whereas it is NP-hard otherwise.
Tomohiro I, Wataru Matsubara, Kouji Shimohira, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Kazuyuki Narisawa and Ayumi Shinohara. Detecting regularities on grammar-compressed strings
Abstract: We solve the problems of detecting and counting various forms of regularities in a string represented as a Straight Line Program (SLP). Given an SLP of size $n$ that represents a string $s$ of length $N$, our algorithm compute all runs and squares in $s$ in $O(n^3h)$ time and $O(n^2)$ space, where $h$ is the height of the derivation tree of the SLP. We also show an algorithm to compute all gapped-palindromes in $O(n^3h + gnh\log N)$ time and $O(n^2)$ space, where $g$ is the length of the gap. The key technique of the above solution also allows us to compute the periods and covers of the string in $O(n^2 h)$ time and $O(nh(n+\log^2 N))$ time, respectively.
Giorgio Bacci, Giovanni Bacci, Kim Guldstrand Larsen and Radu Mardare. Computing Behavioral Distances, Compositionally
Abstract: We propose a general definition of composition operator on Markov Decision Processes with rewards (MDPs) and identify a well behaved class of operators, called safe, that are guaranteed to be non-extensive w.r.t. the bisimilarity pseudometrics of Ferns et al., which measure behavioral similarities between MDPs. For MDPs built using safe/non-extensive operators, we present the first method that exploits the structure of the system for (exactly) computing the bisimilarity distance on MDPs. Experimental results show significant improvements upon the non-compositional technique.
Karl Bringmann. Bringing Order to Special Cases of Klee's Measure Problem
Abstract: Klee's Measure Problem (KMP) asks for the volume of the union of n axis-aligned boxes in d-space. Omitting logarithmic factors, the best algorithm has runtime O*(n^{d/2}) [Overmars,Yap'91]. There are faster algorithms known for several special cases: Cube-KMP (where all boxes are cubes), Unitcube-KMP (where all boxes are cubes of equal side length), Hypervolume (where all boxes share a vertex), and k-Grounded (where the projection onto the first k dimensions is a Hypervolume instance).

In this paper we bring some order to these special cases by providing reductions among them. In addition to the trivial inclusions, we establish Hypervolume as the easiest of these special cases, and show that the runtimes of Unitcube-KMP and Cube-KMP are polynomially related.
More importantly, we show that any algorithm for one of the special cases with runtime T(n,d) implies an algorithm for the general case with runtime T(n,2d), yielding the first non-trivial relation between KMP and its special cases. This allows to transfer W[1]-hardness of KMP to all special cases, proving that no n^{o(d)} algorithm exists for any of the special cases assuming the Exponential Time Hypothesis. Furthermore, assuming that there is no "improved" algorithm for the general case of KMP (no algorithm with runtime O(n^{d/2 - eps})) this reduction shows that there is no algorithm with runtime O(n^{(d-1)/4 - eps}) for any of the special cases. Under the same assumption we show a tight lower bound for a recent algorithm for 2-Grounded [Yildiz,Suri'12].
Robert Ganian, Friedrich Slivovsky and Stefan Szeider. Meta-Kernelization with Structural Parameters
Abstract: Meta-kernelization theorems are general results that provide polynomial kernels for large classes of parameterized problems. The known meta-kernelization theorems, in particular the results of Bodlaender et al. (FOCS'09) and of Fomin et al. (FOCS'10), apply to optimization problems parameterized by solution size. We present meta-kernelization theorems that use a structural parameters of the input and not the solution size. Let C be a graph class. We define the C-cover number of a graph to be a the smallest number of modules the vertex set can be partitioned into such that each module induces a subgraph that belongs to the class C.
We show that each graph problem that can be expressed in Monadic Second Order (MSO) logic has a polynomial kernel with a linear number of vertices when parameterized by the C-cover number for any fixed class C of bounded rank-width (or equivalently, of bounded clique-width, or bounded Boolean width). Many graph problems such as Independent Dominating Set, c-Coloring, and c-Domatic Number are covered by this meta-kernelization result.

Our second result applies to MSO expressible optimization problems, such as Minimum Vertex Cover, Minimum Dominating Set, and Maximum Clique. We show that these Problems admit a polynomial annotated kernel with a linear number of vertices.
Wojciech Czerwinski, Petr Jancar, Martin Kot and Zdenek Sawa. Complexity of Checking Bisimilarity between Sequential and Parallel Processes
Abstract: Decidability of bisimilarity for Process Algebra (PA) processes, arising by
mixing sequential and parallel composition, is a long-standing open
problem. The known results for subclasses contain the decidability of
bisimilarity between basic sequential (i.e. BPA) processes and basic
parallel processes (BPP). Here we revisit this subcase and derive an
exponential-time upper bound. Moreover, we show that the problem if a
given basic parallel process is inherently sequential, i.e. bisimilar
with an unspecified BPA process, is PSPACE-complete.
Alexander Rabinovich. An Unusual Temporal Logic
Abstract: Kamp's theorem states that
the temporal logic with modalities Until and Since has the same expressive power as the First-Order Monadic
Logic of Order (FOMLO) over Real and Natural time
flows. Kamp notes that
there are expressions which deserve to be regarded as tense operators but are not representable within FOMLO.
The words `mostly' and `usually' are examples of such expressions. We propose a formalization of `usually' as a generalized Mostowski quantifier
and prove an analog of Kamp's theorem.
Andrew Goldberg, Ilya Razenshteyn and Ruslan Savchenko. Separating Hierarchical and General Hub Labelings
Abstract: In the context of distance oracles, a labeling algorithm computes vertex labels during preprocessing. An s; t query computes the corresponding distance from the labels of s and t only, without looking at the input graph. Hub labels is a class of labels that has been extensively studied. Performance of the hub label query depends on the label size. Hierarchical labels are a natural special kind of hub labels. These labels are related to other problems and can be computed more efficiently. This brings up a natural question of the quality of hierarchical labels. We show that there is a gap: optimal hierarchical labels can be polynomially bigger than the general hub labels. To prove this result, we give tight upper and lower bounds on the size of hierarchical and general labels for hypercubes.
John Hitchcock and A Pavan. Length-Increasing Reductions for PSPACE-Completeness
Abstract: Polynomial-time many-one reductions provide the standard notion of completeness for complexity classes. However, as first explicated by Berman and Hartmanis in their work on the isomorphism conjecture, all natural complete problems are actually complete under reductions with stronger properties. We study the length-increasing property and show under various computational hardness assumptions that all PSPACE-complete problems are complete via length-increasing reductions that are computable with a small amount of nonuniform advice.

If there is a problem in PSPACE that requires exponential time, then polynomial size advice suffices to give length-increasing reduction to all PSPACE-complete sets. Under the stronger assumption that linear space requires exponential-size NP-oracle circuits, we reduce the advice to logarithmic size. Our proofs make use of pseudorandom generators, hardness versus randomness tradeoffs, and worst-case to average-case hardness reductions.
Shenwei Huang. Improved Complexity Results on $k$-Coloring $P_t$-Free Graphs
Abstract: A graph is $H$-free if it does not contain an induced subgraph isomorphic to $H$. We denote by $P_k$ the path on $k$ vertices. In this paper, we prove that 4-COLORING is NP-complete for $P_7$-free graphs, and that 5-COLORING is NP-complete for $P_6$-free graphs. The second result is the first NP-completeness shown for any $k$-COLORING of $P_6$-free graphs. These two results improve two previously best results and almost complete the classification of complexity of $k$-COLORING $P_t$-free graphs for $k\ge 4$ and $t\ge 1$, leaving as the only missing case 4-COLORING $P_6$-free graphs. Our NP-completeness results use a general framework, which we show is not sufficient to prove the NP-completeness of 4-COLORING $P_6$-free graphs. We expect that 4-COLORING is polynomial solvable for $P_6$-free graphs.
Johannes Köbler, Sebastian Kuhnert and Oleg Verbitsky. Helly Circular-Arc Graph Isomorphism is in Logspace
Abstract: We present logspace algorithms for the canonical labeling problem and the representation problem of Helly circular-arc (HCA) graphs. The first step is a reduction to canonical labeling and representation of interval intersection matrices. In a second step, the Delta trees employed in McConnell's linear time representation algorithm for interval matrices are adapted to the logspace setting and endowed with additional information to allow canonization. As a consequence, the isomorphism and recognition problems for HCA graphs turn out to be logspace complete.
Sebastian Bala. Which Finitely Ambiguous Automata Recognize Finitely Sequential Functions?
Abstract: Weighted automata, especially min-plus automata that
operate over the tropical semiring, have both a beautiful
theory and important practical applications. In particular,
if one could find a sequential or finitely sequential
equivalent to a given (or learned) min-plus automaton, one
could increase performance in several applications. But this
question has long remained open even as a decision problem.
We show that existence of a finitely sequential equivalent for
a given finitely ambiguous min-plus automaton is decidable.
Arnold Beckmann, Pavel Pudlák and Neil Thapen. Parity Games and Propositional Proofs
Abstract: A propositional proof system is weakly automatizable if there
is a polynomial time algorithm which separates satisfiable formulas from
formulas which have a short refutation in the system, with respect to a
given length bound. We show that if the resolution proof system is weakly
automatizable, then parity games can be decided in polynomial time. We
also define a combinatorial game which can be decided in polynomial
time if and only if resolution is weakly automatizable.
Orna Kupferman and Jonathan Mosheiff. Prime Languages
Abstract: We say that a deterministic finite automaton (DFA) $\A$ is {\em composite\/} if there are DFAs $\A_1,\ldots,\A_t$ such that $L(\A) = \bigcap_{i=1}^t L(\A_i)$ and the index of every $\A_i$ is strictly smaller than the index of $\A$. Otherwise, $\A$ is {\em prime}. We study the problem of deciding whether a given DFA is composite, the number of DFAs required in a decomposition, methods to prove primality, and structural properties of DFAs that make the problem simpler or are retained in a decomposition.
Leonid Gurvits. A note on deterministic poly-time algorithms for partition functions associated with bipartite graphs with given degrees.
Abstract: We prove a new efficiently computable lower bound on the coefficients of stable homogeneous polynomials and present its algorthmic and combinatorial applications.
Alain Finkel, Stefan Göller and Christoph Haase. Reachability in Register Machines with Polynomial Updates
Abstract: This paper introduces a class of register machines whose registers can be updated by polynomial functions when a transition is taken, and the domain of the registers can be constrained by linear constraints. This model strictly generalises a variety of known formalisms such as various classes of Vector Addition Systems with States. Our main result is that reachability in our class is PSPACE-complete when restricted to one register. We moreover give a classification of the complexity of reachability according to the type of polynomials allowed and the geometry induced by the range-constraining formula.
Harry Buhrman, Lance Fortnow, John M. Hitchcock and Bruno Loff. Learning Reductions to Sparse Sets
Abstract: We study the consequences of NP having non-uniform polynomial size circuits of various types. We continue the work of Agrawal and Arvind (1996) who study the consequences of SAT being many-one reducible to functions computable by non-uniform circuits consisting of a single weighted threshold gate (SAT many-one reduces to LT). They claim that as a consequence P = NP follows, but unfortunately their proof was incorrect.

We take up this question and use results from computational learning theory to show that if SAT many-one reduces to LT then PH = P^NP.

We furthermore show that if SAT disjunctive truth-table (or majority truth-table) reduces to a sparse set then SAT many-one reduces to LT and hence a collapse of PH to P^NP also follows. Lastly we show several interesting consequences if SAT disunctive truth-table reduces to a sparse set.
Ranko Lazic, Joel Ouaknine and James Worrell. Zeno, Hercules and the Hydra: Downward Rational Termination Is Ackermannian
Abstract: Metric temporal logic (MTL) is one of the most prominent specification formalisms for real-time systems. Over infinite timed words, full MTL is undecidable, but satisfiability for its safety fragment was proved decidable several years ago. The problem is also known to be equivalent to a fair termination problem for a class of channel machines with insertion errors. However, the complexity has remained elusive, except for a non-elementary lower bound. Via another equivalent problem, namely termination for a class of rational relations, we show that satisfiability for safety MTL is not primitive recursive, yet is Ackermannian, i.e., among the simplest non-primitive recursive problems. This is surprising since decidability was originally established using Higman's Lemma, suggesting a much higher non-multiply recursive complexity.
Andreas Krebs, Nutan Limaye, Meena Mahajan and Karteek Sreenivasaiah. Small Depth Proof Systems
Abstract: A proof system for a language L is a function f such that
Range(f) is exactly L. In this paper, we look at proof
systems from a circuit complexity point of view and study
proof systems that are computationally very restricted. The
restriction we study is: they can be computed by bounded fanin
circuits of constant depth (NC^0), or of O(log log n)
depth but with O(1) alternations (polylogAC^0). Each
output bit depends on very few input bits; thus such proof
systems correspond to a kind of local error-correction on a
theorem-proof pair.

We identify exactly how much power we need for proof systems
to capture all regular languages. We show that all regular
language have polylogAC^0 proof systems, and from a
previous result (Beyersdorff et al, MFCS 2011, where NC^0
proof systems were first introduced), this is tight. Our
technique also shows that MAJ has polylogAC^0 proof

We explore the question of whether TAUT has NC^0 proof
systems. Addressing this question about 2TAUT, and since
2TAUT is closely related to reachability in graphs, we ask
the same question about Reachability. We show that both
Undirected Reachability and Directed UnReachability have
NC^0 proof systems, but Directed Reachability is still

In the context of how much power is needed for proof systems
for languages in NP, we observe that proof systems for a
good fraction of languages in NP do not need the full power
of AC^0; they have SAC^0 or co-SAC^0 proof systems
P. Buckheister and Georg Zetzsche. Semilinearity and Context-Freeness of Languages Accepted by Valence Automata
Abstract: Valence automata are a generalization of various models of automata with
storage. Here, each edge carries, in addition to an input word, an element of
a monoid. A computation is considered valid if multiplying the monoid elements
on the visited edges yields the identity element. By choosing appropriate
monoids, a variety of automata models can be obtained as special valence

This work is concerned with the accepting power of valence automata.
Specifically, we ask for which monoids valence automata can accept only
context-free languages or only languages with semilinear Parikh image,

First, we present a characterization of those graph products (of monoids) for
which valence automata accept only context-free languages. Second, we provide a
necessary and sufficient condition for a graph product of copies of the
bicyclic monoid and the integers to yield only languages with semilinear Parikh
image when used as a storage mechanism in valence automata. Third, we show that
all languages accepted by valence automata over torsion groups have a
semilinear Parikh image.
Martin Huschenbett and Jiamou Liu. A Polychromatic Ramsey Theory for Ordinals
Abstract: The Ramsey degree of an ordinal $\alpha$ is the least number $n$ such that any colouring of the edges of the complete graph on $\alpha$ using finitely many colours contains an $n$-chromatic clique of order type $\alpha$. The Ramsey degree exists for any ordinal $\alpha<\omega^\omega$. We provide an explicit expression for computing the Ramsey degree given $\alpha$. We further establish a version of this result for automatic structures. In this version the ordinal and the colouring are presentable by finite automata and the clique is additionally required to be regular. The corresponding automatic Ramsey degree turns out to be greater than the set theoretic Ramsey degree. Finally, we demonstrate that a version for computable structures fails.
Eric Angel, Evripidis Bampis, Alexander Kononov, Dimitris Paparas, Emmanouil Pountourakis and Vassilis Zissimopoulos. Clustering on k-edge-colored graphs
Abstract: We study the Max k-colored clustering problem, where, given
an edge-colored graph with k colors, we seek to find a clustering of the
vertices maximizing the number (or the weight) of matched edges, i.e.
the edges whose extremities are colored with the same color as them. We
show that the cardinality problem is NP-hard even for edge-colored bipartite
graphs with a chromatic degree equal to two and k >=3. Our main
result is a constant approximation algorithm for the weighted version of
the Max k-colored clustering problem which is based on a rounding of
a natural linear programming relaxation. For graphs with chromatic degree
equal to two, we improve this ratio by exploiting the relation of our
problem with the Max 2-and problem. We also present a reduction to
the maximum-weight independent set (IS) problem in bipartite graphs
which leads to a polynomial time algorithm for the case of two colors.
Prachi Goyal, Vikram Kamat and Neeldhara Misra. On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem
Abstract: We investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer $q\geq 2$ and graph $G$, the goal is to find a coloring of the edges of $G$ with the maximum number of colors such that every vertex of the graph sees at most $q$ colors. This problem is NP-hard for $q \geq 2$, and has been well-studied from the point of view of approximation. Our main focus is the case when $q=2$, which is already theoretically intricate and practically relevant. We show fixed-parameter tractable algorithms for both the standard and the dual parameter, and for the latter problem, the result is based on a cubic problem kernel.
Thomas Place, Lorijn van Rooijen and Marc Zeitoun. Separating regular languages by piecewise testable and unambiguous languages
Abstract: Separation is a classical problem asking whether, given two sets belonging to some class, it is possible to separate them by s set from a smaller class. We discuss the separation problem for regular languages. We give a PTIME algorithm to check whether two given regular languages are separable by a piecewise testable language, that is, whether a B\Sigma_1(<) sentence can witness that the languages are disjoint. The proof refines an algebraic argument from Almeida and the third author. When separation is possible, we also express a separator by saturating one of the original languages by a suitable congruence. Following the same line, we show that one can as well decide whether two regular languages can be separated by an FO2(<)-definable language, albeit with a higher complexity.
Taolue Chen, Vojtech Forejt, Marta Kwiatkowska, Aistis Simaitis and Clemens Wiltsche. On Stochastic Games with Multiple Objectives
Abstract: We study two-player stochastic games, where the goal of one player is to satisfy a formula given as a boolean combination of expected total reward objectives and the behaviour of the second player is adversarial. Such games are important for modelling, synthesis and verification of open systems with stochastic behaviour. We show that finding a winning strategy is PSPACE-hard in general and undecidable for deterministic strategies. We also prove that optimal strategy, if such exists, may require infinite memory and randomisation. However, when restricted to disjunctions of objectives only, memoryless deterministic strategies suffice, and the problem of deciding whether a winning strategy exists is NP-complete. We also present algorithms to approximate the Pareto sets of achievable objectives for the class of stopping games.
Sarel Cohen, Amos Fiat, Moshik Hershcovitch and Haim Kaplan. Minimal Indices for Successor Search [Best paper award (joint)]
Abstract: We give a new successor data structure which improves upon the index size of the Patrascu-Thorup data structures, reducing the index size from O(nw^{4/5}) bits to O(n log w) bits, with optimal probe complexity. Alternately, our new data structure can be viewed as matching the space complexity of the (probe-suboptimal) z-fast trie of Belazzougui et al. Thus, we get the best of both approaches with respect to both probe count and index size. The penalty we pay is an extra O(log w) inter-register operations. Our data structure can also be used to solve the weak prefix search problem, the index size of O(n log w) bits is known to be optimal for any such data structure.
The technical contributions include highly efficient single word indices, with out-degree w/log w (compared to the w^{1/5} out-degree of fusion tree based indices). To construct such high efficiency single word indices we device highly efficient bit selectors which, we believe, are of independent interest.