OpenRaiser/Intern-Atlas huggingface dataset:
Asymptotically Regular LDPC Codes with Linear Distance Growth and Thresholds Close to Capacity
Venue: arXiv cs.IT 2010
Year: 2010

Families of "asymptotically regular" LDPC block code ensembles can be formed by terminating (J,K)-regular protograph-based LDPC convolutional codes. By varying the termination length, we obtain a large selection of LDPC block code ensembles with varying code rates and substantially better iterative decoding thresholds than those of (J,K)-regular LDPC block code ensembles, despite the fact that the terminated ensembles are almost regular. Also, by means of an asymptotic weight enumerator analysis, we show that minimum distance grows linearly with block length for all of the ensembles in these families, i.e., the ensembles are asymptotically good. We find that, as the termination length increases, families of "asymptotically regular" codes with capacity approaching iterative decoding thresholds and declining minimum distance growth rates are obtained, allowing a code designer to trade-off between distance growth rate and threshold. Further, we show that the thresholds and the distance growth rates can be improved by carefully choosing the component protographs used in the code construction.
New Families of LDPC Block Codes Formed by Terminating Irregular Protograph-Based LDPC Convolutional Codes
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we present a method of constructing new families of LDPC block code ensembles formed by terminating irregular protograph-based LDPC convolutional codes. Using the accumulate-repeat-by-4-jagged-accumulate (AR4JA) protograph as an example, a density evolution analysis for the binary erasure channel shows that this flexible design technique gives rise to a large selection of LDPC block code ensembles with varying code rates and thresholds close to capacity. Further, by means of an asymptotic weight enumerator analysis, we show that all the ensembles in this family also have minimum distance that grows linearly with block length, i.e., they are asymptotically good.
Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction
Venue: arXiv cs.LO 2010
Year: 2010

We study techniques for deciding the computational complexity of infinite-domain constraint satisfaction problems. For certain fundamental algebraic structures Delta, we prove definability dichotomy theorems of the following form: for every first-order expansion Gamma of Delta, either Gamma has a quantifier-free Horn definition in Delta, or there is an element d of Gamma such that all non-empty relations in Gamma contain a tuple of the form (d,...,d), or all relations with a first-order definition in Delta have a primitive positive definition in Gamma. The results imply that several families of constraint satisfaction problems exhibit a complexity dichotomy: the problems are in P or NP-hard, depending on the choice of the allowed relations. As concrete examples, we investigate fundamental algebraic constraint satisfaction problems. The first class consists of all first-order expansions of (Q;+). The second class is the affine variant of the first class. In both cases, we obtain full dichotomies by utilising our general methods.
Cooperative Sequential Spectrum Sensing Algorithms for OFDM
Venue: arXiv cs.IT 2010
Year: 2010

This paper considers the problem of spectrum sensing in cognitive radio networks when the primary user employs Orthogonal Frequency Division Multiplexing (OFDM). We develop cooperative sequential detection algorithms based on energy detectors and the autocorrelation property of cyclic prefix (CP) used in OFDM systems and compare their performances. We show that sequential detection provides much better performance than the traditional fixed sample size (snapshot) based detectors. We also study the effect of model uncertainties such as timing and frequency offset, IQ-imbalance and uncertainty in noise and transmit power on the performance of the detectors. We modify the detectors to mitigate the effects of these impairments. The performance of the proposed algorithms are studied via simulations. It is shown that energy detector performs significantly better than the CP-based detector, except in case of a snapshot detector with noise power uncertainty. Also, unlike for the CP-based detector, most of the above mentioned impairments have no effect on the energy detector.
Energy and Link Quality Based Routing for Data Gathering Tree in Wireless Sensor Networks Under TINYOS - 2.X
Venue: arXiv cs.NI 2010
Year: 2010

