OpenRaiser/Intern-Atlas huggingface dataset:
Coded Caching Schemes with Low Rate and Subpacketizations
Venue: arXiv cs.IT 2017
Year: 2017

Coded caching scheme, which is an effective technique to increase the transmission efficiency during peak traffic times, has recently become quite popular among the coding community. Generally rate can be measured to the transmission in the peak traffic times, i.e., this efficiency increases with the decreasing of rate. In order to implement a coded caching scheme, each file in the library must be split in a certain number of packets. And this number directly reflects the complexity of a coded caching scheme, i.e., the complexity increases with the increasing of the packet number. However there exists a tradeoff between the rate and packet number. So it is meaningful to characterize this tradeoff and design the related Pareto-optimal coded caching schemes with respect to both parameters. Recently, a new concept called placement delivery array (PDA) was proposed to characterize the coded caching scheme. However as far as we know no one has yet proved that one of the previously known PDAs is Pareto-optimal. In this paper, we first derive two lower bounds on the rate under the framework of PDA. Consequently, the PDA proposed by Maddah-Ali and Niesen is Pareto-optimal, and a tradeoff between rate and packet number is obtained for some parameters. Then, from the above observations and the view point of combinatorial design, two new classes of Pareto-optimal PDAs are obtained. Based on these PDAs, the schemes with low rate and packet number are obtained. Finally the performance of some previously known PDAs are estimated by comparing with these two classes of schemes.
Perceiving and Reasoning About Liquids Using Fully Convolutional Networks
Venue: arXiv cs.RO 2017
Year: 2017

Liquids are an important part of many common manipulation tasks in human environments. If we wish to have robots that can accomplish these types of tasks, they must be able to interact with liquids in an intelligent manner. In this paper, we investigate ways for robots to perceive and reason about liquids. That is, a robot asks the questions What in the visual data stream is liquid? and How can I use that to infer all the potential places where liquid might be? We collected two datasets to evaluate these questions, one using a realistic liquid simulator and another on our robot. We used fully convolutional neural networks to learn to detect and track liquids across pouring sequences. Our results show that these networks are able to perceive and reason about liquids, and that integrating temporal information is important to performing such tasks well.
Graph sampling with determinantal processes
Venue: arXiv cs.LG 2017
Year: 2017

We present a new random sampling strategy for k-bandlimited signals defined on graphs, based on determinantal point processes (DPP). For small graphs, ie, in cases where the spectrum of the graph is accessible, we exhibit a DPP sampling scheme that enables perfect recovery of bandlimited signals. For large graphs, ie, in cases where the graph's spectrum is not accessible, we investigate, both theoretically and empirically, a sub-optimal but much faster DPP based on loop-erased random walks on the graph. Preliminary experiments show promising results especially in cases where the number of measurements should stay as small as possible and for graphs that have a strong community structure. Our sampling scheme is efficient and can be applied to graphs with up to $10^6$ nodes.
Fair Allocation of Indivisible Goods to Asymmetric Agents
Venue: arXiv cs.GT 2017
Year: 2017

We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang wherein the agents are assumed to be symmetric with respect to their entitlements. Although Procaccia and Wang show an almost fair (constant approximation) allocation exists in their setting, our main result is in sharp contrast to their observation. We show that, in some cases with $n$ agents, no allocation can guarantee better than $1/n$ approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a $1/n$ approximation guarantee. Our second result is for a restricted version of the problem where the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. Although this assumption might seem w.l.o.g, we show it enables us to find a $1/2$ approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items.
Pneumatic Modelling for Adroit Manipulation Platform
Venue: arXiv cs.RO 2017
Year: 2017

ADROIT Manipulation platform is a pneumatically actuated, tendon driven 28 degree of freedom platform being developed for investigating complex hand manipulation behaviors. ADROIT derives its unique capabilities, necessary to support dynamic and dexterous manipulation, from a custom designed high-performance pneumatic actuation system for tendon-driven hands. The custom pneumatic actuation system is fast, strong, low friction-stiction, compliant and is capable of actuating a shadow hand skeleton faster that human capabilities -- at a unique combination of speed, force, and compliance that has never been achieved before. In this paper, we develop models for the pneumatic muscles of ADROIT and perform a thorough investigation of the various parameters that affect pressure dynamics in a pneumatic system such as, different cylinder types, leakage from valves and cylinders, valve deadzone, input pressure fluctuations etc to improve the model's accuracy.
Parameterized complexity of finding a spanning tree with minimum reload cost diameter
Venue: arXiv cs.DS 2017
Year: 2017

