OpenRaiser/Intern-Atlas huggingface dataset:
Bounds on the capacity of OFDM underspread frequency selective fading channels
Venue: arXiv cs.IT 2011
Year: 2011

The analysis of the channel capacity in the absence of prior channel knowledge (noncoherent channel) has gained increasing interest in recent years, but it is still unknown for the general case. In this paper we derive bounds on the capacity of the noncoherent, underspread complex Gaussian, orthogonal frequency division multiplexing (OFDM), wide sense stationary channel with uncorrelated scattering (WSSUS), under a peak power constraint or a constraint on the second and fourth moments of the transmitted signal. These bounds are characterized only by the system signal-to-noise ratio (SNR) and by a newly defined quantity termed effective coherence time. Analysis of the effective coherence time reveals that it can be interpreted as the length of a block in the block fading model in which a system with the same SNR will achieve the same capacity as in the analyzed channel. Unlike commonly used coherence time definitions, it is shown that the effective coherence time depends on the SNR, and is a nonincreasing function of it. We show that for low SNR the capacity is proportional to the effective coherence time, while for higher SNR the coherent channel capacity can be achieved provided that the effective coherence time is large enough.
An Information Theoretic Representation of Agent Dynamics as Set Intersections
Venue: arXiv cs.IT 2011
Year: 2011

We represent agents as sets of strings. Each string encodes a potential interaction with another agent or environment. We represent the total set of dynamics between two agents as the intersection of their respective strings, we prove complexity properties of player interactions using Algorithmic Information Theory. We show how the proposed construction is compatible with Universal Artificial Intelligence, in that the AIXI model can be seen as universal with respect to interaction.
Selling train tickets by SMS
Venue: arXiv cs.CR 2011
Year: 2011

Selling train tickets has evolved in the last ten years from queuing in the railway station, to buying tickets on the internet and printing them. Both alternatives are still viable options, though they are time consuming or need printing devices. Nowadays it is essential to offer a service that is as fast and efficient as possible: mobile phones provide an accessible, affordable and widely available tool for supplying information and transferring data. The goal of this project is to design a train ticket contained in a SMS message. While there are several challenges related to the project, the main one is the security and how we can digitally sign a train ticket that is contained in 160 characters. The solution offered in this project is the implementation of the MOVA Signature (from the name of the inventors MOnnerat and VAudenay) that uses an interactive verification and therefore allows signature of 20 bits (roughly 4 characters).
Integrating Generic Sensor Fusion Algorithms with Sound State Representations through Encapsulation of Manifolds
Venue: arXiv cs.RO 2011
Year: 2011

Common estimation algorithms, such as least squares estimation or the Kalman filter, operate on a state in a state space S that is represented as a real-valued vector. However, for many quantities, most notably orientations in 3D, S is not a vector space, but a so-called manifold, i.e. it behaves like a vector space locally but has a more complex global topological structure. For integrating these quantities, several ad-hoc approaches have been proposed. Here, we present a principled solution to this problem where the structure of the manifold S is encapsulated by two operators, state displacement [+]:S x R^n --> S and its inverse [-]: S x S --> R^n. These operators provide a local vector-space view δ; --> x [+] δ; around a given state x. Generic estimation algorithms can then work on the manifold S mainly by replacing +/- with [+]/[-] where appropriate. We analyze these operators axiomatically, and demonstrate their use in least-squares estimation and the Unscented Kalman Filter. Moreover, we exploit the idea of encapsulation from a software engineering perspective in the Manifold Toolkit, where the [+]/[-] operators mediate between a "flat-vector" view for the generic algorithm and a "named-members" view for the problem specific functions.
AISMOTIF-An Artificial Immune System for DNA Motif Discovery
Venue: arXiv cs.CE 2011
Year: 2011

