Extremal Relations between Additive Loss Functions and the Kolmogorov Complexity

Conditions are presented under which the maximum of the Kolmogorov complexity (algorithmic entropy) K(₁... _N ) is attained, given the cost f( _i ) of a message ₁... _N . Various extremal relations between the message cost and the Kolmogorov complexity are also considered; in particular, the minimization problem for the function f( _i ) – K(₁... _N ) is studied. Here, is a parameter, called the temperature by analogy with thermodynamics. We also study domains of small variation of this function.     

Primality testing with fewer random bits

In the usual formulations of the Miller-Rabin and Solovay-Strassen primality testing algorithms for a numbern, the algorithm chooses candidatesx ₁,x ₂, ...,x _k uniformly and independently at random from _n , and tests if any is a witness to the compositeness ofn. For either algorithm, the probabilty that it errs is at most 2^–k .In this paper, we study the error probabilities of these algorithms when the candidates are instead chosen asx, x+1, ..., x+k–1, wherex is chosen uniformly at random from _n . We prove that fork=[1/2log₂ n], the error probability of the Miller-Rabin test is no more thann ^–1/2+o(1), which improves on the boundn ^–1/4+o(1) previously obtained by Bach. We prove similar bounds for the Solovay-Strassen test, but they are not quite as strong; in particular, we only obtain a bound ofn ^–1/2+o(1) if the number of distinct prime factors ofn iso(logn/loglogn).     

The Nonexistence of Ternary [284, 6, 188] Codes

Let [n, k, d] _q codes be linear codes of length n, dimension k, and minimum Hamming distance d over GF(q). Let n _q (k, d) be the smallest value of n for which there exists an [n, k, d] _q code. It is known from [1, 2] that 284 n ₃(6, 188) 285 and 285 n ₃(6, 189) 286. In this paper, the nonexistence of [284, 6, 188]₃ codes is proved, whence we get n ₃(6, 188) = 285 and n ₃(6, 189) = 286.     

Maintaining the visibility map of spheres while moving the viewpoint on a circle at infinity

We investigate three-dimensional visibility problems for scenes that consist ofn non-intersecting spheres. The viewing point moves on a flightpath that is part of a circle at infinity given by a planeP and a range of angles {(t)¦t[01]} [02]. At timet, the lines of sight are parallel to the ray inP, which starts in the origin ofP and represents the angle(t) (orthographic views of the scene). We give an algorithm that computes the visibility graph at the start of the flight, all time parameters at which the topology of the scene changes, and the corresponding topology changes. The algorithm has running time0(n + k + p) logn), wheren is the number of spheres in the scene;p is the number of transparent topology changes (the number of different scene topologies visible along the flight path, assuming that all spheres are transparent); andk denotes the number of vertices (conflicts) which are in the (transparent) visibility graph at the start and do not disappear during the flight.The second author was supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM).     

Sufficiency conditions for existence of an optimal feedback control in stochastic mechanics

In the framework of stochastic mechanics, the following problem is considered: in a set of admissible feedback controls v, with range inE ⁿ , find one minimizing the expectationE _sx { _s ^T L(t, (t), (t, (t)))dt + W _T ((T))} for all (s, x) [0,T) E ⁿ , whereL(t, x, ) = (/12)m ² – U(t, x) is the classical action integrand and is an-dimensional diffusion process in the weak sense, (see Bensoussan, 1982) with drift and diffusion coefficientD constant > 0.W _T andU are given real functions. Sufficiency conditions for the existence of such an optimal feedback control are given. Dedicated to George Leitmann Recommended by G.J. Olsder Presented at the Third Workshop on Control Mechanics in honor of George Leitmann, January 22–24, 1990, University of Southern California, Los Angeles, California (USA).     

Systems of Strings with High Mutual Complexity

Consider a binary string x ₀ of Kolmogorov complexity K(x ₀) n. The question is whether there exist two strings x ₁ and x ₂ such that the approximate equalities K(x _i x _j ) n and K(x _i x _j , x _k ) n hold for all 0 i, j, k 2, i j k, i k. We prove that the answer is positive if we require the equalities to hold up to an additive term O(log K(x ₀)). It becomes negative in the case of better accuracy, namely, O(log n).     

