OpenRaiser/Intern-Atlas huggingface dataset:
Utility Optimization in Heterogeneous Networks via CSMA-Based Algorithms
Venue: arXiv cs.NI 2013
Year: 2013

We study algorithms for carrier and rate allocation in cellular systems with distributed components such as a heterogeneous LTE system with macrocells and femtocells. Existing work on LTE systems often involves centralized techniques or requires significant signaling, and is therefore not always applicable in the presence of femtocells. More distributed CSMA-based algorithms (carrier-sense multiple access) were developed in the context of 802.11 systems and have been proven to be utility optimal. However, the proof typically assumes a single transmission rate on each carrier. Further, it relies on the CSMA collision detection mechanisms to know whether a transmission is feasible. In this paper we present a framework for LTE scheduling that is based on CSMA techniques. In particular we first prove that CSMA-based algorithms can be generalized to handle multiple transmission rates in a multi-carrier setting while maintaining utility optimality. We then show how such an algorithm can be implemented in a heterogeneous LTE system where the existing Channel Quality Indication (CQI) mechanism is used to decide transmission feasibility.
Application of three graph Laplacian based semi-supervised learning methods to protein function prediction problem
Venue: arXiv cs.LG 2013
Year: 2013

Protein function prediction is the important problem in modern biology. In this paper, the un-normalized, symmetric normalized, and random walk graph Laplacian based semi-supervised learning methods will be applied to the integrated network combined from multiple networks to predict the functions of all yeast proteins in these multiple networks. These multiple networks are network created from Pfam domain structure, co-participation in a protein complex, protein-protein interaction network, genetic interaction network, and network created from cell cycle gene expression measurements. Multiple networks are combined with fixed weights instead of using convex optimization to determine the combination weights due to high time complexity of convex optimization method. This simple combination method will not affect the accuracy performance measures of the three semi-supervised learning methods. Experiment results show that the un-normalized and symmetric normalized graph Laplacian based methods perform slightly better than random walk graph Laplacian based method for integrated network. Moreover, the accuracy performance measures of these three semi-supervised learning methods for integrated network are much better than the best accuracy performance measures of these three methods for the individual network.
On sensor fusion for airborne wind energy systems
Venue: arXiv cs.SY 2013
Year: 2013

A study on filtering aspects of airborne wind energy generators is presented. This class of renewable energy systems aims to convert the aerodynamic forces generated by tethered wings, flying in closed paths transverse to the wind flow, into electricity. The accurate reconstruction of the wing's position, velocity and heading is of fundamental importance for the automatic control of these kinds of systems. The difficulty of the estimation problem arises from the nonlinear dynamics, wide speed range, large accelerations and fast changes of direction that the wing experiences during operation. It is shown that the overall nonlinear system has a specific structure allowing its partitioning into sub-systems, hence leading to a series of simpler filtering problems. Different sensor setups are then considered, and the related sensor fusion algorithms are presented. The results of experimental tests carried out with a small-scale prototype and wings of different sizes are discussed. The designed filtering algorithms rely purely on kinematic laws, hence they are independent from features like wing area, aerodynamic efficiency, mass, etc. Therefore, the presented results are representative also of systems with larger size and different wing design, different number of tethers and/or rigid wings.
Non-Interference and Local Correctness in Transactional Memory
Venue: arXiv cs.DC 2013
Year: 2013

Transactional memory promises to make concurrent programming tractable and efficient by allowing the user to assemble sequences of actions in atomic transactions with all-or-nothing semantics. It is believed that, by its very virtue, transactional memory must ensure that all committed transactions constitute a serial execution respecting the real-time order. In contrast, aborted or incomplete transactions should not "take effect." But what does "not taking effect" mean exactly? It seems natural to expect that aborted or incomplete transactions do not appear in the global serial execution, and, thus, no committed transaction can be affected by them. We investigate another, less obvious, feature of "not taking effect" called non-interference: aborted or incomplete transactions should not force any other transaction to abort. In the strongest form of non-interference that we explore in this paper, by removing a subset of aborted or incomplete transactions from the history, we should not be able to turn an aborted transaction into a committed one without violating the correctness criterion. We show that non-interference is, in a strict sense, not implementable with respect to the popular criterion of opacity that requires all transactions (be they committed, aborted or incomplete) to witness the same global serial execution. In contrast, when we only require local correctness, non-interference is implementable. Informally, a correctness criterion is local if it only requires that every transaction can be serialized along with (a subset of) the transactions committed before its last event (aborted or incomplete transactions ignored). We give a few examples of local correctness properties, including the recently proposed criterion of virtual world consistency, and present a simple though efficient implementation that satisfies non-interference and local opacity.
On the Performance Bound of Sparse Estimation with Sensing Matrix Perturbation
Venue: arXiv cs.IT 2013
Year: 2013

