OpenRaiser/Intern-Atlas huggingface dataset:
Coding for Two-User SISO and MIMO Multiple Access Channels
Venue: arXiv cs.IT 2009
Year: 2009

Constellation Constrained (CC) capacity regions of a two-user SISO Gaussian Multiple Access Channel (GMAC) with finite complex input alphabets and continuous output are computed in this paper. When both the users employ the same code alphabet, it is well known that an appropriate rotation between the alphabets provides unique decodability to the receiver. For such a set-up, a metric is proposed to compute the angle(s) of rotation between the alphabets such that the CC capacity region is maximally enlarged. Subsequently, code pairs based on Trellis Coded Modulation (TCM) are designed for the two-user GMAC with $M$-PSK and $M$-PAM alphabet pairs for arbitrary values of $M$ and it is proved that, for certain angles of rotation, Ungerboeck labelling on the trellis of each user maximizes the guaranteed squared Euclidean distance of the \textit{sum trellis}. Hence, such a labelling scheme can be used systematically to construct trellis code pairs for a two-user GMAC to achieve sum rates close to the sum capacity of the channel. More importantly, it is shown for the first time that ML decoding complexity at the destination is significantly reduced when $M$-PAM alphabet pairs are employed with \textit{almost} no loss in the sum capacity. \indent A two-user Multiple Input Multiple Output (MIMO) fading MAC with $N_{t}$ antennas at both the users and a single antenna at the destination has also been considered with the assumption that the destination has the perfect knowledge of channel state information and the two users have the perfect knowledge of only the phase components of their channels. For such a set-up, two distinct classes of Space Time Block Code (STBC) pairs derived from the well known class of real orthogonal designs are proposed such that the STBC pairs are information lossless and have low ML decoding complexity.
An Algorithm for File Transfer Scheduling in Grid Environments
Venue: arXiv cs.NI 2009
Year: 2009

This paper addresses the data transfer scheduling problem for Grid environments, presenting a centralized scheduler developed with dynamic and adaptive features. The algorithm offers a reservation system for user transfer requests that allocates them transfer times and bandwidth, according to the network topology and the constraints the user specified for the requests. This paper presents the projects related to the data transfer field, the design of the framework for which the scheduler was built, the main features of the scheduler, the steps for transfer requests rescheduling and two tests that illustrate the system's behavior for different types of transfer requests.
Design of a P System based Artificial Graph Chemistry
Venue: arXiv cs.NE 2009
Year: 2009

Artificial Chemistries (ACs) are symbolic chemical metaphors for the exploration of Artificial Life, with specific focus on the origin of life. In this work we define a P system based artificial graph chemistry to understand the principles leading to the evolution of life-like structures in an AC set up and to develop a unified framework to characterize and classify symbolic artificial chemistries by devising appropriate formalism to capture semantic and organizational information. An extension of P system is considered by associating probabilities with the rules providing the topological framework for the evolution of a labeled undirected graph based molecular reaction semantics.
A Step Forward in Studying the Compact Genetic Algorithm
Venue: arXiv cs.NE 2009
Year: 2009

The compact Genetic Algorithm (cGA) is an Estimation of Distribution Algorithm that generates offspring population according to the estimated probabilistic model of the parent population instead of using traditional recombination and mutation operators. The cGA only needs a small amount of memory; therefore, it may be quite useful in memory-constrained applications. This paper introduces a theoretical framework for studying the cGA from the convergence point of view in which, we model the cGA by a Markov process and approximate its behavior using an Ordinary Differential Equation (ODE). Then, we prove that the corresponding ODE converges to local optima and stays there. Consequently, we conclude that the cGA will converge to the local optima of the function to be optimized.
A Theoretical Analysis of Joint Manifolds
Venue: arXiv cs.LG 2009
Year: 2009

