An efficient string sorting algorithm for weighing matrices of small weight

In this paper, we demonstrate that the search for weighing matrices of small weights constructed from two circulants can be viewed as a string sorting problem together with a linear time algorithm to locate common strings in two sorted arrays. We also introduce a sparse encoding of the periodic autocorrelation function vector, based on concepts from Algorithmic Information Theory, also known as Kolmogorov complexity, that allows us to speed up the algorithm considerably. Finally, we use these ideas to find new weighing matrices W(2 · n, 9) constructed from two circulants, for many values of n in the range 100 ≤  n ≤  300. These matrices are given here for the first time. We also discuss briefly a connection with Combinatorial Optimization.     

On joint conditional complexity (Entropy)

The conditional Kolmogorov complexity of a word a relative to a word b is the minimum length of a program that prints a given b as an input. We generalize this notion to quadruples of strings a, b, c, d: their joint conditional complexity K((a → c)∧(b → d)) is defined as the minimum length of a program that transforms a into c and transforms b into d. In this paper, we prove that the joint conditional complexity cannot be expressed in terms of the usual conditional (and unconditional) Kolmogorov complexity. This result provides a negative answer to the following question asked by A. Shen on a session of the Kolmogorov seminar at Moscow State University in 1994: Is there a problem of information processing whose complexity is not expressible in terms of the conditional (and unconditional) Kolmogorov complexity? We show that a similar result holds for the classical Shannon entropy. We provide two proofs of both results, an effective one and a “quasi-effective” one. Finally, we present a quasi-effective proof of a strong version of the following statement: there are two strings whose mutual information cannot be extracted. Previously, only a noneffective proof of that statement has been known.     

Quasi‐completeness and functions without fixed‐points

We prove a completeness criterion for quasi‐reducibility and generalize it to higher levels of the arithmetical hierarchy. As an application of the criterion we obtain Q‐completeness of the set of all pairs (x, n) such that the prefix‐free Kolmogorov complexity of x is less than n. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the Transient Behavior of the M/M/1 and M/M/1/M Queues

This paper gives a transient analysis of the classic M/M/1 and M/M/1/K queues. Our results are asymptotic as time and queue length become simultaneously large for the infinite capacity queue, and as the system’s storage capacity K becomes large for the finite capacity queue. We give asymptotic expansions for p_n(t), which is the probability that the system contains n customers at time t. We treat several cases of initial conditions and different traffic intensities. The results are based on (i) asymptotic expansion of an exact integral representation for p_n(t) and (ii) applying the ray method to a scaled form of the forward Kolmogorov equation which describes the time evolution of p_n(t).     

Kolmogorov complexity and set theoretical representations of integers

We reconsider some classical natural semantics of integers (namely iterators of functions, cardinals of sets, index of equivalence relations) in the perspective of Kolmogorov complexity. To each such semantics one can attach a simple representation of integers that we suitably effectivize in order to develop an associated Kolmogorov theory. Such effectivizations are particular instances of a general notion of “self‐enumerated system” that we introduce in this paper. Our main result asserts that, with such effectivizations, Kolmogorov theory allows to quantitatively distinguish the underlying semantics. We characterize the families obtained by such effectivizations and prove that the associated Kolmogorov complexities constitute a hierarchy which coincides with that of Kolmogorov complexities defined via jump oracles and/or infinite computations (cf. [6]). This contrasts with the well‐known fact that usual Kolmogorov complexity does not depend (up to a constant) on the chosen arithmetic representation of integers, let it be in any base n ≥ 2 or in unary. Also, in a conceptual point of view, our result can be seen as a mean to measure the degree of abstraction of these diverse semantics. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Fundamental group and contractible closed geodesics

We prove the existence of a nonempty class of finitely presented groups with the following property: If the fundamental group of a compact Riemannian manifold M belongs to this class, then there exists a constant c(M) > 1 such that for any sufficiently large x the number of contractible closed geodesics on M of length not exceeding x is greater than c(M)^x. In order to prove this result, we give a lower bound for the number of contractible closed geodesics of length ≤ x on a compact Riemannian manifold M in terms of the resource-bounded Kolmogorov complexity of the word problem for π₁ (M), thus answering a question posed by Gromov. © 1996 John Wiley & Sons, Inc.     

Seperating the intrinsic complexity and the derivational complexity of the word problem for finitely presented groups

A pseudo-natural algorithm for the word problem of a finitely presented group is an algorithm which not only tells us whether or not a word w equals 1 in the group but also gives a derivation of 1 from w when w equals 1. In [13], [14] Madlener and Otto show that, if we measure complexity of a primitive recursive algorithm by its level in the Grzegorczyk hierarchy, there are groups in which a pseudo-natural algorithm is arbitrarily more complicated than an algorithm which simply solves the word problem. In a given group the lowest degree of complexity that can be realised by a pseudo-natural algorithm is essentially the derivational complexity of that group. Thus the result separates the derivational complexity of the word problem of a finitely presented group from its intrinsic complexity. The proof given in [13] involves the construction of a finitely presented group G from a Turing machine T such that the intrinsic complexity of the word problem for G reflects the complexity of the halting problem of T, while the derivational complexity of the word problem for G reflects the runtime complexity of T. The proof of one of the crucial lemmas in [13] is only sketched, and part of the purpose of this paper is to give the full details of this proof. We will also obtain a variant of their proof, using modular machines rather than Turing machines. As for several other results, this simplifies the proofs considerably. MSC: 03D40, 20F10.     

