Theory and Applications of Models of Computation

Over the past five years a new approach to privacy-preserving data analysis has born fruit [13, 18, 7, 19, 5, 37, 35, 8, 32]. This approach differs from much (but not all!) of the related literature in the statistics, databases, theory, and cryptography communities, in that a formal and

ad omnia

privacy guarantee is defined, and the data analysis techniques presented are rigorously proved to satisfy the guarantee. The key privacy guarantee that has emerged is

differential privacy

. Roughly speaking, this ensures that (almost, and quantifiably) no risk is incurred by joining a statistical database.

In this survey, we recall the definition of differential privacy and two basic techniques for achieving it. We then show some interesting applications of these techniques, presenting algorithms for three specific tasks and three general results on differentially private learning.

If we measure the position of a point particle, then we will come about with an interval [

a

n

,

b

n

] into which the point falls. We make use of a

Gedankenexperiment

to find better and better values of

a

n

and

b

n

, by reducing their relative distance, in a succession of intervals [

a

1

,

b

1

] ⊃ [

a

2

,

b

2

] ⊃ ... ⊃ [

a

n

,

b

n

] that contain the point. We then use such a point as an oracle to perform relative computation in polynomial time, by considering the succession of approximations to the point as suitable answers to the queries in an oracle Turing machine. We prove that, no matter the precision achieved in such a

Gedankenexperiment

, within the limits studied, the Turing Machine, equipped with such an oracle, will be able to compute above the classical Turing limit for the polynomial time resource, either generating the class

P

/

poly

either generating the class

BPP

//

log

*, if we allow for an arbitrary precision in measurement or just a limited precision, respectively. We think that this result is astonishingly interesting for Classical Physics and its connection to the Theory of Computation, namely for the implications on the nature of space and the perception of space in Classical Physics. (Some proofs are provided, to give the flavor of the subject. Missing proofs can be found in a detailed long report at the address

http://fgc.math.ist.utl.pt/papers/sm.pdf

.)

In this survey paper we give an intuitive treatment of the discrete time quantization of classical Markov chains. Grover search and the quantum walk based search algorithms of Ambainis, Szegedy and Magniez et al. will be stated as quantum analogues of classical search procedures. We present a rather detailed description of a somewhat simplified version of the MNRS algorithm. Finally, in the query complexity model, we show how quantum walks can be applied to the following search problems: Element Distinctness, Matrix Product Verification, Restricted Range Associativity, Triangle, and Group Commutativity.

This paper investigates the language class defined by Propositional Projection Temporal Logic with star (PPTL with star). To this end, B

ü

chi automata are first extended with stutter rule (SBA) to accept finite words. Correspondingly,

ω

-regular expressions are also extended (ERE) to express finite words. Consequently, by three transformation procedures between PPTL with star, SBA and ERE, PPTL with star is proved to represent exactly the full regular language.

Reversal, transposition and transreversal are common events in genome rearrangement. The genome rearrangement sorting problem is to transform one genome into another using the minimum number of rearrangement operations. Hannenhalli and Pevzner discovered that singleton is the major obstacle for unsigned reversal sorting. They also gave a polynomial algorithm for reversal sorting on those unsigned permutations with

O

(log

n

) singletons. This paper involves two aspects. (1) We describe one case for which Hannenhalli and Pevzner’s algorithm may fail, and propose a corrected algorithm for unsigned reversal sorting. (2) We propose a (1 + 

ε

)-approximation algorithm for the weighted sorting problem on unsigned permutations with

O

(log

n

) singletons. The weighted sorting means: sorting a permutation by weighted reversals, transpositions and transreversals, where reversal is assigned weight 1 and transposition(including transreversal) is assigned weight 2.

We show that several problems that figure prominently in quantum computing, including

Hidden Coset

,

Hidden Shift

, and

Orbit Coset

, are equivalent or reducible to

Hidden Subgroup

. We also show that, over permutation groups, the decision version and search version of

Hidden Subgroup

are polynomial-time equivalent. For

Hidden Subgroup

over dihedral groups, such an equivalence can be obtained if the order of the group is smooth. Finally, we give nonadaptive program checkers for

Hidden Subgroup

and its decision version.

Packing problems have formed an important class of NP-hard problems. In this paper, we provide further theoretical study on the structure of the problems, and design improved algorithm for packing problems. For the 3-Set Packing problem, we present a deterministic algorithm of time