The emergence of low-cost sensor architectures for diverse modalities has made it possible to deploy sensor arrays that capture a single event from a large number of vantage points and using multiple modalities. In many scenarios, these sensors acquire very high-dimensional data such as audio signals, images, and video. To cope with such high-dimensional data, we typically rely on low-dimensional models. Manifold models provide a particularly powerful model that captures the structure of high-dimensional data when it is governed by a low-dimensional set of parameters. However, these models do not typically take into account dependencies among multiple sensors. We thus propose a new joint manifold framework for data ensembles that exploits such dependencies. We show that simple algorithms can exploit the joint manifold structure to improve their performance on standard signal processing applications. Additionally, recent results concerning dimensionality reduction for manifolds enable us to formulate a network-scalable data compression scheme that uses random projections of the sensed data. This scheme efficiently fuses the data from all sensors through the addition of such projections, regardless of the data modalities and dimensions.
A Characterization of Max-Min SIR-Balanced Power Allocation with Applications
Venue: arXiv cs.IT 2009
Year: 2009

We consider a power-controlled wireless network with an established network topology in which the communication links (transmitter-receiver pairs) are corrupted by the co-channel interference and background noise. We have fairly general power constraints since the vector of transmit powers is confined to belong to an arbitrary convex polytope. The interference is completely determined by a so-called gain matrix. Assuming irreducibility of this gain matrix, we provide an elegant characterization of the max-min SIR-balanced power allocation under such general power constraints. This characterization gives rise to two types of algorithms for computing the max-min SIR-balanced power allocation. One of the algorithms is a utility-based power control algorithm to maximize a weighted sum of the utilities of the link SIRs. Our results show how to choose the weight vector and utility function so that the utility-based solution is equal to the solution of the max-min SIR-balancing problem. The algorithm is not amenable to distributed implementation as the weights are global variables. In order to mitigate the problem of computing the weight vector in distributed wireless networks, we point out a saddle point characterization of the Perron root of some extended gain matrices and discuss how this characterization can be used in the design of algorithms in which each link iteratively updates its weight vector in parallel to the power control recursion. Finally, the paper provides a basis for the development of distributed power control and beamforming algorithms to find a global solution of the max-min SIR-balancing problem.
Developments in ROOT I/O and trees
Venue: arXiv cs.OH 2009
Year: 2009

For the last several months the main focus of development in the ROOT I/O package has been code consolidation and performance improvements. Access to remote files is affected both by bandwidth and latency. We introduced a pre-fetch mechanism to minimize the number of transactions between client and server and hence reducing the effect of latency. We will review the implementation and how well it works in different conditions (gain of an order of magnitude for remote file access). We will also review new utilities, including a faster implementation of TTree cloning (gain of an order of magnitude), a generic mechanism for object references, and a new entry list mechanism tuned both for small and large number of selections. In addition to reducing the coupling with the core module and becoming its owns library (libRIO) (as part of the general restructuration of the ROOT libraries), the I/O package has been enhanced in the area of XML and SQL support, thread safety, schema evolution, TTreeFormula, and many other areas. We will also discuss various ways, ROOT will be able to benefit from multi-core architecture to improve I/O performances.
A High Dynamic Range 3-Moduli-Set with Efficient Reverse Converter
Venue: arXiv cs.AR 2009
Year: 2009

-Residue Number System (RNS) is a valuable tool for fast and parallel arithmetic. It has a wide application in digital signal processing, fault tolerant systems, etc. In this work, we introduce the 3-moduli set {2^n, 2^{2n}-1, 2^{2n}+1} and propose its residue to binary converter using the Chinese Remainder Theorem. We present its simple hardware implementation that mainly includes one Carry Save Adder (CSA) and a Modular Adder (MA). We compare the performance and area utilization of our reverse converter to the reverse converters of the moduli sets {2^n-1, 2^n, 2^n+1, 2^{2n}+1} and {2^n-1, 2^n, 2^n+1, 2^n-2^{(n+1)/2}+1, 2^n+2^{(n+1)/2}+1} that have the same dynamic range and we demonstrate that our architecture is better in terms of performance and area utilization. Also, we show that our reverse converter is faster than the reverse converter of {2^n-1, 2^n, 2^n+1} for dynamic ranges like 8-bit, 16-bit, 32-bit and 64-bit however it requires more area.
On Profit-Maximizing Pricing for the Highway and Tollbooth Problems
Venue: arXiv cs.DS 2009
Year: 2009

