Theory and Applications of Models of Computation

In this talk we shall first give a brief review of a quantitative approach to understanding neural computation [4-6]. We target so-called

random access

tasks, defined as those in which one instance of a task execution may need to access arbitrary combinations of items in memory. Such tasks are communication intensive, and therefore the known severe constraints on connectivity in the brain can inform their analysis.

A large class of problems in AI and other areas of computer science can be viewed as constraint-satisfaction problems. This includes problems in database query optimization, machine vision, belief maintenance, scheduling, temporal reasoning, type reconstruction, graph theory, and satisfiability. All of these problems can be recast as questions regarding the existence of homomorphisms between two directed graphs. It is well-known that the constraint-satisfaction problem is NP-complete. This motivated an extensive research program into identify tractable cases of constraint satisfaction.

This research proceeds along two major lines. The first line of research focuses on non-uniform constraint satisfaction, where the target graph is fixed. The goal is to identify those target graphs that give rise to a tractable constraint-satisfaction problem. The second line of research focuses on identifying large classes of source graphs for which constraint-satisfaction is tractable. We show in how tools from graph theory, universal algebra, logic, and complexity theory, shed light on the tractability of constraint satisfaction.

Process description languages, such as the picalculus [SW01], offer the possibility of formally describing system behaviour at varying levels of abstraction, and applying logical techniques to verify this behaviour.

But system behaviour often depends on environmental considerations. What a system can do depends on the current context in which it finds itself. It is this context which determines what information is available to the system, and therefore affects its future evolution. In a dual manner the current context determines the knowledge of the system which is available to its environment, and thus affects the use which can be made of the system. Moreover this interplay between a system and its environment is dynamic, changing as either or both evolve.

In this talk I will offer a survey of recent work on behavioural theories of systems in which their environments play a crucial role. We will see three instances in which environmental knowledge involves key features of

distributed

systems.

Access control

: Capabilities on resources and access rights to sites are determined by a static type system, [HRY05]; only partial knowledge of these types are available to the environment.

Network failure

: Systems run on a dynamically changing network of inter-connected nodes, where both the nodes and the connections are subject to failure, [FH08]; this network is shared between the system and its environment.

Resource cost

: Use of resources entail a cost, which must be borne by the processes responsible, [HG08]; the environment determines the overall funds available to processes for access to resources.

The focus will be on a particular process description language called Dpi [Hen07], oriented towards distributed systems.

Information content of a pool of sequences has been defined in information theory through enthropic measures aimed to capture the amount of variability within sequences. When dealing with biological sequences coding for proteins, a first approach is to align these sequences to estimate the probability of each amino-acid to occur within alignment positions and to combine these values through an “entropy” function whose minimum corresponds to the case where for each position, each amino-acid has the same probability to occur. This model is too restrictive when the purpose is to evaluate sequence constraints that have to be conserved to maintain the function of the proteins under random mutations. In fact, co-evolution of amino-acids appearing in pairs or tuplets of positions in sequences constitutes a fine signal of important structural, functional and mechanical information for protein families. It is clear that classical information theory should be revisited when applied to biological data. A large number of approaches to co-evolution of biological sequences have been developed in the last seven years. We present a few of them, discuss their limitations and some related questions, like the generation of random structures to validate predictions based on co-evolution, which appear crucial for new advances in structural bioinformatics.

Computability concerns information with a causal – typically algorithmic – structure. As such, it provides a schematic analysis of many naturally occurring situations. We look at ways in which computability-theoretic structure emerges in natural contexts. We will look at how algorithmic structure does not just emerge mathematically from information, but how that emergent structure can model the emergence of very basic aspects of the real world.

The need of formalizing a satisfactory notion of relative computability of partial functions leads to enumeration reducibility, which can be viewed as computing with nondeterministic Turing machines using positive information. This paper is dedicated to certain reducibilities that are stronger than enumeration reducibility, with emphasis given to s-reducibility,which appears often in computability theory and applications. We review some of the most notable properties of s-reducibility, together with the main differences distinguishing the s-degrees from the e-degrees, both at the global and local level.

We survey some practical techniques for designing fixed-parameter algorithms for NP-hard graph-modeled data clustering problems. Such clustering problems ask to modify a given graph into a union of dense subgraphs. In particular, we discuss (polynomial-time) kernelizations and depth-bounded search trees and provide concrete applications of these techniques. After that, we shortly review the use of two further algorithmic techniques, iterative compression and average parameterization, applied to graph-modeled data clustering. Finally, we address some challenges for future research.

