OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Spectral Efficiency Maximization in Full-Duplex Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

Three-node full-duplex is a promising new transmission mode between a full-duplex capable wireless node and two other wireless nodes that use half-duplex transmission and reception respectively. Although three-node full-duplex transmissions can increase the spectral efficiency without requiring full-duplex capability of user devices, inter-node interference - in addition to the inherent self-interference - can severely degrade the performance. Therefore, as methods that provide effective self-interference mitigation evolve, the management of inter-node interference is becoming increasingly important. This paper considers a cellular system in which a full-duplex capable base station serves a set of half-duplex capable users. As the spectral efficiencies achieved by the uplink and downlink transmissions are inherently intertwined, the objective is to device channel assignment and power control algorithms that maximize the weighted sum of the uplink-downlink transmissions. To this end a distributed auction based channel assignment algorithm is proposed, in which the scheduled uplink users and the base station jointly determine the set of downlink users for full-duplex transmission. Realistic system simulations indicate that the spectral efficiency can be up to 89% better than using the traditional half-duplex mode. Furthermore, when the self-interference cancelling level is high, the impact of the user-to-user interference is severe unless properly managed.
Client-CASH: Protecting Master Passwords against Offline Attacks
Venue: arXiv cs.CR 2016
Year: 2016

Offline attacks on passwords are increasingly commonplace and dangerous. An offline adversary is limited only by the amount of computational resources he or she is willing to invest to crack a user's password. The danger is compounded by the existence of authentication servers who fail to adopt proper password storage practices like key-stretching. Password managers can help mitigate these risks by adopting key stretching procedures like hash iteration or memory hard functions to derive site specific passwords from the user's master password on the client-side. While key stretching can reduce the offline adversary's success rate, these procedures also increase computational costs for a legitimate user. Motivated by the observation that most of the password guesses of the offline adversary will be incorrect, we propose a client side cost asymmetric secure hashing scheme (Client-CASH). Client-CASH randomizes the runtime of client-side key stretching procedure in a way that the expected computational cost of our key derivation function is greater when run with an incorrect master password. We make several contributions. First, we show how to introduce randomness into a client-side key stretching algorithms through the use of halting predicates which are selected randomly at the time of account creation. Second, we formalize the problem of finding the optimal running time distribution subject to certain cost constraints for the client and certain security constrains on the halting predicates. Finally, we demonstrate that Client-CASH can reduce the adversary's success rate by up to $21\%$. These results demonstrate the promise of the Client-CASH mechanism.
Super Mario as a String: Platformer Level Generation Via LSTMs
Venue: arXiv cs.NE 2016
Year: 2016

The procedural generation of video game levels has existed for at least 30 years, but only recently have machine learning approaches been used to generate levels without specifying the rules for generation. A number of these have looked at platformer levels as a sequence of characters and performed generation using Markov chains. In this paper we examine the use of Long Short-Term Memory recurrent neural networks (LSTMs) for the purpose of generating levels trained from a corpus of Super Mario Brothers levels. We analyze a number of different data representations and how the generated levels fit into the space of human authored Super Mario Brothers levels.
Tight Analysis of a Multiple-Swap Heuristic for Budgeted Red-Blue Median
Venue: arXiv cs.DS 2016
Year: 2016

Budgeted Red-Blue Median is a generalization of classic $k$-Median in that there are two sets of facilities, say $\mathcal{R}$ and $\mathcal{B}$, that can be used to serve clients located in some metric space. The goal is to open $k_r$ facilities in $\mathcal{R}$ and $k_b$ facilities in $\mathcal{B}$ for some given bounds $k_r, k_b$ and connect each client to their nearest open facility in a way that minimizes the total connection cost. We extend work by Hajiaghayi, Khandekar, and Kortsarz [2012] and show that a multiple-swap local search heuristic can be used to obtain a $(5+ε)$-approximation for Budgeted Red-Blue Median for any constant $ε> 0$. This is an improvement over their single swap analysis and beats the previous best approximation guarantee of 8 by Swamy [2014]. We also present a matching lower bound showing that for every $p \geq 1$, there are instances of Budgeted Red-Blue Median with local optimum solutions for the $p$-swap heuristic whose cost is $5 + Ω\left(\frac{1}{p}\right)$ times the optimum solution cost. Thus, our analysis is tight up to the lower order terms. In particular, for any $ε> 0$ we show the single-swap heuristic admits local optima whose cost can be as bad as $7-ε$ times the optimum solution cost.
Formalising Confluence in PVS
Venue: arXiv cs.LO 2016
Year: 2016