In the \emph{tollbooth problem}, we are given a tree $\bT=(V,E)$ with $n$ edges, and a set of $m$ customers, each of whom is interested in purchasing a path on the tree. Each customer has a fixed budget, and the objective is to price the edges of $\bT$ such that the total revenue made by selling the paths to the customers that can afford them is maximized. An important special case of this problem, known as the \emph{highway problem}, is when $\bT$ is restricted to be a line. For the tollbooth problem, we present a randomized $O(\log n)$-approximation, improving on the current best $O(\log m)$-approximation. We also study a special case of the tollbooth problem, when all the paths that customers are interested in purchasing go towards a fixed root of $\bT$. In this case, we present an algorithm that returns a $(1-ε)$-approximation, for any $ε> 0$, and runs in quasi-polynomial time. On the other hand, we rule out the existence of an FPTAS by showing that even for the line case, the problem is strongly NP-hard. Finally, we show that in the \emph{coupon model}, when we allow some items to be priced below zero to improve the overall profit, the problem becomes even APX-hard.
Folded Algebraic Geometric Codes From Galois Extensions
Venue: arXiv cs.IT 2009
Year: 2009

We describe a new class of list decodable codes based on Galois extensions of function fields and present a list decoding algorithm. These codes are obtained as a result of folding the set of rational places of a function field using certain elements (automorphisms) from the Galois group of the extension. This work is an extension of Folded Reed Solomon codes to the setting of Algebraic Geometric codes. We describe two constructions based on this framework depending on if the order of the automorphism used to fold the code is large or small compared to the block length. When the automorphism is of large order, the codes have polynomially bounded list size in the worst case. This construction gives codes of rate $R$ over an alphabet of size independent of block length that can correct a fraction of $1-R-ε$ errors subject to the existence of asymptotically good towers of function fields with large automorphisms. The second construction addresses the case when the order of the element used to fold is small compared to the block length. In this case a heuristic analysis shows that for a random received word, the expected list size and the running time of the decoding algorithm are bounded by a polynomial in the block length. When applied to the Garcia-Stichtenoth tower, this yields codes of rate $R$ over an alphabet of size $(\frac{1}{ε^2})^{O(\frac{1}ε)}$, that can correct a fraction of $1-R-ε$ errors.
Logical Algorithms meets CHR: A meta-complexity result for Constraint Handling Rules with rule priorities
Venue: arXiv cs.PL 2009
Year: 2009

This paper investigates the relationship between the Logical Algorithms language (LA) of Ganzinger and McAllester and Constraint Handling Rules (CHR). We present a translation schema from LA to CHR-rp: CHR with rule priorities, and show that the meta-complexity theorem for LA can be applied to a subset of CHR-rp via inverse translation. Inspired by the high-level implementation proposal for Logical Algorithm by Ganzinger and McAllester and based on a new scheduling algorithm, we propose an alternative implementation for CHR-rp that gives strong complexity guarantees and results in a new and accurate meta-complexity theorem for CHR-rp. It is furthermore shown that the translation from Logical Algorithms to CHR-rp combined with the new CHR-rp implementation, satisfies the required complexity for the Logical Algorithms meta-complexity result to hold.
An Internet-based Audience Response System for the Improvement of Teaching
Venue: arXiv cs.CY 2009
Year: 2009