On Bounding Solutions of Underdetermined Systems

Sufficient conditions for the existence and uniqueness of a solution x* D (R ⁿ ) of Y(x) = 0 where : R ⁿ R ^m (m n) with C ²(D) where D R ⁿ is an open convex set and Y = (x)⁺ are given, and are compared with similar results due to Zhang, Li and Shen (Reliable Computing 5(1) (1999)). An algorithm for bounding zeros of f (·) is described, and numerical results for several examples are given.     

Range Estimation Is NP-Hard for ε2 Accuracy and Feasible for ε2−δ

The basic problem of interval computations is: given a function f(x ₁,..., x _n) and n intervals [x _i, x _i], find the (interval) range yof the given function on the given intervals. It is known that even for quadratic polynomials f(x ₁,..., x _n), this problem is NP-hard. In this paper, following the advice of A. Neumaier, we analyze the complexity of asymptotic range estimation, when the bound on the width of the input intervals tends to 0. We show that for small c > 0, if we want to compute the range with an accuracy c ₂, then the problem is still NP-hard; on the other hand, for every > 0, there exists a feasible algorithm which asymptotically, estimates the range with an accuracy c ^2–.     

Diagrammatic Analysis of Interval Linear Equations - Part II: The Two-Dimensional Case and Generalization to n Dimensions

Using the results obtained for the one-dimensional case in Part I (Reliable Computing 9(1) (2003), pp. 1–20) of the paper, an analysis of the two-dimensional relational expression a ₁ x ₁ + a ₂ x ₂ b, where {, , , =}, is conducted with the help of a midpoint-radius diagram and other auxiliary diagrams. The solution sets are obtained with a simple boundary-line selection rule derived using these tools, and are characterized by types of one-dimensional cuts through the solution space. A classification of basic possible solution types is provided in detail. The generalization of the approach for n-dimensional interval systems and avenues for further research are also outlined.     

The existence of solutions,stability, and linearization of volterra systems

LetB be a Banach space ofR _n valued continuous functions on [0, ) withfB. Consider the nonlinear Volterra integral equation (^*)x(t)+ _o ^t K(t,s,x(s))ds. We use the implicit function theorem to give sufficient conditions onB andK (t,s,x) for the existence of a unique solutionxB to (^*) for eachf B with f ^B sufficiently small. Moreover, there is a constantM>0 independent off with Mf^B.Part of this work was done while the author was visiting at Wright State University.     

Correlation structure of training data and the fitting ability of back propagation networks: Some experimental results

