OpenRaiser/Intern-Atlas huggingface dataset:
Evolutionary Socioeconomics: Notes on the Computer Simulation according to the de Finetti - Simon Principia
Venue: arXiv cs.CY 2007
Year: 2007

The present note includes explanatory comments about the synergic interaction within the sphere of the socioeconomic analysis between the two following theoretical frameworks. (I). The Darwinian evolutionary model. (II). The computer simulation in accordance with the principia established by Bruno de Finetti and Herbert Simon.
Physarum machine: Implementation of Kolmogorov-Uspensky machine in biological substrat
Venue: arXiv cs.AR 2007
Year: 2007

We implement Kolmogorov-Uspensky machine on a plasmodium of true slime mold {\em Physarum polycephalum}. We provide experimental findings on realization of the machine instructions, illustrate basic operations, and elements of programming.
Computing Good Nash Equilibria in Graphical Games
Venue: arXiv cs.GT 2007
Year: 2007

This paper addresses the problem of fair equilibrium selection in graphical games. Our approach is based on the data structure called the {\em best response policy}, which was proposed by Kearns et al. \cite{kls} as a way to represent all Nash equilibria of a graphical game. In \cite{egg}, it was shown that the best response policy has polynomial size as long as the underlying graph is a path. In this paper, we show that if the underlying graph is a bounded-degree tree and the best response policy has polynomial size then there is an efficient algorithm which constructs a Nash equilibrium that guarantees certain payoffs to all participants. Another attractive solution concept is a Nash equilibrium that maximizes the social welfare. We show that, while exactly computing the latter is infeasible (we prove that solving this problem may involve algebraic numbers of an arbitrarily high degree), there exists an FPTAS for finding such an equilibrium as long as the best response policy has polynomial size. These two algorithms can be combined to produce Nash equilibria that satisfy various fairness criteria.
Pragmatic Space-Time Trellis Codes for Block Fading Channels
Venue: arXiv cs.IT 2007
Year: 2007

A pragmatic approach for the construction of space-time codes over block fading channels is investigated. The approach consists in using common convolutional encoders and Viterbi decoders with suitable generators and rates, thus greatly simplifying the implementation of space-time codes. For the design of pragmatic space-time codes a methodology is proposed and applied, based on the extension of the concept of generalized transfer function for convolutional codes over block fading channels. Our search algorithm produces the convolutional encoder generators of pragmatic space-time codes for various number of states, number of antennas and fading rate. Finally it is shown that, for the investigated cases, the performance of pragmatic space-time codes is better than that of previously known space-time codes, confirming that they are a valuable choice in terms of both implementation complexity and performance.
How much feedback is required in MIMO Broadcast Channels?
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, a downlink communication system, in which a Base Station (BS) equipped with M antennas communicates with N users each equipped with K receive antennas ($K \leq M$), is considered. It is assumed that the receivers have perfect Channel State Information (CSI), while the BS only knows the partial CSI, provided by the receivers via feedback. The minimum amount of feedback required at the BS, to achieve the maximum sum-rate capacity in the asymptotic case of $N \to \infty$ and different ranges of SNR is studied. In the fixed and low SNR regimes, it is demonstrated that to achieve the maximum sum-rate, an infinite amount of feedback is required. Moreover, in order to reduce the gap to the optimum sum-rate to zero, in the fixed SNR regime, the minimum amount of feedback scales as $θ(\ln \ln \ln N)$, which is achievable by the Random Beam-Forming scheme proposed in [14]. In the high SNR regime, two cases are considered; in the case of $K < M$, it is proved that the minimum amount of feedback bits to reduce the gap between the achievable sum-rate and the maximum sum-rate to zero grows logaritmically with SNR, which is achievable by the "Generalized Random Beam-Forming" scheme, proposed in [18]. In the case of $K = M$, it is shown that by using the Random Beam-Forming scheme and the total amount of feedback not growing with SNR, the maximum sum-rate capacity is achieved.
On The Capacity Of Time-Varying Channels With Periodic Feedback
Venue: arXiv cs.IT 2007
Year: 2007