O

*

(3.52

3

k

), which significantly improves the previous best algorithm of time

O

*

(4.61

3

k

).

The “richness” of properties that are indistinguishable from first-order properties is investigated. Indistinguishability is a concept of equivalence among properties of combinatorial structures that is appropriate in the context of testability. All formulas in a restricted class of second-order logic are shown to be indistinguishable from first-order formulas. Arbitrarily hard properties, including RE-complete properties, that are indistinguishable from first-order formulas are shown to exist. Implications on the search for a logical characterization of the testable properties are discussed.

In this article, we study the randomness-efficient graph tests for homomorphism over arbitrary groups (which can be used in locally testing the Hadamard code and PCP construction). We try to optimize both the amortized-tradeoff (between number of queries and error probability) and the randomness complexity of the homomorphism test simultaneously. For an abelian group

$G=\mathbb Z_{p}^{m}$

, by using the

λ

-biased set

S

of

G

, we show that, on any given bipartite graph

H

 = (

V

1

,

V

2

;

E

), the graph test for linearity over

G

is a test with randomness complexity |

V

1

|log|

G

| + |

V

2

|

O

(log|

S

|), query complexity |

V

1

| + |

V

2

| + |

E

| and error probability at most

p

− |

E

|

 + (1 − 

p

− |

E

|

)·

δ

for any

f

which is

$1-p^{-1}(1+\frac{\sqrt{\delta^{2}-\lambda}}{2})$

-far from being affine linear. For a non-abelian group

G

, we introduce a random walk of some length, ℓ say, on expander graphs to design a probabilistic homomorphism test over

G

with randomness complexity log|

G

| + 

O

(loglog|

G

|), query complexity 2ℓ + 1 and error probability at most

$1- \frac{\displaystyle\delta^{2}\ell^{2}}{\displaystyle(\delta\ell+\delta^{2}\ell^{2}- \delta^{2}\ell)+2\psi(\lambda,\ell)}$

for any f which is 2

δ

/(1 − 

λ

)-far from being affine homomorphism, here

$\psi(\lambda,\ell)=\sum_{0\leq i<j\leq\ell-1}\lambda^{j-i-1}$

.

In this article, we show that there exist c.e. bounded Turing degrees

$\textbf{a}$

,

$\textbf{b}$

such that

0 < a

 < 0

′

, and that for any c.e. bounded Turing degree

$\textbf{x}$

,