We study the minimum diameter spanning tree problem under the reload cost model (DIAMETER-TREE for short) introduced by Wirth and Steffan (2001). In this problem, given an undirected edge-colored graph $G$, reload costs on a path arise at a node where the path uses consecutive edges of different colors. The objective is to find a spanning tree of $G$ of minimum diameter with respect to the reload costs. We initiate a systematic study of the parameterized complexity of the DIAMETER-TREE problem by considering the following parameters: the cost of a solution, and the treewidth and the maximum degree $Δ$ of the input graph. We prove that DIAMETER-TREE is para-NP-hard for any combination of two of these three parameters, and that it is FPT parameterized by the three of them. We also prove that the problem can be solved in polynomial time on cactus graphs. This result is somehow surprising since we prove DIAMETER-TREE to be NP-hard on graphs of treewidth two, which is best possible as the problem can be trivially solved on forests. When the reload costs satisfy the triangle inequality, Wirth and Steffan (2001) proved that the problem can be solved in polynomial time on graphs with $Δ= 3$, and Galbiati (2008) proved that it is NP-hard if $Δ= 4$. Our results show, in particular, that without the requirement of the triangle inequality, the problem is NP-hard if $Δ= 3$, which is also best possible. Finally, in the case where the reload costs are polynomially bounded by the size of the input graph, we prove that DIAMETER-TREE is in XP and W[1]-hard parameterized by the treewidth plus $Δ$.
Refactoring Legacy JavaScript Code to Use Classes: The Good, The Bad and The Ugly
Venue: arXiv cs.SE 2017
Year: 2017

JavaScript systems are becoming increasingly complex and large. To tackle the challenges involved in implementing these systems, the language is evolving to include several constructions for programming- in-the-large. For example, although the language is prototype-based, the latest JavaScript standard, named ECMAScript 6 (ES6), provides native support for implementing classes. Even though most modern web browsers support ES6, only a very few applications use the class syntax. In this paper, we analyze the process of migrating structures that emulate classes in legacy JavaScript code to adopt the new syntax for classes introduced by ES6. We apply a set of migration rules on eight legacy JavaScript systems. In our study, we document: (a) cases that are straightforward to migrate (the good parts); (b) cases that require manual and ad-hoc migration (the bad parts); and (c) cases that cannot be migrated due to limitations and restrictions of ES6 (the ugly parts). Six out of eight systems (75%) contain instances of bad and/or ugly cases. We also collect the perceptions of JavaScript developers about migrating their code to use the new syntax for classes.
Word forms - not just their lengths- are optimized for efficient communication
Venue: arXiv cs.CL 2017
Year: 2017

The inverse relationship between the length of a word and the frequency of its use, first identified by G.K. Zipf in 1935, is a classic empirical law that holds across a wide range of human languages. We demonstrate that length is one aspect of a much more general property of words: how distinctive they are with respect to other words in a language. Distinctiveness plays a critical role in recognizing words in fluent speech, in that it reflects the strength of potential competitors when selecting the best candidate for an ambiguous signal. Phonological information content, a measure of a word's string probability under a statistical model of a language's sound or character sequences, concisely captures distinctiveness. Examining large-scale corpora from 13 languages, we find that distinctiveness significantly outperforms word length as a predictor of frequency. This finding provides evidence that listeners' processing constraints shape fine-grained aspects of word forms across languages.
Ad-hoc Affectance-selective Families for Layer Dissemination
Venue: arXiv cs.DC 2017
Year: 2017

Information dissemination protocols for ad-hoc wireless networks frequently use a minimal subset of the available communication links, defining a rooted "broadcast" tree. In this work, we focus on the core challenge of disseminating from one layer to the next one of such tree. We call this problem Layer Dissemination. We study Layer Dissemination under a generalized model of interference, called affectance. The affectance model subsumes previous models, such as Radio Network and Signal to Inteference-plus-Noise Ratio. We present randomized and deterministic protocols for Layer Dissemination. These protocols are based on a combinatorial object that we call Affectance-selective Families. Our approach combines an engineering solution with theoretical guarantees. That is, we provide a method to characterize the network with a global measure of affectance based on measurements of interference in the specific deployment area. Then, our protocols distributedly produce an ad-hoc transmissions schedule for dissemination. In the randomized protocol only the network characterization is needed, whereas the deterministic protocol requires full knowledge of affectance. Our theoretical analysis provides guarantees on schedule length. We also present simulations of a real network-deployment area contrasting the performance of our randomized protocol, which takes into account affectance, against previous work for interference models that ignore some physical constraints. The striking improvement in performance shown by our simulations show the importance of utilizing a more physically-accurate model of interference that takes into account other effects beyond distance to transmitters.
Surprise-Based Intrinsic Motivation for Deep Reinforcement Learning
Venue: arXiv cs.LG 2017
Year: 2017

