OpenRaiser/Intern-Atlas huggingface dataset:
Performance of Spatial Modulation using Measured Real-World Channels
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, for the first time real-world channel measurements are used to analyse the performance of spatial modulation (SM), where a full analysis of the average bit error rate performance (ABER) of SM using measured urban correlated and uncorrelated Rayleigh fading channels is provided. The channel measurements are taken from an outdoor urban multiple input multiple output (MIMO) measurement campaign. Moreover, ABER performance results using simulated Rayleigh fading channels are provided and compared with a derived analytical bound for the ABER of SM, and the ABER results for SM using the measured urban channels. The ABER results using the measured urban channels validate the derived analytical bound and the ABER results using the simulated channels. Finally, the ABER of SM is compared with the performance of spatial multiplexing (SMX) using the measured urban channels for small and large scale MIMO. It is shown that SM offers nearly the same or a slightly better performance than SMX for small scale MIMO. However, SM offers large reduction in ABER for large scale MIMO.
A Comparison of Maps Application Programming Interfaces
Venue: arXiv cs.SE 2013
Year: 2013

The development of web applications that manipulate geo-referenced information is often supported by Application Programming Interfaces (APIs), al-lowing a fast development cycle for high quality applications. APIs can be used by programmers with different expertise levels and choosing an adequate API may have a dramatic impact on the productivity achieved by those programmers. Our goal is to compare maps APIs with respect to their usability. We compare three different APIs: the Google Maps JavaScript API, the ArcGIS API for JavaScript, and the OpenLayers JavaScript Mapping Library. Our comparison is supported by a set of software metrics and is performed in two orthogonal ways: the comparison of three implementations of the same system prototype, each using one of the APIs under scrutiny; the comparison of the APIs specifications. The main results of the study are related to the size of the APIs, with the Google API being significantly smaller than the others.
Stationary analysis of the "Shortest Queue First" service policy: the asymmetric case
Venue: arXiv cs.PF 2013
Year: 2013

As a follow-up to a recent paper considering two symmetric queues, the \textit{Shortest Queue First} service discipline is presently analysed for two general asymmetric queues. Using the results previously established and assuming exponentially distributed service times, the bivariate Laplace transform of workloads in each queue is shown to depend on the solution $\mathbf{M}$ to a two-dimensional functional equation $$ \mathbf{M} = Q_1 \cdot \mathbf{M}\circ h_1 + Q_2 \cdot \mathbf{M}\circ h_2 + \mathbf{L} $$ with given matrices $Q_1$, $Q_2$ and vector $\mathbf{L}$ and where functions $h_1$ and $h_2$ are defined each on some rational curve; solution $\mathbf{M}$ can then represented by a series expansion involving the semi-group $< h_1, h_2 >$ generated by these two functions. The empty queue probabilities along with the tail behaviour of the workload distribution at each queue are characterised.
Admissibility in Finitely Generated Quasivarieties
Venue: arXiv cs.LO 2013
Year: 2013

Checking the admissibility of quasiequations in a finitely generated (i.e., generated by a finite set of finite algebras) quasivariety Q amounts to checking validity in a suitable finite free algebra of the quasivariety, and is therefore decidable. However, since free algebras may be large even for small sets of small algebras and very few generators, this naive method for checking admissibility in $\Q$ is not computationally feasible. In this paper, algorithms are introduced that generate a minimal (with respect to a multiset well-ordering on their cardinalities) finite set of algebras such that the validity of a quasiequation in this set corresponds to admissibility of the quasiequation in Q. In particular, structural completeness (validity and admissibility coincide) and almost structural completeness (validity and admissibility coincide for quasiequations with unifiable premises) can be checked. The algorithms are illustrated with a selection of well-known finitely generated quasivarieties, and adapted to handle also admissibility of rules in finite-valued logics.
Analysis of a non-work conserving Generalized Processor Sharing queue
Venue: arXiv cs.PF 2013
Year: 2013