The capacity of time-varying channels with periodic feedback at the transmitter is evaluated. It is assumed that the channel state information is perfectly known at the receiver and is fed back to the transmitter at the regular time-intervals. The system capacity is investigated in two cases: i) finite state Markov channel, and ii) additive white Gaussian noise channel with time-correlated fading. In the first case, it is shown that the capacity is achievable by multiplexing multiple codebooks across the channel. In the second case, the channel capacity and the optimal adaptive coding is obtained. It is shown that the optimal adaptation can be achieved by a single Gaussian codebook, while adaptively allocating the total power based on the side information at the transmitter.
Exploring Logic Artificial Chemistries: An Illogical Attempt?
Venue: arXiv cs.NE 2007
Year: 2007

Robustness to a wide variety of negative factors and the ability to self-repair is an inherent and natural characteristic of all life forms on earth. As opposed to nature, man-made systems are in most cases not inherently robust and a significant effort has to be made in order to make them resistant against failures. This can be done in a wide variety of ways and on various system levels. In the field of digital systems, for example, techniques such as triple modular redundancy (TMR) are frequently used, which results in a considerable hardware overhead. Biologically-inspired computing by means of bio-chemical metaphors offers alternative paradigms, which need to be explored and evaluated. Here, we are interested to evaluate the potential of nature-inspired artificial chemistries and membrane systems as an alternative information representing and processing paradigm in order to obtain robust and spatially extended Boolean computing systems in a distributed environment. We investigate conceptual approaches inspired by artificial chemistries and membrane systems and compare proof-of-concepts. First, we show, that elementary logical functions can be implemented. Second, we illustrate how they can be made more robust and how they can be assembled to larger-scale systems. Finally, we discuss the implications for and paths to possible genuine implementations. Compared to the main body of work in artificial chemistries, we take a very pragmatic and implementation-oriented approach and are interested in realizing Boolean computations only. The results emphasize that artificial chemistries can be used to implement Boolean logic in a spatially extended and distributed environment and can also be made highly robust, but at a significant price.
Quantum Lambda Calculi with Classical Control: Syntax and Expressive Power
Venue: arXiv cs.LO 2007
Year: 2007

We study an untyped lambda calculus with quantum data and classical control. This work stems from previous proposals by Selinger and Valiron and by Van Tonder. We focus on syntax and expressiveness, rather than (denotational) semantics. We prove subject reduction, confluence and a standardization theorem. Moreover, we prove the computational equivalence of the proposed calculus with a suitable class of quantum circuit families.
Capacity Scaling for MIMO Two-Way Relaying
Venue: arXiv cs.IT 2008
Year: 2008

A multiple input multiple output (MIMO) two-way relay channel is considered, where two sources want to exchange messages with each other using multiple relay nodes, and both the sources and relay nodes are equipped with multiple antennas. Both the sources are assumed to have equal number of antennas and have perfect channel state information (CSI) for all the channels of the MIMO two-way relay channel, whereas, each relay node is either assumed to have CSI for its transmit and receive channel (the coherent case) or no CSI for any of the channels (the non-coherent case). The main results in this paper are on the scaling behavior of the capacity region of the MIMO two-way relay channel with increasing number of relay nodes. In the coherent case, the capacity region of the MIMO two-way relay channel is shown to scale linearly with the number of antennas at source nodes and logarithmically with the number of relay nodes. In the non-coherent case, the capacity region is shown to scale linearly with the number of antennas at the source nodes and logarithmically with the signal to noise ratio.
Multimedia Capacity Analysis of the IEEE 802.11e Contention-based Infrastructure Basic Service Set
Venue: arXiv cs.IT 2008
Year: 2008

