OpenRaiser/Intern-Atlas huggingface dataset:
PaperBricks: An Alternative to Complete-Story Peer Reviewing
Venue: arXiv cs.DL 2011
Year: 2011

The peer review system as used in several computer science communities has several flaws including long review times, overloaded reviewers, as well as fostering of niche topics. These flaws decrease quality, lower impact, slowdown the innovation process, and lead to frustration of authors, readers, and reviewers. In order to fix this, we propose a new peer review system termed paper bricks. Paper bricks has several advantages over the existing system including shorter publications, better competition for new ideas, as well as an accelerated innovation process. Furthermore, paper bricks may be implemented with minimal change to the existing peer review systems.
Linear Error Correcting Codes with Anytime Reliability
Venue: arXiv cs.IT 2011
Year: 2011

We consider rate R = k/n causal linear codes that map a sequence of k-dimensional binary vectors {b_t} to a sequence of n-dimensional binary vectors {c_t}, such that each c_t is a function of {b_1,b_2,...,b_t}. Such a code is called anytime reliable, for a particular binary-input memoryless channel, if at each time, probability of making an error about a source bit that was sent d time instants ago decays exponentially in d. Anytime reliable codes are useful in interactive communication problems and, in particular, can be used to stabilize unstable plants across noisy channels. Schulman proved the existence of such codes which, due to their structure, he called tree codes; however, to date, no explicit constructions and tractable decoding algorithms have been devised. In this paper, we show the existence of anytime reliable "linear" codes with "high probability", i.e., suitably chosen random linear causal codes are anytime reliable with high probability. The key is to consider time-invariant codes (i.e., ones with Toeplitz generator and parity check matrices) which obviates the need to union bound over all times. For the binary erasure channel we give a simple ML decoding algorithm whose average complexity is constant per time iteration and for which the probability that complexity at a given time t exceeds KC^3 decays exponentially in C. We show the efficacy of the method by simulating the stabilization of an unstable plant across a BEC, and remark on the tradeoffs between the utilization of the communication resources and the control performance.
A Tool for the Certification of PLCs based on a Coq Semantics for Sequential Function Charts
Venue: arXiv cs.SE 2011
Year: 2011

In this report we describe a tool framework for certifying properties of PLCs: CERTPLC. CERTPLC can handle PLC descriptions provided in the Sequential Function Chart (SFC) language of the IEC 61131-3 standard. It provides routines to certify properties of systems by delivering an independently checkable formal system description and proof (called certificate) for the desired properties. We focus on properties that can be described as inductive invariants. System descriptions and certificates are generated and handled using the COQ proof assistant. Our tool framework is used to provide supporting evidence for the safety of embedded systems in the industrial automation domain to third-party authorities. In this document we describe the tool framework: usage scenarios, the archi-tecture, semantics of PLCs and their realization in COQ, proof generation and the construction of certificates.
Packet-pair technique for available bandwidth estimation in IPv6 network
Venue: arXiv cs.NI 2011
Year: 2011

This paper presents experimental checking of the model for measuring available bandwidth in IPv6. The experiment was performed using a measuring infrastructure RIPE test box, ensuring precision accuracy. The experimental results showed that to increase the accuracy of available bandwidth, we need to neutralize the effect of the variable part of the delay by increasing the number of measurements. Finally, we made the computer simulation, which allowed us to establish a dependence between the measurement error of the available bandwidth and the number of measurements.
Heterogeneous download times in a homogeneous BitTorrent swarm
Venue: arXiv cs.NI 2011
Year: 2011

Modeling and understanding BitTorrent (BT) dynamics is a recurrent research topic mainly due to its high complexity and tremendous practical efficiency. Over the years, different models have uncovered various phenomena exhibited by the system, many of which have direct impact on its performance. In this paper we identify and characterize a phenomenon that has not been previously observed: homogeneous peers (with respect to their upload capacities) experience heterogeneous download rates. The consequences of this phenomenon have direct impact on peer and system performance, such as high variability of download times, unfairness with respect to peer arrival order, bursty departures and content synchronization. Detailed packet-level simulations and prototype-based experiments on the Internet were performed to characterize this phenomenon. We also develop a mathematical model that accurately predicts the heterogeneous download rates of the homogeneous peers as a function of their content. Although this phenomenon is more prevalent in unpopular swarms (very few peers), these by far represent the most common type of swarm in BT.
Physical-Layer Security over Correlated Erasure Channels
Venue: arXiv cs.CR 2011
Year: 2011

