The complexity of constructing pseudorandom generators from hard functions

We study the complexity of constructing pseudorandom generators (PRGs) from hard functions, focussing on constant-depth circuits. We show that, starting from a function computable in alternating time O(l) with O(1) alternations that is hard on average (i.e. there is a constant such that every circuit of size fails to compute f on at least a 1/poly(l) fraction of inputs) we can construct a computable by DLOGTIME-uniform constant-depth circuits of size polynomial in n. Such a PRG implies under DLOGTIME-uniformity. On the negative side, we prove that starting from a worst-case hard function (i.e. there is a constant such that every circuit of size fails to compute f on some input) for every positive constant there is no black-box construction of a computable by constant-depth circuits of size polynomial in n. We also study worst-case hardness amplification, which is the related problem of producing an average-case hard function starting from a worst-case hard one. In particular, we deduce that there is no blackbox worst-case hardness amplification within the polynomial time hierarchy. These negative results are obtained by showing that polynomialsize constant-depth circuits cannot compute good extractors and listdecodable codes.     

A Time-Splitting Spectral Method for the Generalized Zakharov System in Multi-Dimensions

The generalized Zakharov system (ZS) couples a dispersive field E (scalar or vectorial) and nondispersive fields with a propagating speed of . In this paper, we extend our one-dimensional time-splitting spectral method (TSSP) for the generalized ZS into higher dimension. A main new idea is to reformulate the multi-dimensional wave equations for the nondispersive fields into a first-order system using a change of variable defined in the Fourier space. The proposed scheme TSSP is unconditionally stable, second-order in time and spectrally accurate in space. Moreover, in the subsonic regime, it allows numerical capturing of the subsonic limit without resolving the small parameters . Numerical examples confirm these properties of this method     

Crash failure detection in asynchronous agent communication languages

Agent Communication Languages (ACLs) have been developed to provide a way for agents to communicate with each other supporting cooperation in Multi-Agent Systems (MAS). In the past few years many ACLs have been proposed for MAS and new standards are emerging such as the ACL developed by the Foundation for Intelligent Physical Agents (FIPA). Despite these efforts, an important issue in the research on ACLs is still open and concerns how these languages should deal with failures of agents in asynchronous MAS. The Fault Tolerant Agent Communication Language ( - ) presented in this paper addresses this issue dealing with crash failures of agents. - provides high-level communication primitives which support a fault-tolerant anonymous interaction protocol designed for open MAS. We present a formal semantics for - and a formal specification of the underlying agent architecture. This formal framework allows us to prove that the ACL satisfies a set of well defined knowledge-level programming requirements. To illustrate the language features we show how - can be effectively used to write high-level executable specifications of fault tolerant protocols, such as the Contract Net one.     

An algebraic approach for $${\mathcal{H}}$$-matrix preconditioners

Hierarchical matrices ( -matrices) approximate matrices in a data-sparse way, and the approximate arithmetic for -matrices is almost optimal. In this paper we present an algebraic approach for constructing -matrices which combines multilevel clustering methods with -matrix arithmetic to compute the -inverse, -LU, and the -Cholesky factors of a matrix. Then the -inverse, -LU or -Cholesky factors can be used as preconditioners in iterative methods to solve systems of linear equations. The numerical results show that this method is efficient and greatly speeds up convergence compared to other approaches, such as JOR or AMG, for solving some large, sparse linear systems, and is comparable to other -matrix constructions based on Nested Dissection.     

Deriving escape analysis by abstract interpretation

Escape analysis of object-oriented languages approximates the set of objects which do not escape from a given context. If we take a method as context, the non-escaping objects can be allocated on its activation stack; if we take a thread, Java synchronisation locks on such objects are not needed. In this paper, we formalise a basic escape domain as an abstract interpretation of concrete states, which we then refine into an abstract domain which is more concrete than and, hence, leads to a more precise escape analysis than . We provide optimality results for both and , in the form of Galois insertions from the concrete to the abstract domains and of optimal abstract operations. The Galois insertion property is obtained by restricting the abstract domains to those elements which do not contain garbage, by using an abstract garbage collector. Our implementation of is hence an implementation of a formally correct escape analyser, able to detect the stack allocatable creation points of Java (bytecode) applications.     

Cardinal interpolation with periodic polysplines on strips

Abstract  We obtain a multivariate extension of a classical result of Schoenberg on cardinal spline interpolation. Specifically, we prove the existence of a unique function in , polyharmonic of order p on each strip , , and periodic in its last n variables, whose restriction to the parallel hyperplanes , , coincides with a prescribed sequence of n-variate periodic data functions satisfying a growth condition in . The constructive proof is based on separation of variables and on Micchelli’s theory of univariate cardinal -splines. Keywords: cardinal -splines, polyharmonic functions, multivariable interpolation Mathematics Subject Classification (2000): 41A05, 41A15, 41A63     

Lange and Wiehagen's pattern language learning algorithm: An average-case analysis with respect to its total learning time

The present paper deals with the best-case, worst-case and average-case behavior of Lange and Wiehagen's (1991) pattern language learning algorithm with respect to its total learning time. Pattern languages have been introduced by Angluin (1980) and are defined as follows: Let be any non-empty finite alphabet containing at least two elements. Furthermore, let be an infinite set of variables such that . Patterns are non-empty strings over . L(π), the language generated by pattern π, is the set of strings which can be obtained by substituting non-null strings from for the variables of the pattern π. Lange and Wiehagen's (1991) algorithm learns the class of all pattern languages in the limit from text. We analyze this algorithm with respect to its total learning time behavior, i.e., the overall time taken by the algorithm until convergence. For every pattern π containing k different variables it is shown that the total learning time is in the best-case and unbounded in the worst-case. Furthermore, we estimate the expectation of the total learning time. In particular, it is shown that Lange and Wiehagen's algorithm possesses an expected total learning time of with respect to the uniform distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