We consider the problem of computing spanners of Euclidean graphs embedded in the 2-dimensional Euclidean plane. We present an

$O(n\lg{n})$

time algorithm that computes a spanner of a Euclidean graph that is of bounded degree and plane, where

n

is the number of points in the graph. Both upper bounds on the degree and the stretch factor significantly improve the previous bounds. We extend this algorithm to compute a bounded-degree plane

lightweight

spanner of a Euclidean graph.

Our results rely on elegant structural and geometric results that we develop. Moreover, our results can be extended to Unit Disk graphs under the local distributed model of computation.

We are reviewing recent advances in the run time analysis of search tree algorithms, including indications to open problems. In doing so, we also try to cover the historical dimensions of this topic.

In this paper, we present a survey of the approximability and fixed-parameter tractability results for some Exemplar Genomic Distance problems. We mainly focus on three problems: the exemplar breakpoint distance problem and its complement (i.e., the exemplar non-breaking similarity or the exemplar adjacency number problem), and the maximal strip recovery (MSR) problem. The following results hold for the simplest case between only two genomes (genomic maps)

${\cal G}$

and

${\cal H}$

, each containing only one sequence of genes (gene markers), possibly with repetitions.

1

For the general Exemplar Breakpoint Distance problem, it was shown that deciding if the optimal solution value of some given instance is zero is NP-hard. This implies that the problem does not admit any approximation, neither any FPT algorithm, unless P=NP. In fact, this result holds even when a gene appears in

${\cal G}$

(

${\cal H}$

) at most two times.

1

For the Exemplar Non-breaking Similarity problem, it was shown that the problem is linearly reducible from Independent Set. Hence, it does not admit any factor-

O

(

n

ε

) approximation unless P=NP and it is W[1]-complete (loosely speaking, there is no way to obtain an

O

(

n

o

(

k

)

) time exact algorithm unless FPT=W[1], here

k

is the optimal solution value of the problem).

1

For the MSR problem, after quite a lot of struggle, we recently showed that the problem is NP-complete. On the other hand, the problem was previously known to have a factor-4 approximation and we showed recently that it admits a simple FPT algorithm which runs in

O

(2

2.73

k

n

 + 

n

2

) time, where

k

is the optimal solution value of the problem.

We present a reduction procedure that takes an arbitrary instance of the 3-Set Packing problem and produces an equivalent instance whose number of elements is bounded by a quadratic function of the input parameter. Such parameterized reductions are known as kernelization algorithms, and each reduced instance is called a problem kernel. Our result improves on previously known kernelizations and can be generalized to produce improved kernels for the

r

-Set Packing problem whenever

r

is a fixed constant. Improved kernelization for

r

-Dimensional-Matching can also be inferred.

We show that, for any abstract complexity measure in the sense of Blum and for any computable function

f

(or computable operator

F

), the class of problems which are

f

-speedable (or

F

-speedable) does not have effective measure 0. On the other hand, for sufficiently fast growing

f

(or

F

), the class of the nonspeedable problems does not have effective measure 0 too. These results answer some questions raised by Calude and Zimand in [CZ96] and [Zim06]. We also give a short quantitative analysis of Borodin and Trakhtenbrot’s Gap Theorem which corrects a claim in [CZ96] and [Zim06].

Consider the longest path problem for directed acyclic graphs (DAGs), where a mutually independent random variable is associated with each of the edges as its edge length. Given a DAG

G

and any distributions that the random variables obey, let

F

MAX

(

x

) be the distribution function of the longest path length. We first represent

F

MAX

(

x

) by a repeated integral that involves

n

 − 1 integrals, where

n

is the order of

G

. We next present an algorithm to symbolically execute the repeated integral, provided that the random variables obey the standard exponential distribution. Although there can be

Ω

(2

n

) paths in

G

, its running time is bounded by a polynomial in

n

, provided that

k

, the cardinality of the maximum anti-chain of the incidence graph of

G

, is bounded by a constant. We finally propose an algorithm that takes

x

and

ε

> 0 as inputs and approximates the value of repeated integral of

x

, assuming that the edge length distributions satisfy the following three natural conditions: (1) The length of each edge (

v

i

,

v

j

) ∈ 

E

is non-negative, (2) the Taylor series of its distribution function