We explore the additional security obtained by noise at the physical layer in a wiretap channel model setting. Security enhancements at the physical layer have been proposed recently using a secrecy metric based on the degrees of freedom that an attacker has with respect to the sent ciphertext. Prior work focused on cases in which the wiretap channel could be modeled as statistically independent packet erasure channels for the legitimate receiver and an eavesdropper. In this paper, we go beyond the state-of-the-art by addressing correlated erasure events across the two communication channels. The resulting security enhancement is presented as a function of the correlation coefficient and the erasure probabilities for both channels. It is shown that security improvements are achievable by means of judicious physical-layer design even when the eavesdropper has a better channel than the legitimate receiver. The only case in which this assertion may not hold is when erasures are highly correlated across channels. However, we are able to prove that correlation cannot nullify the expected security enhancement if the channel quality of the legitimate receiver is strictly better than that of the eavesdropper.
Efficient File Synchronization: a Distributed Source Coding Approach
Venue: arXiv cs.IT 2011
Year: 2011

The problem of reconstructing a source sequence with the presence of decoder side-information that is mis-synchronized to the source due to deletions is studied in a distributed source coding framework. Motivated by practical applications, the deletion process is assumed to be bursty and is modeled by a Markov chain. The minimum rate needed to reconstruct the source sequence with high probability is characterized in terms of an information theoretic expression, which is interpreted as the amount of information of the deleted content and the locations of deletions, subtracting "nature's secret", that is, the uncertainty of the locations given the source and side-information. For small bursty deletion probability, the asymptotic expansion of the minimum rate is computed.
Swapping: a natural bridge between named and indexed explicit substitution calculi
Venue: arXiv cs.LO 2011
Year: 2011

This article is devoted to the presentation of lambda_rex, an explicit substitution calculus with de Bruijn indexes and a simple notation. By being isomorphic to lambda_ex - a recent formalism with variable names -, lambda_rex accomplishes simulation of beta-reduction (Sim), preservation of beta-strong normalization (PSN) and meta-confluence (MC), among other desirable properties. Our calculus is based on a novel presentation of lambda_dB, using a swap notion that was originally devised by de Bruijn. Besides lambda_rex, two other indexed calculi isomorphic to lambda_x and lambda_xgc are presented, demonstrating the potential of our technique when applied to the design of indexed versions of known named calculi.
Higher-order Rewriting for Executable Compiler Specifications
Venue: arXiv cs.LO 2011
Year: 2011

In this paper we outline how a simple compiler can be completely specified using higher order rewriting in all stages: parsing, analysis/optimization, and code emission, specifically using the crsx.sf.net system for a small declarative language called "X" inspired by XQuery (for which we are building a production quality compiler in the same way).
Cooperative Wideband Spectrum Sensing for the Centralized Cognitive Radio Network
Venue: arXiv cs.IT 2011
Year: 2011

Various primary user (PU) radios have been allocated into fixed frequency bands in the whole spectrum. A cognitive radio network (CRN) should be able to perform the wideband spectrum sensing (WSS) to detect temporarily unoccupied frequency bands. We summarize four occupancy features for the frequency bands. 1. The occupancy is sparse; 2. The frequency band allocation information is fixed and common; 3. There are three categories for the frequency band usages; 4. The occupied frequency bands are common in the CRN. For the first time, we consider all features as the prior knowledge in the compressed sensing based cooperative WSS (CWSS) algorithm design for a centralized CRN. We propose a modified orthogonal matching pursuit (Mod-OMP) algorithm and a modified simultaneous orthogonal matching pursuit (Mod-SOMP) algorithm for the CWSS. We compare the CWSS performance of Mod-OMP/Mod-SOMP with the original OMP/SOMP and show the performance improvements.
Active Clustering: Robust and Efficient Hierarchical Clustering using Adaptively Selected Similarities
Venue: arXiv cs.IT 2011
Year: 2011

Hierarchical clustering based on pairwise similarities is a common tool used in a broad range of scientific applications. However, in many problems it may be expensive to obtain or compute similarities between the items to be clustered. This paper investigates the hierarchical clustering of N items based on a small subset of pairwise similarities, significantly less than the complete set of N(N-1)/2 similarities. First, we show that if the intracluster similarities exceed intercluster similarities, then it is possible to correctly determine the hierarchical clustering from as few as 3N log N similarities. We demonstrate this order of magnitude savings in the number of pairwise similarities necessitates sequentially selecting which similarities to obtain in an adaptive fashion, rather than picking them at random. We then propose an active clustering method that is robust to a limited fraction of anomalous similarities, and show how even in the presence of these noisy similarity values we can resolve the hierarchical clustering using only O(N log^2 N) pairwise similarities.
Concentration-Based Guarantees for Low-Rank Matrix Reconstruction
Venue: arXiv cs.LG 2011
Year: 2011

