OpenRaiser/Intern-Atlas huggingface dataset:
Synchronized Task Decomposition for Cooperative Multi-agent Systems
Venue: arXiv cs.MA 2011
Year: 2011

It is an amazing fact that remarkably complex behaviors could emerge from a large collection of very rudimentary dynamical agents through very simple local interactions. However, it still remains elusive on how to design these local interactions among agents so as to achieve certain desired collective behaviors. This paper aims to tackle this challenge and proposes a divide-and-conquer approach to guarantee specified global behaviors through local coordination and control design for multi-agent systems. The basic idea is to decompose the requested global specification into subtasks for each individual agent. It should be noted that the decomposition is not arbitrary. The global specification should be decomposed in such a way that the fulfilment of these subtasks by each individual agent will imply the satisfaction of the global specification as a team. First, it is shown by a counterexample that not all specifications can be decomposed in this sense. Then, a natural follow-up question is what the necessary and sufficient condition should be for the proposed decomposability of a global specification. The main part of the paper is set to answer this question. The case of two cooperative agents is investigated first, and a necessary and sufficient condition is presented and proven. Later on, the result is generalized to the case of arbitrary finite number of agents, and a hierarchical algorithm is proposed, which is shown to be a sufficient condition. Finally, a cooperative control scenario for a team of three robots is developed to illustrate the task decomposition procedure.
Xampling: Signal Acquisition and Processing in Union of Subspaces
Venue: arXiv cs.IT 2011
Year: 2011

We introduce Xampling, a unified framework for signal acquisition and processing of signals in a union of subspaces. The main functions of this framework are two. Analog compression that narrows down the input bandwidth prior to sampling with commercial devices. A nonlinear algorithm then detects the input subspace prior to conventional signal processing. A representative union model of spectrally-sparse signals serves as a test-case to study these Xampling functions. We adopt three metrics for the choice of analog compression: robustness to model mismatch, required hardware accuracy and software complexities. We conduct a comprehensive comparison between two sub-Nyquist acquisition strategies for spectrally-sparse signals, the random demodulator and the modulated wideband converter (MWC), in terms of these metrics and draw operative conclusions regarding the choice of analog compression. We then address lowrate signal processing and develop an algorithm for that purpose that enables convenient signal processing at sub-Nyquist rates from samples obtained by the MWC. We conclude by showing that a variety of other sampling approaches for different union classes fit nicely into our framework.
Order algebras: a quantitative model of interaction
Venue: arXiv cs.LO 2011
Year: 2011

A quantitative model of concurrent interaction is introduced. The basic objects are linear combinations of partial order relations, acted upon by a group of permutations that represents potential non-determinism in synchronisation. This algebraic structure is shown to provide faithful interpretations of finitary process algebras, for an extension of the standard notion of testing semantics, leading to a model that is both denotational (in the sense that the internal workings of processes are ignored) and non-interleaving. Constructions on algebras and their subspaces enjoy a good structure that make them (nearly) a model of differential linear logic, showing that the underlying approach to the representation of non-determinism as linear combinations is the same.
Opportunistic capacity and error exponent regions for compound channel with feedback
Venue: arXiv cs.IT 2011
Year: 2011

Variable length communication over a compound channel with feedback is considered. Traditionally, capacity of a compound channel without feedback is defined as the maximum rate that is determined before the start of communication such that communication is reliable. This traditional definition is pessimistic. In the presence of feedback, an opportunistic definition is given. Capacity is defined as the maximum rate that is determined at the end of communication such that communication is reliable. Thus, the transmission rate can adapt to the channel chosen by nature. Under this definition, feedback communication over a compound channel is conceptually similar to multi-terminal communication. Transmission rate is a vector rather than a scalar; channel capacity is a region rather than a scalar; error exponent is a region rather than a scalar. In this paper, variable length communication over a compound channel with feedback is formulated, its opportunistic capacity region is characterized, and lower bounds for its error exponent region are provided..
PyCUDA and PyOpenCL: A Scripting-Based Approach to GPU Run-Time Code Generation
Venue: arXiv cs.DC 2011
Year: 2011