We have developed an Internet-based audience response system (called ARSBO). In this way we combine the advantages of common audience response systems using handheld devices and the easy and cheap access to the Internet. Evaluations of audience response systems in the literature have shown their success: encouraging participation of the students as well as immediate feedback to answers to the whole group for evaluational purposes of the teacher. However, commercial systems are relatively expensive and the number of students in such a teaching-learning scenario is limited. ARSBO solves these problems. Using the Internet (e.g. in computer rooms or by wireless Internet access) there are no special costs and the number of participating students is not limited. ARSBO is very easy to use for students as well as for the construction of new questions with possible answers and for the visualization of statistical results to questions.
Bitslicing and the Method of Four Russians Over Larger Finite Fields
Venue: arXiv cs.MS 2009
Year: 2009

We present a method of computing with matrices over very small finite fields of size larger than 2. Specifically, we show how the Method of Four Russians can be efficiently adapted to these larger fields, and introduce a row-wise matrix compression scheme that both reduces memory requirements and allows one to vectorize element operations. We also present timings which confirm the efficiency of these methods and exceed the speed of the fastest implementations the authors are aware of.
An Online Multi-unit Auction with Improved Competitive Ratio
Venue: arXiv cs.GT 2009
Year: 2009

We improve the best known competitive ratio (from 1/4 to 1/2), for the online multi-unit allocation problem, where the objective is to maximize the single-price revenue. Moreover, the competitive ratio of our algorithm tends to 1, as the bid-profile tends to ``smoothen''. This algorithm is used as a subroutine in designing truthful auctions for the same setting: the allocation has to be done online, while the payments can be decided at the end of the day. Earlier, a reduction from the auction design problem to the allocation problem was known only for the unit-demand case. We give a reduction for the general case when the bidders have decreasing marginal utilities. The problem is inspired by sponsored search auctions.
A Fully Equivalent Global Pressure Formulation for Three-Phase Compressible Flow
Venue: arXiv cs.NA 2009
Year: 2009

We introduce a new global pressure formulation for immiscible three-phase compressible flows in porous media which is fully equivalent to the original equations, unlike the one introduced in \cite{CJ86}. In this formulation, the total volumetric flow of the three fluids and the global pressure follow a classical Darcy law, which simplifies the resolution of the pressure equation. However, this global pressure formulation exists only for Total Differential (TD) three-phase data, which depend only on two functions of saturations and global pressure: the global capillary pressure and the global mobility. Hence we introduce a class of interpolation which constructs such TD-three-phase data from any set of three two-phase data (for each pair of fluids) which satisfy a TD-compatibility condition.
New Bounds for Binary and Ternary Overloaded CDMA
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we study binary and ternary matrices that are used for CDMA applications that are injective on binary or ternary user vectors. In other words, in the absence of additive noise, the interference of overloaded CDMA can be removed completely. Some new algorithms are proposed for constructing such matrices. Also, using an information theoretic approach, we conjecture the extent to which such CDMA matrix codes exist. For overloaded case, we also show that some of the codes derived from our algorithms perform better than the binary Welch Bound Equality codes; the decoding is ML but of low complexity.
A statistical mechanical interpretation of instantaneous codes
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we develop a statistical mechanical interpretation of the noiseless source coding scheme based on an absolutely optimal instantaneous code. The notions in statistical mechanics such as statistical mechanical entropy, temperature, and thermal equilibrium are translated into the context of noiseless source coding. Especially, it is discovered that the temperature 1 corresponds to the average codeword length of an instantaneous code in this statistical mechanical interpretation of noiseless source coding scheme. This correspondence is also verified by the investigation using box-counting dimension. Using the notion of temperature and statistical mechanical arguments, some information-theoretic relations can be derived in the manner which appeals to intuition.
A Channel Coding Perspective of Recommendation Systems
Venue: arXiv cs.IT 2009
Year: 2009

