OpenRaiser/Intern-Atlas huggingface dataset:
Analysis of peeling decoder for MET ensembles
Venue: arXiv cs.IT 2009
Year: 2009

The peeling decoder introduced by Luby, et al. allows analysis of LDPC decoding for the binary erasure channel (BEC). For irregular ensembles, they analyze the decoder state as a Markov process and present a solution to the differential equations describing the process mean. Multi-edge type (MET) ensembles allow greater precision through specifying graph connectivity. We generalize the the peeling decoder for MET ensembles and derive analogous differential equations. We offer a new change of variables and solution to the node fraction evolutions in the general (MET) case. This result is preparatory to investigating finite-length ensemble behavior.
Active Learning for Mention Detection: A Comparison of Sentence Selection Strategies
Venue: arXiv cs.CL 2009
Year: 2009

We propose and compare various sentence selection strategies for active learning for the task of detecting mentions of entities. The best strategy employs the sum of confidences of two statistical classifiers trained on different views of the data. Our experimental results show that, compared to the random selection strategy, this strategy reduces the amount of required labeled training data by over 50% while achieving the same performance. The effect is even more significant when only named mentions are considered: the system achieves the same performance by using only 42% of the training data required by the random selection strategy.
People-Sensing Spatial Characteristics of RF Sensor Networks
Venue: arXiv cs.NI 2009
Year: 2009

An "RF sensor" network can monitor RSS values on links in the network and perform device-free localization, i.e., locating a person or object moving in the area in which the network is deployed. This paper provides a statistical model for the RSS variance as a function of the person's position w.r.t. the transmitter (TX) and receiver (RX). We show that the ensemble mean of the RSS variance has an approximately linear relationship with the expected total affected power (ETAP). We then use analysis to derive approximate expressions for the ETAP as a function of the person's position, for both scattering and reflection. Counterintuitively, we show that reflection, not scattering, causes the RSS variance contours to be shaped like Cassini ovals. Experimental tests reported here and in past literature are shown to validate the analysis.
Interference Channels With Arbitrarily Correlated Sources
Venue: arXiv cs.IT 2009
Year: 2009

Communicating arbitrarily correlated sources over interference channels is considered in this paper. A sufficient condition is found for the lossless transmission of a pair of correlated sources over a discrete memoryless interference channel. With independent sources, the sufficient condition reduces to the Han-Kobayashi achievable rate region for the interference channel. For a special correlation structure (in the sense of Slepian-Wolf, 1973), the proposed region reduces to the known achievable region for interference channels with common information. A simple example is given to show that the separation approach, with Slepian-Wolf encoding followed by optimal channel coding, is strictly suboptimal.
An Iteratively Reweighted Algorithm for Sparse Reconstruction of Subsurface Flow Properties from Nonlinear Dynamic Data
Venue: arXiv cs.NA 2009
Year: 2009

In this paper, we present a practical algorithm based on sparsity regularization to effectively solve nonlinear dynamic inverse problems that are encountered in subsurface model calibration. We use an iteratively reweighted algorithm that is widely used to solve linear inverse problems with sparsity constraint known as compressed sensing to estimate permeability fields from nonlinear dynamic flow data.
Characterizing Polynomial Time Computability of Rational and Real Functions
Venue: arXiv cs.CC 2009
Year: 2009

Recursive analysis was introduced by A. Turing [1936], A. Grzegorczyk [1955], and D. Lacombe [1955]. It is based on a discrete mechanical framework that can be used to model computation over the real numbers. In this context the computational complexity of real functions defined over compact domains has been extensively studied. However, much less have been done for other kinds of real functions. This article is divided into two main parts. The first part investigates polynomial time computability of rational functions and the role of continuity in such computation. On the one hand this is interesting for its own sake. On the other hand it provides insights into polynomial time computability of real functions for the latter, in the sense of recursive analysis, is modeled as approximations of rational computations. The main conclusion of this part is that continuity does not play any role in the efficiency of computing rational functions. The second part defines polynomial time computability of arbitrary real functions, characterizes it, and compares it with the corresponding notion over rational functions. Assuming continuity, the main conclusion is that there is a conceptual difference between polynomial time computation over the rationals and the reals manifested by the fact that there are polynomial time computable rational functions whose extensions to the reals are not polynomial time computable and vice versa.
Cybermatter
Venue: arXiv cs.CY 2009
Year: 2009

