A stabilizing solution to the algebraic Riccati equation the resolvent method

A new approach to the problem of analytic representation of the stabilizing solution to the algebraic Riccati equation is proposed. The quadratic matrix equation is reduced to a linear one using the resolvent (sI _2n -H)^?1 of the Hamilton matrix. The symmetric solution to the obtained linear equation defines a stabilizing solution to the Riccati equation. Matrix coefficients of the linear equation are defined by the integral of resolvent in the complex domain over the closed contour which contains all its right poles. This construction of the solution to the problem gives rise to the development of important parts of the analysis and of the corresponding computing procedures.     

Attracting ellipsoids and synthesis of oscillatory regimes

An approach to stabilization of nonlinear oscillations in multidimensional spaces is proposed on the basis of the V.I. Zubov’s stability theory for invariant sets. As a special case, the derived controls make it possible to excite self-oscillating regimes in specified state subspaces R ^2k ? R ²ⁿ with simultaneous oscillation damping on Cartesian products R ^2n?2k .     

Relativizing small complexity classes and their theories

Existing definitions of the relativizations of NC ¹, L and NL do not preserve the inclusions \({{\bf NC}^1 \subseteq {\bf L}, {\bf NL}\subseteq {\bf AC}^1}\). We start by giving the first definitions that preserve them. Here for L and NL we define their relativizations using Wilson’s stack oracle model, but limit the height of the stack to a constant (instead of log(n)). We show that the collapse of any two classes in \({\{{\bf AC}^0 (m), {\bf TC}^0, {\bf NC}^1, {\bf L}, {\bf NL}\}}\) implies the collapse of their relativizations. Next we exhibit an oracle α that makes AC ^k (α) a proper hierarchy. This strengthens and clarifies the separations of the relativized theories in Takeuti (1995). The idea is that a circuit whose nested depth of oracle gates is bounded by k cannot compute correctly the (k + 1) compositions of every oracle function. Finally, we develop theories that characterize the relativizations of subclasses of P by modifying theories previously defined by the second two authors. A function is provably total in a theory iff it is in the corresponding relativized class, and hence, the oracle separations imply separations for the relativized theories.     

The M-computations induced by accessibility relations in nonstandard models M of Hoare logic

Hoare logic [1] is a logic used as a way of specifying semantics of programming languages, which has been extended to be a separation logic to reason about mutable heap structure [2]. In a model M of Hoare logic, each program α induces an M-computable function f _α ^M on the universe of M; and the M-recursive functions are defined on M. It will be proved that the class of all the M-computable functions f _α ^M induced by programs is equal to the class of all the M-recursive functions. Moreover, each M-recursive function is \(\sum {_1^{{N^M}}} \)-definable in M, where the universal quantifier is a number quantifier ranging over the standard part of a nonstandard model M.     

raSAT: an SMT solver for polynomial constraints

This paper presents raSAT SMT solver, which is aimed to handle polynomial constraints over both reals and integers with simple unified methodologies. Its three main features are (1) a raSAT loop for inequalities, which adds testing to interval constraint propagation to accelerate SAT detection, (2) a non-constructive reasoning for equations over reals based on the generalized intermediate value theorem, and (3) soundness of floating-point arithmetic that is guaranteed by (a) rounding up/down over-approximations of intervals, and (b) confirmation of a satisfying instance detected by testing using the iRRAM package, which guarantees error bounds.     

Error bounds for complementarity problems with tridiagonal nonlinear functions

In this paper we consider the complementarity problem NCP(f) with f(x) = Mx + φ(x), where M ∈ R ^n×n is a real matrix and φ is a so-called tridiagonal (nonlinear) mapping. This problem occurs, for example, if certain classes of free boundary problems are discretized. We compute error bounds for approximations \({\hat x}\) to a solution x* of the discretized problems. The error bounds are improved by an iterative method and can be made arbitrarily small. The ideas are illustrated by numerical experiments.     

Property-Preserving Data Reconstruction