${\bf b\lor x=0^{'}}$

if and only if

$\textbf{x}\geq\textbf{a}$

. The result gives an unexpected definability theorem in the structure of bounded Turing reducibilities.

An

H

(

p

,

q

)-labeling of a graph

G

is a vertex mapping

f

:

V

G

→

V

H

such that the distance between

f

(

u

) and

f

(

v

) (measured in the graph

H

) is at least

p

if the vertices

u

and

v

are adjacent in

G

, and the distance is at least

q

if

u

and

v

are at distance two in

G

. This notion generalizes the notions of

L

(

p

,

q

)- and

C

(

p

,

q

)-labelings of graphs studied as particular graph models of the Frequency Assignment Problem. We study the computational complexity of the problem of deciding the existence of such a labeling when the graphs

G

and

H

come from restricted graph classes. In this way we extend known results for linear and cyclic labelings of trees, with a hope that our results would help to open a new angle of view on the still open problem of

L

(

p

,

q

)-labeling of trees for fixed

p

 > 

q

 > 1 (i.e., when

G

is a tree and

H

is a path).

We present a polynomial time algorithm for

H

(

p

,1)-labeling of trees for arbitrary

H

. We show that the

H

(

p

,

q

)-labeling problem is

NP

-complete when the graph

G

is a star. As the main result we prove

NP

-completeness for

H

(

p

,

q

)-labeling of trees when

H

is a symmetric

q

-caterpillar.

This paper is part of a research on static analysis in order to predict program resources and belongs to the implicit computational complexity line of research. It presents intrinsic characterizations of the classes of functions, which are computable in

$\textit{NC}^{\textit{k}}$

, that is by a uniform, poly-logarithmic depth and polynomial size family of circuits, using first order functional programs. Our characterizations are new in terms of first order functional programming language and extend the characterization of

$\textit{NC}^{\textit{1}}$

in [9]. These characterizations are obtained using a complexity measure, the sup-interpretation, which gives upper bounds on the size of computed values and captures a lot of program schemas.

We introduce a new subrecursive degree structure:

the structure of detour degrees

. We provide definitions and basic properties of the detour degrees, including that they form a lattice and admit a jump operator. Our degree structure sheds light upon the open problems involving the small Grzegorcyk classes. There are also connections to complexity theory and complexity classes defined by resource-bounded Turing machines.

In this paper, we sketch structure characterization of a class of networks, called Matching Composition Networks (MCNs), to establish necessary conditions for determining the conditional fault hamiltonicity. We then apply our result to

n

-dimensional restricted hypercube-like networks, including

n

-dimensional crossed cubes, and

n

-dimensional locally twisted cubes, to show that there exists a fault-free Hamiltonian cycle if there are at most 2

n

 − 5 faulty edges in which each node is incident to at least two fault-free edges. We also demonstrate that our result is worst-case optimal with respect to the number of faulty edges tolerated.

The problem of computing locally a coloring of an arbitrary planar subgraph of a unit disk graph is studied. Each vertex knows its coordinates in the plane, can directly communicate with all its neighbors within unit distance. Using this setting, first a simple algorithm is given whereby each vertex can compute its color in a 9-coloring of the planar graph using only information on the subgraph located within at most 9 hops away from it in the original unit disk graph. A more complicated algorithm is then presented whereby each vertex can compute its color in a 7-coloring of the planar graph using only information on the subgraph located within a constant number of hops away from it.

The so called (

σ

,

ρ

)-domination, introduced by J.A. Telle, is a concept which provides a unifying generalization for many variants of domination in graphs. (A set

S

of vertices of a graph

G

is called (

σ

,

ρ

)

-dominating

if for every vertex

v

 ∈ 

S

, |

S

 ∩ 

N

(

v

)| ∈ 

σ

, and for every

v

 ∉ 

S

, |

S

 ∩ 

N

(

v

)| ∈ 

ρ

, where

σ

and

ρ

are sets of nonnegative integers and

N

(

v

) denotes the open neighborhood of the vertex

v

in

G

.) It is known that for any two nonempty finite sets

σ

and

ρ

(such that 0 ∉ 

ρ

), the decision problem whether an input graph contains a (

σ

,

ρ

)-dominating set is NP-complete, but that when restricted to some graph classes, polynomial time solvable instances occur. We show that for every

k

, the problem performs a complete dichotomy when restricted to

k

-degenerate graphs, and we fully characterize the polynomial and NP-complete instances. It is further shown that the problem is polynomial time solvable if

σ

,

ρ

are such that every

k

-degenerate graph contains at most one (

σ

,

ρ

)-dominating set, and NP-complete otherwise. This relates to the concept of ambivalent graphs previously introduced for chordal graphs.

Deciding strong and weak bisimilarity of BPP are challenging because of the infinite nature of the state space of such processes. Deciding weak bisimilarity is harder since the usual decomposition property which holds for strong bisimilarity fails. Hirshfeld proposed the notion of bisimulation tree to prove that weak bisimulation is decidable for totally normed BPA and BPP processes. In this paper, we present a tableau method to decide weak bisimilarity of totally normed BPP. Compared with Hirshfeld’s bisimulation tree method, our method is more intuitive and more direct. Moreover from the decidability proof we can derive a complete axiomatisation for the weak bisimulation of totally normed BPP.

In this paper, we study the extensions of embeddings in the computably enumerable Turing degrees. We show that for any c.e. degrees

${\bf x\not\leq y}$

, if either

y

is low or

x

is high, then there is a c.e. degree

a

such that both

0 < a

 ≤ x

and

${\bf x\not\leq y\cup a}$

hold.

We study the parameterized complexity of a generalized matching problem, the

P

2

-packing problem. The problem is NP-hard and has been studied by a number of researchers. In this paper, we provide further study of the structures of the

P

2

-packing problem, and propose a new kernelization algorithm that produces a kernel of size 7

k

for the problem, improving the previous best kernel size 15

k

. The new kernelization leads to an improved algorithm for the problem with running time

O

*

(2

4.142

k

), improving the previous best algorithm of time

O

*

(2

5.301

k

).

In this paper we consider deterministic hot-potato routing algorithms on

n

×

n

meshes and tori. We present algorithms for the permutation routing problem on these networks and achieve new upper bounds. The basic ideas used in the presented algorithms are sorting, packet concentration and fast algorithms for one-dimensional submeshes. Using this ideas we solve the permutation routing problem in 3.25

n

 + 

o

(

n

) steps on an

n

×

n

mesh and in 2.75

n

 + 

o

(

n

) steps on an

n

×

n

torus.

We study a natural probabilistic model for motif discovery that has been used to experimentally test the quality 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 randomly generated approximate copy of

G

. For a randomly generated approximate copy

b

1

b

2

...

b

m

of

G

, every character is randomly generated such that the probability for

b

i

 ≠ 

g

i

is at most

α

. In this paper, we give the first analytical proof that multiple background sequences do help for finding subtle and faint motifs.

We investigate the problem of stable in-place merging from a ratio

$k=\frac{n}{m}$

based point of view where

m

,

n

are the sizes of the input sequences with

m

 ≤ 

n

. We introduce a novel algorithm for this problem that is asymptotically optimal regarding the number of assignments as well as comparisons. Our algorithm uses knowledge about the ratio of the input sizes to gain optimality and does not stay in the tradition of Mannila and Ukkonen’s work [8] in contrast to all other stable in-place merging algorithms proposed so far. It has a simple modular structure and does not demand the additional extraction of a movement imitation buffer as needed by its competitors. For its core components we give concrete implementations in form of Pseudo Code. Using benchmarking we prove that our algorithm performs almost always better than its direct competitor proposed in [6].

As additional sub-result we show that stable in-place merging is a quite simple problem for every ratio

$k\geq\sqrt{m}$

by proving that there exists a primitive algorithm that is asymptotically optimal for such ratios.

Four sub-recursive classes of functions,

${\mathcal{B}}$

,

${\mathcal{D}}$

,

${\mathcal{BD}}$

and

${\mathcal{BDD}}$

are defined, and compared to the classes

G

0

,

G

1

and

G

2

, originally defined by Grzegorczyk, based on

bounded minimalisation

, and characterised by Harrow in [5].

${\mathcal{B}}$

is essentially

G

0

with

predecessor

substituted for

successor

;

${\mathcal{BD}}$

is

G

1

with

(truncated) difference

substituted for

addition

. We prove that the induced relational classes are preserved (

$G^0_\star={\mathcal{B}}_\star$

and

$G^1_\star={\mathcal{BD}}_\star$

). We also obtain

${\mathcal{D}}_\star={{{\mathfrak{PrA}}^{\text{\tiny qf}}}_\star}$

(the quantifier free fragment of Presburger Arithmetic), and

${\mathcal{BD}}_\star={\mathfrak{PrA}}_\star$

, and

${\mathcal{BDD}}_\star=G^2_\star$

, where

${\mathcal{BDD}}$

is

G

2

with

integer division

and

remainder

substituted for

multiplication

, and where

$G^2_\star$

is known to be equal to the predicates definable by a bounded formula in

Peano Arithmetic

.

The minimum 3-way cut problem in an edge-weighted hypergraph is to find a partition of the vertices into 3 sets minimizing the total weight of hyperedges with at least two endpoints in two different sets. In this paper we present some structural properties for minimum 3-way cuts and design an

O

(

dmn

3

) algorithm for the minimum 3-way cut problem in hypergraphs, where

n

and

m

are the numbers of vertices and edges respectively, and

d

is the sum of the degrees of all the vertices. Our algorithm is the first deterministic algorithm finding minimum 3-way cuts in hypergraphs.

Given a bipartite graph

G

 = (

V

1

,

V

2

,

E

) where edges take on

both

positive and negative weights from set

$\mathcal{S}$

, the

maximum weighted edge biclique

problem, or

$\mathcal{S}$

-MWEB for short, asks to find a bipartite subgraph whose sum of edge weights is maximized. This problem has various applications in bioinformatics, machine learning and databases and its (in)approximability remains open. In this paper, we show that for a wide range of choices of

$\mathcal{S}$

, specifically when

$\left| \frac{\min\mathcal{S}} {\max \mathcal{S}} \right| \in \Omega(\eta^{\delta-1/2}) \cap O(\eta^{1/2-\delta})$

(where

η

 =  max {|

V

1

|, |

V

2

|}, and

δ

 ∈ (0,1/2]), no polynomial time algorithm can approximate

$\mathcal{S}$

-MWEB within a factor of

n

ε

for some

ε

> 0 unless

RP = 

NP

. This hardness result gives justification of the heuristic approaches adopted for various applied problems in the aforementioned areas, and indicates that good approximation algorithms are unlikely to exist. Specifically, we give two applications by showing that: 1) finding statistically significant biclusters in the SAMBA model, proposed in [18] for the analysis of microarray data, is

n

ε

-inapproximable; and 2) no polynomial time algorithm exists for the Minimum Description Length with Holes problem [4] unless