Energy is one of the most important and scarce resources in Wireless Sensor Networks (WSN). WSN nodes work with the embedded operating system called TinyOS, which addresses the constrains of the WSN nodes such as limited processing power, memory, energy, etc and it uses the collection Tree Protocol (CTP) to collect the data from the sensor nodes. It uses either the four-bit link estimation or Link Estimation Exchange Protocol (LEEP) to predict the bi directional quality of the wireless link between the nodes and the next hop candidate is based on the estimated link quality. The residual energy of the node is an important key factor, which plays a vital role in the lifetime of the network and hence this has to taken as one of the metric in the parent selection. In this work, we consider the remaining energy of the node as one of the metric to decide the parent in addition to the link quality metrics. The proposed protocol was compared with CTP protocol in terms of number of packets forwarded by each node and packet reception ratio (PRR) of the network. This work was simulated in TOSSIM simulator and the same was tested in Crossbow IRIS radio test bed. The results show that our algorithm performs better than CTP in terms of load distribution and hence the increased lifetime
Bandwidth Modeling and Estimation in Peer to Peer Networks
Venue: arXiv cs.NI 2010
Year: 2010

Recent studies have shown that the majority of today's internet traffic is related to Peer to Peer (P2P) traffic. The study of bandwidth in P2P networks is very important. Because it helps us in more efficient capacity planning and QoS provisioning when we would like to design a large scale computer networks. In this paper motivated by the behavior of peers (sources or seeds) that is modeled by Ornstein Uhlenbeck (OU) process, we propose a model for bandwidth in P2P networks. This model is represented with a stochastic integral. We also model the bandwidth when we have multiple downloads or uploads. The autocovariance structure of bandwidth in either case is studied and the statistical parameters such as mean, variance and autocovariance are obtained. We then study the queue length behavior of the bandwidth model. The methods for generating synthetic bandwidth process and estimation of the bandwidth parameters using maximum likehood estimation are presented.
The ABC of Digital Business Ecosystems
Venue: arXiv cs.CY 2010
Year: 2010

The European Commission has the power to inspire, initiate and sponsor huge transnational projects to an extent impossible for most other entities. These projects can address universal themes and develop well-being models that are valuable across a diversity of societies and economies. It is a universal fact that SMEs in all countries provide a substantial proportion of total employment, and conduct much of a nation's innovative activity. Yet these smaller companies struggle in global markets on a far from level playing field, where large companies have distinct advantages. To redress this imbalance the Commission saw it as a priority to improve the trading capability of the Small and Medium-sized Enterprises (SMEs), and perceived digital platforms as the modern means to this end. They considered that the best operational model for a vibrant Web2.0-based Internet services industry would be by analogy to well-performing biological ecosystems. Open Source Software is adopted in the DBE/OPAALS projects as the best support for sustainability of such complex electronic webs, since it minimises interoperability problems, enables code access for cheaper in-house modification or development of systems, and reduces both capital and operating expenditure.
Analyzing the Performance of Active Queue Management Algorithms
Venue: arXiv cs.PF 2010
Year: 2010

Congestion is an important issue which researchers focus on in the Transmission Control Protocol (TCP) network environment. To keep the stability of the whole network, congestion control algorithms have been extensively studied. Queue management method employed by the routers is one of the important issues in the congestion control study. Active queue management (AQM) has been proposed as a router-based mechanism for early detection of congestion inside the network. In this paper we analyzed several active queue management algorithms with respect to their abilities of maintaining high resource utilization, identifying and restricting disproportionate bandwidth usage, and their deployment complexity. We compare the performance of FRED, BLUE, SFB, and CHOKe based on simulation results, using RED and Drop Tail as the evaluation baseline. The characteristics of different algorithms are also discussed and compared. Simulation is done by using Network Simulator(NS2) and the graphs are drawn using X- graph.
Incorporating prediction models in the SelfLet framework: a plugin approach
Venue: arXiv cs.SE 2010
Year: 2010

