Model complexity plays an essential role in its selection, namely, by choosing a model that fits the data and is also succinct. Two-part codes and the minimum description length have been successful in delivering procedures to single out the best models, avoiding overfitting. In this work, we pursue this approach and complement it by performing further assumptions in the parameter space. Concretely, we assume that the parameter space is a smooth manifold, and by using tools of Riemannian geometry, we derive a sharper expression than the standard one given by the stochastic complexity, where the scalar curvature of the Fisher information metric plays a dominant role. Furthermore, we compute a sharper approximation to the capacity for exponential families and apply our results to derive optimal dimensional reduction in the context of principal component analysis.

The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is ɛ-far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification technique. At first, we study here a particular testing problem: namely whether a given Boolean function f, of n variables, is identical with a given function g or is ɛ-far from g, where ɛ is the parameter. We present a one-sided error quantum algorithm to deal with this problem that has the query complexity [Formula: see text]. Moreover, we show that our quantum algorithm is optimal. Afterwards we show that the classical randomized query complexity of this problem is [Formula: see text]. Secondly, we consider the D-J problem from the perspective of functional correlations and let C( f, g) denote the correlation of f and g. We propose an exact quantum algorithm for making distinction between | C( f, g)| = ɛ and | C( f, g)| = 1 using six queries, while the classical deterministic query complexity for this problem is Θ(2 n ) queries. Finally, we propose a one-sided error quantum query algorithm for testing whether one Boolean function is balanced versus ɛ-far balanced using [Formula: see text] queries. We also prove here that our quantum algorithm for balancedness testing is optimal. At the same time, for this balancedness testing problem we present a classical randomized algorithm with query complexity of O(1/ ɛ 2 ). Also this randomized algorithm is optimal. Besides, we link the problems considered here together and generalize them to the general case.

Despite years of research, the Internet still lacks a routing protocol with guaranteed termination. As is well-known, decentralization of routing decisions among the Autonomous Systems (ASes) that comprise the Internet may result in permanent oscillations of the state of its routing protocol - the Border Gateway Protocol (BGP). Some permanent oscillations are made from routing loops - the propagation of routing messages around the cycles of a network - that come back time and again. We discovered that the routing loop detection capability of BGP can be sharpened to predict which routing loops potentially recur and that the import policies can be adjusted to prevent the recurrence. The resulting protocol, named Self-Stable BGP (SS-BGP), is more stable than BGP. For the broad and common class of isotone routing policies, all permament oscillations are made from recurrent routing loops. For this class of routing policies, SS-BGP terminates. Our simulations with realistic Internet topologies and realistic variations of the Gao-Rexford (GR) inter-AS routing policies show that SS-BGP arrives at stable states at the expense of alterations in the import policies of only a handful of ASes.

A simple notion of quantum Turing machine with deterministic, classical control is proposed and shown to be powerful enough to compute any unitary transformation that is computable by a finitely generated quantum circuit. An efficient universal machine with the s-m-n property is presented. The BQP class is recovered. A robust notion of plain Kolmogorov complexity of quantum states is proposed and compared with those previously reported in the literature.

A complete extension of classical propositional logic is proposed for reasoning about circuits with unreliable gates. The pitfalls of extrapolating classical reasoning to such unreliable circuits are extensively illustrated. Several metatheorems are shown to hold with additional provisos. Applications are provided in verification of logic circuits and improving their reliability.

When studying probabilistic dynamical systems, temporal logic has typically been used to analyze path properties. Recently, there has been some interest in analyzing the dynamical evolution of state probabilities of these systems. In this article, we show that verifying linear temporal properties concerning the state evolution induced by a Markov chain is equivalent to the decidability of the Skolem problem -- a long-standing open problem in Number Theory. However, from a practical point of view, usually it is enough to check properties up to some acceptable error bound ϵ. We show that an approximate version of the Skolem problem is decidable, and that it can be applied to verify, up to arbitrarily small ϵ, linear temporal properties of the state evolution induced by a Markov chain.

Frequently, mathematical structures of a certain type and their morphisms fail to form a category for lack of composability of the morphisms; one example of this problem is the class of probabilistic automata when equipped with morphisms that allow restriction as well as relabelling. The proper mathematical framework for this situation is provided by a generalisation of category theory in the shape of the so-called precategories, which are introduced and studied in this paper. In particular, notions of adjointness, weak adjointness and partial adjointness for precategories are presented and justified in detail. This makes it possible to use universal properties as characterisations of well-known basic constructions in the theory of (generative) probabilistic automata: we show that accessible automata and decision trees, respectively, form coreflective subprecategories of the precategory of probabilistic automata. Moreover, the aggregation of two automata is identified as a partial product, whereas restriction and interconnection of automata are recognised as Cartesian lifts.

The purpose of this article is to extend the situation calculus, a logical framework for the specification of theories of action and change, with actions that have a non-deterministic or uncertain nature. Our approach is based upon the idea that actions may have a deterministic component, and a probabilistic component. For example, the act of flipping a coin has a deterministic component (the actual coin toss) and an uncertain component (the outcome). We extend the language of the situation calculus in order to make explicit this distinction between these two action components. Furthermore, we provide means to reason about the outcomes of processes specified only in terms of deterministic action components (which we call behaviors). In particular, we show how one can compute the probability that some fluent will hold after specific behavior is realized. An important feature of our approach is that the syntactic and semantic structure of actions and situations is independent of the decomposition of actions into deterministic and uncertain components. Thus, we inherit solutions to the frame problem ramification problem, etc.