Confluence is a critical property of computational systems which is related with determinism and non ambiguity and thus with other relevant computational attributes of functional specifications and rewriting system as termination and completion. Several criteria have been explored that guarantee confluence and their formalisations provide further interesting information. This work discusses topics and presents personal positions and views related with the formalisation of confluence properties in the Prototype Verification System PVS developed at our research group.
Elastic Net Hypergraph Learning for Image Clustering and Semi-supervised Classification
Venue: arXiv cs.CV 2016
Year: 2016

Graph model is emerging as a very effective tool for learning the complex structures and relationships hidden in data. Generally, the critical purpose of graph-oriented learning algorithms is to construct an informative graph for image clustering and classification tasks. In addition to the classical $K$-nearest-neighbor and $r$-neighborhood methods for graph construction, $l_1$-graph and its variants are emerging methods for finding the neighboring samples of a center datum, where the corresponding ingoing edge weights are simultaneously derived by the sparse reconstruction coefficients of the remaining samples. However, the pair-wise links of $l_1$-graph are not capable of capturing the high order relationships between the center datum and its prominent data in sparse reconstruction. Meanwhile, from the perspective of variable selection, the $l_1$ norm sparse constraint, regarded as a LASSO model, tends to select only one datum from a group of data that are highly correlated and ignore the others. To simultaneously cope with these drawbacks, we propose a new elastic net hypergraph learning model, which consists of two steps. In the first step, the Robust Matrix Elastic Net model is constructed to find the canonically related samples in a somewhat greedy way, achieving the grouping effect by adding the $l_2$ penalty to the $l_1$ constraint. In the second step, hypergraph is used to represent the high order relationships between each datum and its prominent samples by regarding them as a hyperedge. Subsequently, hypergraph Laplacian matrix is constructed for further analysis. New hypergraph learning algorithms, including unsupervised clustering and multi-class semi-supervised classification, are then derived. Extensive experiments on face and handwriting databases demonstrate the effectiveness of the proposed method.
Minimization of Büchi Automata using Fair Simulation
Venue: arXiv cs.FL 2016
Year: 2016

We present an algorithm, which reduces the size of Büchi automata using fair simulation. Its time complexity is $\mathcal{O}(|Q|^4 \cdot |Δ|^2)$, the space complexity is $\mathcal{O}(|Q| \cdot |Δ|)$. Simulation is a common approach for minimizing $ω$-automata such as Büchi automata. Direct simulation, delayed simulation and fair simulation are different types of simulation. As we will show, minimization based on direct or delayed simulation is conceptually simple. Whereas the algorithm based on fair simulation is more complex. However, fair simulation allows a stronger minimization of the automaton. Further, we illustrate the theory behind the algorithm, cover optimizations useful in practice, give experimental results and compare our technique to other minimization strategies.
If-Conversion Optimization using Neuro Evolution of Augmenting Topologies
Venue: arXiv cs.DC 2016
Year: 2016

Control-flow dependence is an intrinsic limiting factor for pro- gram acceleration. With the availability of instruction-level par- allel architectures, if-conversion optimization has, therefore, be- come pivotal for extracting parallelism from serial programs. While many if-conversion optimization heuristics have been proposed in the literature, most of them consider rigid criteria regardless of the underlying hardware and input programs. In this paper, we propose a novel if-conversion scheme that preforms an efficient if-conversion transformation using a machine learning technique (NEAT). This method enables if-conversion customization overall branches within a program unlike the literature that considered in- dividual branches. Our technique also provides flexibility required when compiling for heterogeneous systems. The efficacy of our approach is shown by experiments and reported results which il- lustrate that the programs can be accelerated on the same archi- tecture and without modifying the original code. Our technique applies for general purpose programming languages (e.g. C/C++) and is transparent for the programmer. We implemented our tech- nique in LLVM 3.6.1 compilation infrastructure and experimented on the kernels of SPEC-CPU2006 v1.1 benchmarks suite running on a multicore system of Intel(R) Xeon(R) 3.50GHz processors. Our findings show a performance gain up to 8.6% over the stan- dard optimized code (LLVM -O2 with if-conversion included), in- dicating the need for If-conversion compilation optimization that can adapt to the unique characteristics of every individual branch.
Deep Reinforcement Learning from Self-Play in Imperfect-Information Games
Venue: arXiv cs.LG 2016
Year: 2016