RP

=

NP

.

This paper investigates symbolic algorithm analysis of rectangular hybrid systems. To deal with the symbolic reachability problem, a restricted constraint system called

hybrid zone

is formalized. Hybrid zones are also applied to a symbolic model-checking algorithm for verifying some important classes of timed computation tree logic formulas. To present hybrid zones, a data structure called

difference constraint matrix

is defined. Using this structure, all reachability operations and model checking algorithms for rectangular hybrid systems are implemented. These enable us to deal with the symbolic algorithm analysis of rectangular hybrid systems in an efficient way.

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations. Ordered binary decision diagrams (OBDDs) are the most common dynamic data structure for boolean functions. Among the many areas of application are verification, model checking, computer-aided design, relational algebra, and symbolic graph algorithms. In this paper it is shown that the OBDD complexity of the most significant bit of integer multiplication is exponential answering an open question posed by Wegener (2000).

In this paper we define and investigate basic logical closure properties of propositional proof systems such as closure of arbitrary proof systems under modus ponens or substitutions. As our main result we obtain a purely logical characterization of the degrees of schematic extensions of

${\mathit{EF}}$

in terms of a simple combination of these properties. This result underlines the empirical evidence that

${\mathit{EF}}$

and its extensions admit a robust definition which rests on only a few central concepts from propositional logic.