We initiate a new line of investigation into online property-preserving data reconstruction. Consider a dataset which is assumed to satisfy various (known) structural properties; e.g., it may consist of sorted numbers, or points on a manifold, or vectors in a polyhedral cone, or codewords from an error-correcting code. Because of noise and errors, however, an (unknown) fraction of the data is deemed unsound, i.e., in violation with the expected structural properties. Can one still query into the dataset in an online fashion and be provided data that is always sound? In other words, can one design a filter which, when given a query to any item I in the dataset, returns a sound item J that, although not necessarily in the dataset, differs from I as infrequently as possible. No preprocessing should be allowed and queries should be answered online.We consider the case of a monotone function. Specifically, the dataset encodes a function f:{1,…,n}?? R that is at (unknown) distance ε from monotone, meaning that f can—and must—be modified at ε n places to become monotone.Our main result is a randomized filter that can answer any query in O(log?² nlog? log?n) time while modifying the function f at only O(ε n) places. The amortized time over n function evaluations is O(log?n). The filter works as stated with probability arbitrarily close to 1. We provide an alternative filter with O(log?n) worst case query time and O(ε nlog?n) function modifications. For reconstructing d-dimensional monotone functions of the form f:{1,…,n} ^d ? ? R, we present a filter that takes (2 ^O(d)(log?n)^4d?2log?log?n) time per query and modifies at most O(ε n ^d ) function values (for constant d).     

Patterns and anomalies in <Emphasis Type="Italic">k</Emphasis>-cores of real-world graphs with applications

How do the k-core structures of real-world graphs look like? What are the common patterns and the anomalies? How can we exploit them for applications? A k-core is the maximal subgraph in which all vertices have degree at least k. This concept has been applied to such diverse areas as hierarchical structure analysis, graph visualization, and graph clustering. Here, we explore pervasive patterns related to k-cores and emerging in graphs from diverse domains. Our discoveries are: (1) Mirror Pattern: coreness (i.e., maximum k such that each vertex belongs to the k-core) is strongly correlated with degree. (2) Core-Triangle Pattern: degeneracy (i.e., maximum k such that the k-core exists) obeys a 3-to-1 power-law with respect to the count of triangles. (3) Structured Core Pattern: degeneracy–cores are not cliques but have non-trivial structures such as core–periphery and communities. Our algorithmic contributions show the usefulness of these patterns. (1) Core-A, which measures the deviation from Mirror Pattern, successfully spots anomalies in real-world graphs, (2) Core-D, a single-pass streaming algorithm based on Core-Triangle Pattern, accurately estimates degeneracy up to 12 \(\times \) faster than its competitor. (3) Core-S, inspired by Structured Core Pattern, identifies influential spreaders up to 17 \(\times \) faster than its competitors with comparable accuracy.     

Distributive mereotopology: extended distributive contact lattices

The notion of contact algebra is one of the main tools in the region based theory of space. It is an extension of Boolean algebra with an additional relation C called contact. The elements of the Boolean algebra are considered as formal representations of spatial regions as analogues of physical bodies and Boolean operations are considered as operations for constructing new regions from given ones and also to define some mereological relations between regions as part-of, overlap and underlap. The contact relation is one of the basic mereotopological relations between regions expressing some topological nature. It is used also to define some other important mereotopological relations like non-tangential inclusion, dual contact, external contact and others. Most of these definitions are given by means of the operation of Boolean complementation. There are, however, some problems related to the motivation of the operation of Boolean complementation. In order to avoid these problems we propose a generalization of the notion of contact algebra by dropping the operation of complement and replacing the Boolean part of the definition by that of a distributive lattice. First steps in this direction were made in (Düntsch et al. Lect. Notes Comput. Sci. 4136, 135–147, 2006, Düntsch et al. J. Log. Algebraic Program. 76, 18–34, 2008) presenting the notion of distributive contact lattice based on the contact relation as the only mereotopological relation. In this paper we consider as non-definable primitives the relations of contact, nontangential inclusion and dual contact, extending considerably the language of distributive contact lattices. Part I of the paper is devoted to a suitable axiomatization of the new language called extended distributive contact lattice (EDC-lattice) by means of universal first-order axioms true in all contact algebras. EDC-lattices may be considered also as an algebraic tool for a certain subarea of mereotopology, called in this paper distributive mereotopology. The main result of Part I of the paper is a representation theorem, stating that each EDC-lattice can be isomorphically embedded into a contact algebra, showing in this way that the presented axiomatization preserves the meaning of mereotopological relations without considering Boolean complementation. Part II of the paper is devoted to topological representation theory of EDC-lattices, transferring into the distributive case important results from the topological representation theory of contact algebras. It is shown that under minor additional assumptions on distributive lattices as extensionality of the definable relations of overlap or underlap one can preserve the good topological interpretations of regions as regular closed or regular open sets in topological space.     

