OpenRaiser/Intern-Atlas huggingface dataset:
On the Benefits of Partial Channel State Information for Repetition Protocols in Block Fading Channels
Venue: arXiv cs.IT 2011
Year: 2011

This paper studies the throughput performance of HARQ (hybrid automatic repeat request) protocols over block fading Gaussian channels. It proposes new protocols that use the available feedback bit(s) not only to request a retransmission, but also to inform the transmitter about the instantaneous channel quality. An explicit protocol construction is given for any number of retransmissions and any number of feedback bits. The novel protocol is shown to simultaneously realize the gains of HARQ and of power control with partial CSI (channel state information). Remarkable throughput improvements are shown, especially at low and moderate SNR (signal to noise ratio), with respect to protocols that use the feedback bits for retransmission request only. In particular, for the case of a single retransmission and a single feedback bit, it is shown that the repetition is not needed at low $\snr$ where the throughput improvement is due to power control only. On the other hand, at high SNR, the repetition is useful and the performance gain comes form a combination of power control and ability of make up for deep fades.
An Overview of IEEE 802.15.6 Standard
Venue: arXiv cs.NI 2011
Year: 2011

Wireless Body Area Networks (WBAN) has emerged as a key technology to provide real-time health monitoring of a patient and diagnose many life threatening diseases. WBAN operates in close vicinity to, on, or inside a human body and supports a variety of medical and non-medical applications. IEEE 802 has established a Task Group called IEEE 802.15.6 for the standardization of WBAN. The purpose of the group is to establish a communication standard optimized for low-power in-body/on-body nodes to serve a variety of medical and non-medical applications. This paper explains the most important features of the new IEEE 802.15.6 standard. The standard defines a Medium Access Control (MAC) layer supporting several Physical (PHY) layers. We briefly overview the PHY and MAC layers specifications together with the bandwidth efficiency of IEEE 802.15.6 standard. We also discuss the security paradigm of the standard.
A LTL Fragment for GR(1)-Synthesis
Venue: arXiv cs.LO 2011
Year: 2011

The idea of automatic synthesis of reactive programs starting from temporal logic (LTL) specifications is quite old, but was commonly thought to be infeasible due to the known double exponential complexity of the problem. However, new ideas have recently renewed the interest in LTL synthesis: One major new contribution in this area is the recent work of Piterman et al. who showed how polynomial time synthesis can be achieved for a large class of LTL specifications that is expressive enough to cover many practical examples. These LTL specifications are equivalent to omega-automata having a so-called GR(1) acceptance condition. This approach has been used to automatically synthesize implementations of real-world applications. To this end, manually written deterministic omega-automata having GR(1) conditions were used instead of the original LTL specifications. However, manually generating deterministic monitors is, of course, a hard and error-prone task. In this paper, we therefore present algorithms to automatically translate specifications of a remarkable large fragment of LTL to deterministic monitors having a GR(1) acceptance condition so that the synthesis algorithms can start with more readable LTL specifications.
Multiuser Cognitive Radio Networks: An Information Theoretic Perspective
Venue: arXiv cs.IT 2011
Year: 2011

Achievable rate regions and outer bounds are derived for three-user interference channels where the transmitters cooperate in a unidirectional manner via a noncausal message-sharing mechanism. The three-user channel facilitates different ways of message-sharing between the primary and secondary (or cognitive) transmitters. Three natural extensions of unidirectional message-sharing from two users to three users are introduced: (i) Cumulative message sharing; (ii) primary-only message sharing; and (iii) cognitive-only message sharing. To emphasize the notion of interference management, channels are classified based on different rate-splitting strategies at the transmitters. Standard techniques, superposition coding and Gel'fand-Pinsker's binning principle, are employed to derive an achievable rate region for each of the cognitive interference channels. Simulation results for the Gaussian channel case are presented; they enable visual comparison of the achievable rate regions for different message-sharing schemes along with the outer bounds. These results also provide useful insights into the effect of rate-splitting at the transmitters, which aids in better interference management at the receivers.
Location Cheating: A Security Challenge to Location-based Social Network Services
Venue: arXiv cs.SI 2011
Year: 2011

Location-based mobile social network services such as foursquare and Gowalla have grown exponentially over the past several years. These location-based services utilize the geographical position to enrich user experiences in a variety of contexts, including location-based searching and location-based mobile advertising. To attract more users, the location-based mobile social network services provide real-world rewards to the user, when a user checks in at a certain venue or location. This gives incentives for users to cheat on their locations. In this report, we investigate the threat of location cheating attacks, find the root cause of the vulnerability, and outline the possible defending mechanisms. We use foursquare as an example to introduce a novel location cheating attack, which can easily pass the current location verification mechanism (e.g., cheater code of foursquare). We also crawl the foursquare website. By analyzing the crawled data, we show that automated large scale cheating is possible. Through this work, we aim to call attention to location cheating in mobile social network services and provide insights into the defending mechanisms.
Mixed-Variable Requirements Roadmaps and their Role in the Requirements Engineering of Adaptive Systems
Venue: arXiv cs.SE 2011
Year: 2011

