OpenRaiser/Intern-Atlas huggingface dataset:
On the Index Coding Problem and its Relation to Network Coding and Matroid Theory
Venue: arXiv cs.IT 2008
Year: 2008

The \emph{index coding} problem has recently attracted a significant attention from the research community due to its theoretical significance and applications in wireless ad-hoc networks. An instance of the index coding problem includes a sender that holds a set of information messages $X=\{x_1,...,x_k\}$ and a set of receivers $R$. Each receiver $ρ=(x,H)\in R$ needs to obtain a message $x\in X$ and has prior \emph{side information} comprising a subset $H$ of $X$. The sender uses a noiseless communication channel to broadcast encoding of messages in $X$ to all clients. The objective is to find an encoding scheme that minimizes the number of transmissions required to satisfy the receivers' demands with \emph{zero error}. In this paper, we analyze the relation between the index coding problem, the more general network coding problem and the problem of finding a linear representation of a matroid. In particular, we show that any instance of the network coding and matroid representation problems can be efficiently reduced to an instance of the index coding problem. Our reduction implies that many important properties of the network coding and matroid representation problems carry over to the index coding problem. Specifically, we show that \emph{vector linear codes} outperform scalar linear codes and that vector linear codes are insufficient for achieving the optimum number of transmissions.
Optimizing Binary Code Produced by Valgrind (Project Report on Virtual Execution Environments Course - AVExe)
Venue: arXiv cs.PL 2008
Year: 2008

Valgrind is a widely used framework for dynamic binary instrumentation and its mostly known by its memcheck tool. Valgrind's code generation module is far from producing optimal code. In addition it has many backends for different CPU architectures, which difficults code optimization in an architecture independent way. Our work focused on identifying sub-optimal code produced by Valgrind and optimizing it.
Errorless Codes for Over-loaded CDMA with Active User Detection
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we introduce a new class of codes for over-loaded synchronous wireless CDMA systems which increases the number of users for a fixed number of chips without introducing any errors. In addition these codes support active user detection. We derive an upper bound on the number of users with a fixed spreading factor. Also we propose an ML decoder for a subclass of these codes that is computationally implementable. Although for our simulations we consider a scenario that is worse than what occurs in practice, simulation results indicate that this coding/decoding scheme is robust against additive noise. As an example, for 64 chips and 88 users we propose a coding/decoding scheme that can obtain an arbitrary small probability of error which is computationally feasible and can detect active users. Furthermore, we prove that for this to be possible the number of users cannot be beyond 230.
Channel and Multiuser Diversities in Wireless Systems: Delay-Energy Tradeoff
Venue: arXiv cs.IT 2008
Year: 2008

We consider a communication system with multi-access fading channel. Each user in the system requires certain rate guarantee. Our main contribution is to devise a scheduling scheme called "Opportunistic Super-position Coding" that satisfies the users' rate requirements. Using mean-field analysis, i.e., when the number of users go to infinity, we analytically show that the energy required to guarantee the required user rate can be made as small as required at the cost of a higher delay ("delay-energy tradeoff"). We explicitly compute the delay under the proposed scheduling policy and discuss how delay differentiation can be achieved. We extend the results to multi-band multi-access channel. Finally, all the results can be generalized in a straightforward fashion to broadcast channel due to the AWGN multiaccess-broadcast duality.
Gaussian Belief Propagation for Solving Systems of Linear Equations: Theory and Application
Venue: arXiv cs.IT 2008
Year: 2008

The canonical problem of solving a system of linear equations arises in numerous contexts in information theory, communication theory, and related fields. In this contribution, we develop a solution based upon Gaussian belief propagation (GaBP) that does not involve direct matrix inversion. The iterative nature of our approach allows for a distributed message-passing implementation of the solution algorithm. We address the properties of the GaBP solver, including convergence, exactness, computational complexity, message-passing efficiency and its relation to classical solution methods. We use numerical examples and applications, like linear detection, to illustrate these properties through the use of computer simulations. This empirical study demonstrates the attractiveness (e.g., faster convergence rate) of the proposed GaBP solver in comparison to conventional linear-algebraic iterative solution methods.
Analyse spectrale des textes: détection automatique des frontières de langue et de discours
Venue: arXiv cs.CL 2008
Year: 2008

