OpenRaiser/Intern-Atlas huggingface dataset:
Min-Max decoding for non binary LDPC codes
Venue: arXiv cs.IT 2009
Year: 2009

Iterative decoding of non-binary LDPC codes is currently performed using either the Sum-Product or the Min-Sum algorithms or slightly different versions of them. In this paper, several low-complexity quasi-optimal iterative algorithms are proposed for decoding non-binary codes. The Min-Max algorithm is one of them and it has the benefit of two possible LLR domain implementations: a standard implementation, whose complexity scales as the square of the Galois field's cardinality and a reduced complexity implementation called selective implementation, which makes the Min-Max decoding very attractive for practical purposes.
Resampling and requantization of band-limited Gaussian stochastic signals with flat power spectrum
Venue: arXiv cs.IT 2009
Year: 2009

A theoretical analysis, aimed at characterizing the degradation induced by the resampling and requantization processes applied to band-limited Gaussian signals with flat power spectrum, available through their digitized samples, is presented. The analysis provides an efficient algorithm for computing the complete {joint} bivariate discrete probability distribution associated to the true quantized version of the Gaussian signal and to the quantity estimated after resampling and requantization of the input digitized sequence. The use of Fourier transform techniques allows deriving {approximate} analytical expressions for the quantities of interest, as well as implementing their efficient computation. Numerical experiments are found to be in good agreement with the theoretical results, and confirm the validity of the whole approach.
Unequal Error Protection: An Information Theoretic Perspective
Venue: arXiv cs.IT 2009
Year: 2009

An information theoretic framework for unequal error protection is developed in terms of the exponential error bounds. The fundamental difference between the bit-wise and message-wise unequal error protection (UEP) is demonstrated, for fixed length block codes on DMCs without feedback. Effect of feedback is investigated via variable length block codes. It is shown that, feedback results in a significant improvement in both bit-wise and message-wise UEP (except the single message case for missed detection). The distinction between false-alarm and missed-detection formalizations for message-wise UEP is also considered. All results presented are at rates close to capacity.
Digital Ecosystems: Self-Organisation of Evolving Agent Populations
Venue: arXiv cs.NE 2009
Year: 2009

A primary motivation for our research in Digital Ecosystems is the desire to exploit the self-organising properties of biological ecosystems. Ecosystems are thought to be robust, scalable architectures that can automatically solve complex, dynamic problems. Self-organisation is perhaps one of the most desirable features in the systems that we engineer, and it is important for us to be able to measure self-organising behaviour. We investigate the self-organising aspects of Digital Ecosystems, created through the application of evolutionary computing to Multi-Agent Systems (MASs), aiming to determine a macroscopic variable to characterise the self-organisation of the evolving agent populations within. We study a measure for the self-organisation called Physical Complexity; based on statistical physics, automata theory, and information theory, providing a measure of information relative to the randomness in an organism's genome, by calculating the entropy in a population. We investigate an extension to include populations of variable length, and then built upon this to construct an efficiency measure to investigate clustering within evolving agent populations. Overall an insight has been achieved into where and how self-organisation occurs in our Digital Ecosystem, and how it can be quantified.
A Unified Semi-Supervised Dimensionality Reduction Framework for Manifold Learning
Venue: arXiv cs.LG 2009
Year: 2009

We present a general framework of semi-supervised dimensionality reduction for manifold learning which naturally generalizes existing supervised and unsupervised learning frameworks which apply the spectral decomposition. Algorithms derived under our framework are able to employ both labeled and unlabeled examples and are able to handle complex problems where data form separate clusters of manifolds. Our framework offers simple views, explains relationships among existing frameworks and provides further extensions which can improve existing algorithms. Furthermore, a new semi-supervised kernelization framework called ``KPCA trick'' is proposed to handle non-linear problems.
Phutball is PSPACE-hard
Venue: arXiv cs.GT 2009
Year: 2009