In this paper we examine several aspects of the impact of Cyberworld onto our Reality conceptions, and their social implications.
Performance Analysis of MANET Routing Protocols Using An Elegant Visual Simulation Tool
Venue: arXiv cs.SE 2009
Year: 2009

The task of simulation is often complicated for which many naive users often seek for relatively easier solutions. In many cases, simulations are done without any visual output which makes them non-attractive. In this paper, we present ViSim; a new simulation tool that has a user-friendly graphical interface. ViSim could be useful for researchers, students, teachers in their works, and for the demonstration of various wireless network scenarios on computer screen. It could make the task of simulation more exciting and enhance the interest of the users without going into complex command-only text interface. ViSim is not a simulation engine rather it calls ns-2 simulations in the background and makes the task easy for the users to visualize the simulation in Windows environment. Though ViSim is mainly a simulation demonstration tool, any user with the knowledge of ns-2 and Tcl scripting is also allowed to do necessary modifications and quick configurations for any other MANET routing scenario. Using our simulation tool, we measured the performances of several Mobile Ad-hoc Network (MANET) routing protocols. In this paper, we present the performance analysis of three prominent MANET routing protocols; DSDV, DSR, and AODV using our tool. The details of various features of ViSim, brief descriptions of the selected routing protocols and their comparisons, details about the performed experiments, and the gained results are presented in this work.
Cooperative Precoding/Resource Allocation Games under Spectral Mask and Total Power Constraints
Venue: arXiv cs.IT 2009
Year: 2009

The use of orthogonal signaling schemes such as time-, frequency-, or code-division multiplexing (T-, F-, CDM) in multi-user systems allows for power-efficient simple receivers. It is shown in this paper that by using orthogonal signaling on frequency selective fading channels, the cooperative Nash bargaining (NB)-based precoding games for multi-user systems, which aim at maximizing the information rates of all users, are simplified to the corresponding cooperative resource allocation games. The latter provides additional practically desired simplifications to transmitter design and significantly reduces the overhead during user cooperation. The complexity of the corresponding precoding/resource allocation games, however, depends on the constraints imposed on the users. If only spectral mask constraints are present, the corresponding cooperative NB problem can be formulated as a convex optimization problem and solved efficiently in a distributed manner using dual decomposition based algorithm. However, the NB problem is non-convex if total power constraints are also imposed on the users. In this case, the complexity associate with finding the NB solution is unacceptably high. Therefore, the multi-user systems are categorized into bandwidth- and power-dominant based on a bottleneck resource, and different manners of cooperation are developed for each type of systems for the case of two-users. Such classification guarantees that the solution obtained in each case is Pareto-optimal and actually can be identical to the optimal solution, while the complexity is significantly reduced. Simulation results demonstrate the efficiency of the proposed cooperative precoding/resource allocation strategies and the reduced complexity of the proposed algorithms.
The hardness of routing two pairs on one face
Venue: arXiv cs.DM 2009
Year: 2009

We prove the NP-completeness of the integer multiflow problem in planar graphs, with the following restrictions: there are only two demand edges, both lying on the infinite face of the routing graph. This was one of the open challenges concerning disjoint paths, explicitly asked by Müller. It also strengthens Schwärzler's recent proof of one of the open problems of Schrijver's book, about the complexity of the edge-disjoint paths problem with terminals on the outer boundary of a planar graph. We also give a directed acyclic reduction. This proves that the arc-disjoint paths problem is NP-complete in directed acyclic graphs, even with only two demand arcs.
Fault-Tolerance through Message-logging and Check-pointing: Disaster Recovery for CORBA-based Distributed Bank Servers
Venue: arXiv cs.DC 2009
Year: 2009