We propose a theoretical framework within which information on the vocabulary of a given corpus can be inferred on the basis of statistical information gathered on that corpus. Inferences can be made on the categories of the words in the vocabulary, and on their syntactical properties within particular languages. Based on the same statistical data, it is possible to build matrices of syntagmatic similarity (bigram transition matrices) or paradigmatic similarity (probability for any pair of words to share common contexts). When clustered with respect to their syntagmatic similarity, words tend to group into sublanguage vocabularies, and when clustered with respect to their paradigmatic similarity, into syntactic or semantic classes. Experiments have explored the first of these two possibilities. Their results are interpreted in the frame of a Markov chain modelling of the corpus' generative processe(s): we show that the results of a spectral analysis of the transition matrix can be interpreted as probability distributions of words within clusters. This method yields a soft clustering of the vocabulary into sublanguages which contribute to the generation of heterogeneous corpora. As an application, we show how multilingual texts can be visually segmented into linguistically homogeneous segments. Our method is specifically useful in the case of related languages which happened to be mixed in corpora.
Performance Enhancement of Multiuser Time Reversal UWB Communication System
Venue: arXiv cs.NI 2008
Year: 2008

UWB communication is a recent research area for indoor propagation channels. Time Reversal (TR) communication in UWB has shown promising results for improving the system performance. In multiuser environment, the system performance is significantly degraded due to the interference among different users. TR reduces the interference caused by multiusers due to its spatial focusing property. The performance of a multiuser TR communication system is further improved if the TR filter is modified. In this paper, multiuser TR in UWB communication is investigated using simple TR filter and a modified TR filter with circular shift operation. The concept of circular shift in TR is analytically studied. Thereafter, the channel impulse responses (CIR) of a typical indoor laboratory environment are measured. The measured CIRs are used to analyze the received signal peak power and signal to interference ratio (SIR) with and without performing the circular shift operation in a multiuser environment.
A DCCP Congestion Control Mechanism for Wired- cum-Wireless Environments
Venue: arXiv cs.NI 2008
Year: 2008

Existing transport protocols, be it TCP, SCTP or DCCP, do not provide an efficient congestion control mechanism for heterogeneous wired-cum-wireless networks. Solutions involving implicit loss discrimination schemes have been proposed but were never implemented. Appropriate mechanisms can dramatically improve bandwidth usage over the Internet, especially for multimedia transport based on partial reliability. In this paper we have implemented and evaluated a congestion control mechanism that implicitly discriminates congestion and wireless losses in the datagram congestion control protocol (DCCP) congestion control identification (CCID) framework. The new CCID was implemented as a NS-2 module. Comparisons were made with the TCP-like CCID and showed that the bandwidth utilization was improved by more than 30% and up to 50% in significant setups.
Gaussian Belief Propagation Solver for Systems of Linear Equations
Venue: arXiv cs.IT 2008
Year: 2008

The canonical problem of solving a system of linear equations arises in numerous contexts in information theory, communication theory, and related fields. In this contribution, we develop a solution based upon Gaussian belief propagation (GaBP) that does not involve direct matrix inversion. The iterative nature of our approach allows for a distributed message-passing implementation of the solution algorithm. We also address some properties of the GaBP solver, including convergence, exactness, its max-product version and relation to classical solution methods. The application example of decorrelation in CDMA is used to demonstrate the faster convergence rate of the proposed solver in comparison to conventional linear-algebraic iterative solution methods.
On characterising strong bisimilarity in a fragment of CCS with replication
Venue: arXiv cs.LO 2008
Year: 2008

We provide a characterisation of strong bisimilarity in a fragment of CCS that contains only prefix, parallel composition, synchronisation and a limited form of replication. The characterisation is not an axiomatisation, but is instead presented as a rewriting system. We discuss how our method allows us to derive a new congruence result in the $π$-calculus: congruence holds in the sub-calculus that does not include restriction nor sum, and features a limited form of replication. We have not formalised the latter result in all details.
Initial Offset Placement in p2p Live Streaming Systems
Venue: arXiv cs.MM 2008
Year: 2008

Initial offset placement in p2p streaming systems is studied in this paper. Proportional placement (PP) scheme is proposed. In this scheme, peer places the initial offset as the offset reported by other reference peer with a shift proportional to the buffer width or offset lag of this reference peer. This will introduce a stable placement that supports larger buffer width for peers and small buffer width for tracker. Real deployed placement method in PPLive is studied through measurement. It shows that, instead of based on offset lag, the placement is based on buffer width of the reference peer to facilitate the initial chunk fetching. We will prove that, such a PP scheme may not be stable under arbitrary buffer occupation in the reference peer. The required average buffer width then is derived. A simple good peer selection mechanism to check the buffer occupation of reference peer is proposed for a stable PP scheme based on buffer width
Diversity-Multiplexing Tradeoff of the Half-Duplex Relay Channel
Venue: arXiv cs.IT 2008
Year: 2008