A complex pervasive system is typically composed of many cooperating \emph{nodes}, running on machines with different capabilities, and pervasively distributed across the environment. These systems pose several new challenges such as the need for the nodes to manage autonomously and dynamically in order to adapt to changes detected in the environment. To address the above issue, a number of autonomic frameworks has been proposed. These usually offer either predefined self-management policies or programmatic mechanisms for creating new policies at design time. From a more theoretical perspective, some works propose the adoption of prediction models as a way to anticipate the evolution of the system and to make timely decisions. In this context, our aim is to experiment with the integration of prediction models within a specific autonomic framework in order to assess the feasibility of such integration in a setting where the characteristics of dynamicity, decentralization, and cooperation among nodes are important. We extend an existing infrastructure called \emph{SelfLets} in order to make it ready to host various prediction models that can be dynamically plugged and unplugged in the various component nodes, thus enabling a wide range of predictions to be performed. Also, we show in a simple example how the system works when adopting a specific prediction model from the literature.
A Short Introduction to Kolmogorov Complexity
Venue: arXiv cs.CC 2010
Year: 2010

This is a short introduction to Kolmogorov Complexity. The interested reader is referred to the text books by Cover & Thomas as well as Li & Vítanyi, which cover the fields of information theory and Kolmogorov complexity in depth and with all the necessary rigor.
Flows and Decompositions of Games: Harmonic and Potential Games
Venue: arXiv cs.GT 2010
Year: 2010

In this paper we introduce a novel flow representation for finite games in strategic form. This representation allows us to develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic and nonstrategic components. We analyze natural classes of games that are induced by this decomposition, and in particular, focus on games with no harmonic component and games with no potential component. We show that the first class corresponds to the well-known potential games. We refer to the second class of games as harmonic games, and study the structural and equilibrium properties of this new class of games. Intuitively, the potential component of a game captures interactions that can equivalently be represented as a common interest game, while the harmonic part represents the conflicts between the interests of the players. We make this intuition precise, by studying the properties of these two classes, and show that indeed they have quite distinct and remarkable characteristics. For instance, while finite potential games always have pure Nash equilibria, harmonic games generically never do. Moreover, we show that the nonstrategic component does not affect the equilibria of a game, but plays a fundamental role in their efficiency properties, thus decoupling the location of equilibria and their payoff-related properties. Exploiting the properties of the decomposition framework, we obtain explicit expressions for the projections of games onto the subspaces of potential and harmonic games. This enables an extension of the properties of potential and harmonic games to "nearby" games. We exemplify this point by showing that the set of approximate equilibria of an arbitrary game can be characterized through the equilibria of its projection onto the set of potential games.
Construction of Codes for Network Coding
Venue: arXiv cs.IT 2010
Year: 2010

Based on ideas of Kötter and Kschischang we use constant dimension subspaces as codewords in a network. We show a connection to the theory of q-analogues of a combinatorial designs, which has been studied in Braun, Kerber and Laue as a purely combinatorial object. For the construction of network codes we successfully modified methods (construction with prescribed automorphisms) originally developed for the q-analogues of a combinatorial designs. We then give a special case of that method which allows the construction of network codes with a very large ambient space and we also show how to decode such codes with a very small number of operations.
Note on Maximal Bisection above Tight Lower Bound
Venue: arXiv cs.DS 2010
Year: 2010

In a graph $G=(V,E)$, a bisection $(X,Y)$ is a partition of $V$ into sets $X$ and $Y$ such that $|X|\le |Y|\le |X|+1$. The size of $(X,Y)$ is the number of edges between $X$ and $Y$. In the Max Bisection problem we are given a graph $G=(V,E)$ and are required to find a bisection of maximum size. It is not hard to see that $\lceil |E|/2 \rceil$ is a tight lower bound on the maximum size of a bisection of $G$. We study parameterized complexity of the following parameterized problem called Max Bisection above Tight Lower Bound (Max-Bisec-ATLB): decide whether a graph $G=(V,E)$ has a bisection of size at least $\lceil |E|/2 \rceil+k,$ where $k$ is the parameter. We show that this parameterized problem has a kernel with $O(k^2)$ vertices and $O(k^3)$ edges, i.e., every instance of Max-Bisec-ATLB is equivalent to an instance of Max-Bisec-ATLB on a graph with at most $O(k^2)$ vertices and $O(k^3)$ edges.
A partial proof of Nash's Theorem via exchangeable equilibria
Venue: arXiv cs.GT 2010
Year: 2010