This report presents results of our endeavor towards developing a failure-recovery variant of a CORBA-based bank server that provides fault tolerance features through message logging and checkpoint logging. In this group of projects, three components were developed to satisfy the requirements: 1) a message-logging protocol for the branch servers of the distributed banking system to log required information; 2) a recovery module that restarts the bank server using the message log to help the restarted bank server process subsequent requests for various operations; 3) a monitor module that periodically checks whether the bank server is down and helps the recovery module restart the bank server if the latter has crashed.
Apply Ant Colony Algorithm to Search All Extreme Points of Function
Venue: arXiv cs.AI 2009
Year: 2009

To find all extreme points of multimodal functions is called extremum problem, which is a well known difficult issue in optimization fields. Applying ant colony optimization (ACO) to solve this problem is rarely reported. The method of applying ACO to solve extremum problem is explored in this paper. Experiment shows that the solution error of the method presented in this paper is less than 10^-8. keywords: Extremum Problem; Ant Colony Optimization (ACO)
A Tighter Bound for the Determinization of Visibly Pushdown Automata
Venue: arXiv cs.FL 2009
Year: 2009

Visibly pushdown automata (VPA), introduced by Alur and Madhusuan in 2004, is a subclass of pushdown automata whose stack behavior is completely determined by the input symbol according to a fixed partition of the input alphabet. Since its introduce, VPAs have been shown to be useful in various context, e.g., as specification formalism for verification and as automaton model for processing XML streams. Due to high complexity, however, implementation of formal verification based on VPA framework is a challenge. In this paper we consider the problem of implementing VPA-based model checking algorithms. For doing so, we first present an improvement on upper bound for determinization of VPA. Next, we propose simple on-the-fly algorithms to check universality and inclusion problems of this automata class. Then, we implement the proposed algorithms in a prototype tool. Finally, we conduct experiments on randomly generated VPAs. The experimental results show that the proposed algorithms are considerably faster than the standard ones.
Automated Predicate Abstraction for Real-Time Models
Venue: arXiv cs.LO 2009
Year: 2009

We present a technique designed to automatically compute predicate abstractions for dense real-timed models represented as networks of timed automata. We use the CIPM algorithm in our previous work which computes new invariants for timed automata control locations and prunes the model, to compute a predicate abstraction of the model. We do so by taking information regarding control locations and their newly computed invariants into account.
Final Architecture Specification of security, privacy, and incentive mechanisms
Venue: arXiv cs.CR 2009
Year: 2009

In this document, we define the NADA security architecture based on refined use case scenarios, a derived high level model and security analysis. For the architecure design and verification we are applying the well known STRIDE model.
A Minimal Periods Algorithm with Applications
Venue: arXiv cs.DS 2009
Year: 2009

Kosaraju in ``Computation of squares in a string'' briefly described a linear-time algorithm for computing the minimal squares starting at each position in a word. Using the same construction of suffix trees, we generalize his result and describe in detail how to compute in O(k|w|)-time the minimal k-th power, with period of length larger than s, starting at each position in a word w for arbitrary exponent $k\geq2$ and integer $s\geq0$. We provide the complete proof of correctness of the algorithm, which is somehow not completely clear in Kosaraju's original paper. The algorithm can be used as a sub-routine to detect certain types of pseudo-patterns in words, which is our original intention to study the generalization.
Dense-choice Counter Machines revisited
Venue: arXiv cs.LO 2009
Year: 2009