A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm

Recently, É. Tardos gave a strongly polynomial algorithm for the minimum-cost circulation problem and solved the open problem posed in 1972 by J. Edmonds and R.M. Karp. Her algorithm runs in O(m ² T(m, n) logm) time, wherem is the number of arcs,n is the number of vertices, andT(m, n) is the time required for solving a maximum flow problem in a network withm arcs andn vertices. In the present paper, taking an approach that is a dual of Tardos's, we also give a strongly polynomial algorithm for the minimum-cost circulation problem. Our algorithm runs in O(m ² S(m, n) logm) time and reduces the computational complexity, whereS(m, n) is the time required for solving a shortest path problem with a fixed origin in a network withm arcs,n vertices, and a nonnegative arc length function. The complexity is the same as that of Orlin's algorithm, recently developed by efficiently implementing the Edmonds-Karp scaling algorithm.     

On the complexity of some subgraph problems

We study the complexity of the problem of deciding the existence of a spanning subgraph of a given graph, and of that of finding a maximum (weight) such subgraph. We establish some general relations between these problems, and we use these relations to obtain new NP-completeness results for maximum (weight) spanning subgraph problems from analogous results for existence problems and from results in extremal graph theory. On the positive side, we provide a decomposition method for the maximum (weight) spanning chordal subgraph problem that can be used, e.g., to obtain a linear (or O(nlogn)) time algorithm for such problems in graphs with vertex degree bounded by 3.     

Completeness,Compactness, Effective Dimensions

We investigate a directed metric on the space of infinite binary sequences defined by where C(X?n‖Y?n) is the Kolmogorov complexity of X?n given Y?n. In particular we focus on the topological aspects of the associated metric space—proving that it is complete though very far from being compact. This is a continuation of earlier work investigating other geometrical and toplogical aspects of this metric.     

The location of median paths on grid graphs

In this paper we consider the location of a path shaped facility on a grid graph. In the literature this problem was extensively studied on particular classes of graphs as trees or series-parallel graphs. We consider here the problem of finding a path which minimizes the sum of the (shortest) distances from it to the other vertices of the grid, where the path is also subject to an additional constraint that takes the form either of the length of the path or of the cardinality. We study the complexity of these problems and we find two polynomial time algorithms for two special cases, with time complexity of O(n) and O(nℓ) respectively, where n is the number of vertices of the grid and ℓ is the cardinality of the path to be located. The literature about locating dimensional facilities distinguishes between the location of extensive facilities in continuous spaces and network facility location. We will show that the problems presented here have a close connection with continuous dimensional facility problems, so that the procedures provided can also be useful for solving some open problems of dimensional facilities location in the continuous case.     

The average‐case area of Heilbronn‐type triangles*

From among ${n \choose 3}$ triangles with vertices chosen from n points in the unit square, let T be the one with the smallest area, and let A be the area of T. Heilbronn's triangle problem asks for the maximum value assumed by A over all choices of n points. We consider the average‐case: If the n points are chosen independently and at random (with a uniform distribution), then there exist positive constants c and C such that c/n³<μ_n<C/n³ for all large enough values of n, where μ_n is the expectation of A. Moreover, c/n³<A<C/n³, with probability close to one. Our proof uses the incompressibility method based on Kolmogorov complexity; it actually determines the area of the smallest triangle for an arrangement in “general position.” © 2002 Wiley Periodicals, Inc. Random Struct. Alg. 20: 206–219, 2002     

Almost tight upper bounds for lower envelopes in higher dimensions

We consider the problem of bounding the combinatorial complexity of the lower envelope ofn surfaces or surface patches ind-space (d≥3), all algebraic of constant degree, and bounded by algebraic surfaces of constant degree. We show that the complexity of the lower envelope ofn such surface patches isO(n ^d−1+∈), for any ∈>0; the constant of proportionality depends on ∈, ond, ons, the maximum number of intersections among anyd-tuple of the given surfaces, and on the shape and degree of the surface patches and of their boundaries. This is the first nontrivial general upper bound for this problem, and it almost establishes a long-standing conjecture that the complexity of the envelope isO(n ^d-2λ _q (n)) for some constantq depending on the shape and degree of the surfaces (where λ _q (n) is the maximum length of (n, q) Davenport-Schinzel sequences). We also present a randomized algorithm for computing the envelope in three dimensions, with expected running timeO(n ^2+∈), and give several applications of the new bounds. Work on this paper has been supported by NSF Grant CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F., the German-Israeli Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

