Information theoretic measures of UHG graphs with low computational complexity

We introduce a novel graph class we call universal hierarchical graphs (UHG) whose topology can be found numerously in problems representing, e.g., temporal, spacial or general process structures of systems. For this graph class we show, that we can naturally assign two probability distributions, for nodes and for edges, which lead us directly to the definition of the entropy and joint entropy and, hence, mutual information establishing an information theory for this graph class. Furthermore, we provide some results under which conditions these constraint probability distributions maximize the corresponding entropy. Also, we demonstrate that these entropic measures can be computed efficiently which is a prerequisite for every large scale practical application and show some numerical examples.     

Information granulation and uncertainty measures in interval-valued intuitionistic fuzzy information systems

Information granulation and entropy are main approaches for investigating the uncertainty of information systems, which have been widely employed in many practical domains. In this paper, information granulation and uncertainty measures for interval-valued intuitionistic fuzzy binary granular structures are addressed. First, we propose the representation of interval-valued intuitionistic fuzzy information granules and examine some operations of interval-valued intuitionistic fuzzy granular structures. Second, the interval-valued intuitionistic fuzzy information granularity is introduced to depict the distinguishment ability of an interval-valued intuitionistic fuzzy granular structure (IIFGS), which is a natural extension of fuzzy information granularity. Third, we discuss how to scale the uncertainty of an IIFGS using the extended information entropy and the uncertainty among interval-valued intuitionistic fuzzy granular structures using the expanded mutual information derived from the presented intuitionistic fuzzy information entropy. Fourth, we discovery the relationship between the developed interval-valued intuitionistic fuzzy information entropy and the intuitionistic fuzzy information granularity presented in this paper.     

Accessing complexity from genome information

This paper studies the information content of the chromosomes of 24 species. In a first phase, a scheme inspired in dynamical system state space representation is developed. For each chromosome the state space dynamical evolution is shed into a two dimensional chart. The plots are then analyzed and characterized in the perspective of fractal dimension. This information is integrated in two measures of the species’ complexity addressing its average and variability. The results are in close accordance with phylogenetics pointing quantitative aspects of the species’ genomic complexity.     

Software Engineering and complexity in effective Algebraic Geometry

One may represent polynomials not only by their coefficients but also by arithmetic circuits which evaluate them. This idea allowed in the past fifteen years considerable complexity progress in effective polynomial equation solving. We present a circuit based computation model which captures all known symbolic elimination algorithms in effective Algebraic Geometry and exhibit a class of simple elimination problems which require exponential size circuits to be solved in this model. This implies that the known, circuit based elimination algorithms are already optimal.     

On the complexity of expansive measures

We prove that the existence of positively expansive measures for continuous maps on compact metric spaces implies the existence of e 0 and a sequence of(m, e)-separated sets whose cardinalities go to infinite as m →∞. We then prove that maps exhibiting such a constant e and the positively expansive maps share some properties.     

Error linear complexity measures for multisequences

Complexity measures for sequences over finite fields, such as the linear complexity and the k-error linear complexity, play an important role in cryptology. Recent developments in stream ciphers point towards an interest in word-based stream ciphers, which require the study of the complexity of multisequences. We introduce various options for error linear complexity measures for multisequences. For finite multisequences as well as for periodic multisequences with prime period, we present formulas for the number of multisequences with given error linear complexity for several cases, and we present lower bounds for the expected error linear complexity.     

Galerkin information,the hyperbolic cross,and the complexity of operator equations

We obtain an exact power order of the complexity of the approximate solution of a certain class of operator equations in a Hibert space. We show that the optimal power order is realized by an algorithm that uses Galerkin information associated with the hyperbolic cross. As a corollary we derive an exact power order of the complexity of the approximate solution of Volterra integral equations whose kernels and free terms belong to Sobolev classes.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 43, No. 5, pp. 639–648, May, 1991.     

Information storage and search complexity theory

We propose a new information-graph model for information storage and search. This model generalizes a number of known data-representation models. We study the main properties of the proposed model. We solve the problem of optimal informational graph synthesis for a wide class of search problems, including the most acute database search problems.     

The complexity of depth-two information networks

The lower bound Ω(n log₂ n) for the complexity of an arbitrary depth-two information network with n inputs and n outputs is proved providing the inputs are independent, the outputs are independent, and the total information of any input and any output is n times less than the entropy of any input or output. A similar estimate for Boolean depth-two circuits of functional elements is obtained as a corollary.     

Characterizations, bounds, and probabilistic analysis of two complexity measures for linear programming problems

