OpenRaiser/Intern-Atlas huggingface dataset:
The Re-Encoding Transformation in Algebraic List-Decoding of Reed-Solomon Codes
Venue: arXiv cs.IT 2010
Year: 2010

The main computational steps in algebraic soft-decoding, as well as Sudan-type list-decoding, of Reed-Solomon codes are bivariate polynomial interpolation and factorization. We introduce a computational technique, based upon re-encoding and coordinate transformation, that significantly reduces the complexity of the bivariate interpolation procedure. This re-encoding and coordinate transformation converts the original interpolation problem into another reduced interpolation problem, which is orders of magnitude smaller than the original one. A rigorous proof is presented to show that the two interpolation problems are indeed equivalent. An efficient factorization procedure that applies directly to the reduced interpolation problem is also given.
The Complexity of Reasoning for Fragments of Autoepistemic Logic
Venue: arXiv cs.LO 2010
Year: 2010

Autoepistemic logic extends propositional logic by the modal operator L. A formula that is preceded by an L is said to be "believed". The logic was introduced by Moore 1985 for modeling an ideally rational agent's behavior and reasoning about his own beliefs. In this paper we analyze all Boolean fragments of autoepistemic logic with respect to the computational complexity of the three most common decision problems expansion existence, brave reasoning and cautious reasoning. As a second contribution we classify the computational complexity of counting the number of stable expansions of a given knowledge base. To the best of our knowledge this is the first paper analyzing the counting problem for autoepistemic logic.
Improved compression of network coding vectors using erasure decoding and list decoding
Venue: arXiv cs.IT 2010
Year: 2010

Practical random network coding based schemes for multicast include a header in each packet that records the transformation between the sources and the terminal. The header introduces an overhead that can be significant in certain scenarios. In previous work, parity check matrices of error control codes along with error decoding were used to reduce this overhead. In this work we propose novel packet formats that allow us to use erasure decoding and list decoding. Both schemes have a smaller overhead compared to the error decoding based scheme, when the number of sources combined in a packet is not too small.
The Limits of Error Correction with lp Decoding
Venue: arXiv cs.IT 2010
Year: 2010

An unknown vector f in R^n can be recovered from corrupted measurements y = Af + e where A^(m*n)(m>n) is the coding matrix if the unknown error vector e is sparse. We investigate the relationship of the fraction of errors and the recovering ability of lp-minimization (0 < p <= 1) which returns a vector x minimizing the "lp-norm" of y - Ax. We give sharp thresholds of the fraction of errors that determine the successful recovery of f. If e is an arbitrary unknown vector, the threshold strictly decreases from 0.5 to 0.239 as p increases from 0 to 1. If e has fixed support and fixed signs on the support, the threshold is 2/3 for all p in (0, 1), while the threshold is 1 for l1-minimization.
On the stable recovery of the sparsest overcomplete representations in presence of noise
Venue: arXiv cs.IT 2010
Year: 2010

Let x be a signal to be sparsely decomposed over a redundant dictionary A, i.e., a sparse coefficient vector s has to be found such that x=As. It is known that this problem is inherently unstable against noise, and to overcome this instability, the authors of [Stable Recovery; Donoho et.al., 2006] have proposed to use an "approximate" decomposition, that is, a decomposition satisfying ||x - A s|| < δ, rather than satisfying the exact equality x = As. Then, they have shown that if there is a decomposition with ||s||_0 < (1+M^{-1})/2, where M denotes the coherence of the dictionary, this decomposition would be stable against noise. On the other hand, it is known that a sparse decomposition with ||s||_0 < spark(A)/2 is unique. In other words, although a decomposition with ||s||_0 < spark(A)/2 is unique, its stability against noise has been proved only for highly more restrictive decompositions satisfying ||s||_0 < (1+M^{-1})/2, because usually (1+M^{-1})/2 << spark(A)/2. This limitation maybe had not been very important before, because ||s||_0 < (1+M^{-1})/2 is also the bound which guaranties that the sparse decomposition can be found via minimizing the L1 norm, a classic approach for sparse decomposition. However, with the availability of new algorithms for sparse decomposition, namely SL0 and Robust-SL0, it would be important to know whether or not unique sparse decompositions with (1+M^{-1})/2 < ||s||_0 < spark(A)/2 are stable. In this paper, we show that such decompositions are indeed stable. In other words, we extend the stability bound from ||s||_0 < (1+M^{-1})/2 to the whole uniqueness range ||s||_0 < spark(A)/2. In summary, we show that "all unique sparse decompositions are stably recoverable". Moreover, we see that sparser decompositions are "more stable".
Brain-Like Stochastic Search: A Research Challenge and Funding Opportunity
Venue: arXiv cs.AI 2010
Year: 2010