Many real-world applications can be described as large-scale games of imperfect information. To deal with these challenging domains, prior work has focused on computing Nash equilibria in a handcrafted abstraction of the domain. In this paper we introduce the first scalable end-to-end approach to learning approximate Nash equilibria without prior domain knowledge. Our method combines fictitious self-play with deep reinforcement learning. When applied to Leduc poker, Neural Fictitious Self-Play (NFSP) approached a Nash equilibrium, whereas common reinforcement learning methods diverged. In Limit Texas Holdem, a poker game of real-world scale, NFSP learnt a strategy that approached the performance of state-of-the-art, superhuman algorithms based on significant domain expertise.
Modular Decomposition and Analysis of Registration based Trackers
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents a new way to study registration based trackers by decomposing them into three constituent sub modules: appearance model, state space model and search method. It is often the case that when a new tracker is introduced in literature, it only contributes to one or two of these sub modules while using existing methods for the rest. Since these are often selected arbitrarily by the authors, they may not be optimal for the new method. In such cases, our breakdown can help to experimentally find the best combination of methods for these sub modules while also providing a framework within which the contributions of the new tracker can be clearly demarcated and thus studied better. We show how existing trackers can be broken down using the suggested methodology and compare the performance of the default configuration chosen by the authors against other possible combinations to demonstrate the new insights that can be gained by such an approach. We also present an open source system that provides a convenient interface to plug in a new method for any sub module and test it against all possible combinations of methods for the other two sub modules while also serving as a fast and efficient solution for practical tracking requirements.
An End-to-End Robot Architecture to Manipulate Non-Physical State Changes of Objects
Venue: arXiv cs.RO 2016
Year: 2016

With the advance in robotic hardware and intelligent software, humanoid robot plays an important role in various tasks including service for human assistance and heavy job for hazardous industry. Recent advances in task learning enable humanoid robots to conduct dexterous manipulation tasks such as grasping objects and assembling parts of furniture. Operating objects without physical movements is an even more challenging task for humanoid robot because effects of actions may not be clearly seen in the physical configuration space and meaningful actions could be very complex in a long time horizon. As an example, playing a mobile game in a smart device has such challenges because both swipe actions and complex state transitions inside the smart devices in a long time horizon. In this paper, we solve this problem by introducing an integrated architecture which connects end-to-end dataflow from sensors to actuators in a humanoid robot to operate smart devices. We implement our integrated architecture in the Baxter Research Robot and experimentally demonstrate that the robot with our architecture could play a challenging mobile game, the 2048 game, as accurate as in a simulated environment.
Simplified Relative Citation Ratio for Static Paper Ranking: UFMG/LATIN at WSDM Cup 2016
Venue: arXiv cs.IR 2016
Year: 2016

Static rankings of papers play a key role in the academic search setting. Many features are commonly used in the literature to produce such rankings, some examples are citation-based metrics, distinct applications of PageRank, among others. More recently, learning to rank techniques have been successfully applied to combine sets of features producing effective results. In this work, we propose the metric S-RCR, which is a simplified version of a metric called Relative Citation Ratio --- both based on the idea of a co-citation network. When compared to the classical version, our simplification S-RCR leads to improved efficiency with a reasonable effectiveness. We use S-RCR to rank over 120 million papers in the Microsoft Academic Graph dataset. By using this single feature, which has no parameters and does not need to be tuned, our team was able to reach the 3rd position in the first phase of the WSDM Cup 2016.
Finding best possible constant for a polynomial inequality
Venue: arXiv cs.SC 2016
Year: 2016

Given a multi-variant polynomial inequality with a parameter, how to find the best possible value of this parameter that satisfies the inequality? For instance, find the greatest number $k$ that satisfies $ a^3+b^3+c^3+ k(a^2b+b^2c+c^2a)-(k+1)(ab^2+bc^2+ca^2)\geq 0 $ for all nonnegative real numbers $ a,b,c $. Analogues problems often appeared in studies of inequalities and were dealt with by various methods. In this paper, a general algorithm is proposed for finding the required best possible constant. The algorithm can be easily implemented by computer algebra tools such as Maple.
OFDM demodulation using virtual time reversal processing in underwater acoustic communication
Venue: arXiv cs.IT 2016
Year: 2016

The extremely long underwater channel delay spread causes severe inter-symbol interference (ISI) for underwater acoustic communications. Passive time reversal processing (PTRP) can effectively reduce the channel time dispersion in a simple way via convolving the received packet with a time reversed probe signal. However the probe signal itself may introduce extra noise and interference (self-correlation of the probe signal). In this paper, we propose a virtual time reversal processing (VTRP) for single input single output (SISO) Orthogonal Frequency Division Multiplexing (OFDM) systems. It convolves the received packet with the reversed estimated channel, instead of the probe signal to reduce the interference. Two sparse channel estimation methods, matching pursuit (MP), and basis pursuit de-noising (BPDN), are adopted to estimate the channel impulse response (CIR). We compare the performance of VTRP with the PTRP and without any time reversal processing through MATLAB simulations and the pool experiments. The results reveal that VTRP has outstanding performance over time-invariant channels.
PCF Scheme for Periodic Data Transmission in Smart Metering Network with Cognitive Radio
Venue: arXiv cs.NI 2016
Year: 2016