This document consists of two parts: the second part was submitted earlier as a new proof of Nash's theorem, and the first part is a note explaining a problem found in that proof. We are indebted to Sergiu Hart and Eran Shmaya for their careful study which led to their simultaneous discovery of this error. So far the error has not been fixed, but many of the results and techniques of the paper remain valid, so we will continue to make it available online. Abstract for the original paper: We give a novel proof of the existence of Nash equilibria in all finite games without using fixed point theorems or path following arguments. Our approach relies on a new notion intermediate between Nash and correlated equilibria called exchangeable equilibria, which are correlated equilibria with certain symmetry and factorization properties. We prove these exist by a duality argument, using Hart and Schmeidler's proof of correlated equilibrium existence as a first step. In an appropriate limit exchangeable equilibria converge to the convex hull of Nash equilibria, proving that these exist as well. Exchangeable equilibria are defined in terms of symmetries of the game, so this method automatically proves the stronger statement that a symmetric game has a symmetric Nash equilibrium. The case without symmetries follows by a symmetrization argument.
Dynamical issues in interactive representation of physical objects
Venue: arXiv cs.GR 2010
Year: 2010

The quality of a simulator equipped with a haptic interface is given by the dynamical properties of its components: haptic interface, simulator and control system. Some application areas of such kind of simulator like musical synthesis, animation or more general, instrumental art have specific requirements as for the "haptic rendering" of small movements that go beyond the usual haptic interfaces allow. Object properties variability and different situations of object combination represent important aspects of such type of application which makes that the user can be interested as much in the restitution of certain global properties of an entire object domain as in the restitution of properties that are specific to an isolate object. In the traditional approaches, the usual criteria are founded on the paradigm of transparency and are related to the impedance error introduced by the technical aspects of the system. As a general aim, rather than to minimize these effects, we look to characterize them by physical metaphors conferring to haptic medium the role of a tool. This positioning leads to firstly analyze the natural human object interaction as a simplified evolutive system and then considers its synthesis in the case of the interactive physical simulation. By means of a frequential method, this approach is presented for some elementary configurations of the simulator
Critical control of a genetic algorithm
Venue: arXiv cs.NE 2010
Year: 2010

Based on speculations coming from statistical mechanics and the conjectured existence of critical states, I propose a simple heuristic in order to control the mutation probability and the population size of a genetic algorithm.
Exact counting of Euler Tours for generalized series-parallel graphs
Venue: arXiv cs.DS 2010
Year: 2010

We give a simple polynomial-time algorithm to exactly count the number of Euler Tours (ETs) of any Eulerian generalized series-parallel graph, and show how to adapt this algorithm to exactly sample a random ET of the given generalized series-parallel graph. Note that the class of generalized seriesparallel graphs includes all outerplanar graphs. We can perform the counting in time $O(mΔ^3)$, where $Δ$ is the maximum degree of the graph with $m$ edges. We use $O(mΔ^2 \log Δ)$ bits to store intermediate values during our computations. To date, these are the first known polynomial-time algorithms to count or sample ETs of any class of graphs; there are no other known polynomial-time algorithms to even approximately count or sample ETs of any other class of graphs. The problem of counting ETs is known to be $#P$-complete for general graphs (Brightwell and Winkler, 2005 [3]) and also for planar graphs (Creed, 2009 [4]).
Improved OMP Approach to Sparse Multi-path Channel Estimation via Adaptive Inter-atom Interference Mitigation
Venue: arXiv cs.IT 2010
Year: 2010