This paper clarifies the picture about Dense-choice Counter Machines, which have been less studied than (discrete) Counter Machines. We revisit the definition of "Dense Counter Machines" so that it now extends (discrete) Counter Machines, and we provide new undecidability and decidability results. Using the first-order additive mixed theory of reals and integers, we give a logical characterization of the sets of configurations reachable by reversal-bounded Dense-choice Counter Machines.
Noise Speech wavelet analyzing in special time ranges
Venue: arXiv cs.SD 2009
Year: 2009

Speech analyzing in special periods of time has been presented in this paper. One of the most important periods in signal processing is near to Zero. By this paper, we analyze noise speech signals when these signals are near to Zero. Our strategy is defining some subfunctions and compress histograms when a noise speech signal is in a special period. It can be so useful for wavelet signal processing and spoken systems analyzing.
X-Learn: An XML-Based, Multi-agent System for Supporting "User-Device" Adaptive E-learning
Venue: arXiv cs.CY 2009
Year: 2009

In this paper we present X-Learn, an XML-based, multi-agent system for supporting "user-device" adaptive e-learning. X-Learn is characterized by the following features: (i) it is highly subjective, since it handles quite a rich and detailed user profile that plays a key role during the learning activities; (ii) it is dynamic and flexible, i.e., it is capable of reacting to variations of exigencies and objectives; (iii) it is device-adaptive, since it decides the learning objects to present to the user on the basis of the device she/he is currently exploiting; (iv) it is generic, i.e., it is capable of operating in a large variety of learning contexts; (v) it is XML based, since it exploits many facilities of XML technology for handling and exchanging information connected to e-learning activities. The paper reports also various experimental results as well as a comparison between X-Learn and other related e-learning management systems already presented in the literature.
Manipulability of Single Transferable Vote
Venue: arXiv cs.AI 2009
Year: 2009

For many voting rules, it is NP-hard to compute a successful manipulation. However, NP-hardness only bounds the worst-case complexity. Recent theoretical results suggest that manipulation may often be easy in practice. We study empirically the cost of manipulating the single transferable vote (STV) rule. This was one of the first rules shown to be NP-hard to manipulate. It also appears to be one of the harder rules to manipulate since it involves multiple rounds and since, unlike many other rules, it is NP-hard for a single agent to manipulate without weights on the votes or uncertainty about how the other agents have voted. In almost every election in our experiments, it was easy to compute how a single agent could manipulate the election or to prove that manipulation by a single agent was impossible. It remains an interesting open question if manipulation by a coalition of agents is hard to compute in practice.
Equivalence perspectives in communication, source-channel connections and universal source-channel separation
Venue: arXiv cs.IT 2009
Year: 2009

An operational perspective is used to understand the relationship between source and channel coding. This is based on a direct reduction of one problem to another that uses random coding (and hence common randomness) but unlike all prior work, does not involve any functional computations, in particular, no mutual-information computations. This result is then used to prove a universal source-channel separation theorem in the rate-distortion context where universality is in the sense of a compound ``general channel.''
Error Rates of the Maximum-Likelihood Detector for Arbitrary Constellations: Convex/Concave Behavior and Applications
Venue: arXiv cs.IT 2009
Year: 2009

Motivated by a recent surge of interest in convex optimization techniques, convexity/concavity properties of error rates of the maximum likelihood detector operating in the AWGN channel are studied and extended to frequency-flat slow-fading channels. Generic conditions are identified under which the symbol error rate (SER) is convex/concave for arbitrary multi-dimensional constellations. In particular, the SER is convex in SNR for any one- and two-dimensional constellation, and also in higher dimensions at high SNR. Pairwise error probability and bit error rate are shown to be convex at high SNR, for arbitrary constellations and bit mapping. Universal bounds for the SER 1st and 2nd derivatives are obtained, which hold for arbitrary constellations and are tight for some of them. Applications of the results are discussed, which include optimum power allocation in spatial multiplexing systems, optimum power/time sharing to decrease or increase (jamming problem) error rate, an implication for fading channels ("fading is never good in low dimensions") and optimization of a unitary-precoded OFDM system. For example, the error rate bounds of a unitary-precoded OFDM system with QPSK modulation, which reveal the best and worst precoding, are extended to arbitrary constellations, which may also include coding. The reported results also apply to the interference channel under Gaussian approximation, to the bit error rate when it can be expressed or approximated as a non-negative linear combination of individual symbol error rates, and to coded systems.
Storage Coding for Wear Leveling in Flash Memories
Venue: arXiv cs.IT 2009
Year: 2009

