OpenRaiser/Intern-Atlas huggingface dataset:
MUSE: A Methodology for Characterizing and Quantifying the Use of Spectrum
Venue: arXiv cs.NI 2015
Year: 2015

Dynamic spectrum sharing paradigm is envisaged to meet the growing demand for the Radio Frequency (RF) spectrum. There exist several technical, regulatory, and business impediments for adopting the new paradigm. In this regard, we underscore the need of characterizing and quantifying the use of spectrum by each of the individual transmitters and receivers. We propose MUSE, a methodology to characterize and quantify the use of spectrum in the space, time, and frequency dimensions. MUSE characterizes the use of spectrum by a transmitter at a point in terms of the RF power occupied by the transmitter. It characterizes the use of spectrum by a receiver at a point in terms of the constraints on the RF-power that can be occupied by any of the transmitters in the system in order to ensure successful reception. It divides the spectrum-space into discrete unit-spectrum-spaces and quantifies the spectrum used by the individual transceivers in the discretized spectrum space. We characterize the performance of the spectrum management functions in the discretized spectrum-space and illustrate maximizing the use of spectrum. In order to address the challenges for the dynamic spectrum sharing paradigm, we emphasize on articulating, defining, and enforcing the spectrum-access rights in the discretized spectrum-space.
Model Checking Resource Bounded Systems with Shared Resources via Alternating Büchi Pushdown Systems
Venue: arXiv cs.LO 2015
Year: 2015

It is well known that the verification of resource-constrained multiagent systems is undecidable in general. In many such settings, resources are private to agents. In this paper, we investigate the model checking problem for a resource logic based on Alternating-Time Temporal Logic (ATL) with shared resources. Resources can be consumed and produced up to any amount. We show that the model checking problem is undecidable if two or more of such unbounded resources are available. Our main technical result is that in the case of a single shared resource, the problem becomes decidable. Although intuitive, the proof of decidability is non-trivial. We reduce model checking to a problem over alternating Büchi pushdown systems. An intermediate result connects to general automata-based verification: we show that model checking Computation Tree Logic (CTL) over (compact) alternating Büchi pushdown systems is decidable.
Indonesia embraces the Data Science
Venue: arXiv cs.CY 2015
Year: 2015

The information era is the time when information is not only largely generated, but also vastly processed in order to extract and generated more information. The complex nature of modern living is represented by the various kind of data. Data can be in the forms of signals, images, texts, or manifolds resembling the horizon of observation. The task of the emerging data sciences are to extract information from the data, for people gain new insights of the complex world. The insights may came from the new way of the data representation, be it a visualizations, mapping, or other. The insights may also come from the implementation of mathematical analysis and or computational processing giving new insights of what the states of the nature represented by the data. Both ways implement the methodologies reducing the dimensionality of the data. The relations between the two functions, representation and analysis are the heart of how information in data is transformed mathematically and computationally into new information. The paper discusses some practices, along with various data coming from the social life in Indonesia to gain new insights about Indonesia in the emerging data sciences. The data sciences in Indonesia has made Indonesian Data Cartograms, Indonesian Celebrity Sentiment Mapping, Ethno-Clustering Maps, social media community detection, and a lot more to come, become possible. All of these are depicted as the exemplifications on how Data Science has become integral part of the technology bringing data closer to people.
Two Particle-in-Grid Realisations on Spacetrees
Venue: arXiv cs.DS 2015
Year: 2015

The present paper studies two particle management strategies for dynamically adaptive Cartesian grids at hands of a particle-in-cell code. One holds the particles within the grid cells, the other within the grid vertices. The fundamental challenge for the algorithmic strategies results from the fact that particles may run through the grid without velocity constraints. To facilitate this, we rely on multiscale grid representations. They allow us to lift and drop particles between different spatial resolutions. We call this cell-based strategy particle in tree (PIT). Our second approach assigns particles to vertices describing a dual grid (PIDT) and augments the lifts and drops with multiscale linked cells. Our experiments validate the two schemes at hands of an electrostatic particle-in-cell code by retrieving the dispersion relation of Langmuir waves in a thermal plasma. They reveal that different particle and grid characteristics favour different realisations. The possibility that particles can tunnel through an arbitrary number of grid cells implies that most data is exchanged between neighbouring ranks, while very few data is transferred non-locally. This constraints the scalability as the code potentially has to realise global communication. We show that the merger of an analysed tree grammar with PIDT allows us to predict particle movements among several levels and to skip parts of this global communication a priori. It is capable to outperform several established implementations based upon trees and/or space-filling curves.
Computing Maximal Layers Of Points in $E^{f(n)}$
Venue: arXiv cs.CG 2015
Year: 2015

