OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Transmit Covariance for Ergodic MIMO Channels
Venue: arXiv cs.IT 2005
Year: 2005

In this paper we consider the computation of channel capacity for ergodic multiple-input multiple-output channels with additive white Gaussian noise. Two scenarios are considered. Firstly, a time-varying channel is considered in which both the transmitter and the receiver have knowledge of the channel realization. The optimal transmission strategy is water-filling over space and time. It is shown that this may be achieved in a causal, indeed instantaneous fashion. In the second scenario, only the receiver has perfect knowledge of the channel realization, while the transmitter has knowledge of the channel gain probability law. In this case we determine an optimality condition on the input covariance for ergodic Gaussian vector channels with arbitrary channel distribution under the condition that the channel gains are independent of the transmit signal. Using this optimality condition, we find an iterative algorithm for numerical computation of optimal input covariance matrices. Applications to correlated Rayleigh and Ricean channels are given.
Acyclic orientations with path constraints
Venue: arXiv cs.DM 2005
Year: 2005

Many well-known combinatorial optimization problems can be stated over the set of acyclic orientations of an undirected graph. For example, acyclic orientations with certain diameter constraints are closely related to the optimal solutions of the vertex coloring and frequency assignment problems. In this paper we introduce a linear programming formulation of acyclic orientations with path constraints, and discuss its use in the solution of the vertex coloring problem and some versions of the frequency assignment problem. A study of the polytope associated with the formulation is presented, including proofs of which constraints of the formulation are facet-defining and the introduction of new classes of valid inequalities.
Semantic Embedding of Petri Nets into Event-B
Venue: arXiv cs.LO 2005
Year: 2005

We present an embedding of Petri nets into B abstract systems. The embedding is achieved by translating both the static structure (modelling aspect) and the evolution semantics of Petri nets. The static structure of a Petri-net is captured within a B abstract system through a graph structure. This abstract system is then included in another abstract system which captures the evolution semantics of Petri-nets. The evolution semantics results in some B events depending on the chosen policies: basic nets or high level Petri nets. The current embedding enables one to use conjointly Petri nets and Event-B in the same system development, but at different steps and for various analysis.
Virtual Environments for multiphysics code validation on Computing Grids
Venue: arXiv cs.DC 2005
Year: 2005

We advocate in this paper the use of grid-based infrastructures that are designed for seamless approaches to the numerical expert users, i.e., the multiphysics applications designers. It relies on sophisticated computing environments based on computing grids, connecting heterogeneous computing resources: mainframes, PC-clusters and workstations running multiphysics codes and utility software, e.g., visualization tools. The approach is based on concepts defined by the HEAVEN* consortium. HEAVEN is a European scientific consortium including industrial partners from the aerospace, telecommunication and software industries, as well as academic research institutes. Currently, the HEAVEN consortium works on a project that aims to create advanced services platforms. It is intended to enable "virtual private grids" supporting various environments for users manipulating a suitable high-level interface. This will become the basis for future generalized services allowing the integration of various services without the need to deploy specific grid infrastructures.
Lower bounds on Locality Sensitive Hashing
Venue: arXiv cs.CG 2005
Year: 2005

Given a metric space $(X,d_X)$, $c\ge 1$, $r>0$, and $p,q\in [0,1]$, a distribution over mappings $\h:X\to \mathbb N$ is called a $(r,cr,p,q)$-sensitive hash family if any two points in $X$ at distance at most $r$ are mapped by $\h$ to the same value with probability at least $p$, and any two points at distance greater than $cr$ are mapped by $\h$ to the same value with probability at most $q$. This notion was introduced by Indyk and Motwani in 1998 as the basis for an efficient approximate nearest neighbor search algorithm, and has since been used extensively for this purpose. The performance of these algorithms is governed by the parameter $ρ=\frac{\log(1/p)}{\log(1/q)}$, and constructing hash families with small $ρ$ automatically yields improved nearest neighbor algorithms. Here we show that for $X=\ell_1$ it is impossible to achieve $ρ\le \frac{1}{2c}$. This almost matches the construction of Indyk and Motwani which achieves $ρ\le \frac{1}{c}$.
Automata-based adaptive behavior for economic modeling using game theory
Venue: arXiv cs.MA 2005
Year: 2005

