OpenRaiser/Intern-Atlas huggingface dataset:
Using State Infection Conditions to Detect Equivalent Mutants and Speed up Mutation Analysis
Venue: arXiv cs.SE 2013
Year: 2013

Mutation analysis evaluates test suites and testing techniques by measuring how well they detect seeded defects (mutants). Even though well established in research, mutation analysis is rarely used in practice due to scalability problems --- there are multiple mutations per code statement leading to a large number of mutants, and hence executions of the test suite. In addition, the use of mutation to improve test suites is futile for mutants that are equivalent, which means that there exists no test case that distinguishes them from the original program. This paper introduces two optimizations based on state infection conditions, i.e., conditions that determine for a test execution whether the same execution on a mutant would lead to a different state. First, redundant test execution can be avoided by monitoring state infection conditions, leading to an overall performance improvement. Second, state infection conditions can aid in identifying equivalent mutants, thus guiding efforts to improve test suites.
A Stochastic Grammar for Natural Shapes
Venue: arXiv cs.CV 2013
Year: 2013

We consider object detection using a generic model for natural shapes. A common approach for object recognition involves matching object models directly to images. Another approach involves building intermediate representations via a generic grouping processes. We argue that these two processes (model-based recognition and grouping) may use similar computational mechanisms. By defining a generic model for shapes we can use model-based techniques to implement a mid-level vision grouping process.
Integrated Pre-Processing for Bayesian Nonlinear System Identification with Gaussian Processes
Venue: arXiv cs.AI 2013
Year: 2013

We introduce GP-FNARX: a new model for nonlinear system identification based on a nonlinear autoregressive exogenous model (NARX) with filtered regressors (F) where the nonlinear regression problem is tackled using sparse Gaussian processes (GP). We integrate data pre-processing with system identification into a fully automated procedure that goes from raw data to an identified model. Both pre-processing parameters and GP hyper-parameters are tuned by maximizing the marginal likelihood of the probabilistic model. We obtain a Bayesian model of the system's dynamics which is able to report its uncertainty in regions where the data is scarce. The automated approach, the modeling of uncertainty and its relatively low computational cost make of GP-FNARX a good candidate for applications in robotics and adaptive control.
Approximating 1-dimensional TSP Requires Omega(n log n) Comparisons
Venue: arXiv cs.DS 2013
Year: 2013

We give a short proof that any comparison-based n^(1-epsilon)-approximation algorithm for the 1-dimensional Traveling Salesman Problem (TSP) requires Omega(n log n) comparisons.
Interference Networks: A Complex System View
Venue: arXiv cs.IT 2013
Year: 2013

This paper presents an unusual view of interference wireless networks based on complex system thinking. To proceed with this analysis, a literature review of the different applications of complex systems is firstly presented to illustrate how such an approach can be used in a wide range of research topics, from economics to linguistics. Then the problem of quantifying the fundamental limits of wireless systems where the co-channel interference is the main limiting factor is described and hence contextualized in the perspective of complex systems. Specifically some possible internal and external pressures that the network elements may suffer are identified as, for example, queue stability, maximum packet loss rate and transmit power constraint. Besides, other important external factors such as mobility and incoming traffic are also pointed out. As a study case, a decentralized point-to-point interference network is described and several claims about the optimal design setting for different network states and under two mobility conditions, namely quasi-static and highly mobile, are stated based on results found in the literature. Using these claims as a background, the design of a robust adaptive algorithm that each network element should run is investigated.
Stochastic Service Curve and Delay Bound Analysis: A Single Node Case
Venue: arXiv cs.PF 2013
Year: 2013

A packet-switched network node with constant capacity (in bps) is considered, where packets within each flow are served in the first in first out (FIFO) manner. While this single node system is perhaps the simplest computer communication system, its stochastic service curve characterization and independent case analysis in the context of stochastic network calculus (snetcal) are still basic and many crucial questions surprisingly remain open. Specifically, when the input is a single flow, what stochastic service curve and delay bound does the node provide? When the considered flow shares the node with another flow, what stochastic service curve and delay bound does the node provide to the considered flow, and if the two flows are independent, can this independence be made use of and how? The aim of this paper is to provide answers to these fundamental questions.
Adaptive Transmission Techniques for Mobile Satellite Links
Venue: arXiv cs.OH 2013
Year: 2013