Exploration in complex domains is a key challenge in reinforcement learning, especially for tasks with very sparse rewards. Recent successes in deep reinforcement learning have been achieved mostly using simple heuristic exploration strategies such as $ε$-greedy action selection or Gaussian control noise, but there are many tasks where these methods are insufficient to make any learning progress. Here, we consider more complex heuristics: efficient and scalable exploration strategies that maximize a notion of an agent's surprise about its experiences via intrinsic motivation. We propose to learn a model of the MDP transition probabilities concurrently with the policy, and to form intrinsic rewards that approximate the KL-divergence of the true transition probabilities from the learned model. One of our approximations results in using surprisal as intrinsic motivation, while the other gives the $k$-step learning progress. We show that our incentives enable agents to succeed in a wide range of environments with high-dimensional state spaces and very sparse rewards, including continuous control tasks and games in the Atari RAM domain, outperforming several other heuristic exploration techniques.
DIMSpan - Transactional Frequent Subgraph Mining with Distributed In-Memory Dataflow Systems
Venue: arXiv cs.DB 2017
Year: 2017

Transactional frequent subgraph mining identifies frequent subgraphs in a collection of graphs. This research problem has wide applicability and increasingly requires higher scalability over single machine solutions to address the needs of Big Data use cases. We introduce DIMSpan, an advanced approach to frequent subgraph mining that utilizes the features provided by distributed in-memory dataflow systems such as Apache Spark or Apache Flink. It determines the complete set of frequent subgraphs from arbitrary string-labeled directed multigraphs as they occur in social, business and knowledge networks. DIMSpan is optimized to runtime and minimal network traffic but memory-aware. An extensive performance evaluation on large graph collections shows the scalability of DIMSpan and the effectiveness of its pruning and optimization techniques.
High-Resolution Multispectral Dataset for Semantic Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

Unmanned aircraft have decreased the cost required to collect remote sensing imagery, which has enabled researchers to collect high-spatial resolution data from multiple sensor modalities more frequently and easily. The increase in data will push the need for semantic segmentation frameworks that are able to classify non-RGB imagery, but this type of algorithmic development requires an increase in publicly available benchmark datasets with class labels. In this paper, we introduce a high-resolution multispectral dataset with image labels. This new benchmark dataset has been pre-split into training/testing folds in order to standardize evaluation and continue to push state-of-the-art classification frameworks for non-RGB imagery.
Exchangeable choice functions
Venue: arXiv cs.AI 2017
Year: 2017

We investigate how to model exchangeability with choice functions. Exchangeability is a structural assessment on a sequence of uncertain variables. We show how such assessments are a special indifference assessment, and how that leads to a counterpart of de Finetti's Representation Theorem, both in a finite and a countable context.
Distributed Exact Shortest Paths in Sublinear Time
Venue: arXiv cs.DS 2017
Year: 2017