High-performance computing has recently seen a surge of interest in heterogeneous systems, with an emphasis on modern Graphics Processing Units (GPUs). These devices offer tremendous potential for performance and efficiency in important large-scale applications of computational science. However, exploiting this potential can be challenging, as one must adapt to the specialized and rapidly evolving computing environment currently exhibited by GPUs. One way of addressing this challenge is to embrace better techniques and develop tools tailored to their needs. This article presents one simple technique, GPU run-time code generation (RTCG), along with PyCUDA and PyOpenCL, two open-source toolkits that support this technique. In introducing PyCUDA and PyOpenCL, this article proposes the combination of a dynamic, high-level scripting language with the massive performance of a GPU as a compelling two-tiered computing platform, potentially offering significant performance and productivity advantages over conventional single-tier, static systems. The concept of RTCG is simple and easily implemented using existing, robust infrastructure. Nonetheless it is powerful enough to support (and encourage) the creation of custom application-specific tools by its users. The premise of the paper is illustrated by a wide range of examples where the technique has been applied with considerable success.
Hearing the clusters in a graph: A distributed algorithm
Venue: arXiv cs.DM 2011
Year: 2011

We propose a novel distributed algorithm to cluster graphs. The algorithm recovers the solution obtained from spectral clustering without the need for expensive eigenvalue/vector computations. We prove that, by propagating waves through the graph, a local fast Fourier transform yields the local component of every eigenvector of the Laplacian matrix, thus providing clustering information. For large graphs, the proposed algorithm is orders of magnitude faster than random walk based approaches. We prove the equivalence of the proposed algorithm to spectral clustering and derive convergence rates. We demonstrate the benefit of using this decentralized clustering algorithm for community detection in social graphs, accelerating distributed estimation in sensor networks and efficient computation of distributed multi-agent search strategies.
Transmission Capacity of Ad-hoc Networks with Multiple Antennas using Transmit Stream Adaptation and Interference Cancelation
Venue: arXiv cs.IT 2011
Year: 2011

The transmission capacity of an ad-hoc network is the maximum density of active transmitters per unit area, given an outage constraint at each receiver for a fixed rate of transmission. Assuming that the transmitter locations are distributed as a Poisson point process, this paper derives upper and lower bounds on the transmission capacity of an ad-hoc network when each node is equipped with multiple antennas. The transmitter either uses eigen multi-mode beamforming or a subset of its antennas to transmit multiple data streams, while the receiver uses partial zero forcing to cancel certain interferers using some of its spatial receive degrees of freedom (SRDOF). The receiver either cancels the nearest interferers or those interferers that maximize the post-cancelation signal-to-interference ratio. Using the obtained bounds, the optimal number of data streams to transmit, and the optimal SRDOF to use for interference cancelation are derived that provide the best scaling of the transmission capacity with the number of antennas. With beamforming, single data stream transmission together with using all but one SRDOF for interference cancelation is optimal, while without beamforming, single data stream transmission together with using a fraction of the total SRDOF for interference cancelation is optimal.
On the circuit-size of inverses
Venue: arXiv cs.CC 2011
Year: 2011

We reprove a result of Boppana and Lagarias: If Pi_2^P is different from Sigma_2^P then there exists a partial function f that is computable by a polynomial-size family of circuits, but no inverse of f is computable by a polynomial-size family of circuits. We strengthen this result by showing that there exist length-preserving total functions that are one-way by circuit size and that are computable in uniform polynomial time. We also prove, if Pi_2^P is different from Sigma_2^P, that there exist polynomially balanced total surjective functions that are one-way by circuit size; here non-uniformity is used.
Graph-Constrained Group Testing
Venue: arXiv cs.DM 2011
Year: 2011

Non-adaptive group testing involves grouping arbitrary subsets of $n$ items into different pools. Each pool is then tested and defective items are identified. A fundamental question involves minimizing the number of pools required to identify at most $d$ defective items. Motivated by applications in network tomography, sensor networks and infection propagation, a variation of group testing problems on graphs is formulated. Unlike conventional group testing problems, each group here must conform to the constraints imposed by a graph. For instance, items can be associated with vertices and each pool is any set of nodes that must be path connected. In this paper, a test is associated with a random walk. In this context, conventional group testing corresponds to the special case of a complete graph on $n$ vertices. For interesting classes of graphs a rather surprising result is obtained, namely, that the number of tests required to identify $d$ defective items is substantially similar to what is required in conventional group testing problems, where no such constraints on pooling is imposed. Specifically, if T(n) corresponds to the mixing time of the graph $G$, it is shown that with $m=O(d^2T^2(n)\log(n/d))$ non-adaptive tests, one can identify the defective items. Consequently, for the Erdos-Renyi random graph $G(n,p)$, as well as expander graphs with constant spectral gap, it follows that $m=O(d^2\log^3n)$ non-adaptive tests are sufficient to identify $d$ defective items. Next, a specific scenario is considered that arises in network tomography, for which it is shown that $m=O(d^3\log^3n)$ non-adaptive tests are sufficient to identify $d$ defective items. Noisy counterparts of the graph constrained group testing problem are considered, for which parallel results are developed. We also briefly discuss extensions to compressive sensing on graphs.
Effective complexity of stationary process realizations
Venue: arXiv cs.IT 2011
Year: 2011