Brain-Like Stochastic Search (BLiSS) refers to this task: given a family of utility functions U(u,A), where u is a vector of parameters or task descriptors, maximize or minimize U with respect to u, using networks (Option Nets) which input A and learn to generate good options u stochastically. This paper discusses why this is crucial to brain-like intelligence (an area funded by NSF) and to many applications, and discusses various possibilities for network design and training. The appendix discusses recent research, relations to work on stochastic optimization in operations research, and relations to engineering-based approaches to understanding neocortex.
A Smart Approach for GPT Cryptosystem Based on Rank Codes
Venue: arXiv cs.IT 2010
Year: 2010

The concept of Public- key cryptosystem was innovated by McEliece's cryptosystem. The public key cryptosystem based on rank codes was presented in 1991 by Gabidulin -Paramonov-Trejtakov(GPT). The use of rank codes in cryptographic applications is advantageous since it is practically impossible to utilize combinatoric decoding. This has enabled using public keys of a smaller size. Respective structural attacks against this system were proposed by Gibson and recently by Overbeck. Overbeck's attacks break many versions of the GPT cryptosystem and are turned out to be either polynomial or exponential depending on parameters of the cryptosystem. In this paper, we introduce a new approach, called the Smart approach, which is based on a proper choice of the distortion matrix X. The Smart approach allows for withstanding all known attacks even if the column scrambler matrix P over the base field Fq.
Controlled non uniform random generation of decomposable structures
Venue: arXiv cs.DM 2010
Year: 2010

Consider a class of decomposable combinatorial structures, using different types of atoms $\Atoms = \{\At_1,\ldots ,\At_{|{\Atoms}|}\}$. We address the random generation of such structures with respect to a size $n$ and a targeted distribution in $k$ of its \emph{distinguished} atoms. We consider two variations on this problem. In the first alternative, the targeted distribution is given by $k$ real numbers $\TargFreq_1, \ldots, \TargFreq_k$ such that $0 < \TargFreq_i < 1$ for all $i$ and $\TargFreq_1+\cdots+\TargFreq_k \leq 1$. We aim to generate random structures among the whole set of structures of a given size $n$, in such a way that the {\em expected} frequency of any distinguished atom $\At_i$ equals $\TargFreq_i$. We address this problem by weighting the atoms with a $k$-tuple $\Weights$ of real-valued weights, inducing a weighted distribution over the set of structures of size $n$. We first adapt the classical recursive random generation scheme into an algorithm taking $\bigO{n^{1+o(1)}+mn\log{n}}$ arithmetic operations to draw $m$ structures from the $\Weights$-weighted distribution. Secondly, we address the analytical computation of weights such that the targeted frequencies are achieved asymptotically, i. e. for large values of $n$. We derive systems of functional equations whose resolution gives an explicit relationship between $\Weights$ and $\TargFreq_1, \ldots, \TargFreq_k$. Lastly, we give an algorithm in $\bigO{k n^4}$ for the inverse problem, {\it i.e.} computing the frequencies associated with a given $k$-tuple $\Weights$ of weights, and an optimized version in $\bigO{k n^2}$ in the case of context-free languages. This allows for a heuristic resolution of the weights/frequencies relationship suitable for complex specifications. In the second alternative, the targeted distribution is given by a $k$ natural numbers $n_1, \ldots, n_k$ such that $n_1+\cdots+n_k+r=n$ where $r \geq 0$ is the number of undistinguished atoms. The structures must be generated uniformly among the set of structures of size $n$ that contain {\em exactly} $n_i$ atoms $\At_i$ ($1 \leq i \leq k$). We give a $\bigO{r^2\prod_{i=1}^k n_i^2 +m n k \log n}$ algorithm for generating $m$ structures, which simplifies into a $\bigO{r\prod_{i=1}^k n_i +m n}$ for regular specifications.
Capacity scaling law by multiuser diversity in cognitive radio systems
Venue: arXiv cs.IT 2010
Year: 2010