Adapting the transmission rate in an LMS channel is a challenging task because of the relatively fast time variations, of the long delays involved, and of the difficulty in mapping the parameters of a time-varying channel into communication performance. In this paper, we propose two strategies for dealing with these impairments, namely, multi-layer coding (MLC) in the forward link, and open-loop adaptation in the return link. Both strategies rely on physical-layer abstraction tools for predicting the link performance. We will show that, in both cases, it is possible to increase the average spectral efficiency while at the same time keeping the outage probability under a given threshold. To do so, the forward link strategy will rely on introducing some latency in the data stream by using retransmissions. The return link, on the other hand, will rely on a statistical characterization of a physical-layer abstraction measure.
Egocentric vision IT technologies for Alzheimer disease assessment and studies
Venue: arXiv cs.HC 2013
Year: 2013

Egocentric vision technology consists in capturing the actions of persons from their own visual point of view using wearable camera sensors. We apply this new paradigm to instrumental activities monitoring with the objective of providing new tools for the clinical evaluation of the impact of the disease on persons with dementia. In this paper, we introduce the current state of the development of this technology and focus on two technology modules: automatic location estimation and visual saliency estimation for content interpretation.
A Greedy Approximation of Bayesian Reinforcement Learning with Probably Optimistic Transition Model
Venue: arXiv cs.AI 2013
Year: 2013

Bayesian Reinforcement Learning (RL) is capable of not only incorporating domain knowledge, but also solving the exploration-exploitation dilemma in a natural way. As Bayesian RL is intractable except for special cases, previous work has proposed several approximation methods. However, these methods are usually too sensitive to parameter values, and finding an acceptable parameter setting is practically impossible in many applications. In this paper, we propose a new algorithm that greedily approximates Bayesian RL to achieve robustness in parameter space. We show that for a desired learning behavior, our proposed algorithm has a polynomial sample complexity that is lower than those of existing algorithms. We also demonstrate that the proposed algorithm naturally outperforms other existing algorithms when the prior distributions are not significantly misleading. On the other hand, the proposed algorithm cannot handle greatly misspecified priors as well as the other algorithms can. This is a natural consequence of the fact that the proposed algorithm is greedier than the other algorithms. Accordingly, we discuss a way to select an appropriate algorithm for different tasks based on the algorithms' greediness. We also introduce a new way of simplifying Bayesian planning, based on which future work would be able to derive new algorithms.
The complexity of proving that a graph is Ramsey
Venue: arXiv cs.CC 2013
Year: 2013

We say that a graph with $n$ vertices is $c$-Ramsey if it does not contain either a clique or an independent set of size $c \log n$. We define a CNF formula which expresses this property for a graph $G$. We show a superpolynomial lower bound on the length of resolution proofs that $G$ is $c$-Ramsey, for every graph $G$. Our proof makes use of the fact that every Ramsey graph must contain a large subgraph with some of the statistical properties of the random graph.
Nets, relations and linking diagrams
Venue: arXiv cs.LO 2013
Year: 2013

In recent work, the author and others have studied compositional algebras of Petri nets. Here we consider mathematical aspects of the pure linking algebras that underly them. We characterise composition of nets without places as the composition of spans over appropriate categories of relations, and study the underlying algebraic structures.
An Optimal Randomized Online Algorithm for Reordering Buffer Management
Venue: arXiv cs.DS 2013
Year: 2013

We give an $O(\log\log k)$-competitive randomized online algorithm for reordering buffer management, where $k$ is the buffer size. Our bound matches the lower bound of Adamaszek et al. (STOC 2011). Our algorithm has two stages which are executed online in parallel. The first stage computes deterministically a feasible fractional solution to an LP relaxation for reordering buffer management. The second stage "rounds" using randomness the fractional solution. The first stage is based on the online primal-dual schema, combined with a dual fitting argument. As multiplicative weights steps and dual fitting steps are interleaved and in some sense conflicting, combining them is challenging. We also note that we apply the primal-dual schema to a relaxation with mixed packing and covering constraints. We pay the $O(\log\log k)$ competitive factor for the gap between the computed LP solution and the optimal LP solution. The second stage gives an online algorithm that converts the LP solution to an integral solution, while increasing the cost by an O(1) factor. This stage generalizes recent results that gave a similar approximation factor for rounding the LP solution, albeit using an offline rounding algorithm.
New modular multiplication and division algorithms based on continued fraction expansion
Venue: arXiv cs.DS 2013
Year: 2013

In this paper, we apply results on number systems based on continued fraction expansions to modular arithmetic. We provide two new algorithms in order to compute modular multiplication and modular division. The presented algorithms are based on the Euclidean algorithm and are of quadratic complexity.
Integer Space-Time Block Codes for Practical MIMO Systems
Venue: arXiv cs.IT 2013
Year: 2013