F

ij

(

x

) converges to

F

ij

(

x

), and (3) there is a constant

σ

that satisfies

$\sigma^p \le \left|\left(\frac{d}{dx}\right)^p F_{ij}(x)\right|$

for any non-negative integer

p

. It runs in polynomial time in

n

, and its error is bounded by

ε

, when

x

,

ε

,

σ

and

k

can be regarded as constants.

We investigate the complexity of hard counting problems that belong to the class #P but have easy decision version; several well-known problems such as #

Perfect Matchings

, #

DNFSat

share this property. We focus on classes of such problems which emerged through two disparate approaches: one taken by Hemaspaandra

et al.

[1] who defined classes of functions that count the size of intervals of ordered strings, and one followed by Kiayias

et al.

[2] who defined the class TotP, consisting of functions that count the total number of paths of NP computations. We provide inclusion and separation relations between TotP and interval size counting classes, by means of new classes that we define in this work. Our results imply that many known #P-complete problems with easy decision are contained in the classes defined in [1]—but are unlikely to be complete for these classes under certain types of reductions. We also define a new class of interval size functions which strictly contains FP and is strictly contained in TotP under reasonable complexity-theoretic assumptions. We show that this new class contains some hard counting problems.

A geometric spanning tree of a point set

S

is a tree whose vertex set is

S

and whose edge set is a set of non-crossing straight line segments with endpoints in

S

. Given a set of red points and a set of blue points in the plane, the red/blue spanning tree problem is to find a geometric spanning tree for red points and a geometric spanning tree for blue points such that the number of crossing points of the two trees is minimum. If no three points are collinear, we show that the minimum number of crossing points is completely determined by the number of maximal red chains on the convex hull of all red points and blue points. We design an optimal algorithm for constructing a geometric spanning tree of all the red points and a geometric spanning tree of all the blue points with the minimum number of crossing points. If collinear points are allowed, we prove that the problem of deciding whether there exists a geometric spanning path of all the red points and a geometric spanning path of all the blue points without crossing is NP-complete.

Priced Probabilistic Timed Automata (PPTA) extend timed automata with cost-rates in locations and discrete probabilistic branching. The model is a natural combination of Priced Timed Automata and Probabilistic Timed Automata. In this paper we focus on cost-bounded probabilistic reachability for PPTA, which determines if the maximal probability to reach a goal location within a given cost bound (and time bound) exceeds a threshold

p

 ∈ (0,1]. We prove undecidability of the problem for simple PPTA in 3 variants: with 3 clocks and stopwatch cost-rates or strictly positive cost-rates. Because we encode a 2-counter machine in a new way, we can also show undecidability for cost-rates in ℤ and only 2 clocks.

We explore a computational approach to proving

intractability

of certain counting problems. More specifically we study the complexity of Holant of 3-regular graphs. These problems include concrete problems such as counting the number of vertex covers or independent sets for 3-regular graphs. The high level principle of our approach is algebraic, which provides sufficient conditions for

interpolation

to succeed. Another algebraic component is

holographic reductions

. We then analyze in detail polynomial maps on ℝ

2

induced by some combinatorial constructions. These maps define sufficiently complicated

dynamics

of ℝ

2

that we can only analyze them computationally. We use both numerical computation (as intuitive guidance) and symbolic computation (as proof theoretic verification) to derive that a certain collection of combinatorial constructions, in myriad combinations, fulfills the algebraic requirements of proving #P-hardness. The final result is a dichotomy theorem for a class of counting problems.

The

$\mathcal{G}$

-width of a class of graphs

$\mathcal{G}$

is defined as follows. A graph

G

has

$\mathcal{G}$

-width

k

if there are

k

independent sets

$\mathbb{N}_1,\dots,\mathbb{N}_{\rm \tt k}$

in

G

such that

G

can be embedded into a graph

${\rm H \in \mathcal{G}}$

such that for every edge

e

in

H

which is not an edge in

G

, there exists an

i

such that both endpoints of

e

are in ℕ

i

. For the class

$\mathfrak{B}$

of block graphs we show that

$\mathfrak{B}$

-width is NP-complete and we present fixed-parameter algorithms.

The minimum vertex ranking spanning tree problem on graph

G

is to find a spanning tree

T

of

G

such that the minimum vertex ranking of

T

is minimum among all possible spanning trees of

G