Motivated by recommendation systems, we consider the problem of estimating block constant binary matrices (of size $m \times n$) from sparse and noisy observations. The observations are obtained from the underlying block constant matrix after unknown row and column permutations, erasures, and errors. We derive upper and lower bounds on the achievable probability of error. For fixed erasure and error probability, we show that there exists a constant $C_1$ such that if the cluster sizes are less than $C_1 \ln(mn)$, then for any algorithm the probability of error approaches one as $m, n \tends \infty$. On the other hand, we show that a simple polynomial time algorithm gives probability of error diminishing to zero provided the cluster sizes are greater than $C_2 \ln(mn)$ for a suitable constant $C_2$.
Towards Optimal Range Medians
Venue: arXiv cs.DS 2009
Year: 2009

We consider the following problem: given an unsorted array of $n$ elements, and a sequence of intervals in the array, compute the median in each of the subarrays defined by the intervals. We describe a simple algorithm which uses O(n) space and needs $O(n\log k + k\log n)$ time to answer the first $k$ queries. This improves previous algorithms by a logarithmic factor and matches a lower bound for $k=O(n)$. Since the algorithm decomposes the range of element values rather than the array, it has natural generalizations to higher dimensional problems -- it reduces a range median query to a logarithmic number of range counting queries.
Optimal Detector for Channels with Non-Gaussian Interference
Venue: arXiv cs.IT 2009
Year: 2009

The detection problem in the Gaussian interference channel is addressed, when transmitters employ non-Gaussian schemes designed for the single-user Gaussian channel. A structure consisting of a separate symbol-by-symbol detector and a hard decoder is considered. Given this structure, an optimal detector is presented that is compared to an interferenceunaware conventional detector, an interference-aware successive interference cancellation (SIC) detector, and a minimum-distance detector. It is demonstrated analytically and by simulation that the optimal detector outperforms both the conventional and the SIC detector, and that it attains decreasing symbol error rates even in the presence of strong interference. Moreover, the minimum-distance detector performs almost as well as the optimal detector in most scenarios and is significantly less complex.
Notes on Reed-Muller Codes
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we consider the Reed-Muller (RM) codes. For the first order RM code, we prove that it is unique in the sense that any linear code with the same length, dimension and minimum distance must be the first order RM code; For the second order RM code, we give a constructive linear sub-code family for the case when m is even. This is an extension of Corollary 17 of Ch. 15 in the coding book by MacWilliams and Sloane. Furthermore, we show that the specified sub-codes of length <= 256 have minimum distance equal to the upper bound or the best known lower bound for all linear codes of the same length and dimension. As another interesting result, we derive an additive commutative group of the symplectic matrices with full rank.
Efficient reconciliation protocol for discrete-variable quantum key distribution
Venue: arXiv cs.IT 2009
Year: 2009

Reconciliation is an essential part of any secret-key agreement protocol and hence of a Quantum Key Distribution (QKD) protocol, where two legitimate parties are given correlated data and want to agree on a common string in the presence of an adversary, while revealing a minimum amount of information. In this paper, we show that for discrete-variable QKD protocols, this problem can be advantageously solved with Low Density Parity Check (LDPC) codes optimized for the BSC. In particular, we demonstrate that our method leads to a significant improvement of the achievable secret key rate, with respect to earlier interactive reconciliation methods used in QKD.
Analysis of Uncoordinated Opportunistic Two-Hop Wireless Ad Hoc Systems
Venue: arXiv cs.IT 2009
Year: 2009

We consider a time-slotted two-hop wireless system in which the sources transmit to the relays in the even time slots (first hop) and the relays forward the packets to the destinations in the odd time slots (second hop). Each source may connect to multiple relays in the first hop. In the presence of interference and without tight coordination of the relays, it is not clear which relays should transmit the packet. We propose four decentralized methods of relay selection, some based on location information and others based on the received signal strength (RSS). We provide a complete analytical characterization of these methods using tools from stochastic geometry. We use simulation results to compare these methods in terms of end-to-end success probability.