This paper focusses on the sparse estimation in the situation where both the the sensing matrix and the measurement vector are corrupted by additive Gaussian noises. The performance bound of sparse estimation is analyzed and discussed in depth. Two types of lower bounds, the constrained Cramér-Rao bound (CCRB) and the Hammersley-Chapman-Robbins bound (HCRB), are discussed. It is shown that the situation with sensing matrix perturbation is more complex than the one with only measurement noise. For the CCRB, its closed-form expression is deduced. It demonstrates a gap between the maximal and nonmaximal support cases. It is also revealed that a gap lies between the CCRB and the MSE of the oracle pseudoinverse estimator, but it approaches zero asymptotically when the problem dimensions tend to infinity. For a tighter bound, the HCRB, despite of the difficulty in obtaining a simple expression for general sensing matrix, a closed-form expression in the unit sensing matrix case is derived for a qualitative study of the performance bound. It is shown that the gap between the maximal and nonmaximal cases is eliminated for the HCRB. Numerical simulations are performed to verify the theoretical results in this paper.
Simultaneous Information and Power Transfer for Broadband Wireless Systems
Venue: arXiv cs.IT 2013
Year: 2013

Far-field microwave power transfer (MPT) will free wireless sensors and other mobile devices from the constraints imposed by finite battery capacities. Integrating MPT with wireless communications to support simultaneous information and power transfer (SIPT) allows the same spectrum to be used for dual purposes without compromising the quality of service. A novel approach is presented in this paper for realizing SIPT in a broadband system where orthogonal frequency division multiplexing and transmit beamforming are deployed to create a set of parallel sub-channels for SIPT, which simplifies resource allocation. Supported by a proposed reconfigurable mobile architecture, different system configurations are considered by combining single-user/multiuser systems, downlink/uplink information transfer, and variable/fixed coding rates. Optimizing the power control for these configurations results in a new class of multiuser power-control problems featuring circuit-power constraints, specifying that the transferred power must be sufficiently large to support the operation of the receiver circuitry. Solving these problems gives a set of power-control algorithms that exploit channel diversity in frequency for simultaneously enhancing the throughput and the MPT efficiency. For the system configurations with variable coding rates, the algorithms are variants of water-filling that account for the circuit-power constraints. The optimal algorithms for those configurations with fixed coding rates are shown to sequentially allocate mobiles their required power for decoding in the ascending order until the entire budgeted power is spent. The required power for a mobile is derived as simple functions of the minimum signal-to-noise ratio for correct decoding, the circuit power and sub-channel gains.
TVR - Tall Vehicle Relaying in Vehicular Networks
Venue: arXiv cs.NI 2013
Year: 2013

Vehicle-to-Vehicle (V2V) communication is a core technology for enabling safety and non-safety applications in next generation Intelligent Transportation Systems. Due to relatively low heights of the antennas, V2V communication is often influenced by topographic features, man-made structures, and other vehicles located between the communicating vehicles. On highways, it was shown experimentally that vehicles can obstruct the line of sight (LOS) communication up to 50 percent of the time; furthermore, a single obstructing vehicle can reduce the power at the receiver by more than 20 dB. Based on both experimental measurements and simulations performed using a validated channel model, we show that the elevated position of antennas on tall vehicles improves communication performance. Tall vehicles can significantly increase the effective communication range, with an improvement of up to 50 percent in certain scenarios. Using these findings, we propose a new V2V relaying scheme called Tall Vehicle Relaying (TVR) that takes advantage of better channel characteristics provided by tall vehicles. TVR distinguishes between tall and short vehicles and, where appropriate, chooses tall vehicles as next hop relays. We investigate TVR's system-level performance through a combination of link-level experiments and system-level simulations and show that it outperforms existing techniques.
Layer-wise learning of deep generative models
Venue: arXiv cs.NE 2013
Year: 2013

When using deep, multi-layered architectures to build generative models of data, it is difficult to train all layers at once. We propose a layer-wise training procedure admitting a performance guarantee compared to the global optimum. It is based on an optimistic proxy of future performance, the best latent marginal. We interpret auto-encoders in this setting as generative models, by showing that they train a lower bound of this criterion. We test the new learning procedure against a state of the art method (stacked RBMs), and find it to improve performance. Both theory and experiments highlight the importance, when training deep architectures, of using an inference model (from data to hidden variables) richer than the generative model (from hidden variables to data).
A space efficient streaming algorithm for triangle counting using the birthday paradox
Venue: arXiv cs.DS 2013
Year: 2013