We give the first characterisation of graphs of linear clique-width at most 3, and we give a polynomial-time recognition algorithm for such graphs.

A Boolean function on

n

variables is called

k

-mixed if for any two different restrictions fixing the same set of

k

variables must induce different functions on the remaining

n

 − 

k

variables. In this paper, we give an explicit construction of an

n

 − 

o

(

n

)-mixed Boolean function whose circuit complexity over the basis

U

2

is 5

n

 + 

o

(

n

). This shows that a lower bound method on the size of a

U

2

-circuit that uses the property of

k

-mixed, which gives the current best lower bound of 5

n

 − 

o

(

n

) on a

U

2

-circuit size (Iwama, Lachish, Morizumi and Raz [STOC ’01, MFCS ’02]), has reached the limit.

In this paper, we present a spatial logic for distributed higher order

π

-calculus. In order to prove that the induced logical equivalence coincides with distributed context bisimulation, we present some new bisimulations, and prove the equivalence between these new bisimulations and distributed context bisimulation. Furthermore, we present a variant of this spatial logic and prove that it gives a logical characterisation of distributed bisimulations.

Yannakakis and Gavril showed in [10] that the problem of finding a maximal matching of minimum size (MMM for short), also called Minimum Edge Dominating Set, is NP-hard in bipartite graphs of maximum degree 3 or planar graphs of maximum degree 3. Horton and Kilakos extended this result to planar bipartite graphs and planar cubic graphs [6]. Here, we extend the result of Yannakakis and Gavril in [10] by showing that MMM is NP-hard in the class of

k

-regular bipartite graphs for all

k

 ≥ 3 fixed.

To tile consists in assembling colored tiles on

${{\mathbb Z}^2}$

while respecting color matching. Tilings, the outcome of the tile process, can be seen as a computation model. In order to better understand the global structure of tilings, we introduce two topologies on tilings, one

à la

Cantor and another one

à la

Besicovitch. Our topologies are concerned with the whole set of tilings that can be generated by any tile set and are thus independent of a particular tile set. We study the properties of these two spaces and compare them. Finally, we introduce two infinite games on these spaces that are promising tools for the study of the structure of tilings.

We provide a domain-based denotational semantics for a sequential language for exact real number computation, equipped with a non-deterministic test operator. The semantics is only an approximate one, because the denotation of a program for a real number may not be precise enough to tell which real number the program computes. However, for many first-order common functions