Discovery of transcription factor binding sites is a much explored and still exploring area of research in functional genomics. Many computational tools have been developed for finding motifs and each of them has their own advantages as well as disadvantages. Most of these algorithms need prior knowledge about the data to construct background models. However there is not a single technique that can be considered as best for finding regulatory motifs. This paper proposes an artificial immune system based algorithm for finding the transcription factor binding sites or motifs and two new weighted scores for motif evaluation. The algorithm is enumerative, but sufficient pruning of the pattern search space has been incorporated using immune system concepts. The performance of AISMOTIF has been evaluated by comparing it with eight state of art composite motif discovery algorithms and found that AISMOTIF predicts known motifs as well as new motifs from the benchmark dataset without any prior knowledge about the data.
Distances for Weighted Transition Systems: Games and Properties
Venue: arXiv cs.LO 2011
Year: 2011

We develop a general framework for reasoning about distances between transition systems with quantitative information. Taking as starting point an arbitrary distance on system traces, we show how this leads to natural definitions of a linear and a branching distance on states of such a transition system. We show that our framework generalizes and unifies a large variety of previously considered system distances, and we develop some general properties of our distances. We also show that if the trace distance admits a recursive characterization, then the corresponding branching distance can be obtained as a least fixed point to a similar recursive characterization. The central tool in our work is a theory of infinite path-building games with quantitative objectives.
Text Classification: A Sequential Reading Approach
Venue: arXiv cs.AI 2011
Year: 2011

We propose to model the text classification process as a sequential decision process. In this process, an agent learns to classify documents into topics while reading the document sentences sequentially and learns to stop as soon as enough information was read for deciding. The proposed algorithm is based on a modelisation of Text Classification as a Markov Decision Process and learns by using Reinforcement Learning. Experiments on four different classical mono-label corpora show that the proposed approach performs comparably to classical SVM approaches for large training sets, and better for small training sets. In addition, the model automatically adapts its reading process to the quantity of training information provided.
Accelerating Lossless Data Compression with GPUs
Venue: arXiv cs.IT 2011
Year: 2011

Huffman compression is a statistical, lossless, data compression algorithm that compresses data by assigning variable length codes to symbols, with the more frequently appearing symbols given shorter codes than the less. This work is a modification of the Huffman algorithm which permits uncompressed data to be decomposed into indepen- dently compressible and decompressible blocks, allowing for concurrent compression and decompression on multiple processors. We create implementations of this modified algorithm on a current NVIDIA GPU using the CUDA API as well as on a current Intel chip and the performance results are compared, showing favorable GPU performance for nearly all tests. Lastly, we discuss the necessity for high performance data compression in today's supercomputing ecosystem.
A multilingual/multicultural semantic-based approach to improve Data Sharing in an SDI for Nature Conservation
Venue: arXiv cs.DL 2011
Year: 2011

The paper proposes an approach to transcend multicultural and multilingual barriers in the use and reuse of geographical data at the European level. The approach aims at sharing scientific terms in the field of nature conservation with the goal of assisting different user communities with metadata compilation and information discovery. A multi-thesauri solution is proposed, based on a Common Thesaurus Framework for Nature Conservation, where different well-known Knowledge Organization Systems are assembled and shared. It has been designed according to semantic web and W3C recommendations employing SKOS standard models and Linked Data to publish the thesauri as a whole in machine-understandable format. The outcome is a powerful framework satisfying the requirements of modularity and openness for further thesaurus extension and updating, interlinking among thesauri, and exploitability from other systems. The paper supports the employment of Linked Data to deal with terminologies in complex domains such as nature conservation and it proposes a hands-on recipe to publish thesauri in the framework.
On Krawtchouk Transforms
Venue: arXiv cs.IT 2011
Year: 2011

Krawtchouk polynomials appear in a variety of contexts, most notably as orthogonal polynomials and in coding theory via the Krawtchouk transform. We present an operator calculus formulation of the Krawtchouk transform that is suitable for computer implementation. A positivity result for the Krawtchouk transform is shown. Then our approach is compared with the use of the Krawtchouk transform in coding theory where it appears in MacWilliams' and Delsarte's theorems on weight enumerators. We conclude with a construction of Krawtchouk polynomials in an arbitrary finite number of variables, orthogonal with respect to the multinomial distribution.
Utility Optimal Coding for Packet Transmission over Wireless Networks - Part II: Networks of Packet Erasure Channels
Venue: arXiv cs.IT 2011
Year: 2011