The requirements roadmap concept is introduced as a solution to the problem of the requirements engineering of adaptive systems. The concept requires a new general definition of the requirements problem which allows for quantitative (numeric) variables, together with qualitative (binary boolean) propositional variables, and distinguishes monitored from controlled variables for use in control loops. We study the consequences of these changes, and argue that the requirements roadmap concept bridges the gap between current general definitions of the requirements problem and its notion of solution, and the research into the relaxation of requirements, the evaluation of their partial satisfaction, and the monitoring and control of requirements, all topics of particular interest in the engineering of requirements for adaptive systems [Cheng et al. 2009]. From the theoretical perspective, we show clearly and formally the fundamental differences between more traditional conception of requirements engineering (e.g., Zave & Jackson [1997]) and the requirements engineering of adaptive systems (from Fickas & Feather [1995], over Letier & van Lamsweerde [2004], and up to Whittle et al. [2010] and the most recent research). From the engineering perspective, we define a proto-framework for early requirements engineering of adaptive systems, which illustrates the features needed in future requirements frameworks for this class of systems.
Sparse neural networks with large learning diversity
Venue: arXiv cs.LG 2011
Year: 2011

Coded recurrent neural networks with three levels of sparsity are introduced. The first level is related to the size of messages, much smaller than the number of available neurons. The second one is provided by a particular coding rule, acting as a local constraint in the neural activity. The third one is a characteristic of the low final connection density of the network after the learning phase. Though the proposed network is very simple since it is based on binary neurons and binary connections, it is able to learn a large number of messages and recall them, even in presence of strong erasures. The performance of the network is assessed as a classifier and as an associative memory.
Protein Models Comparator: Scalable Bioinformatics Computing on the Google App Engine Platform
Venue: arXiv cs.CE 2011
Year: 2011

The comparison of computer generated protein structural models is an important element of protein structure prediction. It has many uses including model quality evaluation, selection of the final models from a large set of candidates or optimisation of parameters of energy functions used in template-free modelling and refinement. Although many protein comparison methods are available online on numerous web servers, they are not well suited for large scale model comparison: (1) they operate with methods designed to compare actual proteins, not the models of the same protein, (2) majority of them offer only a single pairwise structural comparison and are unable to scale up to a required order of thousands of comparisons. To bridge the gap between the protein and model structure comparison we have developed the Protein Models Comparator (pm-cmp). To be able to deliver the scalability on demand and handle large comparison experiments the pm-cmp was implemented "in the cloud". Protein Models Comparator is a scalable web application for a fast distributed comparison of protein models with RMSD, GDT TS, TM-score and Q-score measures. It runs on the Google App Engine (GAE) cloud platform and is a showcase of how the emerging PaaS (Platform as a Service) technology could be used to simplify the development of scalable bioinformatics services. The functionality of pm-cmp is accessible through API which allows a full automation of the experiment submission and results retrieval. Protein Models Comparator is free software released on the Affero GNU Public Licence and is available with its source code at: http://www.infobiotics.org/pm-cmp This article presents a new web application addressing the need for a large-scale model-specific protein structure comparison and provides an insight into the GAE (Google App Engine) platform and its usefulness in scientific computing.
On the Semantics of Purpose Requirements in Privacy Policies
Venue: arXiv cs.CR 2011
Year: 2011

Privacy policies often place requirements on the purposes for which a governed entity may use personal information. For example, regulations, such as HIPAA, require that hospital employees use medical information for only certain purposes, such as treatment. Thus, using formal or automated methods for enforcing privacy policies requires a semantics of purpose requirements to determine whether an action is for a purpose or not. We provide such a semantics using a formalism based on planning. We model planning using a modified version of Markov Decision Processes, which exclude redundant actions for a formal definition of redundant. We use the model to formalize when a sequence of actions is only for or not for a purpose. This semantics enables us to provide an algorithm for automating auditing, and to describe formally and compare rigorously previous enforcement methods.
Link Prediction by De-anonymization: How We Won the Kaggle Social Network Challenge
Venue: arXiv cs.CR 2011
Year: 2011