This paper analyzes the multiuser diversity gain in a cognitive radio (CR) system where secondary transmitters opportunistically utilize the spectrum licensed to primary users only when it is not occupied by the primary users. To protect the primary users from the interference caused by the missed detection of primary transmissions in the secondary network, minimum average throughput of the primary network is guaranteed by transmit power control at the secondary transmitters. The traffic dynamics of a primary network are also considered in our analysis. We derive the average achievable capacity of the secondary network and analyze its asymptotic behaviors to characterize the multiuser diversity gains in the CR system.
XQ2P: Efficient XQuery P2P Time Series Processing
Venue: arXiv cs.DB 2010
Year: 2010

In this demonstration, we propose a model for the management of XML time series (TS), using the new XQuery 1.1 window operator. We argue that centralized computation is slow, and demonstrate XQ2P, our prototype of efficient XQuery P2P TS computation in the context of financial analysis of large data sets (>1M values).
Termination of Rewriting with Right-Flat Rules Modulo Permutative Theories
Venue: arXiv cs.LO 2010
Year: 2010

We present decidability results for termination of classes of term rewriting systems modulo permutative theories. Termination and innermost termination modulo permutative theories are shown to be decidable for term rewrite systems (TRS) whose right-hand side terms are restricted to be shallow (variables occur at depth at most one) and linear (each variable occurs at most once). Innermost termination modulo permutative theories is also shown to be decidable for shallow TRS. We first show that a shallow TRS can be transformed into a flat (only variables and constants occur at depth one) TRS while preserving termination and innermost termination. The decidability results are then proved by showing that (a) for right-flat right-linear (flat) TRS, non-termination (respectively, innermost non-termination) implies non-termination starting from flat terms, and (b) for right-flat TRS, the existence of non-terminating derivations starting from a given term is decidable. On the negative side, we show PSPACE-hardness of termination and innermost termination for shallow right-linear TRS, and undecidability of termination for flat TRS.
Image transmission over OFDM channel with rate allocation scheme and minimum peak-toaverage power ratio
Venue: arXiv cs.NI 2010
Year: 2010

This paper proposes new scheme for efficient rate allocation in conjunction with reducing peak-to-average power ratio (PAPR) in orthogonal frequency-division multiplexing (OFDM) systems. Modification of the set partitioning in hierarchical trees (SPIHT) image coder is proposed to generate four different groups of bit-stream relative to its significances. The significant bits, the sign bits, the set bits and the refinement bits are transmitted in four different groups. The proposed method for reducing the PAPR utilizes twice the unequal error protection (UEP), using the Read-Solomon codes (RS), in conjunction with bit-rate allocation and selective interleaving to provide minimum PAPR. The output bit-stream from the source code (SPIHT) will be started by the most significant types of bits (first group of bits). The optimal unequal error protection (UEP) of the four groups is proposed based on the channel destortion. The proposed structure provides significant improvement in bit error rate (BER) performance. Performed computer simulations have shown that the proposed scheme outperform the performance of most of the recent PAPR reduction techniques in most cases. Moreover, the simulation results indicate that the proposed scheme provides significantly better PSNR performance in comparison to well-known robust coding schemes.
Performance Evaluation of Two-Stage Shared FDL Optical Packet Switch using Contention Resolution Scheme with Packet Releasing Priority
Venue: arXiv cs.NI 2010
Year: 2010