We define a class of multi--hop erasure networks that approximates a wireless multi--hop network. The network carries unicast flows for multiple users, and each information packet within a flow is required to be decoded at the flow destination within a specified delay deadline. The allocation of coding rates amongst flows/users is constrained by network capacity. We propose a proportional fair transmission scheme that maximises the sum utility of flow throughputs. This is achieved by {\em jointly optimising the packet coding rates and the allocation of bits of coded packets across transmission slots.}
A Novel Agent Based Approach for Controlling Network Storms
Venue: arXiv cs.NI 2011
Year: 2011

One of the fundamental data transmission mechanisms in Ethernet LAN is broadcasting. Flooding is a direct broadcasting technique used in these networks. A significant drawback of this method is that it can lead to broadcast storms. This phenomenon is more common in multivendor switch environment. Broadcast storms usually results in dissension, collision and redundancy leading to degradation of the network performance. Most of the storms appear without much warning and it affects the efficiency of network even in situations when the network is expected to work most efficiently. There are several characteristic patterns by which storm can appear in a LAN, like rate monotonic repetition, transient appearances with different types of growth properties and decay profiles. In this paper we discuss the storm build up pattern in an industry and present various reasons for storm in LAN. We have identified a strategy for controlling network storms, using multiple static agents. These agents inhibit storm packet regeneration in the network using the knowledge of storm growth pattern. A model developed out of empirical studies is used to differentiate normal packet growth from storm packet growth and used in control mechanism of storms.
Kunchenko's Polynomials for Template Matching
Venue: arXiv cs.CV 2011
Year: 2011

This paper reviews Kunchenko's polynomials using as template matching method to recognize template in one-dimensional input signal. Kunchenko's polynomials method is compared with classical methods - cross-correlation and sum of squared differences according to numerical statistical example.
Extend Commitment Protocols with Temporal Regulations: Why and How
Venue: arXiv cs.AI 2011
Year: 2011

The proposal of Elisa Marengo's thesis is to extend commitment protocols to explicitly account for temporal regulations. This extension will satisfy two needs: (1) it will allow representing, in a flexible and modular way, temporal regulations with a normative force, posed on the interaction, so as to represent conventions, laws and suchlike; (2) it will allow committing to complex conditions, which describe not only what will be achieved but to some extent also how. These two aspects will be deeply investigated in the proposal of a unified framework, which is part of the ongoing work and will be included in the thesis.
ForOpenCL: Transformations Exploiting Array Syntax in Fortran for Accelerator Programming
Venue: arXiv cs.PL 2011
Year: 2011

Emerging GPU architectures for high performance computing are well suited to a data-parallel programming model. This paper presents preliminary work examining a programming methodology that provides Fortran programmers with access to these emerging systems. We use array constructs in Fortran to show how this infrequently exploited, standardized language feature is easily transformed to lower-level accelerator code. The transformations in ForOpenCL are based on a simple mapping from Fortran to OpenCL. We demonstrate, using a stencil code solving the shallow-water fluid equations, that the performance of the ForOpenCL compiler-generated transformations is comparable with that of hand-optimized OpenCL code.
Maximum Matchings via Glauber Dynamics
Venue: arXiv cs.DS 2011
Year: 2011