This paper describes the winning entry to the IJCNN 2011 Social Network Challenge run by Kaggle.com. The goal of the contest was to promote research on real-world link prediction, and the dataset was a graph obtained by crawling the popular Flickr social photo sharing website, with user identities scrubbed. By de-anonymizing much of the competition test set using our own Flickr crawl, we were able to effectively game the competition. Our attack represents a new application of de-anonymization to gaming machine learning contests, suggesting changes in how future competitions should be run. We introduce a new simulated annealing-based weighted graph matching algorithm for the seeding step of de-anonymization. We also show how to combine de-anonymization with link prediction---the latter is required to achieve good performance on the portion of the test set not de-anonymized---for example by training the predictor on the de-anonymized portion of the test set, and combining probabilistic predictions from de-anonymization and link prediction.
Modelling the Dynamics of the Work-Employment System by Predator-Prey Interactions
Venue: arXiv cs.CE 2011
Year: 2011

The broad application range of the predator-prey modelling enabled us to apply it to represent the dynamics of the work-employment system. For the adopted period, we conclude that this dynamics is chaotic in the beginning of the time series and tends to less perturbed states, as time goes by, due to public policies and hidden intrinsic system features. Basic Lotka-Volterra approach was revised and adapted to the reality of the study. The final aim is to provide managers with generalized theoretical elements that allow to a more accurate understanding of the behavior of the work-employment system.
Superposition Noisy Network Coding
Venue: arXiv cs.IT 2011
Year: 2011

We present a superposition coding scheme for communication over a network, which combines partial decode and forward and noisy network coding. This hybrid scheme is termed as superposition noisy network coding. The scheme is designed and analyzed for single relay channel, single source multicast network and multiple source multicast network. The achievable rate region is determined for each case. The special cases of Gaussian single relay channel and two way relay channel are analyzed for superposition noisy network coding. The achievable rate of the proposed scheme is higher than the existing schemes of noisy network coding and compress-forward.
Optimal Quantization for Compressive Sensing under Message Passing Reconstruction
Venue: arXiv cs.IT 2011
Year: 2011

We consider the optimal quantization of compressive sensing measurements following the work on generalization of relaxed belief propagation (BP) for arbitrary measurement channels. Relaxed BP is an iterative reconstruction scheme inspired by message passing algorithms on bipartite graphs. Its asymptotic error performance can be accurately predicted and tracked through the state evolution formalism. We utilize these results to design mean-square optimal scalar quantizers for relaxed BP signal reconstruction and empirically demonstrate the superior error performance of the resulting quantizers.
Adaptive Channel Recommendation For Opportunistic Spectrum Access
Venue: arXiv cs.DC 2011
Year: 2011

We propose a dynamic spectrum access scheme where secondary users recommend "good" channels to each other and access accordingly. We formulate the problem as an average reward based Markov decision process. We show the existence of the optimal stationary spectrum access policy, and explore its structure properties in two asymptotic cases. Since the action space of the Markov decision process is continuous, it is difficult to find the optimal policy by simply discretizing the action space and use the policy iteration, value iteration, or Q-learning methods. Instead, we propose a new algorithm based on the Model Reference Adaptive Search method, and prove its convergence to the optimal policy. Numerical results show that the proposed algorithms achieve up to 18% and 100% performance improvement than the static channel recommendation scheme in homogeneous and heterogeneous channel environments, respectively, and is more robust to channel dynamics.
Data Base Mappings and Monads: (Co)Induction
Venue: arXiv cs.DB 2011
Year: 2011

In this paper we presented the semantics of database mappings in the relational DB category based on the power-view monad T and monadic algebras. The objects in this category are the database-instances (a database-instance is a set of n-ary relations, i.e., a set of relational tables as in standard RDBs). The morphisms in DB category are used in order to express the semantics of view-based Global and Local as View (GLAV) mappings between relational databases, for example those used in Data Integration Systems. Such morphisms in this DB category are not functions but have the complex tree structures based on a set of complex query computations between two database-instances. Thus DB category, as a base category for the semantics of databases and mappings between them, is different from the Set category used dominantly for such issues, and needs the full investigation of its properties. In this paper we presented another contributions for an intensive exploration of properties and semantics of this category, based on the power-view monad T and the Kleisli category for databases. Here we stressed some Universal algebra considerations based on monads and relationships between this DB category and the standard Set category. Finally, we investigated the general algebraic and induction properties for databases in this category, and we defined the initial monadic algebras for database instances.
Information Loss in Static Nonlinearities
Venue: arXiv cs.IT 2011
Year: 2011

In this work, conditional entropy is used to quantify the information loss induced by passing a continuous random variable through a memoryless nonlinear input-output system. We derive an expression for the information loss depending on the input density and the nonlinearity and show that the result is strongly related to the non-injectivity of the considered system. Tight upper bounds are presented, which can be evaluated with less difficulty than a direct evaluation of the information loss, which involves the logarithm of a sum. Application of our results is illustrated on a set of examples.
Power-Bandwidth Efficiency and Capacity of Wireless Feedback Communication Systems
Venue: arXiv cs.IT 2011
Year: 2011