Two time-efficient gibbs sampling inference algorithms for biterm topic model

Biterm Topic Model (BTM) is an effective topic model proposed to handle short texts. However, its standard gibbs sampling inference method (StdBTM) costs much more time than that (StdLDA) of Latent Dirichlet Allocation (LDA). To solve this problem we propose two time-efficient gibbs sampling inference methods, SparseBTM and ESparseBTM, for BTM by making a tradeoff between space and time consumption in this paper. The idea of SparseBTM is to reduce the computation in StdBTM by both recycling intermediate results and utilizing the sparsity of count matrix \(\mathbf {N}^{\mathbf {T}}_{\mathbf {W}}\). Theoretically, SparseBTM reduces the time complexity of StdBTM from O(|B| K) to O(|B| K _w ) which scales linearly with the sparsity of count matrix \(\mathbf {N}^{\mathbf {T}}_{\mathbf {W}}\) (K _w ) instead of the number of topics (K) (K _w < K, K _w is the average number of non-zero topics per word type in count matrix \(\mathbf {N}^{\mathbf {T}}_{\mathbf {W}}\)). Experimental results have shown that in good conditions SparseBTM is approximately 18 times faster than StdBTM. Compared with SparseBTM, ESparseBTM is a more time-efficient gibbs sampling inference method proposed based on SparseBTM. The idea of ESparseBTM is to reduce more computation by recycling more intermediate results through rearranging biterm sequence. In theory, ESparseBTM reduces the time complexity of SparseBTM from O(|B|K _w ) to O(R|B|K _w ) (0 < R < 1, R is the ratio of the number of biterm types to the number of biterms). Experimental results have shown that the percentage of the time efficiency improved by ESparseBTM on SparseBTM is between 6.4% and 39.5% according to different datasets.     

Tolerance limits on order statistics in future samples coming from the Pareto distribution

It is often desirable to have statistical tolerance limits available for the distributions used to describe time-to-failure data in reliability problems. For example, one might wish to know if at least a certain proportion, say β, of a manufactured product will operate at least T hours. This question cannot usually be answered exactly, but it may be possible to determine a lower tolerance limit L(X), based on a random sample X, such that one can say with a certain confidence γ that at least 100β% of the product will operate longer than L(X). Then reliability statements can be made based on L(X), or, decisions can be reached by comparing L(X) to T. Tolerance limits of the type mentioned above are considered in this paper, which presents a new approach to constructing lower and upper tolerance limits on order statistics in future samples. Attention is restricted to invariant families of distributions under parametric uncertainty. The approach used here emphasizes pivotal quantities relevant for obtaining tolerance factors and is applicable whenever the statistical problem is invariant under a group of transformations that acts transitively on the parameter space. It does not require the construction of any tables and is applicable whether the past data are complete or Type II censored. The proposed approach requires a quantile of the F distribution and is conceptually simple and easy to use. For illustration, the Pareto distribution is considered. The discussion is restricted to one-sided tolerance limits. A practical example is given.     

Information Lower Bounds via Self-Reducibility

We use self-reduction methods to prove strong information lower bounds on two of the most studied functions in the communication complexity literature: Gap Hamming Distance (GHD) and Inner Product (IP). In our first result we affirm the conjecture that the information cost of GHD is linear even under the uniform distribution, which strengthens the Ω(n) bound recently shown by Kerenidis et al. (2012), and answers an open problem from Chakrabarti et al. (2012). In our second result we prove that the information cost of IP_n is arbitrarily close to the trivial upper bound n as the permitted error tends to zero, again strengthening the Ω(n) lower bound recently proved by Braverman and Weinstein (Electronic Colloquium on Computational Complexity (ECCC) 18, 164 2011). Our proofs demonstrate that self-reducibility makes the connection between information complexity and communication complexity lower bounds a two-way connection. Whereas numerous results in the past (Chakrabarti et al. 2001; Bar-Yossef et al. J. Comput. Syst. Sci. 68(4), 702–732 2004; Barak et al. 2010) used information complexity techniques to derive new communication complexity lower bounds, we explore a generic way in which communication complexity lower bounds imply information complexity lower bounds in a black-box manner.     