$f:{\mathbb R}^n \rightarrow {\mathbb R}$

, there exists a program for

f

whose denotation is precise enough to show that the program indeed computes the function

f

. In practice such programs possessing a faithful denotation are not difficult to find.

The existence of bisimulations for objects in the Kleisli category associated with the Giry monad of subprobabilities over Polish spaces is studied. We first investigate these morphisms and show that the problem can be reduced to the existence of bisimulations for objects in the base category of stochastic relations using simulation equivalent congruences. This leads to a criterion for two objects related through the monad to be bisimilar.

We study the border minimization problem (BMP), which arises in microarray synthesis to place and embed probes in the array. The synthesis is based on a light-directed chemical process in which unintended illumination may contaminate the quality of the experiments. Border length is a measure of the amount of unintended illumination and the objective of BMP is to find a placement and embedding of probes such that the border length is minimized. The problem is believed to be NP-hard. In this paper we show that BMP admits an

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

-approximation, where

n

is the number of probes to be synthesized. In the case where the placement is given in advance, we show that the problem is

O

(log

2

n

)-approximable. We also study a related problem called agreement maximization problem (AMP). In contrast to BMP, we show that AMP admits a constant approximation even when placement is not given in advance.

For many TxtEX-learnable computable families of recursively enumerable sets, all their computable numberings are equivalent with respect to the reduction via the functions recursive in the halting problem. We show that this holds for every TxtEX-learnable computable family of recursively enumerable sets, but, in general, the converse is not true.

The individual haplotyping problem Minimum Letter Flip (MLF) is a computational problem that, given a set of aligned DNA sequence fragment data of an individual, induces the corresponding haplotypes by flipping minimum SNPs. There has been no practical exact algorithm to solve the problem. In DNA sequencing experiments, due to technical limits, the maximum length of a fragment sequenced directly is about 1kb. In consequence, with a genome-average SNP density of 1.84 SNPs per 1 kb of DNA sequence, the maximum number

k

1

of SNP sites that a fragment covers is usually small. Moreover, in order to save time and money, the maximum number

k

2

of fragments that cover a SNP site is usually no more than 19. Based on the properties of fragment data, the current paper introduces a new parameterized algorithm of running time

$O(nk_22^{k_2}+mlogm+mk_1)$

, where

m

is the number of fragments,

n

is the number of SNP sites. The algorithm solves the MLF problem efficiently even if

m

and

n

are large, and is more practical in real biological applications.

The NP-hard

Bicluster Editing

is to add or remove at most

k

edges to make a bipartite graph

G

 = (

V

,

E

) a vertex-disjoint union of complete bipartite subgraphs. It has applications in the analysis of gene expression data. We show that by polynomial-time preprocessing, one can shrink a problem instance to one with 4

k

vertices, thus proving that the problem has a linear kernel, improving a quadratic kernel result. We further give a search tree algorithm that improves the running time bound from the trivial

O

(4

k

 + |

E

|) to

O

(3.24

k

 + |

E

|). Finally, we give a randomized 4-approximation, improving a known approximation with factor 11.

Among the several notions of resource-bounded Kolmogorov complexity that suggest themselves, the following one due to Levin [Le] has probably received most attention in the literature. With some appropriate universal machine

U

understood, let the Kolmogorov complexity of a word

w

be the minimum of |

d

| + log

t

over all pairs of a word

d

and a natural number

t

such that

U

takes time

t

to check that

d

determines

w

. One then differentiates between generation complexity and distinction complexity [A, Sip], where the former asks for a program

d

such that

w

can actually be computed from

d

, whereas the latter asks for a program

d

that distinguishes

w

from other words in the sense that given

d

and any word

u

, one can effectively check whether

u

is equal to

w

.

Allender et al. [A] consider a notion of solvability for nondeterministic computations that for a given resource-bounded model of computation amounts to require that for any nondeterministic machine

N

there is a deterministic machine that exhibits the same acceptance behavior as

N

on all inputs for which the number of accepting paths of

N

is not too large. They demonstrate that nondeterminism is solvable for computations restricted to polynomially exponential time if and only if for any word the generation complexity is at most polynomial in the distinction complexity. We extend their work and a related result by Fortnow and Kummer [FK] as follows. First, nondeterminism is solvable for linearly exponential time bounds if and only if generation complexity is at most linear in distinction complexity. Second, nondeterminism is solvable for polynomial time bounds if and only if the conditional generation complexity of a word