This note studies _A , a condition number used in the linear programming algorithm of Vavasis and Ye [14] whose running time depends only on the constraint matrix A∈ℝ ^m×n , and (A), a variant of another condition number due to Ye [17] that also arises in complexity analyses of linear programming problems. We provide a new characterization of _A and relate _A and (A). Furthermore, we show that if A is a standard Gaussian matrix, then E(ln _A )=O(min{mlnn,n}). Thus, the expected running time of the Vavasis-Ye algorithm for linear programming problems is bounded by a polynomial in m and n for any right-hand side and objective coefficient vectors when A is randomly generated in this way. As a corollary of the close relation between _A and (A), we show that the same bound holds for E(ln(A)). Received: September 1998 / Accepted: September 2000?Published online January 17, 2001     

Duality respecting representations and compatible complexity measures for gammoids

We show that every gammoid has special digraph representations, such that a representation of the dual of the gammoid may be easily obtained by reversing all arcs. In an informal sense, the duality notion of a poset applied to the digraph of a special representation of a gammoid commutes with the operation of forming the dual of that gammoid. We use these special representations in order to define a complexity measure for gammoids, such that the classes of gammoids with bounded complexity are closed under duality, minors, and direct sums.     

Borel complexity of the space of probability measures

Using a technique developed by Louveau and Saint Raymond, we find the complexity of the space of probability measures in the Borel hierarchy: if is any non-Polish Borel subspace of a Polish space, then , the space of probability Borel measures on with the weak topology, is always true , where is the least ordinal such that is .

     

Single machine total tardiness maximization problems: complexity and algorithms

In this paper, we consider some scheduling problems on a single machine, where weighted or unweighted total tardiness has to be maximized in contrast to usual minimization problems. These problems are theoretically important and have also practical interpretations. For the total weighted tardiness maximization problem, we present an NP-hardness proof and a pseudo-polynomial solution algorithm. For the unweighted total tardiness maximization problem with release dates, NP-hardness is proven. Complexity results for some other classical objective functions (e.g., the number of tardy jobs, total completion time) and various additional constraints (e.g., deadlines, weights and/or release dates of jobs may be given) are presented as well.     

Cumulative measures of information and stochastic orders

In this paper we present some known results on cumulative measures of information, study their properties and relate these definitions to concepts of reliability theory. We give some relations of these measures of discrimination with some well-known stochastic orders and with the relative reversed hazard rate order. We investigate also a stochastic comparison among the empirical cumulative measures that can be related to the cumulative measures. Large part of this paper is a survey article; however, in the last section, we define a new measure of discrimination between residual lifetimes and study some of its properties.     

Composition limits and separating examples for some boolean function complexity measures

Block sensitivity (bs(f)), certificate complexity (C(f)) and fractional certificate complexity (C*(f)) are three fundamental combinatorial measures of complexity of a boolean function f. It has long been known that bs(f) ≤ C*(f) ≤ C(f) = O(bs(f)²). We provide an infinite family of examples for which C(f) grows quadratically in C*(f) (and also bs(f)) giving optimal separations between these measures. Previously the biggest separation known was \(C(f) = C*(f)^{\log _{4,5} 5}\). We also give a family of examples for which C*(f)= Ω (bs(f)^3/2).These examples are obtained by composing boolean functions in various ways. Here the composition fog of f with g is obtained by substituting for each variable of f a copy of g on disjoint sets of variables. To construct and analyse these examples we systematically investigate the behaviour under function composition of these measures and also the sensitivity measure s(f). The measures s(f), C(f) and C*(f) behave nicely under composition: they are submultiplicative (where measure m is submultiplicative if m(fog) ≤ m(f)m(g)) with equality holding under some fairly general conditions. The measure bs(f) is qualitatively different: it is not submultiplicative. This qualitative difference was not noticed in the previous literature and we correct some errors that appeared in previous papers. We define the composition limit of a measure m at function f, m ^lim(f) to be the limit as k grows of m(f ^(k))^1/k , where f ^(k) is the iterated composition of f with itself k-times. For any function f we show that bs ^lim(f) = (C*)^lim(f) and characterize s ^lim(f); (C*)^lim(f), and C ^lim(f) in terms of the largest eigenvalue of a certain set of 2×2 matrices associated with f.     

Information complexity of weakly singular integral equations

We establish the exact power order of information complexity for integral equations whose kernels have power singularities and free terms belong to the corresponding Hölder space.Translated from Ukrainskii Matematicheskii Zhurnal, Vol.46, No. 11, pp. 1527–1533, November, 1994.This work was supported by the Foundation for Fundamental Researches of the Ukrainian State Committee on Science and Technology.