Full-rate space-time block codes (STBCs) achieve high spectral-efficiency by transmitting linear combinations of information symbols through every transmit antenna. However, the coefficients used for the linear combinations, if not chosen carefully, results in ({\em i}) large number of processor bits for the encoder and ({\em ii}) high peak-to-average power ratio (PAPR) values. In this work, we propose a new class of full-rate STBCs called Integer STBCs (ICs) for multiple-input multiple-output (MIMO) fading channels. A unique property of ICs is the presence of integer coefficients in the code structure which enables reduced numbers of processor bits for the encoder and lower PAPR values. We show that the reduction in the number of processor bits is significant for small MIMO channels, while the reduction in the PAPR is significant for large MIMO channels. We also highlight the advantages of the proposed codes in comparison with the well known full-rate algebraic STBCs.
Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of Chip-firing game on directed graphs
Venue: arXiv cs.CC 2013
Year: 2013

In this paper we present further studies of recurrent configurations of Chip-firing games on Eulerian directed graphs (simple digraphs), a class on the way from undirected graphs to general directed graphs. A computational problem that arises naturally from this model is to find the minimum number of chips of a recurrent configuration, which we call the minimum recurrent configuration (MINREC) problem. We point out a close relationship between MINREC and the minimum feedback arc set (MINFAS) problem on Eulerian directed graphs, and prove that both problems are NP-hard.
Using Serious Games to Train Evacuation Behaviour
Venue: arXiv cs.MA 2013
Year: 2013

Emergency evacuation plans and evacuation drills are mandatory in public buildings in many countries. Their importance is considerable when it comes to guarantee safety and protection during a crisis. However, sometimes discrepancies arise between the goals of the plan and its outcomes, because people find it hard to take them very seriously, or due to the financial and time resources required. Serious games are a possible solution to tackle this problem. They have been successfully applied in different areas such as health care and education, since they can simulate an environment/task quite accurately, making them a practical alternative to real-life simulations. This paper presents a serious game developed using Unity3D to recreate a virtual fire evacuation training tool. The prototype application was deployed which allowed the validation by user testing. A sample of 30 individuals tested the evacuating scenario, having to leave the building during a fire in the shortest time possible. Results have shown that users effectively end up learning some evacuation procedures from the activity, even if only to look for emergency signs indicating the best evacuation paths. It was also evidenced that users with higher video game experience had a significantly better performance.
Low-Complexity Channel Estimation with Set-Membership Algorithms for Cooperative Wireless Sensor Networks
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we consider a general cooperative wireless sensor network (WSN) with multiple hops and the problem of channel estimation. Two matrix-based set-membership algorithms are developed for the estimation of the complex matrix channel parameters. The main goal is to reduce the computational complexity significantly as compared with existing channel estimators and extend the lifetime of the WSN by reducing its power consumption. The first proposed algorithm is the set-membership normalized least mean squares (SM-NLMS) algorithm. The second is the set-membership recursive least squares (RLS) algorithm called BEACON. Then, we present and incorporate an error bound function into the two channel estimation methods which can adjust the error bound automatically with the update of the channel estimates. Steady-state analysis in the output mean-squared error (MSE) are presented and closed-form formulae for the excess MSE and the probability of update in each recursion are provided. Computer simulations show good performance of our proposed algorithms in terms of convergence speed, steady state mean square error and bit error rate (BER) and demonstrate reduced complexity and robustness against the time-varying environments and different signal-to-noise ratio (SNR) values.
An improved semantic similarity measure for document clustering based on topic maps
Venue: arXiv cs.IR 2013
Year: 2013

A major computational burden, while performing document clustering, is the calculation of similarity measure between a pair of documents. Similarity measure is a function that assigns a real number between 0 and 1 to a pair of documents, depending upon the degree of similarity between them. A value of zero means that the documents are completely dissimilar whereas a value of one indicates that the documents are practically identical. Traditionally, vector-based models have been used for computing the document similarity. The vector-based models represent several features present in documents. These approaches to similarity measures, in general, cannot account for the semantics of the document. Documents written in human languages contain contexts and the words used to describe these contexts are generally semantically related. Motivated by this fact, many researchers have proposed seman-tic-based similarity measures by utilizing text annotation through external thesauruses like WordNet (a lexical database). In this paper, we define a semantic similarity measure based on documents represented in topic maps. Topic maps are rapidly becoming an industrial standard for knowledge representation with a focus for later search and extraction. The documents are transformed into a topic map based coded knowledge and the similarity between a pair of documents is represented as a correlation between the common patterns (sub-trees). The experimental studies on the text mining datasets reveal that this new similarity measure is more effective as compared to commonly used similarity measures in text clustering.
Generalized parallel concatenated block codes based on BCH and RS codes, construction and Iterative decoding
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, a generalization of parallel concatenated block GPCB codes based on BCH and RS codes is presented.
On the Use of Key Assignment Schemes in Authentication Protocols
Venue: arXiv cs.CR 2013
Year: 2013

