OpenRaiser/Intern-Atlas huggingface dataset:
Polytope of Correct (Linear Programming) Decoding and Low-Weight Pseudo-Codewords
Venue: arXiv cs.IT 2011
Year: 2011

We analyze Linear Programming (LP) decoding of graphical binary codes operating over soft-output, symmetric and log-concave channels. We show that the error-surface, separating domain of the correct decoding from domain of the erroneous decoding, is a polytope. We formulate the problem of finding the lowest-weight pseudo-codeword as a non-convex optimization (maximization of a convex function) over a polytope, with the cost function defined by the channel and the polytope defined by the structure of the code. This formulation suggests new provably convergent heuristics for finding the lowest weight pseudo-codewords improving in quality upon previously discussed. The algorithm performance is tested on the example of the Tanner [155, 64, 20] code over the Additive White Gaussian Noise (AWGN) channel.
Computability of simple games: A complete investigation of the sixty-four possibilities
Venue: arXiv cs.GT 2011
Year: 2011

Classify simple games into sixteen "types" in terms of the four conventional axioms: monotonicity, properness, strongness, and nonweakness. Further classify them into sixty-four classes in terms of finiteness (existence of a finite carrier) and algorithmic computability. For each such class, we either show that it is empty or give an example of a game belonging to it. We observe that if a type contains an infinite game, then it contains both computable ones and noncomputable ones. This strongly suggests that computability is logically, as well as conceptually, unrelated to the conventional axioms.
Capacity Achieving Linear Codes with Random Binary Sparse Generating Matrices
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we prove the existence of capacity achieving linear codes with random binary sparse generating matrices. The results on the existence of capacity achieving linear codes in the literature are limited to the random binary codes with equal probability generating matrix elements and sparse parity-check matrices. Moreover, the codes with sparse generating matrices reported in the literature are not proved to be capacity achieving. As opposed to the existing results in the literature, which are based on optimal maximum a posteriori decoders, the proposed approach is based on a different decoder and consequently is suboptimal. We also demonstrate an interesting trade-off between the sparsity of the generating matrix and the error exponent (a constant which determines how exponentially fast the probability of error decays as block length tends to infinity). An interesting observation is that for small block sizes, less sparse generating matrices have better performances while for large blok sizes, the performance of the random generating matrices become independent of the sparsity. Moreover, we prove the existence of capacity achieving linear codes with a given (arbitrarily low) density of ones on rows of the generating matrix. In addition to proving the existence of capacity achieving sparse codes, an important conclusion of our paper is that for a sufficiently large code length, no search is necessary in practice to find a deterministic matrix by proving that any arbitrarily selected sequence of sparse generating matrices is capacity achieving with high probability. The focus in this paper is on the binary symmetric and binary erasure channels.her discrete memory-less symmetric channels.
Using Distributed Rotations for a Low-Complexity Dynamic Decode-and-Forward Relay Protocol
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we propose to implement the dynamic decode-and-forward (DDF) protocol with distributed rotations. In addition to being the first minimum-delay implementation of the DDF protocol proposed for any number of relays, this technique allows to exploit cooperative diversity without inducing the high decoding complexity of a space-time code. The analysis of outage probabilities for different number of relays and rotations shows that the performance of this technique is close to optimal. Moreover, a lower-bound on the diversity-multiplexing gain tradeoff (DMT) is provided in the case of a single relay and two rotations. This lower-bound reaches the optimal DDF's DMT when the frame-length grows to infinity, which shows that even a small number of rotations is enough to obtain good performance.
Runtime Adaptability driven by Negotiable Quality Requirements
Venue: arXiv cs.SE 2011
Year: 2011