We show that the diversity-multiplexing tradeoff of a half-duplex single-relay channel with identically distributed Rayleigh fading channel gains meets the 2 by 1 MISO bound. We generalize the result to the case when there are N non-interfering relays and show that the diversity-multiplexing tradeoff is equal to the N + 1 by 1 MISO bound.
Asymptotics of Entropy Rate in Special Families of Hidden Markov Chains
Venue: arXiv cs.IT 2008
Year: 2008

We derive an asymptotic formula for entropy rate of a hidden Markov chain around a "weak Black Hole". We also discuss applications of the asymptotic formula to the asymptotic behaviors of certain channels.
Multipath Channels of Unbounded Capacity
Venue: arXiv cs.IT 2008
Year: 2008

The capacity of discrete-time, noncoherent, multipath fading channels is considered. It is shown that if the variances of the path gains decay faster than exponentially, then capacity is unbounded in the transmit power.
On Outage and Error Rate Analysis of the Ordered V-BLAST
Venue: arXiv cs.IT 2008
Year: 2008

Outage and error rate performance of the ordered BLAST with more than 2 transmit antennas is evaluated for i.i.d. Rayleigh fading channels. A number of lower and upper bounds on the 1st step outage probability at any SNR are derived, which are further used to obtain accurate approximations to average block and total error rates. For m Tx antennas, the effect of the optimal ordering at the first step is an m-fold SNR gain. As m increases to infinity, the BLER decreases to zero, which is a manifestation of the space-time autocoding effect in the V-BLAST. While the sub-optimal ordering (based on the before-projection SNR) suffers a few dB SNR penalty compared to the optimal one, it has a lower computational complexity and a 3 dB SNR gain compared to the unordered V-BLAST and can be an attractive solution for low-complexity/low-energy systems. Uncoded D-BLAST exhibits the same outage and error rate performance as that of the V-BLAST. An SNR penalty of the linear receiver interfaces compared to the BLAST is also evaluated.
Interference Channels with Correlated Receiver Side Information
Venue: arXiv cs.IT 2008
Year: 2008

The problem of joint source-channel coding in transmitting independent sources over interference channels with correlated receiver side information is studied. When each receiver has side information correlated with its own desired source, it is shown that source-channel code separation is optimal. When each receiver has side information correlated with the interfering source, sufficient conditions for reliable transmission are provided based on a joint source-channel coding scheme using the superposition encoding and partial decoding idea of Han and Kobayashi. When the receiver side information is a deterministic function of the interfering source, source-channel code separation is again shown to be optimal. As a special case, for a class of Z-interference channels, when the side information of the receiver facing interference is a deterministic function of the interfering source, necessary and sufficient conditions for reliable transmission are provided in the form of single letter expressions. As a byproduct of these joint source-channel coding results, the capacity region of a class of Z-channels with degraded message sets is also provided.
Efficient Pattern Matching on Binary Strings
Venue: arXiv cs.DS 2008
Year: 2008

The binary string matching problem consists in finding all the occurrences of a pattern in a text where both strings are built on a binary alphabet. This is an interesting problem in computer science, since binary data are omnipresent in telecom and computer network applications. Moreover the problem finds applications also in the field of image processing and in pattern matching on compressed texts. Recently it has been shown that adaptations of classical exact string matching algorithms are not very efficient on binary data. In this paper we present two efficient algorithms for the problem adapted to completely avoid any reference to bits allowing to process pattern and text byte by byte. Experimental results show that the new algorithms outperform existing solutions in most cases.
Dynamic assignment: there is an equilibrium !
Venue: arXiv cs.GT 2008
Year: 2008

Given a network with a continuum of users at some origins, suppose that the users wish to reach specific destinations, but that they are not indifferent to the time needed to reach their destination. They may have several possibilities (of routes or deparure time), but their choices modify the travel times on the network. Hence, each user faces the following problem: given a pattern of travel times for the different possible routes that reach the destination, find a shortest path. The situation in a context of perfect information is a so-called Nash equilibrium, and the question whether there is such an equilibrium and of finding it if it exists is the so-called equilibrium assignment problem. It arises for various kind of networks, such as computers, communication or transportation network. When each user occupies permanently the whole route from the origin to its destination, we call it the static assignment problem, which has been extensively studied with pioneers works by Wardrop or Beckmann. A less studied, but more realistic, and maybe more difficult, problem is when the time needed to reach an arc is taken into account. We speak then of a dynamic assignment problem. Several models have been proposed. For some of them, the existence of an equilibrium has been proved, but always under some technical assumptions or in a very special case (a network with one arc for the case when the users may chose their departure time). The present paper proposes a compact model, with minimal and natural assumptions. For this model, we prove that there is always an equilibrium. To our knowledge, this imply all previous results about existence of an equilibrium for the dynamic assignment problem.
Sheaves and geometric logic and applications to the modular verification of complex systems
Venue: arXiv cs.LO 2008
Year: 2008