w

given a word

y

is at most linear in the conditional distinction complexity of

w

given

y

; hence, in particular, the latter condition implies that

P

is equal to

UP

. Finally, in the setting of space bounds it holds unconditionally that generation complexity is at most linear in distinction complexity.

We consider the problem of load-balanced routing, where a dense network is modelled by a continuous square region and origin and destination nodes correspond to pairs of points in that region. The objective is to define a routing policy that assigns a continuous path to each origin-destination pair while minimizing the traffic, or

load

, passing through any single point. While the average load is minimized by straight-line routing, such a routing policy distributes the load non-uniformly, resulting in higher load near the center of the region. We consider one-turn rectilinear routing policies that divert traffic away from regions of heavier load, resulting in up to a 33% reduction in the maximum load while simultaneously increasing the path lengths by an average of less than 28%. Our policies are simple to implement, being both local and oblivious. We provide a lower bound that shows that no one-turn rectilinear routing policy can reduce the maximum load by more than 39% and we give a polynomial-time procedure for approximating the optimal randomized policy.

We consider the well studied

Full Degree Spanning Tree

problem, a NP-complete variant of the

Spanning Tree

problem, in the realm of moderately exponential time exact algorithms. In this problem, given a graph

G

, the objective is to find a spanning tree

T

of

G

which maximizes the number of vertices that have the same degree in

T

as in

G

. This problem is motivated by its application in fluid networks and is basically a graph-theoretic abstraction of the problem of placing flow meters in fluid networks. We give an exact algorithm for

Full Degree Spanning Tree

running in time

${\mathcal{O}(1.9172^n)}$

. This adds

Full Degree Spanning Tree

to a very small list of “non-local problems”, like

Feedback Vertex Set

and

Connected Dominating Set

, for which non-trivial (non brute force enumeration) exact algorithms are known.

A vertex coloring of a tree is called

convex

if each color induces a connected component. The NP-hard

Convex Recoloring

problem on vertex-colored trees asks for a minimum-weight change of colors to achieve a convex coloring. For the non-uniformly weighted model, where the cost of changing a vertex

v

to color

c

depends on both

v

and

c

, we improve the running time on trees from

O

(

Δ

κ

·

κn

) to

O

(3

κ

·

κn

), where

Δ

is the maximum vertex degree of the input tree

T

,

κ

is the number of colors, and

n

is the number of vertices in

T

. In the uniformly weighted case, where costs depend only on the vertex to be recolored, one can instead parameterize on the number of

bad

colors

β

 ≤ 

κ

, which is the number of colors that do not already induce a connected component. Here, we improve the running time from

O

(

Δ

β

·

βn

) to

O

(3

β

·

βn

). For the case where the weights are integers bounded by

M

, using fast subset convolution, we further improve the running time with respect to the exponential part to

O

(2

κ

·

κ

4

n

2

M

log

2

(

nM

)) and

O

(2

β

·

β

4

n

2

M

log

2

(

nM

)), respectively. Finally, we use fast subset convolution to improve the exponential part of the running time of the related 1-

Connected Coloring Completion

problem.

A

room

is a simple polygon with a prespecified point, called the

door

, on its boundary. Search may be conducted by two guards on the boundary who keep mutual visibility at all times, or by a single boundary searcher with a flashlight. Search starts at the door, and must detect any intruder that was in the room at the time the search started, preventing the intruder from escaping through the door. A room may or may not be searchable, depending on where the door is placed or no matter where the door is placed. We want to find all intervals on the boundary where the door can be placed for the resultant room to be searchable. It is known that this problem can be solved in

O

(

n

log

n

) time, if the given polygon has

n

sides. We improve this complexity to

O

(

n

).

We study the complexity of automatic structures via well-established concepts from both logic and model theory, including ordinal heights (of well-founded relations), Scott ranks of structures, and Cantor-Bendixson ranks (of trees). We prove the following results: 1) The ordinal height of any automatic well-founded partial order is bounded by

ω

ω

; 2) The ordinal heights of automatic well-founded relations are unbounded below

$\omega_{1}^{CK}$

; 3) For any infinite computable ordinal

α

, there is an automatic structure of Scott rank at least

α