We consider in this paper a non work-conserving Generalized Processor Sharing (GPS) system composed of two queues with Poisson arrivals and exponential service times. Using general results due to Fayolle \emph{et al}, we first establish the stability condition for this system. We then determine the functional equation satisfied by the generating function of the numbers of jobs in both queues and the associated Riemann-Hilbert problem. We prove the existence and the uniqueness of the solution. This allows us to completely characterize the system, in particular to compute the empty queue probability. We finally derive the tail asymptotics of the number of jobs in one queue.
Cooperative Relaying in a Poisson Field of Interferers: A Diversity Order Analysis
Venue: arXiv cs.IT 2013
Year: 2013

This work analyzes the gains of cooperative relaying in interference-limited networks, in which outages can be due to interference and fading. A stochastic model based on point process theory is used to capture the spatial randomness present in contemporary wireless networks. Using a modification of the diversity order metric, the reliability gain of selection decode-and-forward is studied for several cases. The main results are as follows: the achievable \emph{spatial-contention} diversity order (SC-DO) is equal to one irrespective of the type of channel which is due to the ineffectiveness of the relay in the MAC-phase (transmit diversity). In the BC-phase (receive diversity), the SC-DO depends on the amount of fading and spatial interference correlation. In the absence of fading, there is a hard transition between SC-DO of either one or two, depending on the system parameters.
The Thinnest Path Problem
Venue: arXiv cs.NI 2013
Year: 2013

We formulate and study the thinnest path problem in wireless ad hoc networks. The objective is to find a path from a source to its destination that results in the minimum number of nodes overhearing the message by a judicious choice of relaying nodes and their corresponding transmission power. We adopt a directed hypergraph model of the problem and establish the NP-completeness of the problem in 2-D networks. We then develop two polynomial-time approximation algorithms that offer $\sqrt{\frac{n}{2}}$ and $\frac{n}{2\sqrt{n-1}}$ approximation ratios for general directed hypergraphs (which can model non-isomorphic signal propagation in space) and constant approximation ratios for ring hypergraphs (which result from isomorphic signal propagation). We also consider the thinnest path problem in 1-D networks and 1-D networks embedded in 2-D field of eavesdroppers with arbitrary unknown locations (the so-called 1.5-D networks). We propose a linear-complexity algorithm based on nested backward induction that obtains the optimal solution to both 1-D and 1.5-D networks. This algorithm does not require the knowledge of eavesdropper locations and achieves the best performance offered by any algorithm that assumes complete location information of the eavesdroppers.
3SUM, 3XOR, Triangles
Venue: arXiv cs.CC 2013
Year: 2013

We show that if one can solve 3SUM on a set of size n in time n^{1+\e} then one can list t triangles in a graph with m edges in time O(m^{1+\e}t^{1/3-\e/3}). This is a reversal of Patrascu's reduction from 3SUM to listing triangles (STOC '10). Our result builds on and extends works by the Paghs (PODS '06) and by Vassilevska and Williams (FOCS '10). We make our reductions deterministic using tools from pseudorandomness. We then re-execute both Patrascu's reduction and our reversal for the variant 3XOR of 3SUM where integer summation is replaced by bit-wise xor. As a corollary we obtain that if 3XOR is solvable in linear time but 3SUM requires quadratic randomized time, or vice versa, then the randomized time complexity of listing m triangles in a graph with $m$ edges is m^{4/3} up to a factor m^αfor any α> 0.
Geometric primitive feature extraction - concepts, algorithms, and applications
Venue: arXiv cs.CV 2013
Year: 2013