Mixed <Emphasis Type="Italic">H</Emphasis><Subscript>2</Subscript>/<Emphasis Type="Italic">H</Emphasis><Subscript>∞</Subscript> control for linear infinite-dimensional systems

In this paper, we consider mixed H ₂/H _∞ control problems for linear infinite-dimensional systems. The first part considers the state feedback control for the H ₂/H _∞ control problems of linear infinite-dimensional systems. The cost horizon can be infinite or finite time. The solutions of the H ₂/H _∞ control problem for linear infinitedimensional systems are presented in terms of the solutions of the coupled operator Riccati equations and coupled differential operator Riccati equations. The second part addresses the observer-based H ₂/H _∞ control of linear infinite-dimensional systems with infinite horizon and finite horizon costs. The solutions for the observer-based H ₂/H _∞ control problem of linear infinite-dimensional systems are represented in terms of the solutions of coupled operator Riccati equations. The first-order partial differential system examples are presented for illustration. In particular, for these examples, the Riccati equations are represented in terms of the coefficients of first-order partial differential systems.     

Fast online algorithm for nonlinear support vector machines and other alike models

Paper presents a unique novel online learning algorithm for eight popular nonlinear (i.e., kernel), classifiers based on a classic stochastic gradient descent in primal domain. In particular, the online learning algorithm is derived for following classifiers: L1 and L2 support vector machines with both a quadratic regularizer w ^t w and the l ₁ regularizer |w|₁; regularized huberized hinge loss; regularized kernel logistic regression; regularized exponential loss with l ₁ regularizer |w|₁ and Least squares support vector machines. The online learning algorithm is aimed primarily for designing classifiers for large datasets. The novel learning model is accurate, fast and extremely simple (i.e., comprised of few coding lines only). Comparisons of performances of the proposed algorithm with the state of the art support vector machine algorithm on few real datasets are shown.     

Machine checked proofs of the design of a fault-tolerant circuit

We describe a formally verified implementation of the “Oral Messages” algorithm of Pease, Shostak and LamportJ. ACM (1980)27, 228–234;ACM TOPLAS (1982)4, 382–401. An abstract implementation of the algorithm is proved to achieve interactive consistency in the presence of faults. This abstract characterisation is then mapped down to a hardware level implementation which inherits the fault-tolerant characteristics of the abstract version. All steps in the proof were checked with the Boyer-Moore theorem prover. A significant result of this work is the demonstration of a fault-tolerant device that is formally specified and the development of an implementation proved correct with respect to this specification. A significant simplifying assumption is that the redundant processors behave synchronously. We also describe a mechanically checked proof that the Oral Messages algorithm is “optimal” in the sense that no algorithm which achieves agreement via similar message passing can tolerate a larger proportion of faulty processors.     

Some lower bounds on the algebraic immunity of functions given by their trace forms

The algebraic immunity of a Boolean function is a parameter that characterizes the possibility to bound this function from above or below by a nonconstant Boolean function of a low algebraic degree. We obtain lower bounds on the algebraic immunity for a class of functions expressed through the inversion operation in the field GF(2 ⁿ ), as well as for larger classes of functions defined by their trace forms. In particular, for n ≥ 5, the algebraic immunity of the function Tr _n (x ^?1) has a lower bound ?2√n + 4? ? 4, which is close enough to the previously obtained upper bound ?√n? + ?n/?√n?? ? 2. We obtain a polynomial algorithm which, give a trace form of a Boolean function f, computes generating sets of functions of degree ≤ d for the following pair of spaces. Each function of the first (linear) space bounds f from below, and each function of the second (affine) space bounds f from above. Moreover, at the output of the algorithm, each function of a generating set is represented both as its trace form and as a polynomial of Boolean variables.     

Organization of self-diagnosis of the discrete multicomponent systems a structure like bipartite quasicomplete graphs

Organization of an efficient self-diagnosis of the multicomponent computer and communication systems of diverse structures always attracted attention of the researchers and engineers. A method to solve these problems is presented in the paper by way of the example of a system whose structure is modeled by a uniform ordinary bipartite graph of diameter d = 3, any degree s > 1, and any number n of vertices, where n = s(s ? 1) + 1. The method requires checking of (s ? 1)³ graph loops of length eight each, which is smaller than the number s ²(s ? 1) + s of checks of single graph edges.     