In this paper we present a randomized algorithm for computing the collection of maximal layers for a point set in $E^{k}$ ($k = f(n)$). The input to our algorithm is a point set $P = \{p_1,...,p_n\}$ with $p_i \in E^{k}$. The proposed algorithm achieves a runtime of $O\left(kn^{2 - {1 \over \log{k}} + \log_k{\left(1 + {2 \over {k+1}}\right)}}\log{n}\right)$ when $P$ is a random order and a runtime of $O(k^2 n^{3/2 + (\log_{k}{(k-1)})/2}\log{n})$ for an arbitrary $P$. Both bounds hold in expectation. Additionally, the run time is bounded by $O(kn^2)$ in the worst case. This is the first non-trivial algorithm whose run-time remains polynomial whenever $f(n)$ is bounded by some polynomial in $n$ while remaining sub-quadratic in $n$ for constant $k$. The algorithm is implemented using a new data-structure for storing and answering dominance queries over the set of incomparable points.
Probabilistic Power Flow Computation via Low-Rank and Sparse Tensor Recovery
Venue: arXiv cs.CE 2015
Year: 2015

This paper presents a tensor-recovery method to solve probabilistic power flow problems. Our approach generates a high-dimensional and sparse generalized polynomial-chaos expansion that provides useful statistical information. The result can also speed up other essential routines in power systems (e.g., stochastic planning, operations and controls). Instead of simulating a power flow equation at all quadrature points, our approach only simulates an extremely small subset of samples. We suggest a model to exploit the underlying low-rank and sparse structure of high-dimensional simulation data arrays, making our technique applicable to power systems with many random parameters. We also present a numerical method to solve the resulting nonlinear optimization problem. Our algorithm is implemented in MATLAB and is verified by several benchmarks in MATPOWER $5.1$. Accurate results are obtained for power systems with up to $50$ independent random parameters, with a speedup factor up to $9\times 10^{20}$.
InAR:Inverse Augmented Reality
Venue: arXiv cs.CV 2015
Year: 2015

Augmented reality is the art to seamlessly fuse virtual objects into real ones. In this short note, we address the opposite problem, the inverse augmented reality, that is, given a perfectly augmented reality scene where human is unable to distinguish real objects from virtual ones, how the machine could help do the job. We show by structure from motion (SFM), a simple 3D reconstruction technique from images in computer vision, the real and virtual objects can be easily separated in the reconstructed 3D scene.
On enery-efficient time synchronization based on source clock frequency recovery in wireless sensor networks
Venue: arXiv cs.NI 2015
Year: 2015

In this paper we study energy-efficient time synchronization schemes with focus on asymmetric wireless sensor networks, where a head node, which is connected to both wired & wireless networks, is equipped with a powerful processor and supplied power from outlet, and sensor nodes, which are connected only through wireless channels, are limited in processing and battery-powered. It is this asymmetry that we focus our study on; unlike existing schemes saving the power of all sensor nodes in the network (including the head node), we concentrate on battery-powered sensor nodes in minimizing energy consumption for synchronization. Specifically, we discuss a time synchronization scheme based on source clock frequency recovery, where we minimize the number of message transmissions from sensor nodes to the head node, and its extension to network-wide, multi-hop synchronization through gateway nodes.
Pore-scale lattice Boltzmann simulation of laminar and turbulent flow through a sphere pack
Venue: arXiv cs.CE 2015
Year: 2015

The lattice Boltzmann method can be used to simulate flow through porous media with full geometrical resolution. With such a direct numerical simulation, it becomes possible to study fundamental effects which are difficult to assess either by developing macroscopic mathematical models or experiments. We first evaluate the lattice Boltzmann method with various boundary handling of the solid-wall and various collision operators to assess their suitability for large scale direct numerical simulation of porous media flow. A periodic pressure drop boundary condition is used to mimic the pressure driven flow through the simple sphere pack in a periodic domain. The evaluation of the method is done in the Darcy regime and the results are compared to a semi-analytic solution. Taking into account computational cost and accuracy, we choose the most efficient combination of the solid boundary condition and collision operator. We apply this method to perform simulations for a wide range of Reynolds numbers from Stokes flow over seven orders of magnitude to turbulent flow. Contours and streamlines of the flow field are presented to show the flow behavior in different flow regimes. Moreover, unknown parameters of the Forchheimer, the Barree--Conway and friction factor models are evaluated numerically for the considered flow regimes.
Cable Capacitance Attack against the KLJN Secure Key Exchange
Venue: arXiv cs.ET 2015
Year: 2015