Key Assignment Schemes (KASs) have been extensively studied in the context of cryptographically-enforced access control, where derived keys are used to decrypt protected resources. In this paper, we explore the use of KASs in entity authentication protocols, where we use derived keys to encrypt challenges. This novel use of KASs permits the efficient authentication of an entity in accordance with an authentication policy by associating entities with security labels representing specific services. Cryptographic keys are associated with each security label and demonstrating knowledge of an appropriate key is used as the basis for authentication. Thus, by controlling the distribution of such keys, restrictions may be efficiently placed upon the circumstances under which an entity may be authenticated and the services to which they may gain access. In this work, we explore how both standardized protocols and novel constructions may be developed to authenticate entities as members of a group associated to a particular security label, whilst protecting the long-term secrets in the system. We also see that such constructions may allow for authentication whilst preserving anonymity, and that by including a trusted third party we can achieve the authentication of individual identities and authentication based on timestamps without the need for synchronized clocks.
Perfectly load-balanced, optimal, stable, parallel merge
Venue: arXiv cs.DC 2013
Year: 2013

We present a simple, work-optimal and synchronization-free solution to the problem of stably merging in parallel two given, ordered arrays of m and n elements into an ordered array of m+n elements. The main contribution is a new, simple, fast and direct algorithm that determines, for any prefix of the stably merged output sequence, the exact prefixes of each of the two input sequences needed to produce this output prefix. More precisely, for any given index (rank) in the resulting, but not yet constructed output array representing an output prefix, the algorithm computes the indices (co-ranks) in each of the two input arrays representing the required input prefixes without having to merge the input arrays. The co-ranking algorithm takes O(log min(m,n)) time steps. The algorithm is used to devise a perfectly load-balanced, stable, parallel merge algorithm where each of p processing elements has exactly the same number of input elements to merge. Compared to other approaches to the parallel merge problem, our algorithm is considerably simpler and can be faster up to a factor of two. Compared to previous algorithms for solving the co-ranking problem, the algorithm given here is direct and maintains stability in the presence of repeated elements at no extra space or time cost. When the number of processing elements p does not exceed (m+n)/log min(m,n), the parallel merge algorithm has optimal speedup. It is easy to implement on both shared and distributed memory parallel systems.
Group-Based Trajectory Modeling of Citations in Scholarly Literature: Dynamic Qualities of "Transient" and "Sticky Knowledge Claims"
Venue: arXiv cs.DL 2013
Year: 2013

Group-based Trajectory Modeling (GBTM) is applied to the citation curves of articles in six journals and to all citable items in a single field of science (Virology, 24 journals), in order to distinguish among the developmental trajectories in subpopulations. Can highly-cited citation patterns be distinguished in an early phase as "fast-breaking" papers? Can "late bloomers" or "sleeping beauties" be identified? Most interesting, we find differences between "sticky knowledge claims" that continue to be cited more than ten years after publication, and "transient knowledge claims" that show a decay pattern after reaching a peak within a few years. Only papers following the trajectory of a "sticky knowledge claim" can be expected to have a sustained impact. These findings raise questions about indicators of "excellence" that use aggregated citation rates after two or three years (e.g., impact factors). Because aggregated citation curves can also be composites of the two patterns, 5th-order polynomials (with four bending points) are needed to capture citation curves precisely. For the journals under study, the most frequently cited groups were furthermore much smaller than ten percent. Although GBTM has proved a useful method for investigating differences among citation trajectories, the methodology does not enable us to define a percentage of highly-cited papers inductively across different fields and journals. Using multinomial logistic regression, we conclude that predictor variables such as journal names, number of authors, etc., do not affect the stickiness of knowledge claims in terms of citations, but only the levels of aggregated citations (that are field-specific).
Design of Binary Network Codes for Multi-user Multi-way Relay Networks
Venue: arXiv cs.IT 2013
Year: 2013

We study multi-user multi-way relay networks where $N$ user nodes exchange their information through a single relay node. We use network coding in the relay to increase the throughput. Due to the limitation of complexity, we only consider the binary multi-user network coding (BMNC) in the relay. We study BMNC matrix (in GF(2)) and propose several design criteria on the BMNC matrix to improve the symbol error probability (SEP) performance. Closed-form expressions of the SEP of the system are provided. Moreover, an upper bound of the SEP is also proposed to provide further insights on system performance. Then BMNC matrices are designed to minimize the error probabilities.