We design a space efficient algorithm that approximates the transitivity (global clustering coefficient) and total triangle count with only a single pass through a graph given as a stream of edges. Our procedure is based on the classic probabilistic result, the birthday paradox. When the transitivity is constant and there are more edges than wedges (common properties for social networks), we can prove that our algorithm requires $O(\sqrt{n})$ space ($n$ is the number of vertices) to provide accurate estimates. We run a detailed set of experiments on a variety of real graphs and demonstrate that the memory requirement of the algorithm is a tiny fraction of the graph. For example, even for a graph with 200 million edges, our algorithm stores just 60,000 edges to give accurate results. Being a single pass streaming algorithm, our procedure also maintains a real-time estimate of the transitivity/number of triangles of a graph, by storing a minuscule fraction of edges.
ConArg: a Tool to Solve (Weighted) Abstract Argumentation Frameworks with (Soft) Constraints
Venue: arXiv cs.AI 2013
Year: 2013

ConArg is a Constraint Programming-based tool that can be used to model and solve different problems related to Abstract Argumentation Frameworks (AFs). To implement this tool we have used JaCoP, a Java library that provides the user with a Finite Domain Constraint Programming paradigm. ConArg is able to randomly generate networks with small-world properties in order to find conflict-free, admissible, complete, stable grounded, preferred, semi-stable, stage and ideal extensions on such interaction graphs. We present the main features of ConArg and we report the performance in time, showing also a comparison with ASPARTIX [1], a similar tool using Answer Set Programming. The use of techniques for constraint solving can tackle the complexity of the problems presented in [2]. Moreover we suggest semiring-based soft constraints as a mean to parametrically represent and solve Weighted Argumentation Frameworks: different kinds of preference levels related to attacks, e.g., a score representing a "fuzziness", a "cost" or a probability, can be represented by choosing different instantiation of the semiring algebraic structure. The basic idea is to provide a common computational and quantitative framework.
Automata for two-variable logic over trees with ordered data values
Venue: arXiv cs.LO 2013
Year: 2013

Data trees are trees in which each node, besides carrying a label from a finite alphabet, also carries a data value from an infinite domain. They have been used as an abstraction model for reasoning tasks on {XML} and verification. However, most existing approaches consider the case where only equality test can be performed on the data values. In this paper we study data trees in which the data values come from a linearly ordered domain, and in addition to equality test, we can test whether the data value in a node is greater than the one in another node. We introduce an automata model for them which we call ordered-data tree automata (ODTA), provide its logical characterisation, and prove that its non-emptiness problem is decidable in 3-NEXPTIME. We also show that the two-variable logic on unranked trees, studied by Bojanczyk, Muscholl, Schwentick and Segoufin in 2009, corresponds precisely to a special subclass of this automata model. Then we define a slightly weaker version of ODTA, which we call weak ODTA, and provide its logical characterisation. The complexity of the non-emptiness problem drops to NP. However, a number of existing formalisms and models studied in the literature can be captured already by weak ODTA. We also show that the definition of ODTA can be easily modified, to the case where the data values come from a tree-like partially ordered domain, such as strings.
The Metadata Anonymization Toolkit
Venue: arXiv cs.CR 2013
Year: 2013

This document summarizes the experience of Julien Voisin during the 2011 edition of the well-known \emph{Google Summer of Code}. This project is a first step in the domain of metadata anonymization in Free Software. This article is articulated in three parts. First, a state of the art and a categorization of usual metadata, then the privacy policy is exposed/discussed in order to find the right balance between information lost and privacy enhancement. Finally, the specification of the Metadata Anonymization Toolkit (MAT) is presented, and future possible works are sketched.
A Categorical Treatment of Ornaments
Venue: arXiv cs.PL 2013
Year: 2013

Ornaments aim at taming the multiplication of special-purpose datatype in dependently-typed theory. In its original form, the definition of ornaments is tied to a particular universe of datatypes. Being a type theoretic object, constructions on ornaments are typically explained through an operational narrative. This overbearing concreteness calls for an abstract model of ornaments. In this paper, we give a categorical model of ornaments. As a necessary first step, we abstract the universe of datatypes using the theory of polynomial functors. We are then able to characterize ornaments as cartesian morphisms between polynomial functors. We thus gain access to powerful mathematical tools that shall help us understand and develop ornaments. We shall also illustrate the adequacy of our model. Firstly, we rephrase the standard ornamental constructions into our framework. Thanks to its conciseness, this process gives us a deeper understanding of the structures at play. Secondly, we develop new ornamental constructions, by translating categorical structures into type theoretic artifacts.
Every locally characterized affine-invariant property is testable
Venue: arXiv cs.CC 2013
Year: 2013