The security of the Kirchhoff-law-Johnson-(like)-noise (KLJN) key exchange system is based on the Fluctuation-Dissipation-Theorem of classical statistical physics. Similarly to quantum key distribution, in practical situations, due to the non-idealities of the building elements, there is a small information leak, which can be mitigated by privacy amplification or other techniques so that the unconditional (information theoretic) security is preserved. In this paper, the industrial cable and circuit simulator LTSPICE is used to validate the information leak due to one of the non-idealities in KLJN, the parasitic (cable) capacitance. Simulation results show that privacy amplification and/or capacitor killer (capacitance compensation) arrangements can effectively eliminate the leak.
Providing High and Controllable Performance in Multicore Systems Through Shared Resource Management
Venue: arXiv cs.DC 2015
Year: 2015

Multiple applications executing concurrently on a multicore system interfere with each other at different shared resources such as main memory and shared caches. Such inter-application interference, if uncontrolled, results in high system performance degradation and unpredictable application slowdowns. While previous work has proposed application-aware memory scheduling as a solution to mitigate inter-application interference and improve system performance, previously proposed memory scheduling techniques incur high hardware complexity and unfairly slowdown some applications. Furthermore, previously proposed memory-interference mitigation techniques are not designed to precisely control application performance. This dissertation seeks to achieve high and controllable performance in multicore systems by mitigating and quantifying the impact of shared resource interference. First, towards mitigating memory interference and achieving high performance, we propose the Blacklisting memory scheduler that achieves high performance and fairness at low complexity. Next, towards quantifying the impact of memory interference and achieving controllable performance in the presence of memory bandwidth interference, we propose the Memory Interference induced Slowdown Estimation (MISE) model. We propose and demonstrate two use cases that can leverage MISE to provide soft performance guarantees and high overall performance/fairness. Finally, we seek to quantify the impact of shared cache interference on application slowdowns, in addition to memory bandwidth interference. Towards this end, we propose the Application Slowdown Model (ASM). We propose and demonstrate several use cases of ASM that leverage it to provide soft performance guarantees and improve performance and fairness.
Semi-Supervised Sound Source Localization Based on Manifold Regularization
Venue: arXiv cs.SD 2015
Year: 2015

Conventional speaker localization algorithms, based merely on the received microphone signals, are often sensitive to adverse conditions, such as: high reverberation or low signal to noise ratio (SNR). In some scenarios, e.g. in meeting rooms or cars, it can be assumed that the source position is confined to a predefined area, and the acoustic parameters of the environment are approximately fixed. Such scenarios give rise to the assumption that the acoustic samples from the region of interest have a distinct geometrical structure. In this paper, we show that the high dimensional acoustic samples indeed lie on a low dimensional manifold and can be embedded into a low dimensional space. Motivated by this result, we propose a semi-supervised source localization algorithm which recovers the inverse mapping between the acoustic samples and their corresponding locations. The idea is to use an optimization framework based on manifold regularization, that involves smoothness constraints of possible solutions with respect to the manifold. The proposed algorithm, termed Manifold Regularization for Localization (MRL), is implemented in an adaptive manner. The initialization is conducted with only few labelled samples attached with their respective source locations, and then the system is gradually adapted as new unlabelled samples (with unknown source locations) are received. Experimental results show superior localization performance when compared with a recently presented algorithm based on a manifold learning approach and with the generalized cross-correlation (GCC) algorithm as a baseline.
Community detection and role identification in directed networks: understanding the Twitter network of the care.data debate
Venue: arXiv cs.SI 2015
Year: 2015

With the rise of social media as an important channel for the debate and discussion of public affairs, online social networks such as Twitter have become important platforms for public information and engagement by policy makers. To communicate effectively through Twitter, policy makers need to understand how influence and interest propagate within its network of users. In this chapter we use graph-theoretic methods to analyse the Twitter debate surrounding NHS England's controversial care.data scheme. Directionality is a crucial feature of the Twitter social graph - information flows from the followed to the followers - but is often ignored in social network analyses; our methods are based on the behaviour of dynamic processes on the network and can be applied naturally to directed networks. We uncover robust communities of users and show that these communities reflect how information flows through the Twitter network. We are also able to classify users by their differing roles in directing the flow of information through the network. Our methods and results will be useful to policy makers who would like to use Twitter effectively as a communication medium.
Computing accurate Horner form approximations to special functions in finite precision arithmetic
Venue: arXiv cs.NA 2015
Year: 2015

In various applications, computers are required to compute approximations to univariate elementary and special functions such as $\exp$ and $\arctan$ to modest accuracy. This paper proposes a new heuristic for automating the design of such implementations. This heuristic takes a certain restricted specification of program structure and the desired error properties as input and takes explicit account of roundoff error during evaluation.
Reward Shaping with Recurrent Neural Networks for Speeding up On-Line Policy Learning in Spoken Dialogue Systems
Venue: arXiv cs.LG 2015
Year: 2015