. In this paper, we propose a linear-time algorithm for this problem on permutation graphs. It improves a previous result that runs in

O

(

n

3

) time where

n

is the number of vertices in the input graph.

In this paper, we show that special instances of parameterized NP-hard problems are as difficult as the general instances in terms of their subexponential time computability. For example, we show that the

Planar Dominating Set

problem on degree-3 graphs can be solved in

$2^{o(\sqrt{k})} p(n)$

parameterized time if and only if the general

Planar Dominating Set

problem can. Apart from their complexity theoretic implications, our results have some interesting algorithmic implications as well.

We study a new model of computation called

stream checking

on graph problems where a space-limited verifier has to verify a proof sequentially (i.e., it reads the proof as a stream). Moreover, the proof itself is nothing but a reordering of the input data. This model has a close relationship to many models of computation in other areas such as data streams, communication complexity, and proof checking and could be used in applications such as cloud computing.

In this paper we focus on graph problems where the input is a sequence of edges. We show that checking if a graph has a perfect matching is impossible to do deterministically using small space. To contrast this, we show that randomized verifiers are powerful enough to check whether a graph has a perfect matching or is connected.

We show that logical and behavioral equivalence for stochastic Kripke models over general measurable spaces are the same. Usually, this requires some topological assumptions and includes bisimilarity; the results here indicate that a measurable structure on the state space of the Kripke model suffices. In contrast to a paper by Danos et al. we focus on the measurable structure of the factor space induced by the logic. This technique worked well in the analytic case, and it is shown to work here as well. The main contribution of the paper is methodological, since it provides a uniform framework for general measurable as well as more specialized analytic spaces.

Haplotyping, also known as haplotype phase prediction, is the problem of predicting likely haplotypes from genotype data. One fast haplotyping method is based on an evolutionary model where a perfect phylogenetic tree is sought that explains the observed data. Unfortunately, when data entries are missing as is often the case in laboratory data, the resulting incomplete perfect phylogeny haplotyping problem

ipph

is NP-complete and no theoretical results are known concerning its approximability, fixed-parameter tractability, or exact algorithms for it. Even radically simplified versions, such as the restriction to phylogenetic trees consisting of just two directed paths from a given root, are still NP-complete; but here a fixed-parameter algorithm is known. We show that such drastic and ad hoc simplifications are not necessary to make

ipph

fixed-parameter tractable: We present the first theoretical analysis of an algorithm, which we develop in the course of the paper, that works for arbitrary instances of

ipph

. On the negative side we show that restricting the topology of perfect phylogenies does not always reduce the computational complexity: while the incomplete directed perfect phylogeny problem is well-known to be solvable in polynomial time, we show that the same problem restricted to path topologies is NP-complete.

For the weighted

r

D-Matching problem, we present a deterministic parameterized algorithm with time complexity

O

*

(4

(

r

 − 1)

k

), improving the previous best upper bound

O

*

(4

rk

). In particular, the algorithm can be applied to solve the unweighted 3D-Matching problem with time

O

*

(16

k

), improving the previous best result

O

*

(21.26

k

). For the weighted

r

-Set Packing problem, we present a deterministic parameterized algorithm with time complexity

O

*

(2

(2

r

 − 1)

k

), improving the previous best result

O

*

(2

2

rk

). The algorithm, when applied to the unweighted 3-Set Packing problem, has running time

O

*

(32

k

), improving the previous best result

O

*

(43.62

k

). Moreover, for the weighted

r

D-Matching and weighted

r

-Set Packing problems, we get a kernel of size

O

(

k

r

).

We compare the fixed parameter complexity of various variants of coloring problems (including

List Coloring, Precoloring Extension, Equitable Coloring,

L

(

p

,1)

-Labeling

and

Channel Assignment

) when parameterized by treewidth and by vertex cover number. In most (but not all) cases we conclude that parametrization by the vertex cover number provides a significant drop in the complexity of the problems.

We study a natural probabilistic model for motif discovery that has been used to experimentally test the effectiveness of motif discovery programs. In this model, there are

k

background sequences, and each character in a background sequence is a random character from an alphabet

Σ

. A motif

G

 = 

g

1

g

2

...

g

m

is a string of

m

characters. Each background sequence is implanted a probabilistically generated approximate copy of

G

. For a probabilistically generated approximate copy

b

1

b

2

...

b

m

of

G

, every character is probabilistically generated such that the probability for

b