White [6–8] has theoretically shown that learning procedures used in network training are inherently statistical in nature. This paper takes a small but pioneering experimental step towards learning about this statistical behaviour by showing that the results obtained are completely in line with White's theory. We show that, given two random vectorsX (input) andY (target), which follow a two-dimensional standard normal distribution, and fixed network complexity, the network's fitting ability definitely improves with increasing correlation coefficient r_XY (0r_XY1) betweenX andY. We also provide numerical examples which support that both increasing the network complexity and training for much longer do improve the network's performance. However, as we clearly demonstrate, these improvements are far from dramatic, except in the case r_XY=+ 1. This is mainly due to the existence of a theoretical lower bound to the inherent conditional variance, as we both analytically and numerically show. Finally, the fitting ability of the network for a test set is illustrated with an example.Nomenclature X Generalr-dimensional random vector. In this work it is a one-dimensional normal vector and represents the input vector - Y Generalp-dimensional random vector. In this work it is a one-dimensional normal vector and represents the target vector - Z Generalr+p dimensional random vector. In this work it is a two-dimensional normal vector - E Expectation operator (Lebesgue integral) - g(X)=E(Y¦X) Conditional expectation - Experimental random error (defined by Eq. (2.1)) - y Realized target value - o Output value - f Network's output function. It is formally expressed asf: R ^r×WR ^p, whereW is the appropriate weight space - Average (or expected) performance function. It is defined by Eq. (2.2) as (w)=E[(Yf(X,w)],w W - Network's performance - w ^* Weight vector for optimal solution. That is, the objective of network is such that (w ^*) is minimum - C ₁ Component one - C ₂ Component two - Z Matrix of realised values of the random vectorZ overn observations - Z _t Transformed matrix version ofZ in such a way thatX andY have values in [0,1] - X _t ,Y _t Transformed versions ofX andY and both are standard one-dimensional normal vectors - n _h Number of hidden nodes (neurons) - r _XY Correlation coefficient between eitherX andY orX _t andY _t - _s and _k in Eq. (3.1) and afterwards _s is average value of 100 differentZ _t matrices. _k is the error function ofkthZ _t , matrix. In Eq. (3.1), the summation is fromk=1 to 100, and in Eq. (3.2) fromi=1 ton. In Eq. (3.2)o _ki andy _ki are the output and target values for the kthZ _t matrix and ith observation, respectively - ^1/2(w ^*) and _k (w_n) k(w_n) is the sample analogue of ^1/2(w ^*) - _Y ² In Eq. (4.1) and afterwards, _Y ² is the variance ofY - _Y ² variance ofY _t . In Sect. 4.3 the transformation isY _t=a Y+b - Y _max,Y _min the maximum and minimum values ofY - R Correlation matrix ofX andY - Covariance matrix ofX andY - Membership symbol in set theory     

On communication-bounded synchronized alternating finite automata

We continue the study of communication-bounded synchronized alternating finite automata (SAFA), first considered by Hromkovi et al. We show that to accept a nonregular language, an SAFA needs to generate at least (log logn) communication symbols infinitely often; furthermore, a synchronized alternating finite automaton without nondeterminism (SUFA) needs to generate at least(log logn) communication symbols infinitely often for some constantk1. We also show that these bounds are tight.Next, we establish dense hierarchies of these machines on the function bounding the number of communication symbols. Finally, we give a characterization of NP in terms of communication-bounded multihead synchronized alternating finite automata, namely, NP = _k1 L(SAFA(k-heads,n ^k -com)). This result recasts the relationships between P, NP, and PSPACE in terms of multihead synchronized alternating finite automata.Research supported in part by NSF Grant CCR89-18409     

On the valuedness of finite transducers

Summary We investigate the valuedness of finite transducers in connection with their inner structure. We show: The valuedness of a finite-valued nondeterministic generalized sequential machine (NGSM) M with n states and output alphabet is at most the maximum of (1-1/#) · (2 ^k ₁ · k ₃ ) ⁿ · n ⁿ ·# ^{n 3 ·k} ₄ / ³ and 1/#·(2 ^k ₂ ·k ₃ ·(1+k ₄ )) ⁿ ·n ⁿ where k ₁6.25 and k ₂11.89 are constants and k ₃1 and k ₄0 are local structural parameters of M. There are two simple criteria which characterize the infinite valuedness of an NGSM. By these criteria, it is decidable in polynomial time whether or not an NGSM is infinite-valued. In both cases, # > 1 and # = 1, the above upper bound for the valuedness is almost optimal. By reduction, all results can be easily generalized to normalized finite transducers.     

The Kreisel length-of-proof problem

A first-order system F has theKreisel length-of-proof property if the following statement is true for all formulas(x): If there is ak1 such that for alln0 there is a proof of(¯n) in F with at mostk lines, then there is a proof of x(x) in F. We consider this property for Parikh systems, which are first-order axiomatic systems that contain a finite number of axiom schemata (including individual axioms) and a finite number of rules of inference. We prove that any usual Parikh system formulation of Peano arithmetic has the Kreisel length-of-proof property if the underlying logic of the system is formulated without a schema for universal instantiation in either one of two ways. (In one way, the formula to be instantiated is built up in steps, and in the other way, the term to be substituted is built up in steps.) Our method of proof uses techniques and ideas from unification theory.     

Gradually intractable problems and nondeterministic log-space lower bounds

The paper places five different problems (thek-pebble game problem, two problems aboutk finite automata, the reachability problem for Petri nets withk tokens, and the teachability problem for graphs whose k-dimensional edge sets are described by Cartesian products ofk factors) into the hierarchyNL _k of problems solvable by nondeterministic Turing machines ink-log₂ n space (and binary tape alphabet, to avoid tape speed-up). The results, when combined with the conjecture thatNL _i contains problems that requireO(n ^k ) deterministic time, show that these problems, while inP for every fixed value ofk, have polynomial deterministic time complexities with the degree of the polynomial growing linearly with the parameterk, and hence are, in this sense, gradually intractable.     

A Delay-Averaged Logistic Model

For the equation x(t) = x(t) (1-(1/) _t-- ^t- x(u)du), > 0, > 0, > 0, conditions for the stability of a nonzero stationary solution under small perturbations are determined.     

Hierarchy theorems for two-way finite state transducers

Summary For a family of languages , CAL() is defined as the family of images of under nondeterministic two-way finite state transducers, while FINITE · VISIT() is the closure of under deterministic two-way finite state transducers; CAL⁰()= and for n0, CAL ⁿ⁺¹()=CAL ⁿ (CAL()). For any semiAFL , if FINITE · VISIT() CAL(), then CAL ⁿ () forms a proper hierarchy and for every n0, FINITE · VISIT(CALⁿ()) CAL ⁿ⁺¹() FINITE · VISIT(CAL ⁿ⁺¹()). If is a SLIP semiAFL or a weakly k-iterative full semiAFL or a semiAFL contained in any full bounded AFL, then FINITE · VISIT() CAL() and in the last two cases, FINITE · VISIT(). If is a substitution closed full principal semiAFL and FINITE · VISIT(), then FINITE · VISIT() CAL(). If is a substitution closed full principal semiAFL generated by a language without an infinite regular set and ₁ is a full semiAFL, then is contained in CAL^m(₁) if and only if it is contained in ₁. Among the applications of these results are the following. For the following families , CAL ⁿ () forms a proper hierarchy: =INDEXED, =ETOL, and any semiAFL contained in CF. The family CF is incomparable with CAL ^m (NESA) where NESA is the family of one-way nonerasing stack languages and INDEXED is incomparable with CAL ^m (STACK) where STACK is the family of one-way stack languages.This work was supported in part by the National Science Foundation under Grants No. DCR74-15091 and MCS-78-04725     

On the Quadratic Convergence of the Levenberg-Marquardt Method without Nonsingularity Assumption

Recently, Yamashita and Fukushima [11] established an interesting quadratic convergence result for the Levenberg-Marquardt method without the nonsingularity assumption. This paper extends the result of Yamashita and Fukushima by using _k=||F(x_k)||, where [1,2], instead of _k=||F(x_k)||² as the Levenberg-Marquardt parameter. If ||F(x)|| provides a local error bound for the system of nonlinear equations F(x)=0, it is shown that the sequence {x_k} generated by the new method converges to a solution quadratically, which is stronger than dist(x_k,X^*)0 given by Yamashita and Fukushima. Numerical results show that the method performs well for singular problems.     

Implementation of an Algorithm for Finding Analyticity Conditions for a Solution of a Difference Equation

A linear difference operator L with polynomial coefficients and a function F(x) satisfying the equation LF(x) = 0 are considered. The function is assumed to be analytic in the interval (–, d), where > 0. In the paper, an implementation of an algorithm suggested by S.A. Abramov and M. van Hoeij for finding conditions that guarantee analyticity of F(x) on the entire real axis is presented. The analyticity conditions are linear relations for values of F(x) and its derivatives at a given point belonging to the half-interval [0, d). A procedure for computing values of F(x) and its derivatives up to a prescribed order at a given point x ₀ is also implemented. Examples illustrating the program operation are presented.     

To the Metrical Rigidity of Binary Codes

A code C in the n-dimensional metric space E ⁿ over GF(2) is called metrically rigid if each isometry I : C E ⁿ can be extended to an isometry of the whole space E ⁿ . For n large enough, metrical rigidity of any length-n binary code that contains a 2-(n, k, )-design is proved. The class of such codes includes, for instance, all families of uniformly packed codes of large enough lengths that satisfy the condition d – 2, where d is the code distance and is the covering radius.