In this paper we study the classic problem of computing a maximum cardinality matching in general graphs $G = (V, E)$. The best known algorithm for this problem till date runs in $O(m \sqrt{n})$ time due to Micali and Vazirani \cite{MV80}. Even for general bipartite graphs this is the best known running time (the algorithm of Karp and Hopcroft \cite{HK73} also achieves this bound). For regular bipartite graphs one can achieve an $O(m)$ time algorithm which, following a series of papers, has been recently improved to $O(n \log n)$ by Goel, Kapralov and Khanna (STOC 2010) \cite{GKK10}. In this paper we present a randomized algorithm based on the Markov Chain Monte Carlo paradigm which runs in $O(m \log^2 n)$ time, thereby obtaining a significant improvement over \cite{MV80}. We use a Markov chain similar to the \emph{hard-core model} for Glauber Dynamics with \emph{fugacity} parameter $λ$, which is used to sample independent sets in a graph from the Gibbs Distribution \cite{V99}, to design a faster algorithm for finding maximum matchings in general graphs. Our result crucially relies on the fact that the mixing time of our Markov Chain is independent of $λ$, a significant deviation from the recent series of works \cite{GGSVY11,MWW09, RSVVY10, S10, W06} which achieve computational transition (for estimating the partition function) on a threshold value of $λ$. As a result we are able to design a randomized algorithm which runs in $O(m\log^2 n)$ time that provides a major improvement over the running time of the algorithm due to Micali and Vazirani. Using the conductance bound, we also prove that mixing takes $Ω(\frac{m}{k})$ time where $k$ is the size of the maximum matching.
Exploring New Directions in Iris Recognition
Venue: arXiv cs.CV 2011
Year: 2011

A new approach in iris recognition based on Circular Fuzzy Iris Segmentation (CFIS) and Gabor Analytic Iris Texture Binary Encoder (GAITBE) is proposed and tested here. CFIS procedure is designed to guarantee that similar iris segments will be obtained for similar eye images, despite the fact that the degree of occlusion may vary from one image to another. Its result is a circular iris ring (concentric with the pupil) which approximates the actual iris. GAITBE proves better encoding of statistical independence between the iris codes extracted from different irides using Hilbert Transform. Irides from University of Bath Iris Database are binary encoded on two different lengths (768 / 192 bytes) and tested in both single-enrollment and multi-enrollment identification scenarios. All cases illustrate the capacity of the newly proposed methodology to narrow down the distribution of inter-class matching scores, and consequently, to guarantee a steeper descent of the False Accept Rate.
Face Recognition using Curvelet Transform
Venue: arXiv cs.CV 2011
Year: 2011

Face recognition has been studied extensively for more than 20 years now. Since the beginning of 90s the subject has became a major issue. This technology is used in many important real-world applications, such as video surveillance, smart cards, database security, internet and intranet access. This report reviews recent two algorithms for face recognition which take advantage of a relatively new multiscale geometric analysis tool - Curvelet transform, for facial processing and feature extraction. This transform proves to be efficient especially due to its good ability to detect curves and lines, which characterize the human's face. An algorithm which is based on the two algorithms mentioned above is proposed, and its performance is evaluated on three data bases of faces: AT&T (ORL), Essex Grimace and Georgia-Tech. k-nearest neighbour (k-NN) and Support vector machine (SVM) classifiers are used, along with Principal Component Analysis (PCA) for dimensionality reduction. This algorithm shows good results, and it even outperforms other algorithms in some cases.
A Two Stage Selective Averaging LDPC Decoding
Venue: arXiv cs.IT 2011
Year: 2011

Low density parity-check (LDPC) codes are a class of linear block codes that are decoded by running belief propagation (BP) algorithm or log-likelihood ratio belief propagation (LLR-BP) over the factor graph of the code. One of the disadvantages of LDPC codes is the onset of an error floor at high values of signal to noise ratio caused by trapping sets. In this paper, we propose a two stage decoder to deal with different types of trapping sets. Oscillating trapping sets are taken care by the first stage of the decoder and the elementary trapping sets are handled by the second stage of the decoder. Simulation results on regular PEG (504,252,3,6) code shows that the proposed two stage decoder performs significantly better than the standard decoder.
Linear-Time Poisson-Disk Patterns
Venue: arXiv cs.GR 2011
Year: 2011

We present an algorithm for generating Poisson-disc patterns taking O(N) time to generate $N$ points. The method is based on a grid of regions which can contain no more than one point in the final pattern, and uses an explicit model of point arrival times under a uniform Poisson process.
A Satisfiability Algorithm for AC$^0$
Venue: arXiv cs.CC 2011
Year: 2011