We first propose a simple mathematical analysis framework for the Enhanced Distributed Channel Access (EDCA) function of the recently ratified IEEE 802.11e standard. Our analysis considers the fact that the distributed random access systems exhibit cyclic behavior. The proposed model is valid for arbitrary assignments of AC-specific Arbitration Interframe Space (AIFS) values and Contention Window (CW) sizes and is the first that considers an arbitrary distribution of active Access Categories (ACs) at the stations. Validating the theoretical results via extensive simulations, we show that the proposed analysis accurately captures the EDCA saturation performance. Next, we propose a framework for multimedia capacity analysis of the EDCA function. We calculate an accurate station- and AC-specific queue utilization ratio by appropriately weighing the service time predictions of the cycle time model for different number of active stations. Based on the calculated queue utilization ratio, we design a simple model-based admission control scheme. We show that the proposed call admission control algorithm maintains satisfactory user-perceived quality for coexisting voice and video connections in an infrastructure BSS and does not present over- or under-admission problems of previously proposed models in the literature.
Channel Capacity Estimation using Free Probability Theory
Venue: arXiv cs.IT 2008
Year: 2008

In many channel measurement applications, one needs to estimate some characteristics of the channels based on a limited set of measurements. This is mainly due to the highly time varying characteristics of the channel. In this contribution, it will be shown how free probability can be used for channel capacity estimation in MIMO systems. Free probability has already been applied in various application fields such as digital communications, nuclear physics and mathematical finance, and has been shown to be an invaluable tool for describing the asymptotic behaviour of many large-dimensional systems. In particular, using the concept of free deconvolution, we provide an asymptotically (w.r.t. the number of observations) unbiased capacity estimator for MIMO channels impaired with noise called the free probability based estimator. Another estimator, called the Gaussian matrix mean based estimator, is also introduced by slightly modifying the free probability based estimator. This estimator is shown to give unbiased estimation of the moments of the channel matrix for any number of observations. Also, the estimator has this property when we extend to MIMO channels with phase off-set and frequency drift, for which no estimator has been provided so far in the literature. It is also shown that both the free probability based and the Gaussian matrix mean based estimator are asymptotically unbiased capacity estimators as the number of transmit antennas go to infinity, regardless of whether phase off-set and frequency drift are present. The limitations in the two estimators are also explained. Simulations are run to assess the performance of the estimators for a low number of antennas and samples to confirm the usefulness of the asymptotic results.
Decentralized sequential change detection using physical layer fusion
Venue: arXiv cs.IT 2008
Year: 2008

The problem of decentralized sequential detection with conditionally independent observations is studied. The sensors form a star topology with a central node called fusion center as the hub. The sensors make noisy observations of a parameter that changes from an initial state to a final state at a random time where the random change time has a geometric distribution. The sensors amplify and forward the observations over a wireless Gaussian multiple access channel and operate under either a power constraint or an energy constraint. The optimal transmission strategy at each stage is shown to be the one that maximizes a certain Ali-Silvey distance between the distributions for the hypotheses before and after the change. Simulations demonstrate that the proposed analog technique has lower detection delays when compared with existing schemes. Simulations further demonstrate that the energy-constrained formulation enables better use of the total available energy than the power-constrained formulation in the change detection problem.
Faster subsequence recognition in compressed strings
Venue: arXiv cs.DS 2008
Year: 2008

Computation on compressed strings is one of the key approaches to processing massive data sets. We consider local subsequence recognition problems on strings compressed by straight-line programs (SLP), which is closely related to Lempel--Ziv compression. For an SLP-compressed text of length $\bar m$, and an uncompressed pattern of length $n$, C{é}gielski et al. gave an algorithm for local subsequence recognition running in time $O(\bar mn^2 \log n)$. We improve the running time to $O(\bar mn^{1.5})$. Our algorithm can also be used to compute the longest common subsequence between a compressed text and an uncompressed pattern in time $O(\bar mn^{1.5})$; the same problem with a compressed pattern is known to be NP-hard.
On the Complexity of the Interlace Polynomial
Venue: arXiv cs.CC 2008
Year: 2008