i

 ≠ 

g

i

is at most

α

. It has been conjectured that multiple background sequences can help with finding faint motifs

G

.

In this paper, we develop an efficient algorithm that can discover a hidden motif from a set of sequences for any alphabet

Σ

with |

Σ

| ≥ 2 and is applicable to DNA motif discovery. We prove that for

$\alpha<{1\over 4}(1-{1\over |\Sigma|})$

and any constant

x

 ≥ 8, there exist positive constants

c

0

,

ε

,

δ

1

and

δ

2

such that if the length

ρ

of motif

G

is at least

δ

1

log

n

, and there are

k

 ≥ 

c

0

log

n

input sequences, then in

O

(

n

2

 + 

kn

) time this algorithm finds the motif with probability at least

$1-{1\over 2^x}$

for every

$G\in \Sigma^{\rho}-\Psi_{\rho, h,\epsilon}(\Sigma)$

, where

ρ

is the length of the motif,

h

is a parameter with

ρ

 ≥ 4

h

 ≥ 

δ

2

log

n

, and

Ψ

ρ

,

h

,

ε

(

Σ

) is a small subset of at most

$2^{-\Theta(\epsilon^2 h)}$

fraction of the sequences in

Σ

ρ

. The constants

c

0

,

ε

,

δ

1

and

δ

2

do not depend on

x

when

x

is a parameter of order

O

(log

n

). Our algorithm can take any number

k

sequences as input.

A

k

-path power is the

k

-power graph of a simple path of arbitrary length. Path powers form a non-trivial subclass of proper interval graphs. Their clique-width is not bounded by a constant, and no polynomial-time algorithm is known for computing their clique-width or linear clique-width. We show that

k

-path powers above a certain size have linear clique-width exactly

k

 + 2, providing the first complete characterisation of the linear clique-width of a graph class of unbounded clique-width. Our characterisation results in a simple linear-time algorithm for computing the linear clique-width of all path powers.

The retention of communication data has recently attracted much public interest, mostly because of the possibility of its misuse. In this paper, we present protocols that address the privacy concerns of the communication partners. Our data retention protocols store streams of encrypted data items, some of which may be flagged as critical (representing misbehavior). The frequent occurrence of critical data items justifies the self-decryption of all recently stored data items, critical or not. Our first protocol allows the party gathering the retained data to decrypt all data items collected within, say, the last half year whenever the number of critical data items reaches some threshold within, say, the last month. The protocol ensures that the senders of data remain anonymous but may reveal that different critical data items came from the same sender. Our second, computationally more complex scheme obscures this affiliation of critical data with high probability.

We introduce a method based on Kolmogorov complexity to prove lower bounds on communication complexity. The intuition behind our technique is close to information theoretic methods [1,2]. Our goal is to gain a better understanding of how information theoretic techniques differ from the family of techniques that follow from Linial and Shraibman’s work on factorization norms [3]. This family extends to quantum communication, which prevents them from being used to prove a gap with the randomized setting.

We use Kolmogorov complexity for three different things: first, to give a general lower bound in terms of Kolmogorov mutual information; second, to prove an alternative to Yao’s minmax principle based on Kolmogorov complexity; and finally, to identify worst case inputs.

We show that our method implies the rectangle and corruption bounds [4], known to be closely related to the subdistribution bound [2]. We apply our method to the hidden matching problem, a relation introduced to prove an exponential gap between quantum and classical communication [5]. We then show that our method generalizes the VC dimension [6] and shatter coefficient lower bounds [7]. Finally, we compare one-way communication and simultaneous communication in the case of distributional communication complexity and improve the previous known result [7].

Wang tiles are unit size squares with colored edges. In this paper, we approach one aspect of the study of tilings computability: the quest for a universal tile set. Using a complex construction, based on Robinson’s classical construction and its different modifications, we build a tile set

μ

(pronounced

ayin

) which

almost always

simulates any tile set. By way of Banach-Mazur games on tilings topological spaces, we prove that the set of

μ

-tilings which do not satisfy the universality condition is meager in the set of

μ

-tilings.

We provide polynomial time data reduction rules for

Connected Dominating Set

in planar graphs and analyze these to obtain a linear kernel for the planar

Connected Dominating Set

problem. To obtain the desired kernel we introduce a method that we call

reduce or refine

