International Journal of Foundations of Computer Science

We consider the routing number of trees, denoted by rt(), with respect to the matching routing model. For an arbitrary n-node tree T, it is known that rt(T) < 3n/2 + O(log n). In this paper, by providing a recursive off-line permutation routing algorithm, we show that the routing number of an n-node complete d-ary tree of height h(T) > 1 is bounded from above by n + o(n). This is near optimal since, for an n-node complete d-ary tree T of height h(T) > 1 it holds that rt(T) ≥ n.

Let G be a k-tree such that |{v ∈ V(G): deg_G(v) = k}| = 2, n = |V(G)| ≥ 2k + 2, and the maximum degree of G is at most 2k. In this paper, we will show that such a k-tree G is isomorphic to P_n,k. In this way, we give a new characterization of k-th power (i.e. P_n,k) of paths with n vertices in terms of k-trees.

Let G be a connected bipartite graph with with bipartition (X, Y) such that |X| ≥ |Y| (≥ 2). Put n = |X|, m = |Y| and l = m + n. Suppose that, for all vertices x ∈ X and y ∈ Y, dist(x,y) = 3 implies d(x) + d(y) ≥ n + 1. We show that G contains a cycle of length 2m. We also give an efficient algorithm to obtain such a cycle. The complexity of this algorithm is O(l³). In case m = n, we find a hamiltonian cycle of G. This generalizes a result given in [10].

New variants of (a,b)-trees with relaxed balance are proposed. These variants have better space utilization than the earlier proposals, while the asymptotic complexity of rebalancing is unchanged. The proof of complexity, which is derived, is much simpler than the ones previously published. Through experiments, some of the most interesting applications of this data structure are modeled, and it is demonstrated that the new variants are competitive.

According to the Algorithmic Coding Theorem, minimal programs of any universal machine are prefix-codes asymptotically optimal (i.e. optimal up to at most an additive, unknown constant) with respect to the machine algorithmic probabilities. A stronger version of this result will be proven for a class of machines, not necessarily universal, and any semi-distribution. Furthermore, minimal programs with respect to universal machines will be shown to be almost optimal (i.e. optimal up to an additive constant less than or equal to 2) for any semi-computable semi-distribution. Finally, a complete characterization of all machines satisfying the Algorithmic Coding Theorem is given.

We employ the Always Approximately Correct or AAC model defined in [35], to prove learnability results for classes of Boolean functions over arbitrary finite Abelian groups. This model is an extension of Angluin's Query model of exact learning. The Boolean functions we consider belong to approximation classes, i.e. functions that are approximable (in various norms) by few Fourier basis functions, or irreducible characters of the domain Abelian group. We contrast our learnability results to previous results for similar classes in the PAC model of learning with and without membership queries.

In addition, we discuss new, natural issues and questions that arise when the AAC model is used. One such question is whether a uniform training set is available for learning any function in a given approximation class. No analogous question seems to have been studied in the context of Angluin's Query model. Another question is whether the training set can be found quickly if the approximation class of the function is completely unknown to the learner, or only partial information about the approximation class is given to the learner (in addition to the answers to membership queries).

In order to prove the learnability results in this paper we require new techniques for efficiently sampling Boolean functions using the character theory of finite Abelian groups, as well as the development of algebraic algorithms. The techniques result in other natural applications closely related to learning, for example, query complexity of deterministic algorithms for testing linearity, efficient pseudorandom generators, and estimating VC dimensions for classes of Boolean functions over finite Abelian groups.

The Parallel Repetition Theorem says that n-fold parallel execution of a two-prover one-round interactive proof system reduces the error probability exponentially in n. The bound on the error probability of the parallelized system depends on the error probability and the answer size of the single proof system. It is still unknown whether the theorem holds true with a bound depending only on the query size. This kind of a bound may be preferable whenever the query size is considerably smaller than the answer size, what really happens in some cryptographic protocols. Such a bound is only known in the case that queries to the provers are independent. The present paper extends this result to some cases of strong correlation between queries. In particular, a query-based variant of the Parallel Repetition Theorem is proven when the graph of dependence between queries to the provers is a tree and, in a bit weaker form, when this graph is a cycle.

The nearest neighbor interchange (nni) distance is a classical metric for measuring the distance (dissimilarity) between evolutionary trees. It has been known that computing the nni distance is NP-complete. Existing approximation algorithms can attain an approximation ratio log n for unweighted trees and 4 log n for weighted trees; yet these algorithms are limited to degree-3 trees. This paper extends the study of nni distance to trees with non-uniform degrees. We formulate the necessary and sufficient conditions for nni transformation and devise more topology-sensitive approximation algorithms to handle trees with non-uniform degrees. The approximation ratios are respectively and for unweighted and weighted trees, where d ≥ 4 is the maximum degree of the input trees.

There are presented certain membrane systems for computing the inverse of one-way functions in a polynomial time. The membrane systems are derived from some mathematical models of natural processes investigated in biochemistry and they have been introduced by Gh. Păun.