We consider the $n\times n$ game of Phutball. It is shown that, given an arbitrary position of stones on the board, it is a PSPACE-hard problem to determine whether the specified player can win the game, regardless of the opponent's choices made during the game.
Grainy Numbers
Venue: arXiv cs.LO 2009
Year: 2009

Grainy numbers are defined as tuples of bits. They form a lattice where the meet and the join operations are an addition and a multiplication. They may be substituted for the real numbers in the definition of fuzzy sets. The aim is to propose an alternative negation for the complement that we'll call supplement.
Robust Cognitive Beamforming With Partial Channel State Information
Venue: arXiv cs.IT 2009
Year: 2009

This paper considers a spectrum sharing based cognitive radio (CR) communication system, which consists of a secondary user (SU) having multiple transmit antennas and a single receive antenna and a primary user (PU) having a single receive antenna. The channel state information (CSI) on the link of the SU is assumed to be perfectly known at the SU transmitter (SU-Tx). However, due to loose cooperation between the SU and the PU, only partial CSI of the link between the SU-Tx and the PU is available at the SU-Tx. With the partial CSI and a prescribed transmit power constraint, our design objective is to determine the transmit signal covariance matrix that maximizes the rate of the SU while keeping the interference power to the PU below a threshold for all the possible channel realization within an uncertainty set. This problem, termed the robust cognitive beamforming problem, can be naturally formulated as a semi-infinite programming (SIP) problem with infinitely many constraints. This problem is first transformed into the second order cone programming (SOCP) problem and then solved via a standard interior point algorithm. Then, an analytical solution with much reduced complexity is developed from a geometric perspective. It is shown that both algorithms obtain the same optimal solution. Simulation examples are presented to validate the effectiveness of the proposed algorithms.
Asymptotic Analysis of the Performance of LAS Algorithm for Large-MIMO Detection
Venue: arXiv cs.IT 2009
Year: 2009

In our recent work, we reported an exhaustive study on the simulated bit error rate (BER) performance of a low-complexity likelihood ascent search (LAS) algorithm for detection in large multiple-input multiple-output (MIMO) systems with large number of antennas that achieve high spectral efficiencies. Though the algorithm was shown to achieve increasingly closer to near maximum-likelihood (ML) performance through simulations, no BER analysis was reported. Here, we extend our work on LAS and report an asymptotic BER analysis of the LAS algorithm in the large system limit, where $N_t,N_r \to \infty$ with $N_t=N_r$, where $N_t$ and $N_r$ are the number of transmit and receive antennas. We prove that the error performance of the LAS detector in V-BLAST with 4-QAM in i.i.d. Rayleigh fading converges to that of the ML detector as $N_t,N_r \to \infty$.
Optimal hash functions for approximate closest pairs on the n-cube
Venue: arXiv cs.IT 2009
Year: 2009

One way to find closest pairs in large datasets is to use hash functions. In recent years locality-sensitive hash functions for various metrics have been given: projecting an n-cube onto k bits is simple hash function that performs well. In this paper we investigate alternatives to projection. For various parameters hash functions given by complete decoding algorithms for codes work better, and asymptotically random codes perform better than projection.
Counteracting Byzantine Adversaries with Network Coding: An Overhead Analysis
Venue: arXiv cs.IT 2009
Year: 2009

Network coding increases throughput and is robust against failures and erasures. However, since it allows mixing of information within the network, a single corrupted packet generated by a Byzantine attacker can easily contaminate the information to multiple destinations. In this paper, we study the transmission overhead associated with three different schemes for detecting Byzantine adversaries at a node using network coding: end-to-end error correction, packet-based Byzantine detection scheme, and generation-based Byzantine detection scheme. In end-to-end error correction, it is known that we can correct up to the min-cut between the source and destinations. However, if we use Byzantine detection schemes, we can detect polluted data, drop them, and therefore, only transmit valid data. For the dropped data, the destinations perform erasure correction, which is computationally lighter than error correction. We show that, with enough attackers present in the network, Byzantine detection schemes may improve the throughput of the network since we choose to forward only reliable information. When the probability of attack is high, a packet-based detection scheme is the most bandwidth efficient; however, when the probability of attack is low, the overhead involved with signing each packet becomes costly, and the generation-based scheme may be preferred. Finally, we characterize the tradeoff between generation size and overhead of detection in bits as the probability of attack increases in the network.
On empirical meaning of randomness with respect to a real parameter
Venue: arXiv cs.LG 2009
Year: 2009

