OpenRaiser/Intern-Atlas huggingface dataset:
Aggregate Download Throughput for TCP-controlled long file transfers in a WLAN with multiple STA-AP association rates
Venue: arXiv cs.NI 2011
Year: 2011

We consider several WLAN stations associated at rates r1, r2, ..., rk with an Access Point. Each station is downloading a long file from a local server, located on the LAN to which the AP is attached. We model these simultaneous TCP-controlled transfers using a Markov Chain. Our analytical approach leads to a procedure to compute aggregate download throughput numerically, and the results match simulations very well.
The Dynamics of Vehicular Networks in Urban Environments
Venue: arXiv cs.OH 2011
Year: 2011

Vehicular Ad hoc NETworks (VANETs) have emerged as a platform to support intelligent inter-vehicle communication and improve traffic safety and performance. The road-constrained, high mobility of vehicles, their unbounded power source, and the emergence of roadside wireless infrastructures make VANETs a challenging research topic. A key to the development of protocols for inter-vehicle communication and services lies in the knowledge of the topological characteristics of the VANET communication graph. This paper explores the dynamics of VANETs in urban environments and investigates the impact of these findings in the design of VANET routing protocols. Using both real and realistic mobility traces, we study the networking shape of VANETs under different transmission and market penetration ranges. Given that a number of RSUs have to be deployed for disseminating information to vehicles in an urban area, we also study their impact on vehicular connectivity. Through extensive simulations we investigate the performance of VANET routing protocols by exploiting the knowledge of VANET graphs analysis.
Performance of the Fuzzy Vault for Multiple Fingerprints (Extended Version)
Venue: arXiv cs.CR 2011
Year: 2011

The fuzzy vault is an error tolerant authentication method that ensures the privacy of the stored reference data. Several publications have proposed the application of the fuzzy vault to fingerprints, but the results of subsequent analyses indicate that a single finger does not contain sufficient information for a secure implementation. In this contribution, we present an implementation of a fuzzy vault based on minutiae information in several fingerprints aiming at a security level comparable to current cryptographic applications. We analyze and empirically evaluate the security, efficiency, and robustness of the construction and several optimizations. The results allow an assessment of the capacity of the scheme and an appropriate selection of parameters. Finally, we report on a practical simulation conducted with ten users.
A GPU-based hyperbolic SVD algorithm
Venue: arXiv cs.NA 2011
Year: 2011

A one-sided Jacobi hyperbolic singular value decomposition (HSVD) algorithm, using a massively parallel graphics processing unit (GPU), is developed. The algorithm also serves as the final stage of solving a symmetric indefinite eigenvalue problem. Numerical testing demonstrates the gains in speed and accuracy over sequential and MPI-parallelized variants of similar Jacobi-type HSVD algorithms. Finally, possibilities of hybrid CPU--GPU parallelism are discussed.
Performance Analysis of Markov Modulated 1-Persistent CSMA/CA Protocols with Exponential Backoff Scheduling
Venue: arXiv cs.NI 2011
Year: 2011

This paper proposes a Markovian model of 1-persistent CSMA/CA protocols with K-Exponential Backoff scheduling algorithms. The input buffer of each access node is modeled as a Geo/G/1 queue, and the service time distribution of each individual head-of-line packet is derived from the Markov chain of the underlying scheduling algorithm. From the queuing model, we derive the characteristic equation of network throughput and obtain the stable throughput and bounded delay regions with respect to the retransmission factor. Our results show that the stable throughput region of the exponential backoff scheme exists even for an infinite population. Moreover, we find that the bounded delay region of exponential backoff is only a sub-set of its stable throughput region due to the large variance of the service time of input packets caused by the capture effect. All analytical results presented in this paper are verified by simulations.
The universality of iterated hashing over variable-length strings
Venue: arXiv cs.DB 2011
Year: 2011