Let F = F_p for any fixed prime p >= 2. An affine-invariant property is a property of functions on F^n that is closed under taking affine transformations of the domain. We prove that all affine-invariant property having local characterizations are testable. In fact, we show a proximity-oblivious test for any such property P, meaning that there is a test that, given an input function f, makes a constant number of queries to f, always accepts if f satisfies P, and rejects with positive probability if the distance between f and P is nonzero. More generally, we show that any affine-invariant property that is closed under taking restrictions to subspaces and has bounded complexity is testable. We also prove that any property that can be described as the property of decomposing into a known structure of low-degree polynomials is locally characterized and is, hence, testable. For example, whether a function is a product of two degree-d polynomials, whether a function splits into a product of d linear polynomials, and whether a function has low rank are all examples of degree-structural properties and are therefore locally characterized. Our results depend on a new Gowers inverse theorem by Tao and Ziegler for low characteristic fields that decomposes any polynomial with large Gowers norm into a function of low-degree non-classical polynomials. We establish a new equidistribution result for high rank non-classical polynomials that drives the proofs of both the testability results and the local characterization of degree-structural properties.
Localization Procedure for Randomly Deployed Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

Wireless Sensor Networks (WSNs) are composed of nodes that gather metrics like temperature, pollution or pressure from events generated by external entities. Localization in WSNs is paramount, given that the collected metrics must be related to the place of occurrence. This document presents an alternative way towards localization in randomly deployed WSNs based on the composability of localization protocols. Results show a totally distributed localization procedure that achieves a higher number of located nodes than the conventional, individual execution of localization protocols while maintaining the same low levels of battery consumption.
Relations among Security Metrics for Template Protection Algorithms
Venue: arXiv cs.CR 2013
Year: 2013

Many biometric template protection algorithms have been proposed mainly in two approaches: biometric feature transformation and biometric cryptosystem. Security evaluation of the proposed algorithms are often conducted in various inconsistent manner. Thus, it is strongly demanded to establish the common evaluation metrics for easier comparison among many algorithms. Simoens et al. and Nagar et al. proposed good metrics covering nearly all aspect of requirements expected for biometric template protection algorithms. One drawback of the two papers is that they are biased to experimental evaluation of security of biometric template protection algorithms. Therefore, it was still difficult mainly for algorithms in biometric cryptosystem to prove their security according to the proposed metrics. This paper will give a formal definitions for security metrics proposed by Simoens et al. and Nagar et al. so that it can be used for the evaluation of both of the two approaches. Further, this paper will discuss the relations among several notions of security metrics.
New Algorithms for Position Heaps
Venue: arXiv cs.DS 2013
Year: 2013

We present several results about position heaps, a relatively new alternative to suffix trees and suffix arrays. First, we show that, if we limit the maximum length of patterns to be sought, then we can also limit the height of the heap and reduce the worst-case cost of insertions and deletions. Second, we show how to build a position heap in linear time independent of the size of the alphabet. Third, we show how to augment a position heap such that it supports access to the corresponding suffix array, and vice versa. Fourth, we introduce a variant of a position heap that can be simulated efficiently by a compressed suffix array with a linear number of extra bits.
Interpolation Properties and SAT-based Model Checking
Venue: arXiv cs.LO 2013
Year: 2013

Craig interpolation is a widespread method in verification, with important applications such as Predicate Abstraction, CounterExample Guided Abstraction Refinement and Lazy Abstraction With Interpolants. Most state-of-the-art model checking techniques based on interpolation require collections of interpolants to satisfy particular properties, to which we refer as "collectives"; they do not hold in general for all interpolation systems and have to be established for each particular system and verification environment. Nevertheless, no systematic approach exists that correlates the individual interpolation systems and compares the necessary collectives. This paper proposes a uniform framework, which encompasses (and generalizes) the most common collectives exploited in verification. We use it for a systematic study of the collectives and of the constraints they pose on propositional interpolation systems used in SAT-based model checking.
Multiple precision evaluation of the Airy Ai function with reduced cancellation
Venue: arXiv cs.SC 2013
Year: 2013

The series expansion at the origin of the Airy function Ai(x) is alternating and hence problematic to evaluate for x > 0 due to cancellation. Based on a method recently proposed by Gawronski, Müller, and Reinhard, we exhibit two functions F and G, both with nonnegative Taylor expansions at the origin, such that Ai(x) = G(x)/F(x). The sums are now well-conditioned, but the Taylor coefficients of G turn out to obey an ill-conditioned three-term recurrence. We use the classical Miller algorithm to overcome this issue. We bound all errors and our implementation allows an arbitrary and certified accuracy, that can be used, e.g., for providing correct rounding in arbitrary precision.