Algorithmic randomness and monotone complexity on product space

We study algorithmic randomness and monotone complexity on product of the set of infinite binary sequences. We explore the following problems: monotone complexity on product space, Lambalgen’s theorem for correlated probability, classification of random sets by likelihood ratio tests, decomposition of complexity and independence, and Bayesian statistics for individual random sequences. Formerly Lambalgen’s theorem for correlated probability is shown under a uniform computability assumption in [H. Takahashi Inform. Compt. 2008]. In this paper we show the theorem without the assumption.     

Communication complexity towards lower bounds on circuit depth

Karchmer, Raz, and Wigderson (1995) discuss the circuit depth complexity of n-bit Boolean functions constructed by composing up to d = log n/log log n levels of k = log n-bit Boolean functions. Any such function is in AC¹ . They conjecture that circuit depth is additive under composition, which would imply that any (bounded fan-in) circuit for this problem requires depth. This would separate AC¹ from NC¹. They recommend using the communication game characterization of circuit depth. In order to develop techniques for using communication complexity to prove circuit depth lower bounds, they suggest an intermediate communication complexity problem which they call the Universal Composition Relation. We give an almost optimal lower bound of dk—O(d ²(k log k)^1/2) for this problem. In addition, we present a proof, directly in terms of communication complexity, that there is a function on k bits requiring circuit depth. Although this fact can be easily established using a counting argument, we hope that the ideas in our proof will be incorporated more easily into subsequent arguments which use communication complexity to prove circuit depth bounds. Received: July 30, 1999.     

Algorithmic stability and sanity-check bounds for leave-one-out cross-validation.

In this article we prove sanity-check bounds for the error of the leave-one-out cross-validation estimate of the generalization error: that is, bounds showing that the worst-case error of this estimate is not much worse than that of the training error estimate. The name sanity check refers to the fact that although we often expect the leave-one-out estimate to perform considerably better than the training error estimate, we are here only seeking assurance that its performance will not be considerably worse. Perhaps surprisingly, such assurance has been given only for limited cases in the prior literature on cross-validation. Any nontrivial bound on the error of leave-one-out must rely on some notion of algorithmic stability. Previous bounds relied on the rather strong notion of hypothesis stability, whose application was primarily limited to nearest-neighbor and other local algorithms. Here we introduce the new and weaker notion of error stability and apply it to obtain sanity-check bounds for leave-one-out for other classes of learning algorithms, including training error minimization procedures and Bayesian algorithms. We also provide lower bounds demonstrating the necessity of some form of error stability for proving bounds on the error of the leave-one-out estimate, and the fact that for training error minimization algorithms, in the worst case such bounds must still depend on the Vapnik-Chervonenkis dimension of the hypothesis class.     

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.     

Some bounds on multiparty communication complexity of pointer jumping

We introduce the model of conservative one-way multiparty complexity and prove lower and upper bounds on the complexity of pointer jumping.? The pointer jumping function takes as its input a directed layered graph with a starting node and k layers of n nodes, and a single edge from each node to one node from the next layer. The output is the node reached by following k edges from the starting node. In a conservative protocol, the ith player can see only the node reached by following the first i–1 edges and the edges on the jth layer for each j > i. This is a restriction of the general model where the ith player sees edges of all layers except for the ith one. In a one-way protocol, each player communicates only once in a prescribed order: first Player 1 writes a message on the blackboard, then Player 2, etc., until the last player gives the answer. The cost is the total number of bits written on the blackboard.?Our main results are the following bounds on k-party conservative one-way communication complexity of pointer jumping with k layers:? (1) A lower bound of order for any .?(2) Matching upper and lower bounds of order for . received March 22, 1996     

Hadamard tensors and lower bounds on multiparty communication complexity

We develop a new method for estimating the discrepancy of tensors associated with multiparty communication problems in the “Number on the Forehead” model of Chandra, Furst, and Lipton. We define an analog of the Hadamard property of matrices for tensors in multiple dimensions and show that any k-party communication problem represented by a Hadamard tensor must have Ω(n/2 ^k ) multiparty communication complexity. We also exhibit constructions of Hadamard tensors. This allows us to obtain Ω(n/2 ^k ) lower bounds on multiparty communication complexity for a new class of explicitly defined Boolean functions.     