Iterated hash functions process strings recursively, one character at a time. At each iteration, they compute a new hash value from the preceding hash value and the next character. We prove that iterated hashing can be pairwise independent, but never 3-wise independent. We show that it can be almost universal over strings much longer than the number of hash values; we bound the maximal string length given the collision probability.
Exact Localization and Superresolution with Noisy Data and Random Illumination
Venue: arXiv cs.IT 2011
Year: 2011

This paper studies the problem of exact localization of sparse (point or extended) objects with noisy data. The crux of the proposed approach consists of random illumination. Several recovery methods are analyzed: the Lasso, BPDN and the One-Step Thresholding (OST). For independent random probes, it is shown that both recovery methods can localize exactly $s=\cO(m)$, up to a logarithmic factor, objects where $m$ is the number of data. Moreover, when the number of random probes is large the Lasso with random illumination has a performance guarantee for superresolution, beating the Rayleigh resolution limit. Numerical evidence confirms the predictions and indicates that the performance of the Lasso is superior to that of the OST for the proposed set-up with random illumination.
LDPC Codes from Latin Squares Free of Small Trapping Sets
Venue: arXiv cs.IT 2011
Year: 2011

This paper is concerned with the construction of low-density parity-check (LDPC) codes with low error floors. Two main contributions are made. First, a new class of structured LDPC codes is introduced. The parity check matrices of these codes are arrays of permutation matrices which are obtained from Latin squares and form a finite field under some matrix operations. Second, a method to construct LDPC codes with low error floors on the binary symmetric channel (BSC) is presented. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the Trapping Set Ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum product algorithm (SPA) by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets.
Inference with Multivariate Heavy-Tails in Linear Models
Venue: arXiv cs.LG 2011
Year: 2011

Heavy-tailed distributions naturally occur in many real life problems. Unfortunately, it is typically not possible to compute inference in closed-form in graphical models which involve such heavy-tailed distributions. In this work, we propose a novel simple linear graphical model for independent latent random variables, called linear characteristic model (LCM), defined in the characteristic function domain. Using stable distributions, a heavy-tailed family of distributions which is a generalization of Cauchy, Lévy and Gaussian distributions, we show for the first time, how to compute both exact and approximate inference in such a linear multivariate graphical model. LCMs are not limited to stable distributions, in fact LCMs are always defined for any random variables (discrete, continuous or a mixture of both). We provide a realistic problem from the field of computer networks to demonstrate the applicability of our construction. Other potential application is iterative decoding of linear channels with non-Gaussian noise.
Comparing Pedigree Graphs
Venue: arXiv cs.DS 2011
Year: 2011

Pedigree graphs, or family trees, are typically constructed by an expensive process of examining genealogical records to determine which pairs of individuals are parent and child. New methods to automate this process take as input genetic data from a set of extant individuals and reconstruct ancestral individuals. There is a great need to evaluate the quality of these methods by comparing the estimated pedigree to the true pedigree. In this paper, we consider two main pedigree comparison problems. The first is the pedigree isomorphism problem, for which we present a linear-time algorithm for leaf-labeled pedigrees. The second is the pedigree edit distance problem, for which we present 1) several algorithms that are fast and exact in various special cases, and 2) a general, randomized heuristic algorithm. In the negative direction, we first prove that the pedigree isomorphism problem is as hard as the general graph isomorphism problem, and that the sub-pedigree isomorphism problem is NP-hard. We then show that the pedigree edit distance problem is APX-hard in general and NP-hard on leaf-labeled pedigrees. We use simulated pedigrees to compare our edit-distance algorithms to each other as well as to a branch-and-bound algorithm that always finds an optimal solution.
Niche as a determinant of word fate in online groups
Venue: arXiv cs.CL 2011
Year: 2011