Since most components of sparse multi-path channel (SMPC) are zero, impulse response of SMPC can be recovered from a short training sequence. Though the ordinary orthogonal matching pursuit (OMP) algorithm provides a very fast implementation of SMPC estimation, it suffers from inter-atom interference (IAI), especially in the case of SMPC with a large delay spread and short training sequence. In this paper, an adaptive IAI mitigation method is proposed to improve the performance of SMPC estimation based on a general OMP algorithm. Unlike the ordinary OMP algorithm, a sensing dictionary is designed adaptively and posterior information is utilized efficiently to prevent false atoms from being selected due to serious IAI. Numeral experiments illustrate that the proposed general OMP algorithm based on adaptive IAI mitigation outperform both the ordinary OMP algorithm and the general OMP algorithm based on non-adaptive IAI mitigation.
An Ontology-based Context Aware System for Selective Dissemination of Information in a Digital Library
Venue: arXiv cs.DL 2010
Year: 2010

Users of Institutional Repositories and Digital Libraries are known by their needs for very specific information about one or more subjects. To characterize users profiles and offer them new documents and resources is one of the main challenges of today's libraries. In this paper, a Selective Dissemination of Information service is described, which proposes an Ontology-based Context Aware system for identifying user's context (research subjects, work team, areas of interest). This system enables librarians to broaden users profiles beyond the information that users have introduced by hand (such as institution, age and language). The system requires a context retrieval layer to capture user information and behavior, and an inference engine to support context inference from many information sources (selected documents and users' queries).
Contention Based Routing in Mobile Ad Hoc Networks with Multiple Copies
Venue: arXiv cs.NI 2010
Year: 2010

Routing the packets efficiently in mobile ad hoc network does not have end to end paths. Multiple copies are forwarded from the source to the destination. To deal with such networks, researches introduced flooding based routing schemes which leads to high probability of delivery. But the flooding based routing schemes suffered with contention and large delays. Here the proposed protocol "Spray Select Focus", sprays a few message copies into the network, neighbors receives a copy and by that relay nodes we are choosing the shortest route and then route that copy towards the destination. Previous works assumption is that there is no contention and dead ends. But we argue that contention and dead ends must be considered for finding efficiency in routing. So we are including a network which has contention and dead ends and we applied the proposed protocol. We can say that this protocol works well for the contention based network.
Software Effort Estimation using Radial Basis and Generalized Regression Neural Networks
Venue: arXiv cs.SE 2010
Year: 2010

Software development effort estimation is one of the most major activities in software project management. A number of models have been proposed to construct a relationship between software size and effort; however we still have problems for effort estimation. This is because project data, available in the initial stages of project is often incomplete, inconsistent, uncertain and unclear. The need for accurate effort estimation in software industry is still a challenge. Artificial Neural Network models are more suitable in such situations. The present paper is concerned with developing software effort estimation models based on artificial neural networks. The models are designed to improve the performance of the network that suits to the COCOMO Model. Artificial Neural Network models are created using Radial Basis and Generalized Regression. A case study based on the COCOMO81 database compares the proposed neural network models with the Intermediate COCOMO. The results were analyzed using five different criterions MMRE, MARE, VARE, Mean BRE and Prediction. It is observed that the Radial Basis Neural Network provided better results
Internet Banking System Prototype
Venue: arXiv cs.HC 2010
Year: 2010

Internet Banking System refers to systems that enable bank customers to access accounts and general information on bank products and services through a personal computer or other intelligent device. Internet banking products and services can include detailed account information for corporate customers as well as account summery and transfer money. Ultimately, the products and services obtained through Internet Banking may mirror products and services offered through other bank delivery channels. In this paper, Internet Banking System Prototype has been proposed in order to illustrate the services which is provided by the Bank online services.