. Our kernelization algorithm analyzes the input graph and either finds an appropriate reduction rule that can be applied, or zooms in on a region of the graph which is more amenable to reduction. We find this method of independent interest and believe that it will be useful to obtain linear kernels for other problems on planar graphs.

In classical network flow theory the choice of paths, on which flow is sent, is only restricted by arc capacities. This, however, is not realistic in most applications. Many problems restrict, e.g., the number of paths being used to route a commodity. One idea to increase reliability of routings, e.g., in telecommunication, is to copy a demand and send the copies along disjoint paths. Such problems theoretically result in the

k

-disjoint flow problem (

k

-DFP). This problem is a variant of the classical multicommodity flow problem with the additional requirement that the number of paths to route a commodity is bounded by a given parameter. Moreover, all paths used by the same commodity have to be arc disjoint.

We present a simple greedy algorithm for the optimization version of the

k

-DFP where the objective is to maximize the sum of routed demands. This algorithm generalizes a greedy algorithm by Kolman and Scheideler (2002) that approximates the corresponding unsplittable flow problem, in which every commodity may be routed along a single path only. We achieve an approximation factor of

$O(k_{\text{max}} \sqrt{m}/k_{\text{min}})$

, where

m

is the number of arcs and

$k_{\text{max}}$

(

$k_{\text{min}}$

) is the maximum (minimum) bound on the number of paths allowed to route any of the commodities. We argue that this performance guarantee is best possible for instances where

$k_{\text{max}}/k_{\text{min}}$

is constant, unless

$\mathcal{P}=\mathcal{P}\mathcal{N}$

.

A minimum ESOP (Exclusive-OR Sum-of-Products) form of a logic function

f

is an AND-EXOR 2-level expression of

f

having the minimum number of product terms. In the paper we deal with multiple-valued 2-input logic functions

f

, and give an algorithm to find a minimum ESOP form of a given function

f

in polynomial time.

Even codes are Huffman based codes in which every encoding contains an even number of 1’s, thus having the ability of detecting the occurrence of an odd number of 1-bit errors in the message. The motivation for defining such codes comes from a problem posed by Hamming in 1980. Even codes have been studied for the case in which symbols have uniform probabilities. In this work, we consider the general situation of arbitrary probabilities. An exact algorithm for constructing an optimal even code is described with complexity

O

(

n

3

), where

n

is the number of symbols. Further, two heuristics for constructing nearly optimal even codes are presented, both requiring

O

(

n

log

n

) time. The cost of the even code constructed by the second heuristics is at most 16,7% higher than the cost of a Huffman code, for the same probabilities. However, computational experiments suggest that, for practical purposes, this value seems to be better: about 5% or less, for

n

large enough. This corresponds to the amount of redundancy to be added to the message in order to keep the ability of error detection. Concerning undetected errors, we obtain bounds on the probability of producing

k

consecutive erroneous symbols, suggesting that such a probability is small for large messages.

We use the Kolmogorov Consistency Theorem from Measure Theory to construct terminal coalgebras for a large class of functors on the category of measurable spaces. In particular, we construct terminal stochastic relations and terminal labelled Markov processes. We use this constructions to provide extended expressivity results for canonical interpretations of modal and temporal logics in these structures.

The natural embedding of the Turing degrees into the enumeration degrees preserves the jump operation, and maps isomorphically the computably enumerable Turing degrees onto the

${\it \Pi}^0_1$

enumeration degrees. The embedding does not preserve minimal pairs, though, unless one of the two sides is low. In particular it is known that there exist high minimal pairs of c.e. Turing degrees that do not embed to minimal pairs of e-degrees. We show however that high minimal pairs of

${\it \Pi}^0_1$

e-degrees do exist.

We consider the problem of searching for a mobile intruder in a

circular corridor

(a polygon with one polygonal hole) by two searchers, who hold a flashlight. Both searchers move on the outer boundary, directing their flashlights at the inner boundary. The objective is to decide whether there exists a

search schedule

for the searchers to detect the intruder, no matter how fast he moves. We give a characterization of the class of circular corridors, which are searchable with two flashlights. Based on our characterization, an

O

(

n

log

n

) time algorithm is then presented to determine the searchability of a circular corridor with two flashlights, where

n

denotes the total number of vertices of the outer and inner boundaries. Moreover, a search schedule can be output in time linear in its size, if it exists. Our result gives the first efficient solution to the polygon search problem for two searchers.

Given a universal constant

k