This paper proposes a two-stage optical packet switch with second stage of recirculate switch of FDL to reduce the number of the FDL used in the switch for contention resolution. The contention resolution scheme with priority in packet releasing from FDL is tested in the two-stage switch for performance evaluation. Simulation result shows that zero packet loss rate achievable with ı< 0.8 for 32x 32 two-stage switch.
Capacity Optimized For Multicarrier OFDM-MIMO Antenna Systems
Venue: arXiv cs.NI 2010
Year: 2010

Motivated by MIMO broad-band fading channel model, in this section we deals with the capacity behaviour of wireless MIMO and OFDM based spatial multiplexing systems in broad-band fading environments for the case where the channel is unknown at the transmitter and perfectly known at the receiver. This influence the propagation and system parameters on ergodic capacity, we furthermore demonstrate that, unlike the single-input single-output (SISO) case, delay spread channels may provide advantage over flat-fading channels not only in terms of outage capacity but also in terms of ergodic capacity. Therefore, MIMO delay spread channels will in general provide both higher diversity gain and higher multiplexing gain than MIMO flat-fading channels.
Improving GPS Precision and Processing Time using Parallel and Reduced-Length Wiener Filters
Venue: arXiv cs.OH 2010
Year: 2010

Increasing GPS precision at low cost has always been a challenge for the manufacturers of the GPS receivers. This paper proposes the use of a Wiener filter for increasing precision in substitution of traditional GPS/INS fusion systems, which require expensive inertial systems. In this paper, we first implement and compare three GPS signal processing schemes: a Kalman filter, a neural network and a Wiener filter and compare them in terms of precision and the processing time. To further reduce the processing time of Wiener filter, we propose parallel and reduced-length implementations. Finally, we calculate the sampling frequency that would be required in every Wiener scheme in order to obtain the same total processing time as the Kalman filter and the neural network.
Imprvoing QoS of all-IP Generation of Pre-WiMax Networks Using Delay-Jitter Model
Venue: arXiv cs.NI 2010
Year: 2010

The topic of this paper is the evaluation of QoS parameters in live Pre-Wimax environments. The main contribution is the validation of an analytical delay-jitter behavior model. These models can be used in optimization algorithms in order to provide opportunistic and reliable all-IP networks. It allows understanding the impact of the jitter constraints on the throughput and packet loss in wireless systems. However, we show that the real-time QoS requirements of real-time and interactive services can be avoided to a large degree by controlling only the packet delay-jitter in a fixed and mobile environment. The QoS metrics have been computed from live measurements in a Pre-Wimax realistic environment (Toulouse/Blagnac Airport).
Implementation of Handoff through wireless access point Techniques
Venue: arXiv cs.NI 2010
Year: 2010

Handoff has become an inevitable part of wireless cellular communication, Soon users will carry small portable handheld devices which will incorporate the computer, phone, camera, GPS, personal control module etc. This paper proposes a new scheme to deal with seam less roaming and reduce failed handoffs. The simulation is done using software called Qualnet meant for wireless communication. The results clearly indicate the advantages of this new scheme.
Fundamental Limits of Wideband Localization - Part II: Cooperative Networks
Venue: arXiv cs.IT 2010
Year: 2010

The availability of positional information is of great importance in many commercial, governmental, and military applications. Localization is commonly accomplished through the use of radio communication between mobile devices (agents) and fixed infrastructure (anchors). However, precise determination of agent positions is a challenging task, especially in harsh environments due to radio blockage or limited anchor deployment. In these situations, cooperation among agents can significantly improve localization accuracy and reduce localization outage probabilities. A general framework of analyzing the fundamental limits of wideband localization has been developed in Part I of the paper. Here, we build on this framework and establish the fundamental limits of wideband cooperative location-aware networks. Our analysis is based on the waveforms received at the nodes, in conjunction with Fisher information inequality. We provide a geometrical interpretation of equivalent Fisher information for cooperative networks. This approach allows us to succinctly derive fundamental performance limits and their scaling behaviors, and to treat anchors and agents in a unified way from the perspective of localization accuracy. Our results yield important insights into how and when cooperation is beneficial.
Multiobjective decomposition of integer matrices: application to radiotherapy
Venue: arXiv cs.DM 2010
Year: 2010