In this paper we show that states, transitions and behavior of concurrent systems can often be modeled as sheaves over a suitable topological space. In this context, geometric logic can be used to describe which local properties (i.e. properties of individual systems) are preserved, at a global level, when interconnecting the systems. The main area of application is to modular verification of complex systems. We illustrate the ideas by means of an example involving a family of interacting controllers for trains on a rail track.
Text as Statistical Mechanics Object
Venue: arXiv cs.CL 2008
Year: 2008

In this article we present a model of human written text based on statistical mechanics approach by deriving the potential energy for different parts of the text using large text corpus. We have checked the results numerically and found that the specific heat parameter effectively separates the closed class words from the specific terms used in the text.
Efficient Algorithms and Routing Protocols for Handling Transient Single Node Failures
Venue: arXiv cs.DS 2008
Year: 2008

Single node failures represent more than 85% of all node failures in the today's large communication networks such as the Internet. Also, these node failures are usually transient. Consequently, having the routing paths globally recomputed does not pay off since the failed nodes recover fairly quickly, and the recomputed routing paths need to be discarded. Instead, we develop algorithms and protocols for dealing with such transient single node failures by suppressing the failure (instead of advertising it across the network), and routing messages to the destination via alternate paths that do not use the failed node. We compare our solution to that of Ref. [11] wherein the authors have presented a "Failure Insensitive Routing" protocol as a proactive recovery scheme for handling transient node failures. We show that our algorithms are faster by an order of magnitude while our paths are equally good. We show via simulation results that our paths are usually within 15% of the optimal for randomly generated graph with 100-1000 nodes.
The Connectivity of NK Landscapes' Basins: A Network Analysis
Venue: arXiv cs.NE 2008
Year: 2008

We propose a network characterization of combinatorial fitness landscapes by adapting the notion of inherent networks proposed for energy surfaces. We use the well-known family of NK landscapes as an example. In our case the inherent network is the graph where the vertices represent the local maxima in the landscape, and the edges account for the transition probabilities between their corresponding basins of attraction. We exhaustively extracted such networks on representative small NK landscape instances, and performed a statistical characterization of their properties. We found that most of these network properties can be related to the search difficulty on the underlying NK landscapes with varying values of K.
The use of entropy to measure structural diversity
Venue: arXiv cs.LG 2008
Year: 2008

In this paper entropy based methods are compared and used to measure structural diversity of an ensemble of 21 classifiers. This measure is mostly applied in ecology, whereby species counts are used as a measure of diversity. The measures used were Shannon entropy, Simpsons and the Berger Parker diversity indexes. As the diversity indexes increased so did the accuracy of the ensemble. An ensemble dominated by classifiers with the same structure produced poor accuracy. Uncertainty rule from information theory was also used to further define diversity. Genetic algorithms were used to find the optimal ensemble by using the diversity indices as the cost function. The method of voting was used to aggregate the decisions.
Comments on the Boundary of the Capacity Region of Multiaccess Fading Channels
Venue: arXiv cs.IT 2008
Year: 2008

A modification is proposed for the formula known from the literature that characterizes the boundary of the capacity region of Gaussian multiaccess fading channels. The modified version takes into account potentially negative arguments of the cumulated density function that would affect the accuracy of the numerical capacity results.
Relationship between Diversity and Perfomance of Multiple Classifiers for Decision Support
Venue: arXiv cs.AI 2008
Year: 2008

The paper presents the investigation and implementation of the relationship between diversity and the performance of multiple classifiers on classification accuracy. The study is critical as to build classifiers that are strong and can generalize better. The parameters of the neural network within the committee were varied to induce diversity; hence structural diversity is the focus for this study. The hidden nodes and the activation function are the parameters that were varied. The diversity measures that were adopted from ecology such as Shannon and Simpson were used to quantify diversity. Genetic algorithm is used to find the optimal ensemble by using the accuracy as the cost function. The results observed shows that there is a relationship between structural diversity and accuracy. It is observed that the classification accuracy of an ensemble increases as the diversity increases. There was an increase of 3%-6% in the classification accuracy.
Capacity of Steganographic Channels
Venue: arXiv cs.CR 2008
Year: 2008

This work investigates a central problem in steganography, that is: How much data can safely be hidden without being detected? To answer this question, a formal definition of steganographic capacity is presented. Once this has been defined, a general formula for the capacity is developed. The formula is applicable to a very broad spectrum of channels due to the use of an information-spectrum approach. This approach allows for the analysis of arbitrary steganalyzers as well as non-stationary, non-ergodic encoder and attack channels. After the general formula is presented, various simplifications are applied to gain insight into example hiding and detection methodologies. Finally, the context and applications of the work are summarized in a general discussion.