Flash memory is a non-volatile computer memory comprised of blocks of cells, wherein each cell is implemented as either NAND or NOR floating gate. NAND flash is currently the most widely used type of flash memory. In a NAND flash memory, every block of cells consists of numerous pages; rewriting even a single page requires the whole block to be erased and reprogrammed. Block erasures determine both the longevity and the efficiency of a flash memory. Therefore, when data in a NAND flash memory are reorganized, minimizing the total number of block erasures required to achieve the desired data movement is an important goal. This leads to the flash data movement problem studied in this paper. We show that coding can significantly reduce the number of block erasures required for data movement, and present several optimal or nearly optimal data-movement algorithms based upon ideas from coding theory and combinatorics. In particular, we show that the sorting-based (non-coding) schemes require at least O(nlogn) erasures to move data among n blocks, whereas coding-based schemes require only O(n) erasures. Furthermore, coding-based schemes use only one auxiliary block, which is the best possible, and achieve a good balance between the number of erasures in each of the n+1 blocks.
Introduction to Bioinformatics
Venue: arXiv cs.CE 2009
Year: 2009

Bioinformatics is a new discipline that addresses the need to manage and interpret the data that in the past decade was massively generated by genomic research. This discipline represents the convergence of genomics, biotechnology and information technology, and encompasses analysis and interpretation of data, modeling of biological phenomena, and development of algorithms and statistics. This article presents an introduction to bioinformatics
MIMO Z-Interference Channels: Capacity Under Strong and Noisy Interference
Venue: arXiv cs.IT 2009
Year: 2009

The capacity regions of multiple-input multiple-output Gaussian Z-interference channels are established for the very strong interference and aligned strong interference cases. The sum-rate capacity of such channels is established under noisy interference. These results generalize known results for scalar Gaussian Z-interference channels.
Improved Algorithm for Degree Bounded Survivable Network Design Problem
Venue: arXiv cs.DS 2009
Year: 2009

We consider the Degree-Bounded Survivable Network Design Problem: the objective is to find a minimum cost subgraph satisfying the given connectivity requirements as well as the degree bounds on the vertices. If we denote the upper bound on the degree of a vertex v by b(v), then we present an algorithm that finds a solution whose cost is at most twice the cost of the optimal solution while the degree of a degree constrained vertex v is at most 2b(v) + 2. This improves upon the results of Lau and Singh and that of Lau, Naor, Salavatipour and Singh.
CanICA: Model-based extraction of reproducible group-level ICA patterns from fMRI time series
Venue: arXiv cs.CV 2009
Year: 2009

Spatial Independent Component Analysis (ICA) is an increasingly used data-driven method to analyze functional Magnetic Resonance Imaging (fMRI) data. To date, it has been used to extract meaningful patterns without prior information. However, ICA is not robust to mild data variation and remains a parameter-sensitive algorithm. The validity of the extracted patterns is hard to establish, as well as the significance of differences between patterns extracted from different groups of subjects. We start from a generative model of the fMRI group data to introduce a probabilistic ICA pattern-extraction algorithm, called CanICA (Canonical ICA). Thanks to an explicit noise model and canonical correlation analysis, our method is auto-calibrated and identifies the group-reproducible data subspace before performing ICA. We compare our method to state-of-the-art multi-subject fMRI ICA methods and show that the features extracted are more reproducible.