Two of the common features of business and the web are diversity and dynamism. Diversity results in users having different preferences for the quality requirements of a system. Diversity also makes possible alternative implementations for functional requirements, called variants, each of them providing different quality. The quality provided by the system may vary due to different variant components and changes in the environment. The challenge is to dynamically adapt to quality variations and to find the variant that best fulfills the multi-criteria quality requirements driven by user preferences and current runtime conditions. For service-oriented systems this challenge is augmented by their distributed nature and lack of control over the constituent services and their provided quality of service (QoS). We propose a novel approach to runtime adaptability that detects QoS changes, updates the system model with runtime information, and uses the model to select the variant to execute at runtime. We introduce negotiable maintenance goals to express user quality preferences in the requirements model and automatically interpret them quantitatively for system execution. Our lightweight selection strategy selects the variant that best fulfills the user required multi-criteria QoS based on updated QoS values.
A Trajectory UML profile For Modeling Trajectory Data: A Mobile Hospital Use Case
Venue: arXiv cs.DB 2011
Year: 2011

A large amount of data resulting from trajectories of moving objects activities are collected thanks to localization based services and some associated automated processes. Trajectories data can be used either for transactional and analysis purposes in various domains (heath care, commerce, environment, etc.). For this reason, modeling trajectory data at the conceptual level is an important stair leading to global vision and successful implementations. However, current modeling tools fail to fulfill specific moving objects activities requirements. In this paper, we propose a new profile based on UML in order to enhance the conceptual modeling of trajectory data related to mobile objects by new stereotypes and icons. As illustration, we present a mobile hospital use case.
Log-Convexity of Rate Region in 802.11e WLANs
Venue: arXiv cs.NI 2011
Year: 2011

In this paper we establish the log-convexity of the rate region in 802.11 WLANs. This generalises previous results for Aloha networks and has immediate implications for optimisation based approaches to the analysis and design of 802.11 wireless networks.
Digraph description of k-interchange technique for optimization over permutations and adaptive algorithm system
Venue: arXiv cs.DS 2011
Year: 2011

The paper describes a general glance to the use of element exchange techniques for optimization over permutations. A multi-level description of problems is proposed which is a fundamental to understand nature and complexity of optimization problems over permutations (e.g., ordering, scheduling, traveling salesman problem). The description is based on permutation neighborhoods of several kinds (e.g., by improvement of an objective function). Our proposed operational digraph and its kinds can be considered as a way to understand convexity and polynomial solvability for combinatorial optimization problems over permutations. Issues of an analysis of problems and a design of hierarchical heuristics are discussed. The discussion leads to a multi-level adaptive algorithm system which analyzes an individual problem and selects/designs a solving strategy (trajectory).
On Dynamic Optimality for Binary Search Trees
Venue: arXiv cs.DS 2011
Year: 2011

Does there exist O(1)-competitive (self-adjusting) binary search tree (BST) algorithms? This is a well-studied problem. A simple offline BST algorithm GreedyFuture was proposed independently by Lucas and Munro, and they conjectured it to be O(1)-competitive. Recently, Demaine et al. gave a geometric view of the BST problem. This view allowed them to give an online algorithm GreedyArb with the same cost as GreedyFuture. However, no o(n)-competitive ratio was known for GreedyArb. In this paper we make progress towards proving O(1)-competitive ratio for GreedyArb by showing that it is O(\log n)-competitive.
New Results on Scrambling Using the Mesh Array
Venue: arXiv cs.CR 2011
Year: 2011

This paper presents new results on randomization using Kak's Mesh Array for matrix multiplication. These results include the periods of the longest cycles when the the array is used for scrambling and the autocorrelation function of the binary sequence obtained from the cycles.
Towards Unbiased BFS Sampling
Venue: arXiv cs.SI 2011
Year: 2011

Breadth First Search (BFS) is a widely used approach for sampling large unknown Internet topologies. Its main advantage over random walks and other exploration techniques is that a BFS sample is a plausible graph on its own, and therefore we can study its topological characteristics. However, it has been empirically observed that incomplete BFS is biased toward high-degree nodes, which may strongly affect the measurements. In this paper, we first analytically quantify the degree bias of BFS sampling. In particular, we calculate the node degree distribution expected to be observed by BFS as a function of the fraction f of covered nodes, in a random graph RG(pk) with an arbitrary degree distribution pk. We also show that, for RG(pk), all commonly used graph traversal techniques (BFS, DFS, Forest Fire, Snowball Sampling, RDS) suffer from exactly the same bias. Next, based on our theoretical analysis, we propose a practical BFS-bias correction procedure. It takes as input a collected BFS sample together with its fraction f. Even though RG(pk) does not capture many graph properties common in real-life graphs (such as assortativity), our RG(pk)-based correction technique performs well on a broad range of Internet topologies and on two large BFS samples of Facebook and Orkut networks. Finally, we consider and evaluate a family of alternative correction procedures, and demonstrate that, although they are unbiased for an arbitrary topology, their large variance makes them far less effective than the RG(pk)-based technique.
The influence lower bound via query elimination
Venue: arXiv cs.CC 2011
Year: 2011