We consider the problem of approximately reconstructing a partially-observed, approximately low-rank matrix. This problem has received much attention lately, mostly using the trace-norm as a surrogate to the rank. Here we study low-rank matrix reconstruction using both the trace-norm, as well as the less-studied max-norm, and present reconstruction guarantees based on existing analysis on the Rademacher complexity of the unit balls of these norms. We show how these are superior in several ways to recently published guarantees based on specialized analysis.
Fife's Theorem Revisited
Venue: arXiv cs.FL 2011
Year: 2011

We give another proof of a theorem of Fife - understood broadly as providing a finite automaton that gives a complete description of all infinite binary overlap-free words. Our proof is significantly simpler than those in the literature. As an application we give a complete characterization of the overlap-free words that are 2-automatic.
AWGN Channel Analysis of Terminated LDPC Convolutional Codes
Venue: arXiv cs.IT 2011
Year: 2011

It has previously been shown that ensembles of terminated protograph-based low-density parity-check (LDPC) convolutional codes have a typical minimum distance that grows linearly with block length and that they are capable of achieving capacity approaching iterative decoding thresholds on the binary erasure channel (BEC). In this paper, we review a recent result that the dramatic threshold improvement obtained by terminating LDPC convolutional codes extends to the additive white Gaussian noise (AWGN) channel. Also, using a (3,6)-regular protograph-based LDPC convolutional code ensemble as an example, we perform an asymptotic trapping set analysis of terminated LDPC convolutional code ensembles. In addition to capacity approaching iterative decoding thresholds and linearly growing minimum distance, we find that the smallest non-empty trapping set of a terminated ensemble grows linearly with block length.
Characterizing Discriminative Patterns
Venue: arXiv cs.DB 2011
Year: 2011

Discriminative patterns are association patterns that occur with disproportionate frequency in some classes versus others, and have been studied under names such as emerging patterns and contrast sets. Such patterns have demonstrated considerable value for classification and subgroup discovery, but a detailed understanding of the types of interactions among items in a discriminative pattern is lacking. To address this issue, we propose to categorize discriminative patterns according to four types of item interaction: (i) driver-passenger, (ii) coherent, (iii) independent additive and (iv) synergistic beyond independent additive. Either of the last three is of practical importance, with the latter two representing a gain in the discriminative power of a pattern over its subsets. Synergistic patterns are most restrictive, but perhaps the most interesting since they capture a cooperative effect. For domains such as genetic research, differentiating among these types of patterns is critical since each yields very different biological interpretations. For general domains, the characterization provides a novel view of the nature of the discriminative patterns in a dataset, which yields insights beyond those provided by current approaches that focus mostly on pattern-based classification and subgroup discovery. This paper presents a comprehensive discussion that defines these four pattern types and investigates their properties and their relationship to one another. In addition, these ideas are explored for a variety of datasets (ten UCI datasets, one gene expression dataset and two genetic-variation datasets). The results demonstrate the existence, characteristics and statistical significance of the different types of patterns. They also illustrate how pattern characterization can provide novel insights into discriminative pattern mining and the discriminative structure of different datasets.
Synthesizing Systems with Optimal Average-Case Behavior for Ratio Objectives
Venue: arXiv cs.LO 2011
Year: 2011

We show how to automatically construct a system that satisfies a given logical specification and has an optimal average behavior with respect to a specification with ratio costs. When synthesizing a system from a logical specification, it is often the case that several different systems satisfy the specification. In this case, it is usually not easy for the user to state formally which system she prefers. Prior work proposed to rank the correct systems by adding a quantitative aspect to the specification. A desired preference relation can be expressed with (i) a quantitative language, which is a function assigning a value to every possible behavior of a system, and (ii) an environment model defining the desired optimization criteria of the system, e.g., worst-case or average-case optimal. In this paper, we show how to synthesize a system that is optimal for (i) a quantitative language given by an automaton with a ratio cost function, and (ii) an environment model given by a labeled Markov decision process. The objective of the system is to minimize the expected (ratio) costs. The solution is based on a reduction to Markov Decision Processes with ratio cost functions which do not require that the costs in the denominator are strictly positive. We find an optimal strategy for these using a fractional linear program.
Comparative Study on DFD to UML Diagrams Transformations
Venue: arXiv cs.SE 2011
Year: 2011

Most of legacy systems use nowadays were modeled and documented using structured approach. Expansion of these systems in terms of functionality and maintainability requires shift towards object-oriented documentation and design, which has been widely accepted by the industry. In this paper, we present a survey of the existing Data Flow Diagram (DFD) to Unified Modeling language (UML) transformation techniques. We analyze transformation techniques using a set of parameters, identified in the survey. Based on identified parameters, we present an analysis matrix, which describes the strengths and weaknesses of transformation techniques. It is observed that most of the transformation approaches are rule based, which are incomplete and defined at abstract level that does not cover in depth transformation and automation issues. Transformation approaches are data centric, which focuses on data-store for class diagram generation. Very few of the transformation techniques have been applied on case study as a proof of concept, which are not comprehensive and majority of them are partially automated.
An algebra for signal processing
Venue: arXiv cs.NA 2011
Year: 2011