. Moreover, there are automatic structures of Scott rank

$\omega_1^{CK}, \omega_1^{CK}+1$

; 4) For any ordinal

$\alpha<\omega_1^{CK}$

, there is an automatic successor tree of Cantor-Bendixson rank

α

.

The notion of

divergence information

of an ensemble of probability distributions was introduced by Jain, Radhakrishnan, and Sen [1,2] in the context of the “substate theorem”. Since then, divergence has been recognized as a more natural measure of information in several situations in quantum and classical communication.

We construct ensembles of probability distributions for which divergence information may be significantly smaller than the more standard Holevo information. As a result, we establish that lower bounds previously shown for Holevo information are weaker than similar ones shown for divergence information.

This paper studies infinite graphs produced from a natural unfolding operation applied to finite graphs. Graphs produced via such operations are of finite degree and can be described by finite automata over the unary alphabet. We investigate algorithmic properties of such unfolded graphs given their finite presentations. In particular, we ask whether a given node belongs to an infinite component, whether two given nodes in the graph are reachable from one another, and whether the graph is connected. We give polynomial time algorithms for each of these questions. Hence, we improve on previous work, in which non-elementary or non-uniform algorithms were found.

The vast number of applications featuring multimedia and geometric data has made the R-tree a ubiquitous data structure in databases. A popular and fundamental operation on R-trees is nearest neighbor search. While nearest neighbor on R-trees has received considerable experimental attention, it has received somewhat less theoretical consideration. We study pruning heuristics for nearest neighbor queries on R-trees. Our primary result is the construction of non-trivial families of R-trees where

k

-nearest neighbor queries based on pessimistic (i.e. min-max) distance estimates provide exponential speedup over queries based solely on optimistic (i.e. min) distance estimates. The exponential speedup holds even when

k

 = 1. This result provides strong theoretical evidence that min-max distance heuristics are an essential component to depth-first nearest-neighbor queries. In light of this, we also consider the time-space tradeoffs of depth-first versus best-first nearest neighbor queries and construct a family of R-trees where best-first search performs exponentially better than depth-first search even when depth-first employs min-max distance heuristics.

This paper continues the project, initiated in [ACK], of describing general conditions under which relative splittings are derivable in the local structure of the enumeration degrees.

The main results below include a proof that any high total e-degree below

$\text{\bf 0}'_e$

is splittable over any low e-degree below it, and a construction of a

$\Pi_1^0$

e-degree unsplittable over a

Δ

2

e-degree below it.

In [ACK] it was shown that using semirecursive sets one can construct minimal pairs of e-degrees by both effective and uniform ways, following which new results concerning the local distribution of total e-degrees and of the degrees of semirecursive sets enabled one to proceed, via the natural embedding of the Turing degrees in the enumeration degrees, to results concerning embeddings of the diamond lattice in the e-degrees. A particularly striking application of these techniques was a relatively simple derivation of a strong generalisation of the Ahmad Diamond Theorem.

For any enumeration degree

a

let

$D^s_{\bf a}$

be the set of

s

-degrees contained in

a

. We answer an open question of Watson by showing that if

a

is a nontrivial

$\Sigma^0_2$

-enumeration degree, then

$D^s_{\bf a}$

has no least element. We also show that every countable partial order embeds into

$D^s_{\bf a}$

.

The existence of isolated degrees was proved by Cooper and Yi in 1995 in [7], where a d.c.e. degree

d

is isolated by a c.e. degree

a

if

a

 < 

d

is the greatest c.e. degree below

d

. A computably enumerable degree

c

is non-isolating if no d.c.e. degree above

c

is isolated by

c

. Obviously,

0

is a non-isolating degree. Cooper and Yi asked in [7] whether there is a nonzero non-isolating degree. Arslanov et al. showed in [3] that nonzero non-isolating degrees exist and that these degrees are downwards dense in the c.e. degrees and can also occur in every jump class. In [11], Salts proved that there is an interval of computably enumerable degrees, each of which isolates a d.c.e. degree. Recently, Cenzer et al. [4] proved that such intervals are dense in the computably enumerable degrees, and hence the non-isolating degrees are nowhere dense in the computably enumerable degrees. In this paper, using a different type of construction to that of [3], we prove that the non-isolating degrees are upwards dense in the computably enumerable degrees. In the context of [4], this is the best possible such result.