The concept of effective complexity of an object as the minimal description length of its regularities has been initiated by Gell-Mann and Lloyd. The regularities are modeled by means of ensembles, that is probability distributions on finite binary strings. In our previous paper we propose a definition of effective complexity in precise terms of algorithmic information theory. Here we investigate the effective complexity of binary strings generated by stationary, in general not computable, processes. We show that under not too strong conditions long typical process realizations are effectively simple. Our results become most transparent in the context of coarse effective complexity which is a modification of the original notion of effective complexity that uses less parameters in its definition. A similar modification of the related concept of sophistication has been suggested by Antunes and Fortnow.
Mortality and Longevity Valuation - A Quantitative Approach
Venue: arXiv cs.OH 2011
Year: 2011

This paper examines several computer algorithms designed to assess mortality and longevity risk.
Efficient Implementation of Rewriting Revisited Technical Report
Venue: arXiv cs.CC 2011
Year: 2011

Recently, many techniques have been introduced that allow the (automated) classification of the runtime complexity of term rewrite systems (TRSs for short). In earlier work, the authors have shown that for confluent TRSs, innermost polynomial runtime complexity induces polytime computability of the functions defined. In this paper, we generalise the above result to full rewriting. Following our previous work, we exploit graph rewriting. We give a new proof of the adequacy of graph rewriting for full rewriting that allows for a precise control of the resources copied. In sum we completely describe an implementation of rewriting on a Turing machine (TM for short). We show that the runtime complexity of the TRS and the runtime complexity of the TM is polynomially related. Our result strengthens the evidence that the complexity of a rewrite system is truthfully represented through the length of derivations. Moreover our result allows the classification of non-deterministic polytime-computation based on runtime complexity analysis of rewrite systems.
Mobile Wireless Localization through Cooperation
Venue: arXiv cs.DC 2011
Year: 2011

This paper considers N mobile nodes that move together in the vicinity of each other, whose initial poses as well as subsequent movements must be accurately tracked in real time with the assist of M(>=3) reference nodes. By engaging the neighboring mobile nodes in a simple but effective cooperation, and by exploiting both the time-of-arrival (TOA) information (between mobile nodes and reference nodes) and the received-signal-strength (RSS) information (between mobile nodes), an effective new localization strategy, termed cooperative TOA and RSS (COTAR), is developed. An optimal maximum likelihood detector is first formulated, followed by the derivation of a low-complexity iterative approach that can practically achieve the Cramer-Rao lower bound. Instead of using simplified channel models as in many previous studies, a sophisticated and realistic channel model is used, which can effectively account for the critical fact that the direct path is not necessarily the strongest path. Extensive simulations are conducted in static and mobile settings, and various practical issues and system parameters are evaluated. It is shown that COTAR significantly outperforms the existing strategies, achieving a localization accuracy of only a few tenths of a meter in clear environments and a couple of meters in heavily obstructed environments.
Bounded Rationality, Strategy Simplification, and Equilibrium
Venue: arXiv cs.GT 2011
Year: 2011

It is frequently suggested that predictions made by game theory could be improved by considering computational restrictions when modeling agents. Under the supposition that players in a game may desire to balance maximization of payoff with minimization of strategy complexity, Rubinstein and co-authors studied forms of Nash equilibrium where strategies are maximally simplified in that no strategy can be further simplified without sacrificing payoff. Inspired by this line of work, we introduce a notion of equilibrium whereby strategies are also maximally simplified, but with respect to a simplification procedure that is more careful in that a player will not simplify if the simplification incents other players to deviate. We study such equilibria in two-player machine games in which players choose finite automata that succinctly represent strategies for repeated games; in this context, we present techniques for establishing that an outcome is at equilibrium and present results on the structure of equilibria.
MISO Capacity with Per-Antenna Power Constraint
Venue: arXiv cs.IT 2011
Year: 2011

We establish in closed-form the capacity and the optimal signaling scheme for a MISO channel with per-antenna power constraint. Two cases of channel state information are considered: constant channel known at both the transmitter and receiver, and Rayleigh fading channel known only at the receiver. For the first case, the optimal signaling scheme is beamforming with the phases of the beam weights matched to the phases of the channel coefficients, but the amplitudes independent of the channel coefficients and dependent only on the constrained powers. For the second case, the optimal scheme is to send independent signals from the antennas with the constrained powers. In both cases, the capacity with per-antenna power constraint is usually less than that with sum power constraint.
Introduction to clarithmetic I
Venue: arXiv cs.LO 2011
Year: 2011