We consider the two-variable interlace polynomial introduced by Arratia, Bollobas and Sorkin (2004). We develop graph transformations which allow us to derive point-to-point reductions for the interlace polynomial. Exploiting these reductions we obtain new results concerning the computational complexity of evaluating the interlace polynomial at a fixed point. Regarding exact evaluation, we prove that the interlace polynomial is #P-hard to evaluate at every point of the plane, except on one line, where it is trivially polynomial time computable, and four lines, where the complexity is still open. This solves a problem posed by Arratia, Bollobas and Sorkin (2004). In particular, three specializations of the two-variable interlace polynomial, the vertex-nullity interlace polynomial, the vertex-rank interlace polynomial and the independent set polynomial, are almost everywhere #P-hard to evaluate, too. For the independent set polynomial, our reductions allow us to prove that it is even hard to approximate at any point except at 0.
Computability of probability measures and Martin-Lof randomness over metric spaces
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we investigate algorithmic randomness on more general spaces than the Cantor space, namely computable metric spaces. To do this, we first develop a unified framework allowing computations with probability measures. We show that any computable metric space with a computable probability measure is isomorphic to the Cantor space in a computable and measure-theoretic sense. We show that any computable metric space admits a universal uniform randomness test (without further assumption).
Deadlock Detection in Basic Models of MPI Synchronization Communication Programs
Venue: arXiv cs.DC 2008
Year: 2008

A model of MPI synchronization communication programs is presented and its three basic simplified models are also defined. A series of theorems and methods for deciding whether deadlocks will occur among the three models are given and proved strictly. These theories and methods for simple models' deadlock detection are the necessary base for real MPI program deadlock detection. The methods are based on a static analysis through programs and with runtime detection in necessary cases and they are able to determine before compiling whether it will be deadlocked for two of the three basic models. For another model, some deadlock cases can be found before compiling and others at runtime. Our theorems can be used to prove the correctness of currently popular MPI program deadlock detection algorithms. Our methods may decrease codes that those algorithms need to change to MPI source or profiling interface and may detects deadlocks ahead of program execution, thus the overheads can be reduced greatly.
A New Perspective on Multi-user Power Control Games in Interference Channels
Venue: arXiv cs.GT 2008
Year: 2008

This paper considers the problem of how to allocate power among competing users sharing a frequency-selective interference channel. We model the interaction between selfish users as a non-cooperative game. As opposed to the existing iterative water-filling algorithm that studies the myopic users, this paper studies how a foresighted user, who knows the channel state information and response strategies of its competing users, should optimize its transmission strategy. To characterize this multi-user interaction, the Stackelberg equilibrium is introduced, and the existence of this equilibrium for the investigated non-cooperative game is shown. We analyze this interaction in more detail using a simple two-user example, where the foresighted user determines its transmission strategy by solving as a bi-level program which allows him to account for the myopic user's response. It is analytically shown that a foresighted user can improve its performance, if it has the necessary information about its competitors. Since the optimal solution of Stackelberg equilibrium is computationally prohibitive, we propose a practical low-complexity approach based on Lagrangian duality theory. Numerical simulations verify the performance improvements. Possible ways to acquire the required information and to extend the formulation to more than two users are also discussed.
Symmetric and Synchronous Communication in Peer-to-Peer Networks
Venue: arXiv cs.DC 2008
Year: 2008

Motivated by distributed implementations of game-theoretical algorithms, we study symmetric process systems and the problem of attaining common knowledge between processes. We formalize our setting by defining a notion of peer-to-peer networks(*) and appropriate symmetry concepts in the context of Communicating Sequential Processes (CSP), due to the common knowledge creating effects of its synchronous communication primitives. We then prove that CSP with input and output guards makes common knowledge in symmetric peer-to-peer networks possible, but not the restricted version which disallows output statements in guards and is commonly implemented. (*) Please note that we are not dealing with fashionable incarnations such as file-sharing networks, but merely use this name for a mathematical notion of a network consisting of directly connected peers "treated on an equal footing", i.e. not having a client-server structure or otherwise pre-determined roles.)
Random subcubes as a toy model for constraint satisfaction problems
Venue: arXiv cs.CC 2008
Year: 2008