Improved complexity results for several multifacility location problems on trees

In this paper we consider multifacility location problems on tree networks. On general networks, these problems are usually NP-hard. On tree networks, however, often polynomial time algorithms exist; e.g., for the median, center, centdian, or special cases of the ordered median problem. We present an enhanced dynamic programming approach for the ordered median problem that has a time complexity of just O(ps ² n ⁶) for the absolute and O(ps ² n ²) for the node restricted problem, improving on the previous results by a factor of O(n ³). (n and p being the number of nodes and new facilities, respectively, and s (≤n) a value specific for the ordered median problem.) The same reduction in complexity is achieved for the multifacility k-centrum problem leading to O(pk ² n ⁴) (absolute) and O(pk ² n ²) (node restricted) algorithms.     

Optimally Cutting a Surface into a Disk

We consider the problem of cutting a subset of the edges of a polyhedral manifold surface, possibly with boundary, to obtain a single topological disk, minimizing either the total number of cut edges or their total length. We show that this problem is NP-hard in general, even for manifolds without boundary and for punctured spheres. We also describe an algorithm with running time n ^O(g+k), where n is the combinatorial complexity, g is the genus, and k is the number of boundary components of the input surface. Finally, we describe a greedy algorithm that outputs a O(log² g)-approximation of the minimum cut graph in O(g ² n log n) time.     

On strategy improvement algorithms for simple stochastic games

The study of simple stochastic games (SSGs) was initiated by Condon for analyzing the computational power of randomized space-bounded alternating Turing machines. The game is played by two players, MAX and MIN, on a directed multigraph, and when the play terminates at a sink vertex s, MAX wins from MIN a payoff p(s)∈[0,1]. Condon proved that the problem SSG-VALUE—given a SSG, determine whether the expected payoff won by MAX is greater than 1/2 when both players use their optimal strategies—is in NP∩coNP. However, the exact complexity of this problem remains open, as it is not known whether the problem is in P or is hard for some natural complexity class. In this paper, we study the computational complexity of a strategy improvement algorithm by Hoffman and Karp for this problem. The Hoffman–Karp algorithm converges to optimal strategies of a given SSG, but no non-trivial bounds were previously known on its running time. We prove a bound of O(n²/n) on the convergence time of the Hoffman–Karp algorithm, and a bound of O(²0.78n) on a randomized variant. These are the first non-trivial upper bounds on the convergence time of these strategy improvement algorithms.     

An approximation algorithm for the minimum two peripatetic salesmen problem with different weight functions

We present a polynomial algorithm with time complexity O(n ⁵) and approximation ratio 4/3 (plus some additive constant) for the minimum 2-peripatetic salesman problem in a complete n-vertex graph with different weight functions valued 1 and 2 (abbreviated to as 2-PSP(1, 2)-min-2w). This result improves the available algorithm for this problem with approximation ratio 11/7.     

Algorithms of Intrinsic Complexity for Point Searching in Compact Real Singular Hypersurfaces

For a real square-free multivariate polynomial F, we treat the general problem of finding real solutions of the equation F=0, provided that the real solution set {F=0}_ℝ is compact. We allow that the equation F=0 may have singular real solutions. We are going to decide whether this equation has a non-singular real solution and, if this is the case, we exhibit one for each generically smooth connected component of {F=0}_ℝ. We design a family of elimination algorithms of intrinsic complexity which solves this problem. In the worst case, the complexity of our algorithms does not exceed the already known extrinsic complexity bound of (nd) ^O(n) for the elimination problem under consideration, where n is the number of indeterminates of F and d its (positive) degree. In the case that the real variety defined by F is smooth, there already exist algorithms of intrinsic complexity that solve our problem. However, these algorithms cannot be used in case when F=0 admits F-singular real solutions.     

Randomized Complexity Lower Bound for Arrangements and Polyhedra

The complexity lower bound Ω (log N ) for randomized computation trees is proved for recognizing an arrangement or a polyhedron with N faces. This provides, in particular, the randomized lower bound Ω (n log n ) for the DISTINCTNESS problem and generalizes [11] where the randomized lower bound Ω (n ² ) was ascertained for the KNAPSACK problem. The core of the method is an extension of the lower bound from [8] on the multiplicative complexity of a polynomial. Received May 14, 1997, and in revised form October 27, 1997, and February 16, 1998.     

Small Spectral Gap in the Combinatorial Laplacian Implies Hamiltonian

We consider the spectral and algorithmic aspects of the problem of finding a Hamiltonian cycle in a graph. We show that a sufficient condition for a graph being Hamiltonian is that the nontrivial eigenvalues of the combinatorial Laplacian are sufficiently close to the average degree of the graph. An algorithm is given for the problem of finding a Hamiltonian cycle in graphs with bounded spectral gaps which has complexity of order n ^{cln n} .