The paper is devoted to the analysis of problems appearing in optimisation and improvement of the power-bandwidth efficiency of digital communication feedback systems (FCS). There is shown that unlike digital systems, adaptive FCS with the analogue forward transmission allow full optimisation and derivation of optimal transmission-reception algorithm approaching their efficiency to the Shannon boundary. Differences between the forward channel capacity and capacity of adaptive FCS as communication unit, as well as their influence of the power-bandwidth efficiency of transmission are considered.
Upper Bounds for Maximally Greedy Binary Search Trees
Venue: arXiv cs.DS 2011
Year: 2011

At SODA 2009, Demaine et al. presented a novel connection between binary search trees (BSTs) and subsets of points on the plane. This connection was independently discovered by Derryberry et al. As part of their results, Demaine et al. considered GreedyFuture, an offline BST algorithm that greedily rearranges the search path to minimize the cost of future searches. They showed that GreedyFuture is actually an online algorithm in their geometric view, and that there is a way to turn GreedyFuture into an online BST algorithm with only a constant factor increase in total search cost. Demaine et al. conjectured this algorithm was dynamically optimal, but no upper bounds were given in their paper. We prove the first non-trivial upper bounds for the cost of search operations using GreedyFuture including giving an access lemma similar to that found in Sleator and Tarjan's classic paper on splay trees.
Witnessed k-Distance
Venue: arXiv cs.CG 2011
Year: 2011

Distance function to a compact set plays a central role in several areas of computational geometry. Methods that rely on it are robust to the perturbations of the data by the Hausdorff noise, but fail in the presence of outliers. The recently introduced distance to a measure offers a solution by extending the distance function framework to reasoning about the geometry of probability measures, while maintaining theoretical guarantees about the quality of the inferred information. A combinatorial explosion hinders working with distance to a measure as an ordinary (power) distance function. In this paper, we analyze an approximation scheme that keeps the representation linear in the size of the input, while maintaining the guarantees on the inference quality close to those for the exact (but costly) representation.
Mathematics of Human Motion: from Animation towards Simulation (A View form the Outside)
Venue: arXiv cs.GR 2011
Year: 2011

Simulation of human motion is the subject of study in a number of disciplines: Biomechanics, Robotics, Computer Animation, Control Theory, Neurophysiology, Medicine, Ergonomics. Since the author has never visited any of these fields, this review is indeed a passer-by's impression. On the other hand, he happens to be a human (who occasionally is moving) and, as everybody else, rates himself an expert in Applied Common Sense. Thus the author hopes that this view from the {\em outside} will be of some interest not only for the strangers like himself, but for those who are {\em inside} as well. Two flaws of the text that follows are inevitable. First, some essential issues that are too familar to the specialists to discuss them may be missing. Second, the author probably failed to provide the uniform "level-of-detail" for this wide range of topics.
Demonstration of Spectrum Sensing with Blindly Learned Feature
Venue: arXiv cs.IT 2011
Year: 2011

Spectrum sensing is essential in cognitive radio. By defining leading \textit{eigenvector} as feature, we introduce a blind feature learning algorithm (FLA) and a feature template matching (FTM) algorithm using learned feature for spectrum sensing. We implement both algorithms on Lyrtech software defined radio platform. Hardware experiment is performed to verify that feature can be learned blindly. We compare FTM with a blind detector in hardware and the results show that the detection performance for FTM is about 3 dB better.
Context-aware Authorization in Highly Dynamic Environments
Venue: arXiv cs.CR 2011
Year: 2011

Highly dynamic computing environments, like ubiquitous and pervasive computing environments, require frequent adaptation of applications. Context is a key to adapt suiting user needs. On the other hand, standard access control trusts users once they have authenticated, despite the fact that they may reach unauthorized contexts. We analyse how taking into account dynamic information like context in the authorization subsystem can improve security, and how this new access control applies to interaction patterns, like messaging or eventing. We experiment and validate our approach using context as an authorization factor for eventing in Web service for device (like UPnP or DPWS), in smart home security.
On the Szegö-Asymptotics for Doubly-Dispersive Gaussian Channels
Venue: arXiv cs.IT 2011
Year: 2011

We consider the time-continuous doubly-dispersive channel with additive Gaussian noise and establish a capacity formula for the case where the channel correlation operator is represented by a symbol which is periodic in time and fulfills some further integrability and smoothness conditions. The key to this result is a new Szegö formula for certain pseudo-differential operators. The formula justifies the water-filling principle along time and frequency in terms of the time--continuous time-varying transfer function (the symbol).