Patterns of word use both reflect and influence a myriad of human activities and interactions. Like other entities that are reproduced and evolve, words rise or decline depending upon a complex interplay between {their intrinsic properties and the environments in which they function}. Using Internet discussion communities as model systems, we define the concept of a word niche as the relationship between the word and the characteristic features of the environments in which it is used. We develop a method to quantify two important aspects of the size of the word niche: the range of individuals using the word and the range of topics it is used to discuss. Controlling for word frequency, we show that these aspects of the word niche are strong determinants of changes in word frequency. Previous studies have already indicated that word frequency itself is a correlate of word success at historical time scales. Our analysis of changes in word frequencies over time reveals that the relative sizes of word niches are far more important than word frequencies in the dynamics of the entire vocabulary at shorter time scales, as the language adapts to new concepts and social groupings. We also distinguish endogenous versus exogenous factors as additional contributors to the fates of words, and demonstrate the force of this distinction in the rise of novel words. Our results indicate that short-term nonstationarity in word statistics is strongly driven by individual proclivities, including inclinations to provide novel information and to project a distinctive social identity.
Center-based Clustering under Perturbation Stability
Venue: arXiv cs.DS 2011
Year: 2011

Clustering under most popular objective functions is NP-hard, even to approximate well, and so unlikely to be efficiently solvable in the worst case. Recently, Bilu and Linial \cite{Bilu09} suggested an approach aimed at bypassing this computational barrier by using properties of instances one might hope to hold in practice. In particular, they argue that instances in practice should be stable to small perturbations in the metric space and give an efficient algorithm for clustering instances of the Max-Cut problem that are stable to perturbations of size $O(n^{1/2})$. In addition, they conjecture that instances stable to as little as O(1) perturbations should be solvable in polynomial time. In this paper we prove that this conjecture is true for any center-based clustering objective (such as $k$-median, $k$-means, and $k$-center). Specifically, we show we can efficiently find the optimal clustering assuming only stability to factor-3 perturbations of the underlying metric in spaces without Steiner points, and stability to factor $2+\sqrt{3}$ perturbations for general metrics. In particular, we show for such instances that the popular Single-Linkage algorithm combined with dynamic programming will find the optimal clustering. We also present NP-hardness results under a weaker but related condition.
An abstract view on syntax with sharing
Venue: arXiv cs.LO 2011
Year: 2011

The notion of term graph encodes a refinement of inductively generated syntax in which regard is paid to the the sharing and discard of subterms. Inductively generated syntax has an abstract expression in terms of initial algebras for certain endofunctors on the category of sets, which permits one to go beyond the set-based case, and speak of inductively generated syntax in other settings. In this paper we give a similar abstract expression to the notion of term graph. Aspects of the concrete theory are redeveloped in this setting, and applications beyond the realm of sets discussed.
Defining and Generating Axial Lines from Street Center Lines for better Understanding of Urban Morphologies
Venue: arXiv cs.CV 2011
Year: 2011

Axial lines are defined as the longest visibility lines for representing individual linear spaces in urban environments. The least number of axial lines that cover the free space of an urban environment or the space between buildings constitute what is often called an axial map. This is a fundamental tool in space syntax, a theory developed by Bill Hillier and his colleagues for characterizing the underlying urban morphologies. For a long time, generating axial lines with help of some graphic software has been a tedious manual process that is criticized for being time consuming, subjective, or even arbitrary. In this paper, we redefine axial lines as the least number of individual straight line segments mutually intersected along natural streets that are generated from street center lines using the Gestalt principle of good continuity. Based on this new definition, we develop an automatic solution to generating the newly defined axial lines from street center lines. We apply this solution to six typical street networks (three from North America and three from Europe), and generate a new set of axial lines for analyzing the urban morphologies. Through a comparison study between the new axial lines and the conventional or old axial lines, and between the new axial lines and natural streets, we demonstrate with empirical evidence that the newly defined axial lines are a better alternative in capturing the underlying urban structure. Keywords: Space syntax, street networks, topological analysis, traffic, head/tail division rule
Efficient Sampling of Band-limited Signals from Sine Wave Crossings
Venue: arXiv cs.IT 2011
Year: 2011