Tight bounds on the complexity index of one-point iterations

We study the minimal complexity index of one-point iterations without memory for the solution of a system of N nonlinear equations F(x)=0. We present an iteration ^* with maximal order of convergence and with linear combinatory complexity. We show the complexity index of ^* is close to the lower bound on the minimal complexity index.     

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?”     

Strong computational lower bounds via parameterized complexity

We develop new techniques for deriving strong computational lower bounds for a class of well-known NP-hard problems. This class includes weighted satisfiability, dominating set, hitting set, set cover, clique, and independent set. For example, although a trivial enumeration can easily test in time O(nk) if a given graph of n vertices has a clique of size k, we prove that unless an unlikely collapse occurs in parameterized complexity theory, the problem is not solvable in time f(k)no(k) for any function f, even if we restrict the parameter values to be bounded by an arbitrarily small function of n. Under the same assumption, we prove that even if we restrict the parameter values k to be of the order Θ(μ(n)) for any reasonable function μ, no algorithm of running time no(k) can test if a graph of n vertices has a clique of size k. Similar strong lower bounds on the computational complexity are also derived for other NP-hard problems in the above class. Our techniques can be further extended to derive computational lower bounds on polynomial time approximation schemes for NP-hard optimization problems. For example, we prove that the NP-hard distinguishing substring selection problem, for which a polynomial time approximation scheme has been recently developed, has no polynomial time approximation schemes of running time f(1/?)no(1/?) for any function f unless an unlikely collapse occurs in parameterized complexity theory.     

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.     

Constructive lower bounds on model complexity of shallow perceptron networks

Limitations of shallow (one-hidden-layer) perceptron networks are investigated with respect to computing multivariable functions on finite domains. Lower bounds are derived on growth of the number of network units or sizes of output weights in terms of variations of functions to be computed. A concrete construction is presented with a class of functions which cannot be computed by signum or Heaviside perceptron networks with considerably smaller numbers of units and smaller output weights than the sizes of the function’s domains. A subclass of these functions is described whose elements can be computed by two-hidden-layer perceptron networks with the number of units depending on logarithm of the size of the domain linearly.

     

Larger lower bounds on the OBDD complexity of integer multiplication

Integer multiplication as one of the basic arithmetic functions has been in the focus of several complexity theoretical investigations and ordered binary decision diagrams (OBDDs) are one of the most common dynamic data structures for Boolean functions. Recently, the question whether the OBDD complexity of the most significant bit of integer multiplication is exponential has been answered affirmatively. In this paper a larger general lower bound is presented using a simpler proof. Furthermore, we prove a larger lower bound for the variable order assumed to be one of the best ones for the most significant bit. Moreover, the best known lower bound on the OBDD complexity for the so-called graph of integer multiplication is improved.     

Astronomical bounds on a future Big Freeze singularity

It was recently found that dark energy in the form of phantom generalized Chaplygin gas may lead to a new form of a cosmic doomsday, the Big Freeze singularity. Like the Big Rip singularity, the Big Freeze singularity would also take place at finite future cosmic time, but, unlike the Big Rip, it happens for a finite scale factor. Our goal is to test if a universe filled with phantom generalized Chaplygin gas can conform to the data of astronomical observations. We shall see that if the universe is only filled with generalized phantom Chaplygin gas with the equation of state p = −c ² s ²/ρ ^α with α < −1, then such a model cannot be matched to the observational data; generally speaking, such a universe has an infinite age. To construct more realistic models, one actually need to add dark matter. This procedure results in cosmological scenarios which do not contradict the values of universe age and expansion rate and allow one to estimate how long we are now from the future Big Freeze doomsday.     

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.     

Controller switching based on output prediction errors

We consider a switched nonlinear feedback control strategy for controlling a plant with unknown parameters so that the output asymptotically tracks a reference signal. The controller is selected online from a given set of controllers according to a switching rule based on output prediction errors. For control problems requiring asymptotic tracking of a reference input we provide sufficient conditions under which the switched closed-loop control system is exponentially stable and asymptotically achieves good control even if the switching does not stop, Our results are illustrated with three examples