Statistical spoken dialogue systems have the attractive property of being able to be optimised from data via interactions with real users. However in the reinforcement learning paradigm the dialogue manager (agent) often requires significant time to explore the state-action space to learn to behave in a desirable manner. This is a critical issue when the system is trained on-line with real users where learning costs are expensive. Reward shaping is one promising technique for addressing these concerns. Here we examine three recurrent neural network (RNN) approaches for providing reward shaping information in addition to the primary (task-orientated) environmental feedback. These RNNs are trained on returns from dialogues generated by a simulated user and attempt to diffuse the overall evaluation of the dialogue back down to the turn level to guide the agent towards good behaviour faster. In both simulated and real user scenarios these RNNs are shown to increase policy learning speed. Importantly, they do not require prior knowledge of the user's goal.
Binary Compressive Sensing via Analog Fountain Coding
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, a compressive sensing (CS) approach is proposed for sparse binary signals' compression and reconstruction based on analog fountain codes (AFCs). In the proposed scheme, referred to as the analog fountain compressive sensing (AFCS), each measurement is generated from a linear combination of L randomly selected binary signal elements with real weight coefficients. The weight coefficients are chosen from a finite weight set and L, called measurement degree, is obtained based on a predefined degree distribution function. We propose a simple verification based reconstruction algorithm for the AFCS in the noiseless case. The proposed verification based decoder is analyzed through SUM-OR tree analytical approach and an optimization problem is formulated to find the optimum measurement degree to minimize the number of measurements required for the reconstruction of binary sparse signals. We show that in the AFCS, the number of required measurements is of O(-n log(1-k/n)), where n is the signal length and k is the signal sparsity level. We then consider the signal reconstruction of AFCS in the presence of additive white Gaussian noise (AWGN) and the standard message passing decoder is then used for the signal recovery. Simulation results show that the AFCS can perfectly recover all non-zero elements of the sparse binary signal with a significantly reduced number of measurements, compared to the conventional binary CS and L1-minimization approaches in a wide range of signal to noise ratios (SNRs). Finally, we show a practical application of the AFCS for the sparse event detection in wireless sensor networks (WSNs), where the sensors' readings can be treated as measurements from the CS point of view.
Codon Context Optimization in Synthetic Gene Design
Venue: arXiv cs.DS 2015
Year: 2015

Advances in de novo synthesis of DNA and computational gene design methods make possible the customization of genes by direct manipulation of features such as codon bias and mRNA secondary structure. Codon context is another feature significantly affecting mRNA translational efficiency, but existing methods and tools for evaluating and designing novel optimized protein coding sequences utilize untested heuristics and do not provide quantifiable guarantees on design quality. In this study we examine statistical properties of codon context measures in an effort to better understand the phenomenon. We analyze the computational complexity of codon context optimization and design exact and efficient heuristic gene recoding algorithms under reasonable constraint models. We also present a web-based tool for evaluating codon context bias in the appropriate context.
Lensless Compressive Imaging
Venue: arXiv cs.CV 2015
Year: 2015

We develop a lensless compressive imaging architecture, which consists of an aperture assembly and a single sensor, without using any lens. An anytime algorithm is proposed to reconstruct images from the compressive measurements; the algorithm produces a sequence of solutions that monotonically converge to the true signal (thus, anytime). The algorithm is developed based on the sparsity of local overlapping patches (in the transformation domain) and state-of-the-art results have been obtained. Experiments on real data demonstrate that encouraging results are obtained by measuring about 10% (of the image pixels) compressive measurements. The reconstruction results of the proposed algorithm are compared with the JPEG compression (based on file sizes) and the reconstructed image quality is close to the JPEG compression, in particular at a high compression rate.
On the Voting Time of the Deterministic Majority Process
Venue: arXiv cs.DC 2015
Year: 2015

In the deterministic binary majority process we are given a simple graph where each node has one out of two initial opinions. In every round, every node adopts the majority opinion among its neighbors. By using a potential argument first discovered by Goles and Olivos (1980), it is known that this process always converges in $O(|E|)$ rounds to a two-periodic state in which every node either keeps its opinion or changes it in every round. It has been shown by Frischknecht, Keller, and Wattenhofer (2013) that the $O(|E|)$ bound on the convergence time of the deterministic binary majority process is indeed tight even for dense graphs. However, in many graphs such as the complete graph, from any initial opinion assignment, the process converges in just a constant number of rounds. By carefully exploiting the structure of the potential function by Goles and Olivos (1980), we derive a new upper bound on the convergence time of the deterministic binary majority process that accounts for such exceptional cases. We show that it is possible to identify certain modules of a graph $G$ in order to obtain a new graph $G^Δ$ with the property that the worst-case convergence time of $G^Δ$ is an upper bound on that of $G$. Moreover, even though our upper bound can be computed in linear time, we show that, given an integer $k$, it is NP-hard to decide whether there exists an initial opinion assignment for which it takes more than $k$ rounds to converge to the two-periodic state.