This correspondence presents an efficient method for reconstructing a band-limited signal in the discrete domain from its crossings with a sine wave. The method makes it possible to design A/D converters that only deliver the crossing timings, which are then used to interpolate the input signal at arbitrary instants. Potentially, it may allow for reductions in power consumption and complexity in these converters. The reconstruction in the discrete domain is based on a recently-proposed modification of the Lagrange interpolator, which is readily implementable with linear complexity and efficiently, given that it re-uses known schemes for variable fractional-delay (VFD) filters. As a spin-off, the method allows one to perform spectral analysis from sine wave crossings with the complexity of the FFT. Finally, the results in the correspondence are validated in several numerical examples.
Rate-Equivocation Optimal Spatially Coupled LDPC Codes for the BEC Wiretap Channel
Venue: arXiv cs.IT 2011
Year: 2011

We consider transmission over a wiretap channel where both the main channel and the wiretapper's channel are Binary Erasure Channels (BEC). We use convolutional LDPC ensembles based on the coset encoding scheme. More precisely, we consider regular two edge type convolutional LDPC ensembles. We show that such a construction achieves the whole rate-equivocation region of the BEC wiretap channel. Convolutional LDPC ensemble were introduced by Felström and Zigangirov and are known to have excellent thresholds. Recently, Kudekar, Richardson, and Urbanke proved that the phenomenon of "Spatial Coupling" converts MAP threshold into BP threshold for transmission over the BEC. The phenomenon of spatial coupling has been observed to hold for general binary memoryless symmetric channels. Hence, we conjecture that our construction is a universal rate-equivocation achieving construction when the main channel and wiretapper's channel are binary memoryless symmetric channels, and the wiretapper's channel is degraded with respect to the main channel.
Capacity Achieving Modulation for Fixed Constellations with Average Power Constraint
Venue: arXiv cs.IT 2011
Year: 2011

The capacity achieving probability mass function (PMF) of a finite signal constellation with an average power constraint is in most cases non-uniform. A common approach to generate non-uniform input PMFs is Huffman shaping, which consists of first approximating the capacity achieving PMF by a sampled Gaussian density and then to calculate the Huffman code of the sampled Gaussian density. The Huffman code is then used as a prefix-free modulation code. This approach showed good results in practice, can however lead to a significant gap to capacity. In this work, a method is proposed that efficiently constructs optimal prefix-free modulation codes for any finite signal constellation with average power constraint in additive noise. The proposed codes operate as close to capacity as desired. The major part of this work elaborates an analytical proof of this property. The proposed method is applied to 64-QAM in AWGN and numeric results are given, which show that, opposed to Huffman shaping, by using the proposed method, it is possible to operate very close to capacity over the whole range of parameters.
The use of machine learning with signal- and NLP processing of source code to fingerprint, detect, and classify vulnerabilities and weaknesses with MARFCAT
Venue: arXiv cs.CR 2011
Year: 2011

We present a machine learning approach to static code analysis and fingerprinting for weaknesses related to security, software engineering, and others using the open-source MARF framework and the MARFCAT application based on it for the NIST's SATE2010 static analysis tool exposition workshop found at http://samate.nist.gov/SATE2010Workshop.html
Interference Alignment with Analog Channel State Feedback
Venue: arXiv cs.IT 2011
Year: 2011

Interference alignment (IA) is a multiplexing gain optimal transmission strategy for the interference channel. While the achieved sum rate with IA is much higher than previously thought possible, the improvement often comes at the cost of requiring network channel state information at the transmitters. This can be achieved by explicit feedback, a flexible yet potentially costly approach that incurs large overhead. In this paper we propose analog feedback as an alternative to limited feedback or reciprocity based alignment. We show that the full multiplexing gain observed with perfect channel knowledge is preserved by analog feedback and that the mean loss in sum rate is bounded by a constant when signal-to-noise ratio is comparable in both forward and feedback channels. When signal-to-noise ratios are not quite symmetric, a fraction of the multiplexing gain is achieved. We consider the overhead of training and feedback and use this framework to optimize the system's effective throughput. We present simulation results to demonstrate the performance of IA with analog feedback, verify our theoretical analysis, and extend our conclusions on optimal training and feedback length.
Duty-Cycle-Aware Minimum-Energy Multicasting in Wireless Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