We consider the problem of efficiently enumerating the satisfying assignments to $\AC^0$ circuits. We give a zero-error randomized algorithm which takes an $\AC^0$ circuit as input and constructs a set of restrictions which partition $\{0,1\}^n$ so that under each restriction the value of the circuit is constant. Let $d$ denote the depth of the circuit and $cn$ denote the number of gates. This algorithm runs in time $|C| 2^{n(1-μ_{c.d})}$ where $|C|$ is the size of the circuit for $μ_{c,d} \ge 1/\bigO[\lg c + d \lg d]^{d-1}$ with probability at least $1-2^{-n}$. As a result, we get improved exponential time algorithms for $\AC^0$ circuit satisfiability and for counting solutions. In addition, we get an improved bound on the correlation of $\AC^0$ circuits with parity. As an important component of our analysis, we extend the Håstad Switching Lemma to handle multiple $\kcnf$s and $\kdnf$s.
Stable, scalable, decentralized P2P file sharing with non-altruistic peers
Venue: arXiv cs.NI 2011
Year: 2011

P2P systems provide a scalable solution for distributing large files in a network. The file is split into many chunks, and peers contact other peers to collect missing chunks to eventually complete the entire file. The so-called `rare chunk' phenomenon, where a single chunk becomes rare and prevents peers from completing the file, is a threat to the stability of such systems. Practical systems such as BitTorrent overcome this issue by requiring a global search for the rare chunk, which necessitates a centralized mechanism. We demonstrate a new system based on an approximate rare-chunk rule, allowing for completely distributed file sharing while retaining scalability and stability. We assume non-altruistic peers and the seed is required to make only a minimal contribution.
Convergence of Weighted Min-Sum Decoding Via Dynamic Programming on Trees
Venue: arXiv cs.IT 2011
Year: 2011

Applying the max-product (and belief-propagation) algorithms to loopy graphs is now quite popular for best assignment problems. This is largely due to their low computational complexity and impressive performance in practice. Still, there is no general understanding of the conditions required for convergence and/or the optimality of converged solutions. This paper presents an analysis of both attenuated max-product (AMP) decoding and weighted min-sum (WMS) decoding for LDPC codes which guarantees convergence to a fixed point when a weight parameter, β, is sufficiently small. It also shows that, if the fixed point satisfies some consistency conditions, then it must be both the linear-programming (LP) and maximum-likelihood (ML) solution. For (dv,dc)-regular LDPC codes, the weight must satisfy β(dv-1) \leq 1 whereas the results proposed by Frey and Koetter require instead that β(dv-1)(dc-1) < 1. A counterexample which shows a fixed point might not be the ML solution if β(dv-1) > 1 is also given. Finally, connections are explored with recent work by Arora et al. on the threshold of LP decoding.
Estimation of Characteristics of a Software Team for Implementing Effective Inspection Process through Inspection Performance Metric
Venue: arXiv cs.SE 2011
Year: 2011

The continued existence of any software industry depends on its capability to develop nearly zero-defect product, which is achievable through effective defect management. Inspection has proven to be one of the promising techniques of defect management. Introductions of metrics like, Depth of Inspection (DI, a process metric) and Inspection Performance Metric (IPM, a people metric) enable one to have an appropriate measurement of inspection technique. This article elucidates a mathematical approach to estimate the IPM value without depending on shop floor defect count at every time. By applying multiple linear regression models, a set of characteristic coefficients of the team is evaluated. These coefficients are calculated from the empirical projects that are sampled from the teams of product-based and service-based IT industries. A sample of three verification projects indicates a close match between the IPM values obtained from the defect count (IPMdc) and IPM values obtained using the team coefficients using the mathematical model (IPMtc). The IPM values observed onsite and IPM values produced by our model which are strongly matching, support the predictive capability of IPM through team coefficients. Having finalized the value of IPM that a company should achieve for a project, it can tune the inspection influencing parameters to realize the desired quality level of IPM. Evaluation of team coefficients resolves several defect-associated issues, which are related to the management, stakeholders, outsourcing agents and customers. In addition, the coefficient vector will further aid the strategy of PSP and TSP