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     

Dynamic Ordering for Asynchronous Backtracking on DisCSPs

An algorithm that performs asynchronous backtracking on distributed , with dynamic ordering of agents is proposed, . Agents propose reorderings of lower priority agents and send these proposals whenever they send assignment messages. Changes of ordering triggers a different computation of . The dynamic ordered asynchronous backtracking algorithm uses polynomial space, similarly to standard . The algorithm with three different ordering heuristics is compared to standard on randomly generated . A Nogood-triggered heuristic, inspired by dynamic backtracking, is found to outperform static order by a large factor in run-time and improve the network load.     

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.     

Coupling and self-stabilization

A randomized self-stabilizing algorithm is an algorithm that, whatever the initial configuration is, reaches a set of М legal configurations} in finite time with probability 1. The proof of convergence towards is generally done by exhibiting a potential function , which measures the “vertical” distance of any configuration to , such that decreases with non-null probability at each step of . We propose here a method, based on the notion of coupling, which makes use of a “horizontal” distance between any pair of configurations, such that decreases in expectation at each step of . In contrast with classical methods, our coupling method does not require the knowledge of . In addition to the proof of convergence, the method allows us to assess the convergence rate according to two different measures. Proofs produced by the method are often simpler or give better upper bounds than their classical counterparts, as examplified here on Herman's mutual exclusion and Iterated Prisoner's Dilemma algorithms in the case of cyclic graphs.     

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 ,

The Expected Size of the Rule k Dominating Set

Dai, Li, and Wu proposed Rule k, a localized approximation algorithm that attempts to find a small connected dominating set in a graph. In this paper we consider the "average-case" performance of two closely related versions of Rule k for the model of random unit disk graphs constructed from n random points in an square. We show that if and then for both versions of Rule k, the expected size of the Rule k dominating set is as It follows that, for in a suitable range, the expected size of the Rule k dominating sets are within a constant factor of the optimum.     

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.     

Nonconforming mixed finite element methods for linear elasticity using rectangular elements in two and three dimensions

Abstract We present nonconforming, rectangular mixed finite element methods based on the Hellinger-Reissner variational principle in both two and three dimensions and show stability and convergence. An optimal error estimate of is obtained for the displacement, along with a suboptimal, , error estimate for the stress, in both dimensions.     

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.     

Coincidental extension of scattered context languages

All the results given in the paper hold true. In the proof of Theorem 1, change steps IV, V, and VI to IV. for every , add to P; V. for every , add , , , , , to P; VI. for every , add to P.     

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.     

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.     

Efficient Algorithms for k Maximum Sums

We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers and an integer parameter k, the problem involves finding the k largest values of for The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. Recently, Bae and Takaoka presented a -time algorithm for the k maximum sum subsequences problem. In this paper we design an efficient algorithm that solves the above problem in time in the worst case. Our algorithm is optimal for and improves over the previously best known result for any value of the user-defined parameter k < 1. Moreover, our results are also extended to the multi-dimensional versions of the k maximum sum subsequences problem; resulting in fast algorithms as well.     

Real Hypercomputation and Continuity

By the sometimes so-called Main Theorem of Recursive Analysis, every computable real function is necessarily continuous. We wonder whether and which kinds of hypercomputation allow for the effective evaluation of also discontinuous . More precisely the present work considers the following three super-Turing notions of real function computability: - relativized computation; specifically given oracle access to the Halting Problem or its jump ; - encoding input and/or output y = f(x) in weaker ways also related to the Arithmetic Hierarchy; - nondeterministic computation. It turns out that any computable in the first or second sense is still necessarily continuous whereas the third type of hypercomputation provides the required power to evaluate for instance the discontinuous Heaviside function.     

Algorithms for the Homogeneous Set Sandwich Problem

A homogeneous set is a non-trivial module of a graph, i.e. a non-empty, non-unitary, proper subset of a graph's vertices such that all its elements present exactly the same outer neighborhood. Given two graphs the Homogeneous Set Sandwich Problem (HSSP) asks whether there exists a sandwich graph which has a homogeneous set. In 2001 Tang et al. published an all-fast algorithm which was recently proven wrong, so that the HSSP's known upper bound would have been reset thereafter at the former determined by Cerioli et al. in 1998. We present, notwithstanding, new deterministic algorithms which have it established at We give as well two even faster randomized algorithms, whose simplicity might lend them didactic usefulness. We believe that, besides providing efficient easy-to-implement procedures to solve it, the study of these new approaches allows a fairly thorough understanding of the problem.     

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.