"Clarithmetic" is a generic name for formal number theories similar to Peano arithmetic, but based on computability logic (see http://www.cis.upenn.edu/~giorgi/cl.html) instead of the more traditional classical or intuitionistic logics. Formulas of clarithmetical theories represent interactive computational problems, and their "truth" is understood as existence of an algorithmic solution. Imposing various complexity constraints on such solutions yields various versions of clarithmetic. The present paper introduces a system of clarithmetic for polynomial time computability, which is shown to be sound and complete. Sound in the sense that every theorem T of the system represents an interactive number-theoretic computational problem with a polynomial time solution and, furthermore, such a solution can be efficiently extracted from a proof of T. And complete in the sense that every interactive number-theoretic problem with a polynomial time solution is represented by some theorem T of the system. The paper is written in a semitutorial style and targets readers with no prior familiarity with computability logic.
Multi-User Cooperative Diversity through Network Coding Based on Classical Coding Theory
Venue: arXiv cs.IT 2011
Year: 2011

In this work, we propose and analyze a generalized construction of distributed network codes for a network consisting of $M$ users sending different information to a common base station through independent block fading channels. The aim is to increase the diversity order of the system without reducing its throughput. The proposed scheme, called generalized dynamic-network codes (GDNC), is a generalization of the dynamic-network codes (DNC) recently proposed by Xiao and Skoglund. The design of the network codes that maximize the diversity order is recognized as equivalent to the design of linear block codes over a nonbinary finite field under the Hamming metric. We prove that adopting a systematic generator matrix of a maximum distance separable block code over a sufficiently large finite field as the network transfer matrix is a sufficient condition for full diversity order under link failure model. The proposed generalization offers a much better tradeoff between rate and diversity order compared to the DNC. An outage probability analysis showing the improved performance is carried out, and computer simulations results are shown to agree with the analytical results.
Minimizing the Complexity of Fast Sphere Decoding of STBCs
Venue: arXiv cs.IT 2011
Year: 2011

Decoding of linear space-time block codes (STBCs) with sphere-decoding (SD) is well known. A fast-version of the SD known as fast sphere decoding (FSD) has been recently studied by Biglieri, Hong and Viterbo. Viewing a linear STBC as a vector space spanned by its defining weight matrices over the real number field, we define a quadratic form (QF), called the Hurwitz-Radon QF (HRQF), on this vector space and give a QF interpretation of the FSD complexity of a linear STBC. It is shown that the FSD complexity is only a function of the weight matrices defining the code and their ordering, and not of the channel realization (even though the equivalent channel when SD is used depends on the channel realization) or the number of receive antennas. It is also shown that the FSD complexity is completely captured into a single matrix obtained from the HRQF. Moreover, for a given set of weight matrices, an algorithm to obtain a best ordering of them leading to the least FSD complexity is presented. The well known classes of low FSD complexity codes (multi-group decodable codes, fast decodable codes and fast group decodable codes) are presented in the framework of HRQF.
Direct Proofs of Order Independence
Venue: arXiv cs.GT 2011
Year: 2011

We establish a generic result concerning order independence of a dominance relation on finite games. It allows us to draw conclusions about order independence of various dominance relations in a direct and simple way.
Revisiting LFSMs
Venue: arXiv cs.CR 2011
Year: 2011

Linear Finite State Machines (LFSMs) are particular primitives widely used in information theory, coding theory and cryptography. Among those linear automata, a particular case of study is Linear Feedback Shift Registers (LFSRs) used in many cryptographic applications such as design of stream ciphers or pseudo-random generation. LFSRs could be seen as particular LFSMs without inputs. In this paper, we first recall the description of LFSMs using traditional matrices representation. Then, we introduce a new matrices representation with polynomial fractional coefficients. This new representation leads to sparse representations and implementations. As direct applications, we focus our work on the Windmill LFSRs case, used for example in the E0 stream cipher and on other general applications that use this new representation. In a second part, a new design criterion called diffusion delay for LFSRs is introduced and well compared with existing related notions. This criterion represents the diffusion capacity of an LFSR. Thus, using the matrices representation, we present a new algorithm to randomly pick LFSRs with good properties (including the new one) and sparse descriptions dedicated to hardware and software designs. We present some examples of LFSRs generated using our algorithm to show the relevance of our approach.