, the multiple Stack Travelling Salesman Problem (

k

STSP in short) consists in finding a pickup tour

T

1

and a delivery tour

T

2

of

n

items on two distinct graphs. The pickup tour successively stores the items at the top of

k

containers, whereas the delivery tour successively picks the items at the current top of the containers: thus, the couple of tours are subject to LIFO (

“Last In First Out”

) constraints. This paper aims at finely characterizing the complexity of

k

STSP in regards to the complexity of TSP. First, we exhibit tractable sub-problems: on the one hand, given two tours

T

1

and

T

2

, deciding whether

T

1

and

T

2

are compatible can be done within polynomial time; on the other hand, given an ordering of the

n

items into the

k

containers, the optimal tours can also be computed within polynomial time. Note that, to the best of our knowledge, the only family of combinatorial precedence constraints for which constrained TSP has been proven to be in

P

is the one of PQ-trees, [2]. Finally, in a more prospective way and having in mind the design of approximation algorithms, we study the relationship between optimal value of different TSP problems and the optimal value of

k

STSP.

We consider the feedback vertex set and feedback arc set problems in bipartite tournaments. We improve on recent results by giving a 2-approximation algorithm for the feedback vertex set problem. We show that this result is the best we can attain when using a certain linear program as the lower bound on the optimal value. For the feedback arc set problem in bipartite tournaments, we show that a recent 4-approximation algorithm proposed by Gupta [5,6] is incorrect. We give an alternative 4-approximation algorithm based on an algorithm for feedback arc set in (regular) tournaments in [10,11].

Spoken dialogue systems (SDSs) have been widely used in human-computer communications, including database querying, online trouble shooting advising, etc. A major challenge in building an SDS is to handle ambiguity in natural languages. User queries, questions, descriptions in a natural language may be ambiguous. To be effective in practical applications, an SDS must be able to disambiguate input from its user(s). In our research, we develop an online algorithm for applying reinforcement learning to handle ambiguity in SDSs. We introduce a new user dialogue policy into the framework of reinforcement learning to model user dialogue behavior. Also, differing from the current reinforcement learning algorithms in speech and language processing that are characterized by offline training, our algorithm conducts both offline and online detection of user dialogue behavior. In this paper, we present the online algorithm for reinforcement learning, emphasizing the detection of user dialogue behavior. We also describe the initial implementation and experiments.

In this paper, we present a fixed-parameter enumeration algorithm for the feedback vertex set problem by using the

branch-and-search

method. The algorithm transforms the feedback vertex set problem to the feedback edge set problem with specific conditions. Then it enumerates the

z

minimum-weight feedback edge sets by enumerating the

z

maximum-weight forests. As a result, we show the problem of enumerating the

z

minimum-weight feedback vertex sets of size

k

is solvable in time

$\mathcal {O}(5^{k}kn^{2}+(5^{k}+3^{k}z)n^{2}\log n)$

.

Given two genomic maps

G

and

H

represented by a sequence of

n

gene markers, a

strip

(syntenic block) is a sequence of distinct markers of length at least two which appear as subsequences in the input maps, either directly or in reversed and negated form. The problem

Maximal Strip Recovery

(MSR) is to find two subsequences

G

′ and

H

′ of

G

and

H

, respectively, such that the total length of disjoint strips in

G

′ and

H

′ is maximized (or, conversely, the number of markers hence deleted, is minimized). Previously, besides some heuristic solutions, a factor-4 polynomial-time approximation is known for the MSR problem; moreover, several close variants of MSR, MSR-

d

(with

d

 > 2 input maps), MSR-DU (with marker duplications) and MSR-WT (with markers weighted) are all shown to be NP-complete. Before this work, the complexity of the original MSR problem was left open. In this paper, we solve the open problem by showing that MSR is NP-complete, using a polynomial time reduction from One-in-Three 3SAT. We also solve the MSR problem and its variants exactly with FPT algorithms, i.e., showing that MSR is fixed-parameter tractable. Let

k

be the minimum number of markers deleted in various versions of MSR, the running time of our algorithms are

O

(2

2.73

k

n

 + 

n

2

) for MSR,

O

(2

2.73

k

dn

 + 

dn

2

) for MSR-

d

, and

O

(2

5.46

k

n

 + 

n

2

) for MSR-DU.

Recently, various randomized search heuristics have been studied for the solution of the minimum vertex cover problem, in particular for sparse random instances according to the