This thesis presents important insights and concepts related to the topic of the extraction of geometric primitives from the edge contours of digital images. Three specific problems related to this topic have been studied, viz., polygonal approximation of digital curves, tangent estimation of digital curves, and ellipse fitting anddetection from digital curves. For the problem of polygonal approximation, two fundamental problems have been addressed. First, the nature of the performance evaluation metrics in relation to the local and global fitting characteristics has been studied. Second, an explicit error bound of the error introduced by digitizing a continuous line segment has been derived and used to propose a generic non-heuristic parameter independent framework which can be used in several dominant point detection methods. For the problem of tangent estimation for digital curves, a simple method of tangent estimation has been proposed. It is shown that the method has a definite upper bound of the error for conic digital curves. It has been shown that the method performs better than almost all (seventy two) existing tangent estimation methods for conic as well as several non-conic digital curves. For the problem of fitting ellipses on digital curves, a geometric distance minimization model has been considered. An unconstrained, linear, non-iterative, and numerically stable ellipse fitting method has been proposed and it has been shown that the proposed method has better selectivity for elliptic digital curves (high true positive and low false positive) as compared to several other ellipse fitting methods. For the problem of detecting ellipses in a set of digital curves, several innovative and fast pre-processing, grouping, and hypotheses evaluation concepts applicable for digital curves have been proposed and combined to form an ellipse detection method.
Exact Recovery Conditions for Sparse Representations with Partial Support Information
Venue: arXiv cs.IT 2013
Year: 2013

We address the exact recovery of a k-sparse vector in the noiseless setting when some partial information on the support is available. This partial information takes the form of either a subset of the true support or an approximate subset including wrong atoms as well. We derive a new sufficient and worst-case necessary (in some sense) condition for the success of some procedures based on lp-relaxation, Orthogonal Matching Pursuit (OMP) and Orthogonal Least Squares (OLS). Our result is based on the coherence "mu" of the dictionary and relaxes the well-known condition mu<1/(2k-1) ensuring the recovery of any k-sparse vector in the non-informed setup. It reads mu<1/(2k-g+b-1) when the informed support is composed of g good atoms and b wrong atoms. We emphasize that our condition is complementary to some restricted-isometry based conditions by showing that none of them implies the other. Because this mutual coherence condition is common to all procedures, we carry out a finer analysis based on the Null Space Property (NSP) and the Exact Recovery Condition (ERC). Connections are established regarding the characterization of lp-relaxation procedures and OMP in the informed setup. First, we emphasize that the truncated NSP enjoys an ordering property when p is decreased. Second, the partial ERC for OMP (ERC-OMP) implies in turn the truncated NSP for the informed l1 problem, and the truncated NSP for p<1.
Air Dominance in Sensor Networks: Guarding Sensor Motes using Selective Interference
Venue: arXiv cs.NI 2013
Year: 2013

Securing wireless sensor networks (WSNs) is a hard problem. In particular, network access control is notoriously difficult to achieve due to the inherent broadcast characteristics of wireless communications: an attacker can easily target any node in its transmission range and affect large parts of a sensor network simultaneously. In this paper, we therefore propose a distributed guardian system to protect a WSN based on physically regulating channel access by means of selective interference. The guardians are deployed alongside a sensor network, inspecting all local traffic, classifying packets based on their content, and destroying any malicious packet while still on the air. In that sense, the system tries to gain "air dominance" over attackers. A key challenge in implementing the guardian system is the resulting real-time requirement in order to classify and destroy packets during transmission. We present a USRP2 software radio based guardian implementation for IEEE 802.15.4 that meets this challenge; using an FPGA-based design we can even check for the content of the very last payload byte of a packet and still prevent its reception by a potential victim mote. Our evaluation shows that the guardians effectively block 99.9% of unauthorized traffic in 802.15.4 networks in our experiments, without disturbing the legitimate operations of the WSN.
Signature Generation for Sensitive Information Leakage in Android Applications
Venue: arXiv cs.CR 2013
Year: 2013

