An Application of an Initialization Protocol to Permutation Routing in a Single-Hop Mobile Ad Hoc Networks

In 1999 Nakano, Olariu, and Schwing in [20], they showed that the permutation routing of n items pretitled on a mobile ad hoc network (MANET for short) of p stations (p known) and k channels (MANET{(n, p, k)) with k < p, can be carried out in broadcast rounds if k p and if each station has a -memory locations. And if k and if each station has a -memory locations, the permutations of these n pretitled items can be done also in broadcast rounds. They used two assumptions: first they suppose that each station of the mobile ad hoc network has an identifier beforehand. Secondly, the stations are partitioned into k groups such that each group has stations, but it was not shown how this partition can be obtained. In this paper, the stations have not identifiers beforehand and p is unknown. We develop a protocol which first names the stations, secondly gives the value of p, and partitions stations in groups of stations. Finally we show that the permutation routing problem can be solved on it in broadcast rounds in the worst case. It can be solved in broadcast rounds in the better case. Note that our approach does not impose any restriction on k.     

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 ,

On the complexity of computing determinants

We present new baby steps/giant steps algorithms of asymptotically fast running time for dense matrix problems. Our algorithms compute the determinant, characteristic polynomial, Frobenius normal form and Smith normal form of a dense n × n matrix A with integer entries in and bit operations; here denotes the largest entry in absolute value and the exponent adjustment by +o(1) captures additional factors for positive real constants C₁, C₂, C₃. The bit complexity results from using the classical cubic matrix multiplication algorithm. Our algorithms are randomized, and we can certify that the output is the determinant of A in a Las Vegas fashion. The second category of problems deals with the setting where the matrix A has elements from an abstract commutative ring, that is, when no divisions in the domain of entries are possible. We present algorithms that deterministically compute the determinant, characteristic polynomial and adjoint of A with n^3.2+o(1) and O(n^2.697263) ring additions, subtractions and multiplications.To B. David Saunders on the occasion of his 60th birthday     

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.     

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.     

Free binary decision diagrams for the computation of EAR n

Free binary decision diagrams (FBDDs) are graph-based data structures representing Boolean functions with the constraint (additional to binary decision diagram) that each variable is tested at most once during the computation. The function EAR_n is the following Boolean function defined for n × n Boolean matrices: EAR_n(M) = 1 iff the matrix M contains two equal adjacent rows. We prove that each FBDD computing EAR_n has size at least and we present a construction of such diagrams of size approximately .     

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.     

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.