In this paper, we deal with some specific domains of applications to game theory. This is one of the major class of models in the new approaches of modelling in the economic domain. For that, we use genetic automata which allow to buid adaptive strategies for the players. We explain how the automata-based formalism proposed - matrix representation of automata with multiplicities - allows to define a semi-distance between the strategy behaviors. With that tools, we are able to generate an automatic processus to compute emergent systems of entities whose behaviors are represented by these genetic automata.
Big Science with a Small Budget: Non-Embarrassingly Parallel Applications in a Non-Dedicated Network of Workstations
Venue: arXiv cs.DC 2005
Year: 2005

Many astronomers and astrophysicists require large computing resources for their research, which are usually obtained via dedicated (and expensive) parallel machines. Depending on the type of the problem to be solved, an alternative solution can be provided by creating dynamically a computer cluster out of non-dedicated workstations using the Condor High Throughput Computing System and the Master-Worker (MW) framework. As an example of this we show in this paper how a radiative transfer application previously coded with MPI is solved using this solution without the need for dedicated machines.
Flat and One-Variable Clauses: Complexity of Verifying Cryptographic Protocols with Single Blind Copying
Venue: arXiv cs.LO 2005
Year: 2005

Cryptographic protocols with single blind copying were defined and modeled by Comon and Cortier using the new class $\mathcal C$ of first order clauses. They showed its satisfiability problem to be in 3-DEXPTIME. We improve this result by showing that satisfiability for this class is NEXPTIME-complete, using new resolution techniques. We show satisfiability to be DEXPTIME-complete if clauses are Horn, which is what is required for modeling cryptographic protocols. While translation to Horn clauses only gives a DEXPTIME upper bound for the secrecy problem for these protocols, we further show that this secrecy problem is actually DEXPTIME-complete.
A Counterexample to Cover's 2P Conjecture on Gaussian Feedback Capacity
Venue: arXiv cs.IT 2005
Year: 2005

We provide a counterexample to Cover's conjecture that the feedback capacity $C_\textrm{FB}$ of an additive Gaussian noise channel under power constraint $P$ be no greater than the nonfeedback capacity $C$ of the same channel under power constraint $2P$, i.e., $C_\textrm{FB}(P) \le C(2P)$.
Discrete Network Dynamics. Part 1: Operator Theory
Venue: arXiv cs.NE 2005
Year: 2005

An operator algebra implementation of Markov chain Monte Carlo algorithms for simulating Markov random fields is proposed. It allows the dynamics of networks whose nodes have discrete state spaces to be specified by the action of an update operator that is composed of creation and annihilation operators. This formulation of discrete network dynamics has properties that are similar to those of a quantum field theory of bosons, which allows reuse of many conceptual and theoretical structures from QFT. The equilibrium behaviour of one of these generalised MRFs and of the adaptive cluster expansion network (ACEnet) are shown to be equivalent, which provides a way of unifying these two theories.
Towards a unified theory of logic programming semantics: Level mapping characterizations of selector generated models
Venue: arXiv cs.AI 2005
Year: 2005

Currently, the variety of expressive extensions and different semantics created for logic programs with negation is diverse and heterogeneous, and there is a lack of comprehensive comparative studies which map out the multitude of perspectives in a uniform way. Most recently, however, new methodologies have been proposed which allow one to derive uniform characterizations of different declarative semantics for logic programs with negation. In this paper, we study the relationship between two of these approaches, namely the level mapping characterizations due to [Hitzler and Wendt 2005], and the selector generated models due to [Schwarz 2004]. We will show that the latter can be captured by means of the former, thereby supporting the claim that level mappings provide a very flexible framework which is applicable to very diversely defined semantics.
The Generalized Area Theorem and Some of its Consequences
Venue: arXiv cs.IT 2005
Year: 2005