The distributed single-source shortest paths problem is one of the most fundamental and central problems in the message-passing distributed computing. Classical Bellman-Ford algorithm solves it in $O(n)$ time, where $n$ is the number of vertices in the input graph $G$. Peleg and Rubinovich (FOCS'99) showed a lower bound of $\tildeΩ(D + \sqrt{n})$ for this problem, where $D$ is the hop-diameter of $G$. Whether or not this problem can be solved in $o(n)$ time when $D$ is relatively small is a major notorious open question. Despite intensive research \cite{LP13,N14,HKN15,EN16,BKKL16} that yielded near-optimal algorithms for the approximate variant of this problem, no progress was reported for the original problem. In this paper we answer this question in the affirmative. We devise an algorithm that requires $O((n \log n)^{5/6})$ time, for $D = O(\sqrt{n \log n})$, and $O(D^{1/3} \cdot (n \log n)^{2/3})$ time, for larger $D$. This running time is sublinear in $n$ in almost the entire range of parameters, specifically, for $D = o(n/\log^2 n)$. For the all-pairs shortest paths problem, our algorithm requires $O(n^{5/3} \log^{2/3} n)$ time, regardless of the value of $D$. We also devise the first algorithm with non-trivial complexity guarantees for computing exact shortest paths in the multipass semi-streaming model of computation. From the technical viewpoint, our algorithm computes a hopset $G"$ of a skeleton graph $G'$ of $G$ without first computing $G'$ itself. We then conduct a Bellman-Ford exploration in $G' \cup G"$, while computing the required edges of $G'$ on the fly. As a result, our algorithm computes exactly those edges of $G'$ that it really needs, rather than computing approximately the entire $G'$.
D2D Communications in LoRaWAN Low Power Wide Area Network: From Idea to Empirical Validation
Venue: arXiv cs.NI 2017
Year: 2017

In this paper we advocate the use of device-to-device (D2D) communications in a LoRaWAN Low Power Wide Area Network (LPWAN). After overviewing the critical features of the LoRaWAN technology, we discuss the pros and cons of enabling the D2D communications for it. Subsequently we propose a network-assisted D2D communications protocol and show its feasibility by implementing it on top of a LoRaWAN-certified commercial transceiver. The conducted experiments show the performance of the proposed D2D communications protocol and enable us to assess its performance. More precisely, we show that the D2D communications can reduce the time and energy for data transfer by 6 to 20 times compared to conventional LoRaWAN data transfer mechanisms. In addition, the use of D2D communications may have a positive effect on the network by enabling spatial re-use of the frequency resources. The proposed LoRaWAN D2D communications can be used for a wide variety of applications requiring high coverage, e.g. use cases in distributed smart grid deployments for management and trading.
Distributed Beamforming with Wirelessly Powered Relay Nodes
Venue: arXiv cs.IT 2017
Year: 2017

This paper studies a system where a set of $N$ relay nodes harvest energy from the signal received from a source to later utilize it when forwarding the source's data to a destination node via distributed beamforming. To this end, we derive (approximate) analytical expressions for the mean SNR at destination node when relays employ: i) time-switching based energy harvesting policy, ii) power-splitting based energy harvesting policy. The obtained results facilitate the study of the interplay between the energy harvesting parameters and the synchronization error, and their combined impact on mean SNR. Simulation results indicate that i) the derived approximate expressions are very accurate even for small $N$ (e.g., $N=15$), ii) time-switching policy by the relays outperforms power-splitting policy by at least $3$ dB.
The Feasibility of Dynamically Granted Permissions: Aligning Mobile Privacy with User Preferences
Venue: arXiv cs.CR 2017
Year: 2017

Current smartphone operating systems regulate application permissions by prompting users on an ask-on-first-use basis. Prior research has shown that this method is ineffective because it fails to account for context: the circumstances under which an application first requests access to data may be vastly different than the circumstances under which it subsequently requests access. We performed a longitudinal 131-person field study to analyze the contextuality behind user privacy decisions to regulate access to sensitive resources. We built a classifier to make privacy decisions on the user's behalf by detecting when context has changed and, when necessary, inferring privacy preferences based on the user's past decisions and behavior. Our goal is to automatically grant appropriate resource requests without further user intervention, deny inappropriate requests, and only prompt the user when the system is uncertain of the user's preferences. We show that our approach can accurately predict users' privacy decisions 96.8% of the time, which is a four-fold reduction in error rate compared to current systems.
Evaluation of Machine Learning Methods to Predict Coronary Artery Disease Using Metabolomic Data
Venue: arXiv cs.LG 2017
Year: 2017

Metabolomic data can potentially enable accurate, non-invasive and low-cost prediction of coronary artery disease. Regression-based analytical approaches however might fail to fully account for interactions between metabolites, rely on a priori selected input features and thus might suffer from poorer accuracy. Supervised machine learning methods can potentially be used in order to fully exploit the dimensionality and richness of the data. In this paper, we systematically implement and evaluate a set of supervised learning methods (L1 regression, random forest classifier) and compare them to traditional regression-based approaches for disease prediction using metabolomic data.
Computing in Memory with Spin-Transfer Torque Magnetic RAM
Venue: arXiv cs.ET 2017
Year: 2017

In-memory computing is a promising approach to addressing the processor-memory data transfer bottleneck in computing systems. We propose Spin-Transfer Torque Compute-in-Memory (STT-CiM), a design for in-memory computing with Spin-Transfer Torque Magnetic RAM (STT-MRAM). The unique properties of spintronic memory allow multiple wordlines within an array to be simultaneously enabled, opening up the possibility of directly sensing functions of the values stored in multiple rows using a single access. We propose modifications to STT-MRAM peripheral circuits that leverage this principle to perform logic, arithmetic, and complex vector operations. We address the challenge of reliable in-memory computing under process variations by extending ECC schemes to detect and correct errors that occur during CiM operations. We also address the question of how STT-CiM should be integrated within a general-purpose computing system. To this end, we propose architectural enhancements to processor instruction sets and on-chip buses that enable STT-CiM to be utilized as a scratchpad memory. Finally, we present data mapping techniques to increase the effectiveness of STT-CiM. We evaluate STT-CiM using a device-to-architecture modeling framework, and integrate cycle-accurate models of STT-CiM with a commercial processor and on-chip bus (Nios II and Avalon from Intel). Our system-level evaluation shows that STT-CiM provides system-level performance improvements of 3.93x on average (upto 10.4x), and concurrently reduces memory system energy by 3.83x on average (upto 12.4x).