We present an exactly solvable random-subcube model inspired by the structure of hard constraint satisfaction and optimization problems. Our model reproduces the structure of the solution space of the random k-satisfiability and k-coloring problems, and undergoes the same phase transitions as these problems. The comparison becomes quantitative in the large-k limit. Distance properties, as well the x-satisfiability threshold, are studied. The model is also generalized to define a continuous energy landscape useful for studying several aspects of glassy dynamics.
Generalized reliability-based syndrome decoding for LDPC codes
Venue: arXiv cs.IT 2008
Year: 2008

Aiming at bridging the gap between the maximum likelihood decoding (MLD) and the suboptimal iterative decodings for short or medium length LDPC codes, we present a generalized ordered statistic decoding (OSD) in the form of syndrome decoding, to cascade with the belief propagation (BP) or enhanced min-sum decoding. The OSD is invoked only when the decoding failures are obtained for the preceded iterative decoding method. With respect to the existing OSD which is based on the accumulated log-likelihood ratio (LLR) metric, we extend the accumulative metric to the situation where the BP decoding is in the probability domain. Moreover, after generalizing the accumulative metric to the context of the normalized or offset min-sum decoding, the OSD shows appealing tradeoff between performance and complexity. In the OSD implementation, when deciding the true error pattern among many candidates, an alternative proposed proves to be effective to reduce the number of real additions without performance loss. Simulation results demonstrate that the cascade connection of enhanced min-sum and OSD decodings outperforms the BP alone significantly, in terms of either performance or complexity.
On the operating unit size of load/store architectures
Venue: arXiv cs.AR 2008
Year: 2008

We introduce a strict version of the concept of a load/store instruction set architecture in the setting of Maurer machines. We take the view that transformations on the states of a Maurer machine are achieved by applying threads as considered in thread algebra to the Maurer machine. We study how the transformations on the states of the main memory of a strict load/store instruction set architecture that can be achieved by applying threads depend on the operating unit size, the cardinality of the instruction set, and the maximal number of states of the threads.
On Low Complexity Maximum Likelihood Decoding of Convolutional Codes
Venue: arXiv cs.IT 2008
Year: 2008

This paper considers the average complexity of maximum likelihood (ML) decoding of convolutional codes. ML decoding can be modeled as finding the most probable path taken through a Markov graph. Integrated with the Viterbi algorithm (VA), complexity reduction methods such as the sphere decoder often use the sum log likelihood (SLL) of a Markov path as a bound to disprove the optimality of other Markov path sets and to consequently avoid exhaustive path search. In this paper, it is shown that SLL-based optimality tests are inefficient if one fixes the coding memory and takes the codeword length to infinity. Alternatively, optimality of a source symbol at a given time index can be testified using bounds derived from log likelihoods of the neighboring symbols. It is demonstrated that such neighboring log likelihood (NLL)-based optimality tests, whose efficiency does not depend on the codeword length, can bring significant complexity reduction to ML decoding of convolutional codes. The results are generalized to ML sequence detection in a class of discrete-time hidden Markov systems.
Detecting palindromes, patterns, and borders in regular languages
Venue: arXiv cs.CC 2008
Year: 2008

Given a language L and a nondeterministic finite automaton M, we consider whether we can determine efficiently (in the size of M) if M accepts at least one word in L, or infinitely many words. Given that M accepts at least one word in L, we consider how long a shortest word can be. The languages L that we examine include the palindromes, the non-palindromes, the k-powers, the non-k-powers, the powers, the non-powers (also called primitive words), the words matching a general pattern, the bordered words, and the unbordered words.