There is a fundamental relationship between belief propagation and maximum a posteriori decoding. The case of transmission over the binary erasure channel was investigated in detail in a companion paper. This paper investigates the extension to general memoryless channels (paying special attention to the binary case). An area theorem for transmission over general memoryless channels is introduced and some of its many consequences are discussed. We show that this area theorem gives rise to an upper-bound on the maximum a posteriori threshold for sparse graph codes. In situations where this bound is tight, the extrinsic soft bit estimates delivered by the belief propagation decoder coincide with the correct a posteriori probabilities above the maximum a posteriori threshold. More generally, it is conjectured that the fundamental relationship between the maximum a posteriori and the belief propagation decoder which was observed for transmission over the binary erasure channel carries over to the general case. We finally demonstrate that in order for the design rate of an ensemble to approach the capacity under belief propagation decoding the component codes have to be perfectly matched, a statement which is well known for the special case of transmission over the binary erasure channel.
An Invariant Cost Model for the Lambda Calculus
Venue: arXiv cs.LO 2005
Year: 2005

We define a new cost model for the call-by-value lambda-calculus satisfying the invariance thesis. That is, under the proposed cost model, Turing machines and the call-by-value lambda-calculus can simulate each other within a polynomial time overhead. The model only relies on combinatorial properties of usual beta-reduction, without any reference to a specific machine or evaluator. In particular, the cost of a single beta reduction is proportional to the difference between the size of the redex and the size of the reduct. In this way, the total cost of normalizing a lambda term will take into account the size of all intermediate results (as well as the number of steps to normal form).
Generalized Kasami Sequences: The Large Set
Venue: arXiv cs.IT 2005
Year: 2005

In this paper new binary sequence families $\mathcal{F}^k$ of period $2^n-1$ are constructed for even $n$ and any $k$ with ${\rm gcd}(k,n)=2$ if $n/2$ is odd or ${\rm gcd}(k,n)=1$ if $n/2$ is even. The distribution of their correlation values is completely determined. These families have maximum correlation $2^{n/2+1}+1$ and family size $2^{3n/2}+2^{n/2}$ for odd $n/2$ or $2^{3n/2}+2^{n/2}-1$ for even $n/2$. The construction of the large set of Kasami sequences which is exactly the $\mathcal{F}^{k}$ with $k=n/2+1$ is generalized.
Eigenvalue Distributions of Sums and Products of Large Random Matrices via Incremental Matrix Expansions
Venue: arXiv cs.IT 2005
Year: 2005