We give a simpler proof, via query elimination, of a result due to O'Donnell, Saks, Schramm and Servedio, which shows a lower bound on the zero-error randomized query complexity of a function f in terms of the maximum influence of any variable of f. Our lower bound also applies to the two-sided error distributional query complexity of f, and it allows an immediate extension which can be used to prove stronger lower bounds for some functions.
Performance Analysis of 3-Dimensional Turbo Codes
Venue: arXiv cs.IT 2011
Year: 2011

In this work, we consider the minimum distance properties and convergence thresholds of 3-dimensional turbo codes (3D-TCs), recently introduced by Berrou et al.. Here, we consider binary 3D-TCs while the original work of Berrou et al. considered double-binary codes. In the first part of the paper, the minimum distance properties are analyzed from an ensemble perspective, both in the finite-length regime and in the asymptotic case of large block lengths. In particular, we analyze the asymptotic weight distribution of 3D-TCs and show numerically that their typical minimum distance dmin may, depending on the specific parameters, asymptotically grow linearly with the block length, i.e., the 3D-TC ensemble is asymptotically good for some parameters. In the second part of the paper, we derive some useful upper bounds on the dmin when using quadratic permutation polynomial (QPP) interleavers with a quadratic inverse. Furthermore, we give examples of interleaver lengths where an upper bound appears to be tight. The best codes (in terms of estimated dmin) obtained by randomly searching for good pairs of QPPs for use in the 3D-TC are compared to a probabilistic lower bound on the dmin when selecting codes from the 3D-TC ensemble uniformly at random. This comparison shows that the use of designed QPP interleavers can improve the dmin significantly. For instance, we have found a (6144,2040) 3D-TC with an estimated dmin of 147, while the probabilistic lower bound is 69. Higher rates are obtained by puncturing nonsystematic bits, and optimized periodic puncturing patterns for rates 1/2, 2/3, and 4/5 are found by computer search. Finally, we give iterative decoding thresholds, computed from an extrinsic information transfer chart analysis, and present simulation results on the additive white Gaussian noise channel to compare the error rate performance to that of conventional turbo codes.
The MST of Symmetric Disk Graphs (in Arbitrary Metrics) is Light
Venue: arXiv cs.CG 2011
Year: 2011

Consider an n-point metric M = (V,delta), and a transmission range assignment r: V \rightarrow \mathbb R^+ that maps each point v in V to the disk of radius r(v) around it. The {symmetric disk graph} (henceforth, SDG) that corresponds to M and r is the undirected graph over V whose edge set includes an edge (u,v) if both r(u) and r(v) are no smaller than delta(u,v). SDGs are often used to model wireless communication networks. Abu-Affash, Aschner, Carmi and Katz (SWAT 2010, \cite{AACK10}) showed that for any {2-dimensional Euclidean} n-point metric M, the weight of the MST of every {connected} SDG for M is O(log n) w(MST(M)), and that this bound is tight. However, the upper bound proof of \cite{AACK10} relies heavily on basic geometric properties of 2-dimensional Euclidean metrics, and does not extend to higher dimensions. A natural question that arises is whether this surprising upper bound of \cite{AACK10} can be generalized for wider families of metrics, such as 3-dimensional Euclidean metrics. In this paper we generalize the upper bound of Abu-Affash et al. \cite{AACK10} for Euclidean metrics of any dimension. Furthermore, our upper bound extends to {arbitrary metrics} and, in particular, it applies to any of the normed spaces ell_p. Specifically, we demonstrate that for {any} n-point metric M, the weight of the MST of every connected SDG for M is O(log n) w(MST(M)).
The Tower of Hanoi problem on Path_h graphs
Venue: arXiv cs.DM 2011
Year: 2011

