Non-reducible descriptions for conditional Kolmogorov complexity

Assume that a program p$p$ on input a$a$ outputs b$b$. We are looking for a shorter program q$q$ having the same property (q(a)=b$q\left(a\right)=b$). In addition, we want q$q$ to be simple conditional to p$p$ (this means that the conditional Kolmogorov complexity K(q|p)$K\left(q\right|p)$ is negligible). In the present paper, we prove that sometimes there is no such program q$q$, even in the case when the complexity of p$p$ is much bigger than K(b|a)$K\left(b\right|a)$. We give three different constructions that use the game approach, probabilistic arguments and algebraic arguments, respectively.     

Lower bounds for the bilinear complexity of associative algebras

Let R(A) denote the bilinear complexity (also called rank) of a finite dimensional associative algebra A.?We prove that if the decomposition of into simple algebras contains only noncommutative factors, that is, the division algebra is noncommutative or . In particular, -matrix multiplication requires at least essential bilinear multiplications. We also derive lower bounds of the form essential bilinear multiplications. We also derive lower bounds of the form for the algebra of upper triangular -matrices and the algebra of truncated bivariate polynomials in the indeterminates X,Y over some field k.?A class of algebras that has received wide attention in this context con-sists of those algebras A for which the Alder—Strassen Bound is sharp, i.e., R(A) = 2dim A—t is the number of maximal twosided ideals in A. These algebras are called algebras of minimal rank. We determine all semisimple algebras of minimal rank over arbitrary fields and all algebras of minimal rank over algebraically closed fields. Received: January 12, 2000.     

Lower bounds for the multiplicative complexity of matrix multiplication

We prove a lower bound of km + mn + k—m + n— 3 for the multiplicative complexity of the multiplication of -matrices with -matrices using the substitution method. Received: July 8, 1997.     

Approximation bounds for some sparse kernel regression algorithms

Gaussian processes have been widely applied to regression problems with good performance. However, they can be computationally expensive. In order to reduce the computational cost, there have been recent studies on using sparse approximations in gaussian processes. In this article, we investigate properties of certain sparse regression algorithms that approximately solve a gaussian process. We obtain approximation bounds and compare our results with related methods.     

Tight complexity bounds for the two-dimensional real knapsack problem

We study the complexity of the 2-dimensional knapsack problem , where . The problem is defined in terms of real numbers and we study it where an integral solution is sought under a real number model of computation. We obtain a tight complexity bound , where . Received: November 1998 / Accepted: December 1998     

On lower bounds for the complexity of polynomials and their multiples

We prove a theorem giving arbitrarily long explicit sequences of algebraic numbers such that any nonzero polynomial f(X) satisfying has nonscalar complexity for some positive constant C independent of s. A similar result is shown for rapidly growing rational sequences. Received: April 6 1999.     

Upper bounds and approximate solutions for multidisk problems

Approximate solutions of multiobjective H^∞ -optimization problems, also referred to as multidisk problems, are considered. The main result is an algorithm that makes it possible to compute an upper bound for linear two-disk problems and also a (suboptimal) controller that achieves this bound. The algorithm involves some graphical techniques which can also be used to demonstrate explicitly the design tradeoffs inherent in problems involving competing objectives. The results can be generalized to multidisk problems     

Some order dimension bounds for communication complexity problems

Summary We associate with a general (0, 1)-matrixM an ordered setP(M) and derive lower and upper bounds for the deterministic communication complexity ofM in terms of the order dimension ofP(M). We furthermore consider the special class of communication matricesM obtained as cliques vs. stable sets incidence matrices of comparability graphsG. We bound their complexity byO((logd)·(logn)), wheren is the number of nodes ofG andd is the order dimension of an orientation ofG. In this special case, our bound is shown to improve other well-known bounds obtained for the general cliques vs. stable set problem.     

Lower bounds on space complexity for contextfree recognition

Summary Using methods from linear algebra and crossing-sequence arguments it is shown that logarithmic space is necessary for the recognition of all context-free nonregular subsets of {a₁}^* ... {a_n}^*, where {a₁,...,a_n} is some alphabet. It then follows that log n is a lower bound on the space complexity for the recognition of any bounded or deterministic non-regular context-free language.     

Upper and lower bounds for approximation in the gap metric

Upper and lower bounds for the closest approximant of degree k <n in the gap metric to a plant of degree n are obtained. The bounds are expressed in terms of the singular values of two Hankel operators defined in terms of the symbol of the graph of the plant. The question of robust stability and performance of feedback systems is examined in the context of approximation of plant and controller in the gap metric     

Upper bounds for the solution of the discrete Riccati equation

Upper bounds for individual eigenvalues and for summations of eigenvalues including the trace of the solution of the discrete algebraic Riccati equation are presented. Some are new, and some supplement bounds in the literature     

Upper matrix bounds for the discrete algebraic Riccati matrixequation

We propose upper matrix bounds for the discrete algebraic Riccati matrix equation. We show that our results are less restrictive than the previous bounds. Finally, we give numerical examples in order to verify the effectiveness of our results     

Aspect-ratio Voronoi diagram and its complexity bounds

This Letter first defines an aspect ratio of a triangle by the ratio of the longest side over the minimal height. Given a set of line segments, any point p in the plane is associated with the worst aspect ratio for all the triangles defined by the point and the line segments. When a line segment si gives the worst ratio, we say that p is dominated by si. Now, an aspect-ratio Voronoi diagram for a set of line segments is a partition of the plane by this dominance relation. We first give a formal definition of the Voronoi diagram and give O(n2+ε) upper bound and Ω(n²) lower bound on the complexity, where ε is any small positive number. The Voronoi diagram is interesting in itself, and it also has an application to a problem of finding an optimal point to insert into a simple polygon to have a triangulation that is optimal in the sense of the aspect ratio.     

Propositional lower bounds: Algorithms and complexity

Propositional greatest lower bounds (GLBs) are logically‐defined approximations of a knowledge base. They were defined in the context of Knowledge Compilation, a technique developed for addressing high computational cost of logical inference. A GLB allows for polynomial‐time complete on‐line reasoning, although soundness is not guaranteed. In this paper we propose new algorithms for the generation of a GLB. Furthermore, we give precise characterization of the computational complexity of the problem of generating such lower bounds, thus addressing in a formal way the question “how many queries are needed to amortize the overhead of compilation?”