The next generation Advanced Metering Infrastructure (AMI), with the aid of two-way Smart Metering Network (SMN), is expected to support many advanced functions. In this work, we focus on the application of remote periodic energy consumption reporting, which is a fundamental and significant component of Demand Response and Load Management. In order to support this periodic application with satisfactory communication performance, a well-suited Media Access Control (MAC) protocol needs to be designed. Because the number of Smart Meters (communication nodes) involved in SMN are much larger than that in today's local area networks, the traditional taking-turns MAC protocol, such as Point Coordination Function (PCF) in WiFi is unlikely to perform well. In order to solve this problem, we propose a modified PCF scheme with the combination of Cognitive Radio technology, in which the Smart Meters may use the free channels (white space) to report energy consumption data to the Local Collector when the Primary Users are not occupying the channels. We also conduct comprehensive throughput analysis on the proposed scheme. The numerical results and simulation results through NS-3 show that the PCF scheme with Cognitive Radio significantly outperform the traditional one in a densely populated network like SMN.
Motivating Healthy Water Intake through Prompting, Historical Information, and Implicit Feedback
Venue: arXiv cs.HC 2016
Year: 2016

We describe Hydroprompt, a prototype for sensing and motivating healthy water intake in work environments. In a 3-week field deployment of Hydroprompt, we evaluate the effectiveness of three approaches to behavior change: historical information enabling users to compare their water intake lev- els across different times of day and days of week, implicit feedback providing subtle cues to users on the current hydration levels, and explicit prompting at- tempting to remind participants when hydration falls below acceptable levels or when substantial amount of time has elapsed since the last sip.
Proportional Fair Rate Allocation for Private Shared Networks
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, we consider fair privacy in a shared network subject to traffic analysis attacks by an eavesdropper. We initiate the study of the joint trade-off between privacy, throughput and delay in such a shared network as a utility fairness problem and derive the proportional fair rate allocation for networks of flows subject to privacy constraints and delay deadlines.
TANGO: Transparent heterogeneous hardware Architecture deployment for eNergy Gain in Operation
Venue: arXiv cs.SE 2016
Year: 2016

The paper is concerned with the issue of how software systems actually use Heterogeneous Parallel Architectures (HPAs), with the goal of optimizing power consumption on these resources. It argues the need for novel methods and tools to support software developers aiming to optimise power consumption resulting from designing, developing, deploying and running software on HPAs, while maintaining other quality aspects of software to adequate and agreed levels. To do so, a reference architecture to support energy efficiency at application construction, deployment, and operation is discussed, as well as its implementation and evaluation plans.
Collecting Examples for Instance-Spanning Constraints
Venue: arXiv cs.SE 2016
Year: 2016

This report presents a meta analysis of various sources from literature, research projects, and experience with the goal of collecting examples for instance-spanning constraints to be implemented through Process-Aware Information Systems.
Depth Superresolution using Motion Adaptive Regularization
Venue: arXiv cs.CV 2016
Year: 2016

Spatial resolution of depth sensors is often significantly lower compared to that of conventional optical cameras. Recent work has explored the idea of improving the resolution of depth using higher resolution intensity as a side information. In this paper, we demonstrate that further incorporating temporal information in videos can significantly improve the results. In particular, we propose a novel approach that improves depth resolution, exploiting the space-time redundancy in the depth and intensity using motion-adaptive low-rank regularization. Experiments confirm that the proposed approach substantially improves the quality of the estimated high-resolution depth. Our approach can be a first component in systems using vision techniques that rely on high resolution depth information.
Queue-Aware Energy-Efficient Joint Remote Radio Head Activation and Beamforming in Cloud Radio Access Networks
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we study the stochastic optimization of cloud radio access networks (C-RANs) by joint remote radio head (RRH) activation and beamforming in the downlink. Unlike most previous works that only consider a static optimization framework with full traffic buffers, we formulate a dynamic optimization problem by explicitly considering the effects of random traffic arrivals and time-varying channel fading. The stochastic formulation can quantify the tradeoff between power consumption and queuing delay. Leveraging on the Lyapunov optimization technique, the stochastic optimization problem can be transformed into a per-slot penalized weighted sum rate maximization problem, which is shown to be non-deterministic polynomial-time hard. Based on the equivalence between the penalized weighted sum rate maximization problem and the penalized weighted minimum mean square error (WMMSE) problem, the group sparse beamforming optimization based WMMSE algorithm and the relaxed integer programming based WMMSE algorithm are proposed to efficiently obtain the joint RRH activation and beamforming policy. Both algorithms can converge to a stationary solution with low-complexity and can be implemented in a parallel manner, thus they are highly scalable to large-scale C-RANs. In addition, these two proposed algorithms provide a flexible and efficient means to adjust the power-delay tradeoff on demand.