Repeated patterns detection in big data using classification and parallelism on LERP Reduced Suffix Arrays

Suffix array is a powerful data structure, used mainly for pattern detection in strings. The main disadvantage of a full suffix array is its quadratic O(n²) space capacity when the actual suffixes are needed. In our previous work [39], we introduced the innovative All Repeated Patterns Detection (ARPaD) algorithm and the Moving Longest Expected Repeated Pattern (MLERP) process. The former detects all repeated patterns in a string using a partition of the full Suffix Array and the latter is capable of analyzing large strings regardless of their size. Furthermore, the notion of Longest Expected Repeated Pattern (LERP), also introduced by the authors in a previous work, significantly reduces to linear O(n) the space capacity needed for the full suffix array. However, so far the LERP value has to be specified in ad hoc manner based on experimental or empirical values. In order to overcome this problem, the Probabilistic Existence of LERP theorem has been proven in this paper and, furthermore, a formula for an accurate upper bound estimation of the LERP value has been introduced using only the length of the string and the size of the alphabet used in constructing the string. The importance of this method is the optimum upper bounding of the LERP value without any previous preprocess or knowledge of string characteristics. Moreover, the new data structure LERP Reduced Suffix Array is defined; it is a variation of the suffix array, and has the advantage of permitting the classification and parallelism to be implemented directly on the data structure. All other alternative methodologies deal with the very common problem of fitting any kind of data structure in a computer memory or disk in order to apply different time efficient methods for pattern detection. The current advanced and elegant proposed methodology allows us to alter the above-mentioned problem such that smaller classes of the problem can be distributed on different systems and then apply current, state-of-the-art, techniques such as parallelism and cloud computing using advanced DBMSs which are capable of handling the storage and analysis of big data. The implementation of the above-described methodology can be achieved by invoking our innovative ARPaD algorithm. Extensive experiments have been conducted on small, comparable strings of Champernowne Constant and DNA as well as on extremely large strings of π with length up to 68 billion digits. Furthermore, the novelty and superiority of our methodology have been also tested on real life application such as a Distributed Denial of Service (DDoS) attack early warning system.     

Central limit theorem and large deviations of the fading Wyner cellular model via product of random matrices theory

We apply the theory of products of random matrices to the analysis of multi-user communication channels similar to the Wyner model, which are characterized by short-range intra-cell broadcasting. We study fluctuations of the per-cell sum-rate capacity in the non-ergodic regime and provide results of the type of the central limit theorem (CLT) and large deviations (LD). Our results show that CLT fluctuations of the per-cell sum-rate C _m are of order \(1/\sqrt m \), where m is the number of cells, whereas they are of order 1/m in classical random matrix theory. We also show an LD regime of the form P(|C _m ? C| > ?) ≤ e ^?mα with α = α(?) > 0 and C = \(\mathop {\lim }\limits_{m \to \infty } \) C _m , as opposed to the rate \(e^{ - m^2 \alpha } \) in classical random matrix theory.     

Optimal Path Embedding in the Exchanged Crossed Cube

The (s + t + 1)-dimensional exchanged crossed cube, denoted as ECQ(s, t), combines the strong points of the exchanged hypercube and the crossed cube. It has been proven that ECQ(s, t) has more attractive properties than other variations of the fundamental hypercube in terms of fewer edges, lower cost factor and smaller diameter. In this paper, we study the embedding of paths of distinct lengths between any two different vertices in ECQ(s, t). We prove the result in ECQ(s, t): if s ≥ 3, t ≥ 3, for any two different vertices, all paths whose lengths are between \( \max \left\{9,\left\lceil \frac{s+1}{2}\right\rceil +\left\lceil \frac{t+1}{2}\right\rceil +4\right\} \) and 2 ^s+t+1 ? 1 can be embedded between the two vertices with dilation 1. Note that the diameter of ECQ(s, t) is \( \left\lceil \frac{s+1}{2}\right\rceil +\left\lceil \frac{t+1}{2}\right\rceil +2 \). The obtained result is optimal in the sense that the dilations of path embeddings are all 1. The result reveals the fact that ECQ(s, t) preserves the path embedding capability to a large extent, while it only has about one half edges of CQ _n .