The Complexity of Learning According to Two Models of a Drifting Environment

We show that a bound on the rate of drift of the distribution generating the examples is sufficient for agnostic learning to relative accuracy , where c > 0 is a constant; this matches a known necessary condition to within a constant factor. We establish a sufficient condition for the realizable case, also matching a known necessary condition to within a constant factor. We provide a relatively simple proof of a bound of + on the sample complexity of agnostic learning in a fixed environment.     

Quantum Orlicz Spaces in Information Geometry

Let H₀ be a selfadjoint operator such that Tr is of trace class for some , and let denote the set of ε-bounded forms, i.e., for some 0 $$" align="middle" border="0"> . Let χ := Span . Let denote the underlying set of the quantum information manifold of states of the form . We show that if Tr ,

Complexity of some arithmetic problems for binary polynomials

We study various combinatorial complexity measures of Boolean functions related to some natural arithmetic problems about binary polynomials, that is, polynomials over . In particular, we consider the Boolean function deciding whether a given polynomial over is squarefree. We obtain an exponential lower bound on the size of a decision tree for this function, and derive an asymptotic formula, having a linear main term, for its average sensitivity. This allows us to estimate other complexity characteristics such as the formula size, the average decision tree depth and the degrees of exact and approximative polynomial representations of this function. Finally, using a different method, we show that testing squarefreeness and irreducibility of polynomials over cannot be done in for any odd prime p. Similar results are obtained for deciding coprimality of two polynomials over as well.     

Image Analysis and Reconstruction using a Wavelet Transform Constructed from a Reducible Representation of the Euclidean Motion Group

Inspired by the early visual system of many mammalians we consider the construction of-and reconstruction from- an orientation score as a local orientation representation of an image, . The mapping is a wavelet transform corresponding to a reducible representation of the Euclidean motion group onto and oriented wavelet . This wavelet transform is a special case of a recently developed generalization of the standard wavelet theory and has the practical advantage over the usual wavelet approaches in image analysis (constructed by irreducible representations of the similitude group) that it allows a stable reconstruction from one (single scale) orientation score. Since our wavelet transform is a unitary mapping with stable inverse, we directly relate operations on orientation scores to operations on images in a robust manner. Furthermore, by geometrical examination of the Euclidean motion group , which is the domain of our orientation scores, we deduce that an operator Φ on orientation scores must be left invariant to ensure that the corresponding operator on images is Euclidean invariant. As an example we consider all linear second order left invariant evolutions on orientation scores corresponding to stochastic processes on G. As an application we detect elongated structures in (medical) images and automatically close the gaps between them. Finally, we consider robust orientation estimates by means of channel representations, where we combine robust orientation estimation and learning of wavelets resulting in an auto-associative processing of orientation features. Here linear averaging of the channel representation is equivalent to robust orientation estimation and an adaptation of the wavelet to the statistics of the considered image class leads to an auto-associative behavior of the system. The Netherlands Organization for Scientific Research is gratefully acknowledged for financial support. This work has been supported by EC Grant IST-2003-004176 COSPAL.     

Linear Interval Equations: Midpoint Preconditioning May Produce a 100% Overestimation for Arbitrarily Narrow Data Even in Case <Emphasis Type="Italic">n</Emphasis> = 4

We construct a linear interval system Ax = b with a 4 × 4 interval matrix whose all proper interval coefficients (there are also some noninterval ones) are of the form [–, ]. It is proved that for each > 0, the interval hull and interval hull of the midpoint preconditioned system satisfy and , hence midpoint preconditioning produces a 100% overestimation of independently of in this case. The example was obtained as a result of an extensive MATLAB search.     

Lower Bound Methods and Separation Results for On-Line Learning Models

We consider the complexity of concept learning in various common models for on-line learning, focusing on methods for proving lower bounds to the learning complexity of a concept class. Among others, we consider the model for learning with equivalence and membership queries. For this model we give lower bounds on the number of queries that are needed to learn a concept class in terms of the Vapnik-Chervonenkis dimension of , and in terms of the complexity of learning with arbitrary equivalence queries. Furthermore, we survey other known lower bound methods and we exhibit all known relationships between learning complexities in the models considered and some relevant combinatorial parameters. As it turns out, the picture is almost complete. This paper has been written so that it can be read without previous knowledge of Computational Learning Theory.     

On the complexity of approximating k-set packing

Given a k-uniform hypergraph, the Maximum k -Set Packing problem is to find the maximum disjoint set of edges. We prove that this problem cannot be efficiently approximated to within a factor of unless P = NP. This improves the previous hardness of approximation factor of by Trevisan. This result extends to the problem of k-Dimensional-Matching.     

Towards proving strong direct product theorems

A fundamental question of complexity theory is the direct product question. A famous example is Yaos XOR-lemma, in which one assumes that some function f is hard on average for small circuits (meaning that every circuit of some fixed size s which attempts to compute f is wrong on a non-negligible fraction of the inputs) and concludes that every circuit of size s only has a small advantage over guessing randomly when computing on independently chosen . All known proofs of this lemma have the property that s < s . In words, the circuit which attempts to compute is smaller than the circuit which attempts to compute f on a single input! This paper addresses the issue of proving strong direct product assertions, that is, ones in which and is in particular larger than s. We study the question of proving strong direct product question for decision trees and communication protocols.