This paper uses an incremental matrix expansion approach to derive asymptotic eigenvalue distributions (a.e.d.'s) of sums and products of large random matrices. We show that the result can be derived directly as a consequence of two common assumptions, and matches the results obtained from using R- and S-transforms in free probability theory. We also give a direct derivation of the a.e.d. of the sum of certain random matrices which are not free. This is used to determine the asymptotic signal-to-interference-ratio of a multiuser CDMA system with a minimum mean-square error linear receiver.
On Quadratic Inverses for Quadratic Permutation Polynomials over Integer Rings
Venue: arXiv cs.IT 2005
Year: 2005

An interleaver is a critical component for the channel coding performance of turbo codes. Algebraic constructions are of particular interest because they admit analytical designs and simple, practical hardware implementation. Sun and Takeshita have recently shown that the class of quadratic permutation polynomials over integer rings provides excellent performance for turbo codes. In this correspondence, a necessary and sufficient condition is proven for the existence of a quadratic inverse polynomial for a quadratic permutation polynomial over an integer ring. Further, a simple construction is given for the quadratic inverse. All but one of the quadratic interleavers proposed earlier by Sun and Takeshita are found to admit a quadratic inverse, although none were explicitly designed to do so. An explanation is argued for the observation that restriction to a quadratic inverse polynomial does not narrow the pool of good quadratic interleavers for turbo codes.
Robust Inference of Trees
Venue: arXiv cs.LG 2005
Year: 2005

This paper is concerned with the reliable inference of optimal tree-approximations to the dependency structure of an unknown distribution generating data. The traditional approach to the problem measures the dependency strength between random variables by the index called mutual information. In this paper reliability is achieved by Walley's imprecise Dirichlet model, which generalizes Bayesian learning with Dirichlet priors. Adopting the imprecise Dirichlet model results in posterior interval expectation for mutual information, and in a set of plausible trees consistent with the data. Reliable inference about the actual tree is achieved by focusing on the substructure common to all the plausible trees. We develop an exact algorithm that infers the substructure in time O(m^4), m being the number of random variables. The new algorithm is applied to a set of data sampled from a known distribution. The method is shown to reliably infer edges of the actual tree even when the data are very scarce, unlike the traditional approach. Finally, we provide lower and upper credibility limits for mutual information under the imprecise Dirichlet model. These enable the previous developments to be extended to a full inferential method for trees.
Societal Implicit Memory and his Speed on Tracking Extrema over Dynamic Environments using Self-Regulatory Swarms
Venue: arXiv cs.MA 2005
Year: 2005

In order to overcome difficult dynamic optimization and environment extrema tracking problems, We propose a Self-Regulated Swarm (SRS) algorithm which hybridizes the advantageous characteristics of Swarm Intelligence as the emergence of a societal environmental memory or cognitive map via collective pheromone laying in the landscape (properly balancing the exploration/exploitation nature of our dynamic search strategy), with a simple Evolutionary mechanism that trough a direct reproduction procedure linked to local environmental features is able to self-regulate the above exploratory swarm population, speeding it up globally. In order to test his adaptive response and robustness, we have recurred to different dynamic multimodal complex functions as well as to Dynamic Optimization Control problems, measuring reaction speeds and performance. Final comparisons were made with standard Genetic Algorithms (GAs), Bacterial Foraging strategies (BFOA), as well as with recent Co-Evolutionary approaches. SRS's were able to demonstrate quick adaptive responses, while outperforming the results obtained by the other approaches. Additionally, some successful behaviors were found. One of the most interesting illustrate that the present SRS collective swarm of bio-inspired ant-like agents is able to track about 65% of moving peaks traveling up to ten times faster than the velocity of a single individual composing that precise swarm tracking system.
On Ants, Bacteria and Dynamic Environments
Venue: arXiv cs.DC 2005
Year: 2005

Wasps, bees, ants and termites all make effective use of their environment and resources by displaying collective swarm intelligence. Termite colonies - for instance - build nests with a complexity far beyond the comprehension of the individual termite, while ant colonies dynamically allocate labor to various vital tasks such as foraging or defense without any central decision-making ability. Recent research suggests that microbial life can be even richer: highly social, intricately networked, and teeming with interactions, as found in bacteria. What strikes from these observations is that both ant colonies and bacteria have similar natural mechanisms based on Stigmergy and Self-Organization in order to emerge coherent and sophisticated patterns of global behaviour. Keeping in mind the above characteristics we will present a simple model to tackle the collective adaptation of a social swarm based on real ant colony behaviors (SSA algorithm) for tracking extrema in dynamic environments and highly multimodal complex functions described in the well-know De Jong test suite. Then, for the purpose of comparison, a recent model of artificial bacterial foraging (BFOA algorithm) based on similar stigmergic features is described and analyzed. Final results indicate that the SSA collective intelligence is able to cope and quickly adapt to unforeseen situations even when over the same cooperative foraging period, the community is requested to deal with two different and contradictory purposes, while outperforming BFOA in adaptive speed.
The Water-Filling Game in Fading Multiple Access Channels
Venue: arXiv cs.IT 2005
Year: 2005

We adopt a game theoretic approach for the design and analysis of distributed resource allocation algorithms in fading multiple access channels. The users are assumed to be selfish, rational, and limited by average power constraints. We show that the sum-rate optimal point on the boundary of the multipleaccess channel capacity region is the unique Nash Equilibrium of the corresponding water-filling game. This result sheds a new light on the opportunistic communication principle and argues for the fairness of the sum-rate optimal point, at least from a game theoretic perspective. The base-station is then introduced as a player interested in maximizing a weighted sum of the individual rates. We propose a Stackelberg formulation in which the base-station is the designated game leader. In this set-up, the base-station announces first its strategy defined as the decoding order of the different users, in the successive cancellation receiver, as a function of the channel state. In the second stage, the users compete conditioned on this particular decoding strategy. We show that this formulation allows for achieving all the corner points of the capacity region, in addition to the sum-rate optimal point. On the negative side, we prove the non-existence of a base-station strategy in this formulation that achieves the rest of the boundary points. To overcome this limitation, we present a repeated game approach which achieves the capacity region of the fading multiple access channel. Finally, we extend our study to vector channels highlighting interesting differences between this scenario and the scalar channel case.
Perfect Space-Time Codes with Minimum and Non-Minimum Delay for Any Number of Antennas
Venue: arXiv cs.IT 2005
Year: 2005

Perfect space-time codes were first introduced by Oggier et. al. to be the space-time codes that have full rate, full diversity-gain, non-vanishing determinant for increasing spectral efficiency, uniform average transmitted energy per antenna and good shaping of the constellation. These defining conditions jointly correspond to optimality with respect to the Zheng-Tse D-MG tradeoff, independent of channel statistics, as well as to near optimality in maximizing mutual information. All the above traits endow the code with error performance that is currently unmatched. Yet perfect space-time codes have been constructed only for 2,3,4 and 6 transmit antennas. We construct minimum and non-minimum delay perfect codes for all channel dimensions.
Bootstrapping the Long Tail in Peer to Peer Systems
Venue: arXiv cs.NI 2005
Year: 2005

We describe an efficient incentive mechanism for P2P systems that generates a wide diversity of content offerings while responding adaptively to customer demand. Files are served and paid for through a parimutuel market similar to that commonly used for betting in horse races. An analysis of the performance of such a system shows that there exists an equilibrium with a long tail in the distribution of content offerings, which guarantees the real time provision of any content regardless of its popularity.
Semidefinite programming and arithmetic circuit evaluation
Venue: arXiv cs.CC 2005
Year: 2005

A rational number can be naturally presented by an arithmetic computation (AC): a sequence of elementary arithmetic operations starting from a fixed constant, say 1. The asymptotic complexity issues of such a representation are studied e.g. in the framework of the algebraic complexity theory over arbitrary field. Here we study a related problem of the complexity of performing arithmetic operations and computing elementary predicates, e.g. ``='' or ``>'', on rational numbers given by AC. In the first place, we prove that AC can be efficiently simulated by the exact semidefinite programming (SDP). Secondly, we give a BPP-algorithm for the equality predicate. Thirdly, we put ``>''-predicate into the complexity class PSPACE. We conjecture that ``>''-predicate is hard to compute. This conjecture, if true, would clarify the complexity status of the exact SDP - a well known open problem in the field of mathematical programming.
Evolving Stochastic Learning Algorithm Based on Tsallis Entropic Index
Venue: arXiv cs.NE 2005
Year: 2005

In this paper, inspired from our previous algorithm, which was based on the theory of Tsallis statistical mechanics, we develop a new evolving stochastic learning algorithm for neural networks. The new algorithm combines deterministic and stochastic search steps by employing a different adaptive stepsize for each network weight, and applies a form of noise that is characterized by the nonextensive entropic index q, regulated by a weight decay term. The behavior of the learning algorithm can be made more stochastic or deterministic depending on the trade off between the temperature T and the q values. This is achieved by introducing a formula that defines a time--dependent relationship between these two important learning parameters. Our experimental study verifies that there are indeed improvements in the convergence speed of this new evolving stochastic learning algorithm, which makes learning faster than using the original Hybrid Learning Scheme (HLS). In addition, experiments are conducted to explore the influence of the entropic index q and temperature T on the convergence speed and stability of the proposed method.