We study the empirical meaning of randomness with respect to a family of probability distributions $P_θ$, where $θ$ is a real parameter, using algorithmic randomness theory. In the case when for a computable probability distribution $P_θ$ an effectively strongly consistent estimate exists, we show that the Levin's a priory semicomputable semimeasure of the set of all $P_θ$-random sequences is positive if and only if the parameter $θ$ is a computable real number. The different methods for generating ``meaningful'' $P_θ$-random sequences with noncomputable $θ$ are discussed.
On the Tradeoffs of Implementing Randomized Network Coding in Multicast Networks
Venue: arXiv cs.IT 2009
Year: 2009

Randomized network coding (RNC) greatly reduces the complexity of implementing network coding in large-scale, heterogeneous networks. This paper examines two tradeoffs in applying RNC: The first studies how the performance of RNC varies with a node's randomizing capabilities. Specifically, a limited randomized network coding (L-RNC) scheme - in which intermediate nodes perform randomized encoding based on only a limited number of random coefficients - is proposed and its performance bounds are analyzed. Such a L-RNC approach is applicable to networks in which nodes have either limited computation/storage capacity or have ambiguity about downstream edge connectivity (e.g., as in ad hoc sensor networks). A second tradeoff studied here examines the relationship between the reliability and the capacity gains of generalized RNC, i.e., how the outage probability of RNC relates to the transmission rate at the source node. This tradeoff reveals that significant reductions in outage probability are possible when the source transmits deliberately and only slightly below network capacity. This approach provides an effective means to improve the feasibility probability of RNC when the size of the finite field is fixed.
Altruism in Atomic Congestion Games
Venue: arXiv cs.GT 2009
Year: 2009

This paper studies the effects of introducing altruistic agents into atomic congestion games. Altruistic behavior is modeled by a trade-off between selfish and social objectives. In particular, we assume agents optimize a linear combination of personal delay of a strategy and the resulting increase in social cost. Our model can be embedded in the framework of congestion games with player-specific latency functions. Stable states are the Nash equilibria of these games, and we examine their existence and the convergence of sequential best-response dynamics. Previous work shows that for symmetric singleton games with convex delays Nash equilibria are guaranteed to exist. For concave delay functions we observe that there are games without Nash equilibria and provide a polynomial time algorithm to decide existence for symmetric singleton games with arbitrary delay functions. Our algorithm can be extended to compute best and worst Nash equilibria if they exist. For more general congestion games existence becomes NP-hard to decide, even for symmetric network games with quadratic delay functions. Perhaps surprisingly, if all delay functions are linear, then there is always a Nash equilibrium in any congestion game with altruists and any better-response dynamics converges. In addition to these results for uncoordinated dynamics, we consider a scenario in which a central altruistic institution can motivate agents to act altruistically. We provide constructive and hardness results for finding the minimum number of altruists to stabilize an optimal congestion profile and more general mechanisms to incentivize agents to adopt favorable behavior.
On dual Schur domain decomposition method for linear first-order transient problems
Venue: arXiv cs.NA 2009
Year: 2009