G

(

n

,

c

/

n

) model, where

c

 > 0 is a constant. Methods from statistical physics suggest that the problem is easy if

c

 < 

e

. This work starts with a rigorous explanation for this claim based on the refined analysis of the Karp-Sipser algorithm by Aronson et al. Subsequently, theoretical supplements are given to experimental studies of search heuristics on random graphs. For

c

 < 1, a greedy and randomized local-search heuristic finds an optimal cover in polynomial time with a probability arbitrarily close to 1. This behavior relies on the absence of a giant component. As an additional insight into the randomized search, it is shown that the heuristic fails badly also on graphs consisting of a single tree component of maximum degree 3.

The notion of superhigh computably enumerable (c.e.) degrees was first introduced by Mohrherr in [7], where she proved the existence of incomplete superhigh c.e. degrees, and high, but not superhigh, c.e. degrees. Recent research shows that the notion of superhighness is closely related to algorithmic randomness and effective measure theory. Jockusch and Mohrherr proved in [4] that the diamond lattice can be embedded into the c.e.

tt

-degrees preserving 0 and 1 and that the two atoms can be low. In this paper, we prove that the two atoms in such embeddings can also be superhigh.

Because of irreversibility of movements, motion planning on directed graphs is much more intricate than that on graphs. Recently we showed that the feasibility of motion planning on acyclic and strongly connected directed graphs can be decided in time

O

(

nm

) (

n

,

m

are respectively the number of vertices and arcs of the directed graph), but left the feasibility of motion planning on (general) directed graphs open. In this paper, we complete the solution by showing that the feasibility of motion planning on directed graphs can be decided in time

O

(

n

2

m

).

Translocation is a prevalent rearrangement event in the evolution of multi-chromosomal species which exchanges ends between two chromosomes. A translocation is reciprocal if none of the exchanged ends is empty; otherwise, non-reciprocal. Given two signed multi-chromosomal genomes

A

and

B

, the problem of sorting by translocations is to find a shortest sequence of translocations transforming

A

into

B

. Several polynomial algorithms have been presented, all of them only allowing reciprocal translocations. Thus they can only be applied to a pair of genomes having the same set of chromosome ends. Such a restriction can be removed if non-reciprocal translocations are also allowed. In this paper, for the first time, we study the problem of sorting by generalized translocations, which allows both reciprocal translocations and non-reciprocal translocations. We present an exact formula for computing the generalized translocation distance, which leads to a polynomial algorithm for this problem.

Consider a simple polygon. A walk is conducted by two guards on the polygon boundary. They start at a boundary point and walk on the boundary. It is required that the two guards maintain their mutual visibility at all times and eventually meet together again. A polygon may or may not be walkable, depending on where the two guards start their walk or no matter where they start on the boundary. In this work, we characterize the class of walkable polygons by two guards by presenting a set of forbidden patterns.

We investigate a natural combinatorial optimization problem called the

Label Cut

problem. Given an input graph

G

with a source

s

and a sink

t

, the edges of

G

are classified into different categories, represented by a set of

labels

. The labels may also have weights. We want to pick a subset of labels of minimum cardinality (or minimum total weight), such that the removal of all edges with these labels disconnects

s

and

t

. We give the first non-trivial approximation and hardness results for the Label Cut problem. Firstly, we present an

$O(\sqrt{m})$

-approximation algorithm for the Label Cut problem, where

m

is the number of edges in the input graph. Secondly, we show that it is

NP

-hard to approximate Label Cut within

$2^{\log ^{1 - 1/\log\log^c n} n}$

for any constant

c

 < 1/2, where

n

is the input length of the problem. Thirdly, our techniques can be applied to other previously considered optimization problems. In particular we show that the Minimum Label Path problem has the same approximation hardness as that of Label Cut, simultaneously improving and unifying two known hardness results for this problem which were previously the best (but incomparable due to different complexity assumptions).

Ostrovsky et al. [1] gave the first definition of non-malleable witness-indistinguishable argument systems. A surprising result given by them showed this notion was incomparable with the notion of non-malleable zero-knowledge. However, they only discussed their relations in the interactive setting. In this paper, we make an observation on relation between the two notions in the non-interactive setting. We show the two notions are still incomparable: that is, there are non-malleable non-interactive zero-knowledge proof systems that are not non-malleable non-interactive witness-indistinguishable, and vice versa.