The generalized Tower of Hanoi problem with h \ge 4 pegs is known to require a sub-exponentially fast growing number of moves in order to transfer a pile of n disks from one peg to another. In this paper we study the Path_h variant, where the pegs are placed along a line, and disks can be moved from a peg to its nearest neighbor(s) only. Whereas in the simple variant there are h(h-1)/2 possible bi-directional interconnections among pegs, here there are only h-1 of them. Despite the significant reduction in the number of interconnections, the number of moves needed to transfer a pile of n disks between any two pegs also grows sub-exponentially as a function of n. We study these graphs, identify sets of mutually recursive tasks, and obtain a relatively tight upper bound for the number of moves, depending on h, n and the source and destination pegs.
New Worst-Case Upper Bound for #XSAT
Venue: arXiv cs.AI 2011
Year: 2011

An algorithm running in O(1.1995n) is presented for counting models for exact satisfiability formulae(#XSAT). This is faster than the previously best algorithm which runs in O(1.2190n). In order to improve the efficiency of the algorithm, a new principle, i.e. the common literals principle, is addressed to simplify formulae. This allows us to eliminate more common literals. In addition, we firstly inject the resolution principles into solving #XSAT problem, and therefore this further improves the efficiency of the algorithm.
Elementary affine $lambda$-calculus with multithreading and side effects
Venue: arXiv cs.PL 2011
Year: 2011

Linear logic provides a framework to control the complexity of higher-order functional programs. We present an extension of this framework to programs with multithreading and side effects focusing on the case of elementary time. Our main contributions are as follows. First, we provide a new combinatorial proof of termination in elementary time for the functional case. Second, we develop an extension of the approach to a call-by-value $lambda$-calculus with multithreading and side effects. Third, we introduce an elementary affine type system that guarantees the standard subject reduction and progress properties. Finally, we illustrate the programming of iterative functions with side effects in the presented formalism.
Spatially Coupled LDPC Codes for Decode-and-Forward in Erasure Relay Channel
Venue: arXiv cs.IT 2011
Year: 2011

We consider spatially-coupled protograph-based LDPC codes for the three terminal erasure relay channel. It is observed that BP threshold value, the maximal erasure probability of the channel for which decoding error probability converges to zero, of spatially-coupled codes, in particular spatially-coupled MacKay-Neal code, is close to the theoretical limit for the relay channel. Empirical results suggest that spatially-coupled protograph-based LDPC codes have great potential to achieve theoretical limit of a general relay channel.
Fine Synchronization through UWB TH-PPM Impulse Radios
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, a novel fine timing algorithm has been tested and developed to synchronize Ultra-Wideband (UWB) signals with pulse position modulation (PPM). By applying this algorithm, we evaluate timing algorithms in both data-aided (DA) and non-data-aided (NDA) modes. Based on correlation operations, our algorithm remains operational in practical UWB settings. The proposed timing scheme consists of two complementary floors or steps. The first floor consists on a coarse synchronization which is founded on the recently proposed acquisition scheme based on dirty templates (TDT). In the second floor, we investigate a new fine synchronization algorithm which gives an improved estimate of timing offset. Simulations confirm performance improvement of our timing synchronization compared to the original TDT algorithm in terms of mean square error.
On the effect of the path length and transitivity of small-world networks on epidemic dynamics
Venue: arXiv cs.SI 2011
Year: 2011

We show how one can trace in a systematic way the coarse-grained solutions of individual-based stochastic epidemic models evolving on heterogeneous complex networks with respect to their topological characteristics. In particular, we have developed algorithms that allow the tuning of the transitivity (clustering coefficient) and the average mean-path length allowing the investigation of the "pure" impacts of the two characteristics on the emergent behavior of detailed epidemic models. The framework could be used to shed more light into the influence of weak and strong social ties on epidemic spread within small-world network structures, and ultimately to provide novel systematic computational modeling and exploration of better contagion control strategies.
Blind Adaptive Successive Interference Cancellation for Multicarrier DS-CDMA
Venue: arXiv cs.IT 2011
Year: 2011

A new adaptive receiver design for the Multicarrier (MC) DS-CDMA is proposed employing successive interference cancellation (SIC) architecture. One of the main problems limiting the performance of SIC in MC DS-CDMA is the imperfect estimation of multiple access interference (MAI), and hence, the limited frequency diversity gain achieved in multipath fading channels. In this paper, we design a blind adaptive SIC with new multiple access interference suppression capability implemented within despreading process to improve both detection and cancellation processes. Furthermore, dynamic scaling factors derived from the despreader weights are used for interference cancellation process. This method applied on each subcarrier is followed by maximum ratio or equal gain combining to fully exploit the frequency diversity inherent in the multicarrier CDMA systems. It is shown that this way of MAI estimation on individual subcarrier provides significantly improved performance for a MC DS-CDMA system compared to that with conventional matched filter (MF) and SIC techniques at a little added complexity. Performance evaluation under severe nearfar, fading correlation and system loading conditions are carried out to affirm the gain of the proposed adaptive receiver design approach.
Reduction of fuzzy automata by means of fuzzy quasi-orders
Venue: arXiv cs.FL 2011
Year: 2011

In our recent paper we have established close relationships between state reduction of a fuzzy recognizer and resolution of a particular system of fuzzy relation equations. In that paper we have also studied reductions by means of those solutions which are fuzzy equivalences. In this paper we will see that in some cases better reductions can be obtained using the solutions of this system that are fuzzy quasi-orders. Generally, fuzzy quasi-orders and fuzzy equivalences are equally good in the state reduction, but we show that right and left invariant fuzzy quasi-orders give better reductions than right and left invariant fuzzy equivalences. We also show that alternate reductions by means of fuzzy quasi-orders give better results than alternate reductions by means of fuzzy equivalences. Furthermore we study a more general type of fuzzy quasi-orders, weakly right and left invariant ones, and we show that they are closely related to determinization of fuzzy recognizers. We also demonstrate some applications of weakly left invariant fuzzy quasi-orders in conflict analysis of fuzzy discrete event systems.
Summary Based Structures with Improved Sublinear Recovery for Compressed Sensing
Venue: arXiv cs.IT 2011
Year: 2011

We introduce a new class of measurement matrices for compressed sensing, using low order summaries over binary sequences of a given length. We prove recovery guarantees for three reconstruction algorithms using the proposed measurements, including $\ell_1$ minimization and two combinatorial methods. In particular, one of the algorithms recovers $k$-sparse vectors of length $N$ in sublinear time $\text{poly}(k\log{N})$, and requires at most $Ω(k\log{N}\log\log{N})$ measurements. The empirical oversampling constant of the algorithm is significantly better than existing sublinear recovery algorithms such as Chaining Pursuit and Sudocodes. In particular, for $10^3\leq N\leq 10^8$ and $k=100$, the oversampling factor is between 3 to 8. We provide preliminary insight into how the proposed constructions, and the fast recovery scheme can be used in a number of practical applications such as market basket analysis, and real time compressed sensing implementation.
Full Rate Collaborative Diversity Scheme for Multiple Access Fading Channels
Venue: arXiv cs.IT 2011
Year: 2011

User cooperation is a well-known approach to achieve diversity without multiple antennas, however at the cost of inevitable loss of rate mostly due to the need of additional channels for relaying. A new collaborative diversity scheme is proposed here for multiple access fading channels to attain full rate with near maximum diversity. This is achieved by allowing two users and their corresponding relays to transmit/forward data on the same channel by exploiting unique spatial-signatures of their fading channels. The base-station jointly detects the co-channel users' data using maximum-likelihood search algorithm over small set of possible data combinations. Full data rate with significant diversity gain near to two-antenna Alamouti scheme is shown.