This paper addresses some numerical and theoretical aspects of dual Schur domain decomposition methods for linear first-order transient partial differential equations. In this work, we consider the trapezoidal family of schemes for integrating the ordinary differential equations (ODEs) for each subdomain and present four different coupling methods, corresponding to different algebraic constraints, for enforcing kinematic continuity on the interface between the subdomains. Method 1 (d-continuity) is based on the conventional approach using continuity of the primary variable and we show that this method is unstable for a lot of commonly used time integrators including the mid-point rule. To alleviate this difficulty, we propose a new Method 2 (Modified d-continuity) and prove its stability for coupling all time integrators in the trapezoidal family (except the forward Euler). Method 3 (v-continuity) is based on enforcing the continuity of the time derivative of the primary variable. However, this constraint introduces a drift in the primary variable on the interface. We present Method 4 (Baumgarte stabilized) which uses Baumgarte stabilization to limit this drift and we derive bounds for the stabilization parameter to ensure stability. Our stability analysis is based on the ``energy'' method, and one of the main contributions of this paper is the extension of the energy method (which was previously introduced in the context of numerical methods for ODEs) to assess the stability of numerical formulations for index-2 differential-algebraic equations (DAEs).
Hybrid Keyword Search Auctions
Venue: arXiv cs.GT 2009
Year: 2009

Search auctions have become a dominant source of revenue generation on the Internet. Such auctions have typically used per-click bidding and pricing. We propose the use of hybrid auctions where an advertiser can make a per-impression as well as a per-click bid, and the auctioneer then chooses one of the two as the pricing mechanism. We assume that the advertiser and the auctioneer both have separate beliefs (called priors) on the click-probability of an advertisement. We first prove that the hybrid auction is truthful, assuming that the advertisers are risk-neutral. We then show that this auction is superior to the existing per-click auction in multiple ways: 1) It takes into account the risk characteristics of the advertisers. 2) For obscure keywords, the auctioneer is unlikely to have a very sharp prior on the click-probabilities. In such situations, the hybrid auction can result in significantly higher revenue. 3) An advertiser who believes that its click-probability is much higher than the auctioneer's estimate can use per-impression bids to correct the auctioneer's prior without incurring any extra cost. 4) The hybrid auction can allow the advertiser and auctioneer to implement complex dynamic programming strategies. As Internet commerce matures, we need more sophisticated pricing models to exploit all the information held by each of the participants. We believe that hybrid auctions could be an important step in this direction.
Algorithms for Scheduling Weighted Packets with Deadlines in a Bounded Queue
Venue: arXiv cs.DS 2009
Year: 2009

Motivated by the Quality-of-Service (QoS) buffer management problem, we consider online scheduling of packets with hard deadlines in a finite capacity queue. At any time, a queue can store at most $b \in \mathbb Z^+$ packets. Packets arrive over time. Each packet is associated with a non-negative value and an integer deadline. In each time step, only one packet is allowed to be sent. Our objective is to maximize the total value gained by the packets sent by their deadlines in an online manner. Due to the Internet traffic's chaotic characteristics, no stochastic assumptions are made on the packet input sequences. This model is called a {\em finite-queue model}. We use competitive analysis to measure an online algorithm's performance versus an unrealizable optimal offline algorithm who constructs the worst possible input based on the knowledge of the online algorithm. For the finite-queue model, we first present a deterministic 3-competitive memoryless online algorithm. Then, we give a randomized ($ϕ^2 = ((1 + \sqrt{5}) / 2)^2 \approx 2.618$)-competitive memoryless online algorithm. The algorithmic framework and its theoretical analysis include several interesting features. First, our algorithms use (possibly) modified characteristics of packets; these characteristics may not be same as those specified in the input sequence. Second, our analysis method is different from the classical potential function approach.
On the Rate of Channel Polarization
Venue: arXiv cs.IT 2009
Year: 2009

It is shown that for any binary-input discrete memoryless channel $W$ with symmetric capacity $I(W)$ and any rate $R <I(W)$, the probability of block decoding error for polar coding under successive cancellation decoding satisfies $P_e \le 2^{-N^β}$ for any $β<\frac12$ when the block-length $N$ is large enough.
Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels
Venue: arXiv cs.IT 2009
Year: 2009