Our paper presents an attempt to axiomatise signal processing. Our long-term goal is to formulate signal processing algorithms for an ideal world of exact computation and prove properties about them, then interpret these ideal formulations and apply them without change to real world discrete data. We give models of the axioms that are based on Gaussian functions, that allow for exact computations and automated tests of signal algorithm properties.
SHREC 2011: robust feature detection and description benchmark
Venue: arXiv cs.CV 2011
Year: 2011

Feature-based approaches have recently become very popular in computer vision and image analysis applications, and are becoming a promising direction in shape retrieval. SHREC'11 robust feature detection and description benchmark simulates the feature detection and description stages of feature-based shape retrieval algorithms. The benchmark tests the performance of shape feature detectors and descriptors under a wide variety of transformations. The benchmark allows evaluating how algorithms cope with certain classes of transformations and strength of the transformations that can be dealt with. The present paper is a report of the SHREC'11 robust feature detection and description benchmark results.
Almost overlap-free words and the word problem for the free Burnside semigroup satisfying x^2=x^3
Venue: arXiv cs.FL 2011
Year: 2011

In this paper we investigate the word problem of the free Burnside semigroup satisfying x^2=x^3 and having two generators. Elements of this semigroup are classes of equivalent words. A natural way to solve the word problem is to select a unique "canonical" representative for each equivalence class. We prove that overlap-free words and so-called almost overlap-free words (this notion is some generalization of the notion of overlap-free words) can serve as canonical representatives for corresponding equivalence classes. We show that such a word in a given class, if any, can be efficiently found. As a result, we construct a linear-time algorithm that partially solves the word problem for the semigroup under consideration.
Solving k-Set Agreement with Stable Skeleton Graphs
Venue: arXiv cs.DC 2011
Year: 2011

In this paper we consider the k-set agreement problem in distributed message-passing systems using a round-based approach: Both synchrony of communication and failures are captured just by means of the messages that arrive within a round, resulting in round-by-round communication graphs that can be characterized by simple communication predicates. We introduce the weak communication predicate PSources(k) and show that it is tight for k-set agreement, in the following sense: We (i) prove that there is no algorithm for solving (k-1)-set agreement in systems characterized by PSources(k), and (ii) present a novel distributed algorithm that achieves k-set agreement in runs where PSources(k) holds. Our algorithm uses local approximations of the stable skeleton graph, which reflects the underlying perpetual synchrony of a run. We prove that this approximation is correct in all runs, regardless of the communication predicate, and show that graph-theoretic properties of the stable skeleton graph can be used to solve k-set agreement if PSources(k) holds.
Root Isolation of Zero-dimensional Polynomial Systems with Linear Univariate Representation
Venue: arXiv cs.SC 2011
Year: 2011

In this paper, a linear univariate representation for the roots of a zero-dimensional polynomial equation system is presented, where the roots of the equation system are represented as linear combinations of roots of several univariate polynomial equations. The main advantage of this representation is that the precision of the roots can be easily controlled. In fact, based on the linear univariate representation, we can give the exact precisions needed for roots of the univariate equations in order to obtain the roots of the equation system to a given precision. As a consequence, a root isolation algorithm for a zero-dimensional polynomial equation system can be easily derived from its linear univariate representation.
Distributed SNR Estimation using Constant Modulus Signaling over Gaussian Multiple-Access Channels
Venue: arXiv cs.IT 2011
Year: 2011

A sensor network is used for distributed joint mean and variance estimation, in a single time snapshot. Sensors observe a signal embedded in noise, which are phase modulated using a constant-modulus scheme and transmitted over a Gaussian multiple-access channel to a fusion center, where the mean and variance are estimated jointly, using an asymptotically minimum-variance estimator, which is shown to decouple into simple individual estimators of the mean and the variance. The constant-modulus phase modulation scheme ensures a fixed transmit power, robust estimation across several sensing noise distributions, as well as an SNR estimate that requires a single set of transmissions from the sensors to the fusion center, unlike the amplify-and-forward approach. The performance of the estimators of the mean and variance are evaluated in terms of asymptotic variance, which is used to evaluate the performance of the SNR estimator in the case of Gaussian, Laplace and Cauchy sensing noise distributions. For each sensing noise distribution, the optimal phase transmission parameters are also determined. The asymptotic relative efficiency of the mean and variance estimators is evaluated. It is shown that among the noise distributions considered, the estimators are asymptotically efficient only when the noise distribution is Gaussian. Simulation results corroborate analytical results.