In recent years, there has been rapid growth in mobile devices such as smartphones, and a number of applications are developed specifically for the smartphone market. In particular, there are many applications that are ``free'' to the user, but depend on advertisement services for their revenue. Such applications include an advertisement module - a library provided by the advertisement service - that can collect a user's sensitive information and transmit it across the network. Users accept this business model, but in most cases the applications do not require the user's acknowledgment in order to transmit sensitive information. Therefore, such applications' behavior becomes an invasion of privacy. In our analysis of 1,188 Android applications' network traffic and permissions, 93% of the applications we analyzed connected to multiple destinations when using the network. 61% required a permission combination that included both access to sensitive information and use of networking services. These applications have the potential to leak the user's sensitive information. In an effort to enable users to control the transmission of their private information, we propose a system which, using a novel clustering method based on the HTTP packet destination and content distances, generates signatures from the clustering result and uses them to detect sensitive information leakage from Android applications. Our system does not require an Android framework modification or any special privileges. Thus users can easily introduce our system to their devices, and manage suspicious applications' network behavior in a fine grained manner. Our system accurately detected 94% of the sensitive information leakage from the applications evaluated and produced only 5% false negative results, and less than 3% false positive results.
Rank metric and Gabidulin codes in characteristic zero
Venue: arXiv cs.IT 2013
Year: 2013

We transpose the theory of rank metric and Gabidulin codes to the case of fields of characteristic zero. The Frobenius automorphism is then replaced by any element of the Galois group. We derive some conditions on the automorphism to be able to easily transpose the results obtained by Gabidulin as well and a classical polynomial-time decoding algorithm. We also provide various definitions for the rank-metric.
Modeling and optimizing a distributed power network : A complex system approach of the prosumer management in the smart grid
Venue: arXiv cs.SY 2013
Year: 2013

One of the most important goals of the 21st century is to change radically the way our society produces and distributes energy. This broad objective embodies in the smart grid's futuristic vision of a completely decentralized system powered by renewable plants. Imagine indeed such a real time power network in which everyone could be a consumer or a producer. Based on a coupled information system, each user would be able to buy or sell energy at a time depending price that would allow a homogenization of the consumption, eradicating the well known morning or evening peak. This attractive idea is currently booming in the scientific community as it generates intellectual challenges in various domains. Nevertheless, lots of unanswered questions remain. The first steps are currently accomplished with the appearance of smart meters or the development of more efficient energy storage devices. However, the design of the decentralized information system of the smart grid, which will have to deal with huge amounts of sensor's data in order to control the system within its stability region, seems to be still in search. In the following survey, we concentrate on the telecommunication part of the smart grid system. We begin by identifying different control level in the system, and we focus on high control levels, which are commonly attributed to the information system. We then define a few concepts of the smart grid and present some interesting approaches using models from the complex system theory. In the last part, we review ongoing works aiming at establishing telecommunication requirements for smart grid applications, and underline the necessity of building accountable models for testing these values.
Trading Performance for Stability in Markov Decision Processes
Venue: arXiv cs.SY 2013
Year: 2013

We study the complexity of central controller synthesis problems for finite-state Markov decision processes, where the objective is to optimize both the expected mean-payoff performance of the system and its stability. We argue that the basic theoretical notion of expressing the stability in terms of the variance of the mean-payoff (called global variance in our paper) is not always sufficient, since it ignores possible instabilities on respective runs. For this reason we propose alernative definitions of stability, which we call local and hybrid variance, and which express how rewards on each run deviate from the run's own mean-payoff and from the expected mean-payoff, respectively. We show that a strategy ensuring both the expected mean-payoff and the variance below given bounds requires randomization and memory, under all the above semantics of variance. We then look at the problem of determining whether there is a such a strategy. For the global variance, we show that the problem is in PSPACE, and that the answer can be approximated in pseudo-polynomial time. For the hybrid variance, the analogous decision problem is in NP, and a polynomial-time approximating algorithm also exists. For local variance, we show that the decision problem is in NP. Since the overall performance can be traded for stability (and vice versa), we also present algorithms for approximating the associated Pareto curve in all the three cases. Finally, we study a special case of the decision problems, where we require a given expected mean-payoff together with zero variance. Here we show that the problems can be all solved in polynomial time.
Local Messages for Smartphones
Venue: arXiv cs.NI 2013
Year: 2013