A method is proposed, called channel polarization, to construct code sequences that achieve the symmetric capacity $I(W)$ of any given binary-input discrete memoryless channel (B-DMC) $W$. The symmetric capacity is the highest rate achievable subject to using the input letters of the channel with equal probability. Channel polarization refers to the fact that it is possible to synthesize, out of $N$ independent copies of a given B-DMC $W$, a second set of $N$ binary-input channels $\{W_N^{(i)}:1\le i\le N\}$ such that, as $N$ becomes large, the fraction of indices $i$ for which $I(W_N^{(i)})$ is near 1 approaches $I(W)$ and the fraction for which $I(W_N^{(i)})$ is near 0 approaches $1-I(W)$. The polarized channels $\{W_N^{(i)}\}$ are well-conditioned for channel coding: one need only send data at rate 1 through those with capacity near 1 and at rate 0 through the remaining. Codes constructed on the basis of this idea are called polar codes. The paper proves that, given any B-DMC $W$ with $I(W)>0$ and any target rate $R < I(W)$, there exists a sequence of polar codes $\{{\mathscr C}_n;n\ge 1\}$ such that ${\mathscr C}_n$ has block-length $N=2^n$, rate $\ge R$, and probability of block error under successive cancellation decoding bounded as $P_{e}(N,R) \le \bigoh(N^{-\frac14})$ independently of the code rate. This performance is achievable by encoders and decoders with complexity $O(N\log N)$ for each.
Error-Correcting Codes in Projective Spaces via Rank-Metric Codes and Ferrers Diagrams
Venue: arXiv cs.IT 2009
Year: 2009

Coding in the projective space has received recently a lot of attention due to its application in network coding. Reduced row echelon form of the linear subspaces and Ferrers diagram can play a key role for solving coding problems in the projective space. In this paper we propose a method to design error-correcting codes in the projective space. We use a multilevel approach to design our codes. First, we select a constant weight code. Each codeword defines a skeleton of a basis for a subspace in reduced row echelon form. This skeleton contains a Ferrers diagram on which we design a rank-metric code. Each such rank-metric code is lifted to a constant dimension code. The union of these codes is our final constant dimension code. In particular the codes constructed recently by Koetter and Kschischang are a subset of our codes. The rank-metric codes used for this construction form a new class of rank-metric codes. We present a decoding algorithm to the constructed codes in the projective space. The efficiency of the decoding depends on the efficiency of the decoding for the constant weight codes and the rank-metric codes. Finally, we use puncturing on our final constant dimension codes to obtain large codes in the projective space which are not constant dimension.
Periodicity, repetitions, and orbits of an automatic sequence
Venue: arXiv cs.DM 2009
Year: 2009

We revisit a technique of S. Lehr on automata and use it to prove old and new results in a simple way. We give a very simple proof of the 1986 theorem of Honkala that it is decidable whether a given k-automatic sequence is ultimately periodic. We prove that it is decidable whether a given k-automatic sequence is overlap-free (or squareefree, or cubefree, etc.) We prove that the lexicographically least sequence in the orbit closure of a k-automatic sequence is k-automatic, and use this last result to show that several related quantities, such as the critical exponent, irrationality measure, and recurrence quotient for Sturmian words with slope alpha, have automatic continued fraction expansions if alpha does.
Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes
Venue: arXiv cs.DB 2009
Year: 2009

Bitmap indexes must be compressed to reduce input/output costs and minimize CPU usage. To accelerate logical operations (AND, OR, XOR) over bitmaps, we use techniques based on run-length encoding (RLE), such as Word-Aligned Hybrid (WAH) compression. These techniques are sensitive to the order of the rows: a simple lexicographical sort can divide the index size by 9 and make indexes several times faster. We investigate reordering heuristics based on computed attribute-value histograms. Simply permuting the columns of the table based on these histograms can increase the sorting efficiency by 40%.