Accepted Papers

A Planarity Test via Construction Sequences

Rent or buy problems with a fixed time horizon

Reversibility of computations in graph-walking automata

Parameterized Algorithms for Module Motif

Approximation Algorithms for Generalized Plant Location

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.

Logic and 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.

Feasible combinatorial matrix theory

Logical aspects of the lexicographic order on 1-counter languages

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

structures).

Reachability in Higher-Order Counters

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.

New Polynomial Cases of the Weighted Efficient Domination Problem

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.

Rewriting Guarded Negation Queries

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.

Guarding Orthogonal Art Galleries using Sliding Cameras: Algorithmic and Hardness Results

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).

Reachability analysis of recursive quantum Markov chains

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.

Paradigms for Parameterized Enumeration

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.

Arithmetic Branching Programs with Memory

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.

Improved bounds for reduction to depth 4 and depth 3 **[Best paper award (joint) + Best student paper award]**

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).

Probabilistic Automata with Isolated Cut-points

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.

On the speed of constraint propagation and the time complexity of arc consistency testing

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.

Linear-Space Data Structures for Range Frequency Queries on Arrays and Trees

On the Recognition of Four-Directional Orthogonal Ray Graphs

Solving 3-superstring in 3^{n/3} Time

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).

Hardness of Classically Simulating Quantum Circuits with Unbounded Toffoli and Fan-Out Gates

On the parameterized complexity of cutting a few vertices from a graph

- 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$.

Random Shortest Paths: Non-Euclidean Instances for Metric Optimization Problems

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.

On the quantifier-free dynamic complexity of Reachability

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.

A Constant Factor Approximation for the Generalized Assignment Problem with Minimum Quantities and Unit Size Items

By using randomized rounding, we obtain a randomized 3.93-approximation algorithm, thereby providing the first nontrivial approximation result for this problem.

Revisiting Space in Proof Complexity: Treewidth and Pathwidth

In-Place Binary Counters

A More Efficient Simulation Algorithm on Kripke Structures

Polynomial threshold functions and Boolean threshold circuits

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

interest.

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

circuits.

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.

Determinacy and Rewriting of Top-Down and MSO Tree Transformations

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.

Strong Completeness for Markovian 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.

Subexponential Algorithm for d-Cluster Edge Deletion: Exception or Rule?

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.

Space-Efficient Parallel Algorithms for Combinatorial Search Problems

On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant

Noninterference with Local Policies

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.

How to pack your items when you have to buy your knapsack

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.

Auctions for Partial Heterogeneous Preferences

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.

Validity of Tree Pattern Queries With Respect to Schema Information

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.

Unlimited decidability of distributed synthesis with limited missing knowledge

Ordering Metro Lines by Block Crossings

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.

A Refined Computational Complexity Analysis of Combinatorial Feature Selection Problems

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.

Detecting regularities on grammar-compressed strings

Computing Behavioral Distances, Compositionally

Bringing Order to Special Cases of Klee's Measure Problem

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].

Meta-Kernelization with Structural Parameters

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.

Complexity of Checking Bisimilarity between Sequential and Parallel Processes

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.

An Unusual Temporal Logic

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.

Separating Hierarchical and General Hub Labelings

Length-Increasing Reductions for PSPACE-Completeness

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.

Improved Complexity Results on $k$-Coloring $P_t$-Free Graphs

Helly Circular-Arc Graph Isomorphism is in Logspace

Which Finitely Ambiguous Automata Recognize Finitely Sequential Functions?

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.

Parity Games and Propositional Proofs

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.

Prime Languages

A note on deterministic poly-time algorithms for partition functions associated with bipartite graphs with given degrees.

Reachability in Register Machines with Polynomial Updates

Learning Reductions to Sparse Sets

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.

Zeno, Hercules and the Hydra: Downward Rational Termination Is Ackermannian

Small Depth Proof Systems

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

system.

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

open.

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

Semilinearity and Context-Freeness of Languages Accepted by Valence Automata

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

automata.

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,

respectively.

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.

A Polychromatic Ramsey Theory for Ordinals

Clustering on k-edge-colored graphs

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.

On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem

Separating regular languages by piecewise testable and unambiguous languages

On Stochastic Games with Multiple Objectives

Minimal Indices for Successor Search **[Best paper award (joint)]**

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.