This paper describes a new model for local messaging based on the network proximity. We present a novelty mobile mashup which combines Wi-Fi proximity measurements with Cloud Messaging. Our mobile mashup combines passive monitoring for smart phones and cloud based messaging for mobile operational systems. Passive monitoring can determine the location of mobile subscribers (mobile phones, actually) without the active participation of mobile users. This paper describes how to combine the passive monitoring and notifications.
Independent set in categorical products of cographs and splitgraphs
Venue: arXiv cs.DM 2013
Year: 2013

We show that there are polynomial-time algorithms to compute maximum independent sets in the categorical products of two cographs and two splitgraphs. We show that the ultimate categorical independence ratio is computable in polynomial time for cographs.
Relay Selection for Bidirectional AF Relay Network with Outdated CSI
Venue: arXiv cs.IT 2013
Year: 2013

Most previous researches on bidirectional relay selection (RS) typically assume perfect channel state information (CSI). However, outdated CSI, caused by the the time-variation of channel, cannot be ignored in the practical system, and it will deteriorate the performance. In this paper, the effect of outdated CSI on the performance of bidirectional amplify-and-forward RS is investigated. The optimal single RS scheme in minimizing the symbol error rate (SER) is revised by incorporating the outdated channels. The analytical expressions of end-to-end signal to noise ratio (SNR) and symbol error rate (SER) are derived in a closed-form, along with the asymptotic SER expression in high SNR. All the analytical expressions are verified by the Monte-Carlo simulations. The analytical and the simulation results reveal that once CSI is outdated, the diversity order degrades to one from full diversity. Furthermore, a multiple RS scheme is proposed and verified that this scheme is a feasible solution to compensate the diversity loss caused by outdated CSI.
Horizon-Independent Optimal Prediction with Log-Loss in Exponential Families
Venue: arXiv cs.LG 2013
Year: 2013

We study online learning under logarithmic loss with regular parametric models. Hedayati and Bartlett (2012b) showed that a Bayesian prediction strategy with Jeffreys prior and sequential normalized maximum likelihood (SNML) coincide and are optimal if and only if the latter is exchangeable, and if and only if the optimal strategy can be calculated without knowing the time horizon in advance. They put forward the question what families have exchangeable SNML strategies. This paper fully answers this open problem for one-dimensional exponential families. The exchangeability can happen only for three classes of natural exponential family distributions, namely the Gaussian, Gamma, and the Tweedie exponential family of order 3/2. Keywords: SNML Exchangeability, Exponential Family, Online Learning, Logarithmic Loss, Bayesian Strategy, Jeffreys Prior, Fisher Information1
Computing class polynomials for abelian surfaces
Venue: arXiv cs.CR 2013
Year: 2013

We describe a quasi-linear algorithm for computing Igusa class polynomials of Jacobians of genus 2 curves via complex floating-point approximations of their roots. After providing an explicit treatment of the computations in quartic CM fields and their Galois closures, we pursue an approach due to Dupont for evaluating $θ$- constants in quasi-linear time using Newton iterations on the Borchardt mean. We report on experiments with our implementation and present an example with class number 17608.
Software Requirements Specification - Softbody Simulation System
Venue: arXiv cs.SE 2013
Year: 2013

The purpose of this document is to give the vision for interactive computer graphics physical based simulation systems. It focuses on the needs of stakeholders and the reasons for such needs.
Reconstruction and Repair Degree of Fractional Repetition Codes
Venue: arXiv cs.IT 2013
Year: 2013

Given a Fractional Repetition code, finding the reconstruction and repair degree in a distributed storage system is an important problem. In this work, we present algorithms for computing the reconstruction and repair degree of fractional repetition codes.