We consider the following problem: to decompose a nonnegative integer matrix into a linear combination of binary matrices that respect the consecutive ones prop- erty. This problem occurs in the radiotherapy treatment of cancer. The nonnegative integer matrix corresponds to fields giving the different radiation beams that a linear accelerator has to send throughout the body of a patient. Due to the in- homogeneous dose levels, leaves from a multi-leaf collimator are used between the accelerator and the body of the patient to block the radiations. The leaves positions can be represented by segments, that are binary matrices with the consecutive ones property. The aim is to find efficient decompositions that simultaneously minimize the irradiation time, the cardinality of the decomposition and the setup-time to configure the multi-leaf collimator at each step of the decomposition. We propose for this NP-hard multiobjective combinatorial problem a heuristic, based on the adaptation of the two-phase Pareto local search. Experiments are carried out on different size instances and the results are reported.
Distributed Rateless Codes with UEP Property
Venue: arXiv cs.IT 2010
Year: 2010

When multiple sources of data need to transmit their rateless coded symbols through a single relay to a common destination, a distributed rateless code instead of several separate conventional rateless codes can be employed to encode the input symbols to increase the transmission efficiency and flexibility. In this paper, we propose distributed rateless codes DU-rateless that can provide unequal error protection (UEP) for distributed sources with different data block lengths and different importance levels. We analyze our proposed DU-rateless code employing And-Or tree analysis technique. Next, we design several sets of optimum DU-rateless codes for various setups employing multi-objective genetic algorithms and evaluate their performances.
Efficient Resource Matching in Heterogeneous Grid Using Resource Vector
Venue: arXiv cs.DC 2010
Year: 2010

In this paper, a method for efficient scheduling to obtain optimum job throughput in a distributed campus grid environment is presented; Traditional job schedulers determine job scheduling using user and job resource attributes. User attributes are related to current usage, historical usage, user priority and project access. Job resource attributes mainly comprise of soft requirements (compilers, libraries) and hard requirements like memory, storage and interconnect. A job scheduler dispatches jobs to a resource if a job's hard and soft requirements are met by a resource. In current scenario during execution of a job, if a resource becomes unavailable, schedulers are presented with limited options, namely re-queuing job or migrating job to a different resource. Both options are expensive in terms of data and compute time. These situations can be avoided, if the often ignored factor, availability time of a resource in a grid environment is considered. We propose resource rank approach, in which jobs are dispatched to a resource which has the highest rank among all resources that match the job's requirement. The results show that our approach can increase throughput of many serial / monolithic jobs.
Biometric Authentication using Nonparametric Methods
Venue: arXiv cs.CV 2010
Year: 2010

The physiological and behavioral trait is employed to develop biometric authentication systems. The proposed work deals with the authentication of iris and signature based on minimum variance criteria. The iris patterns are preprocessed based on area of the connected components. The segmented image used for authentication consists of the region with large variations in the gray level values. The image region is split into quadtree components. The components with minimum variance are determined from the training samples. Hu moments are applied on the components. The summation of moment values corresponding to minimum variance components are provided as input vector to k-means and fuzzy kmeans classifiers. The best performance was obtained for MMU database consisting of 45 subjects. The number of subjects with zero False Rejection Rate [FRR] was 44 and number of subjects with zero False Acceptance Rate [FAR] was 45. This paper addresses the computational load reduction in off-line signature verification based on minimal features using k-means, fuzzy k-means, k-nn, fuzzy k-nn and novel average-max approaches. FRR of 8.13% and FAR of 10% was achieved using k-nn classifier. The signature is a biometric, where variations in a genuine case, is a natural expectation. In the genuine signature, certain parts of signature vary from one instance to another. The system aims to provide simple, fast and robust system using less number of features when compared to state of art works.