In duty-cycled wireless sensor networks, the nodes switch between active and dormant states, and each node may determine its active/dormant schedule independently. This complicates the Minimum-Energy Multicasting (MEM) problem, which has been primarily studied in always-active wireless ad-hoc networks. In this paper, we study the duty-cycle-aware MEM problem in wireless sensor networks, and we present a formulation of the Minimum-Energy Multicast Tree Construction and Scheduling (MEMTCS) problem. We prove that the MEMTCS problem is NP-hard, and it is unlikely to have an approximation algorithm with a performance ratio of $(1-o(1))\lnΔ$, where $Δ$ is the maximum node degree in a network. We propose a polynomial-time approximation algorithm for the MEMTCS problem with a performance ratio of $\mathcal{O}(H(Δ+1))$, where $H(\cdot)$ is the harmonic number. We also provide a distributed implementation of our algorithm. Finally, we perform extensive simulations and the results demonstrate that our algorithm significantly outperform other known algorithms in terms of both the total energy cost and the transmission redundancy.
Converged Algorithms for Orthogonal Nonnegative Matrix Factorizations
Venue: arXiv cs.LG 2011
Year: 2011

This paper proposes uni-orthogonal and bi-orthogonal nonnegative matrix factorization algorithms with robust convergence proofs. We design the algorithms based on the work of Lee and Seung [1], and derive the converged versions by utilizing ideas from the work of Lin [2]. The experimental results confirm the theoretical guarantees of the convergences.
Capacity of Fading Gaussian Channel with an Energy Harvesting Sensor Node
Venue: arXiv cs.IT 2011
Year: 2011

Network life time maximization is becoming an important design goal in wireless sensor networks. Energy harvesting has recently become a preferred choice for achieving this goal as it provides near perpetual operation. We study such a sensor node with an energy harvesting source and compare various architectures by which the harvested energy is used. We find its Shannon capacity when it is transmitting its observations over a fading AWGN channel with perfect/no channel state information provided at the transmitter. We obtain an achievable rate when there are inefficiencies in energy storage and the capacity when energy is spent in activities other than transmission.
Kernels for Below-Upper-Bound Parameterizations of the Hitting Set and Directed Dominating Set Problems
Venue: arXiv cs.DS 2011
Year: 2011

In the {\sc Hitting Set} problem, we are given a collection $\cal F$ of subsets of a ground set $V$ and an integer $p$, and asked whether $V$ has a $p$-element subset that intersects each set in $\cal F$. We consider two parameterizations of {\sc Hitting Set} below tight upper bounds: $p=m-k$ and $p=n-k$. In both cases $k$ is the parameter. We prove that the first parameterization is fixed-parameter tractable, but has no polynomial kernel unless coNP$\subseteq$NP/poly. The second parameterization is W[1]-complete, but the introduction of an additional parameter, the degeneracy of the hypergraph $H=(V,{\cal F})$, makes the problem not only fixed-parameter tractable, but also one with a linear kernel. Here the degeneracy of $H=(V,{\cal F})$ is the minimum integer $d$ such that for each $X\subset V$ the hypergraph with vertex set $V\setminus X$ and edge set containing all edges of $\cal F$ without vertices in $X$, has a vertex of degree at most $d.$ In {\sc Nonblocker} ({\sc Directed Nonblocker}), we are given an undirected graph (a directed graph) $G$ on $n$ vertices and an integer $k$, and asked whether $G$ has a set $X$ of $n-k$ vertices such that for each vertex $y\not\in X$ there is an edge (arc) from a vertex in $X$ to $y$. {\sc Nonblocker} can be viewed as a special case of {\sc Directed Nonblocker} (replace an undirected graph by a symmetric digraph). Dehne et al. (Proc. SOFSEM 2006) proved that {\sc Nonblocker} has a linear-order kernel. We obtain a linear-order kernel for {\sc Directed Nonblocker}.