OpenRaiser/Intern-Atlas huggingface dataset:
Cascades: A view from Audience
Venue: arXiv cs.SI 2017
Year: 2017

Cascades on online networks have been a popular subject of study in the past decade, and there is a considerable literature on phenomena such as diffusion mechanisms, virality, cascade prediction, and peer network effects. However, a basic question has received comparatively little attention: how desirable are cascades on a social media platform from the point of view of users? While versions of this question have been considered from the perspective of the producers of cascades, any answer to this question must also take into account the effect of cascades on their audience. In this work, we seek to fill this gap by providing a consumer perspective of cascade. Users on online networks play the dual role of producers and consumers. First, we perform an empirical study of the interaction of Twitter users with retweet cascades. We measure how often users observe retweets in their home timeline, and observe a phenomenon that we term the "Impressions Paradox": the share of impressions for cascades of size k decays much slower than frequency of cascades of size k. Thus, the audience for cascades can be quite large even for rare large cascades. We also measure audience engagement with retweet cascades in comparison to non-retweeted content. Our results show that cascades often rival or exceed organic content in engagement received per impression. This result is perhaps surprising in that consumers didn't opt in to see tweets from these authors. Furthermore, although cascading content is widely popular, one would expect it to eventually reach parts of the audience that may not be interested in the content. Motivated by our findings, we posit a theoretical model that focuses on the effect of cascades on the audience. Our results on this model highlight the balance between retweeting as a high-quality content selection mechanism and the role of network users in filtering irrelevant content.
LED-it-GO: Leaking (a lot of) Data from Air-Gapped Computers via the (small) Hard Drive LED
Venue: arXiv cs.CR 2017
Year: 2017

In this paper we present a method which allows attackers to covertly leak data from isolated, air-gapped computers. Our method utilizes the hard disk drive (HDD) activity LED which exists in most of today's desktop PCs, laptops and servers. We show that a malware can indirectly control the HDD LED, turning it on and off rapidly (up to 5800 blinks per second) - a rate that exceeds the visual perception capabilities of humans. Sensitive information can be encoded and leaked over the LED signals, which can then be received remotely by different kinds of cameras and light sensors. Compared to other LED methods, our method is unique, because it is also covert - the HDD activity LED routinely flickers frequently, and therefore the user may not be suspicious to changes in its activity. We discuss attack scenarios and present the necessary technical background regarding the HDD LED and its hardware control. We also present various data modulation methods and describe the implementation of a user-level malware, that doesn't require a kernel component. During the evaluation, we examine the physical characteristics of different colored HDD LEDs (red, blue, and white) and tested different types of receivers: remote cameras, extreme cameras, security cameras, smartphone cameras, drone cameras, and optical sensors. Finally, we discuss hardware and software countermeasures for such a threat. Our experiment shows that sensitive data can be successfully leaked from air-gapped computers via the HDD LED at a maximum bit rate of 4000 bits per second, depending on the type of receiver and its distance from the transmitter. Notably, this speed is 10 times faster than the existing optical covert channels for air-gapped computers. These rates allow fast exfiltration of encryption keys, keystroke logging, and text and binary files.
Efficient CSMA using Regional Free Energy Approximations
Venue: arXiv cs.NI 2017
Year: 2017

CSMA (Carrier Sense Multiple Access) algorithms based on Gibbs sampling can achieve throughput optimality if certain parameters called the fugacities are appropriately chosen. However, the problem of computing these fugacities is NP-hard. In this work, we derive estimates of the fugacities by using a framework called the regional free energy approximations. In particular, we derive explicit expressions for approximate fugacities corresponding to any feasible service rate vector. We further prove that our approximate fugacities are exact for the class of chordal graphs. A distinguishing feature of our work is that the regional approximations that we propose are tailored to conflict graphs with small cycles, which is a typical characteristic of wireless networks. Numerical results indicate that the fugacities obtained by the proposed method are quite accurate and significantly outperform the existing Bethe approximation based techniques.
A Simple Convex Layers Algorithm
Venue: arXiv cs.CG 2017
Year: 2017

Given a set of $n$ points $P$ in the plane, the first layer $L_1$ of $P$ is formed by the points that appear on $P$'s convex hull. In general, a point belongs to layer $L_i$, if it lies on the convex hull of the set $P \setminus \bigcup_{j<i}\{L_j\}$. The \emph{convex layers problem} is to compute the convex layers $L_i$. Existing algorithms for this problem either do not achieve the optimal $\mathcal{O}\left(n\log n\right)$ runtime and linear space, or are overly complex and difficult to apply in practice. We propose a new algorithm that is both optimal and simple. The simplicity is achieved by independently computing four sets of monotone convex chains in $\mathcal{O}\left(n\log n\right)$ time and linear space. These are then merged in $\mathcal{O}\left(n\log n\right)$ time.
Intent Recognition in Smart Living Through Deep Recurrent Neural Networks
Venue: arXiv cs.CY 2017
Year: 2017

Electroencephalography (EEG) signal based intent recognition has recently attracted much attention in both academia and industries, due to helping the elderly or motor-disabled people controlling smart devices to communicate with outer world. However, the utilization of EEG signals is challenged by low accuracy, arduous and time- consuming feature extraction. This paper proposes a 7-layer deep learning model to classify raw EEG signals with the aim of recognizing subjects' intents, to avoid the time consumed in pre-processing and feature extraction. The hyper-parameters are selected by an Orthogonal Array experiment method for efficiency. Our model is applied to an open EEG dataset provided by PhysioNet and achieves the accuracy of 0.9553 on the intent recognition. The applicability of our proposed model is further demonstrated by two use cases of smart living (assisted living with robotics and home automation).
Parameterized Shifted Combinatorial Optimization
Venue: arXiv cs.CC 2017
Year: 2017

Shifted combinatorial optimization is a new nonlinear optimization framework which is a broad extension of standard combinatorial optimization, involving the choice of several feasible solutions at a time. This framework captures well studied and diverse problems ranging from so-called vulnerability problems to sharing and partitioning problems. In particular, every standard combinatorial optimization problem has its shifted counterpart, which is typically much harder. Already with explicitly given input set the shifted problem may be NP-hard. In this article we initiate a study of the parameterized complexity of this framework. First we show that shifting over an explicitly given set with its cardinality as the parameter may be in XP, FPT or P, depending on the objective function. Second, we study the shifted problem over sets definable in MSO logic (which includes, e.g., the well known MSO partitioning problems). Our main results here are that shifted combinatorial optimization over MSO definable sets is in XP with respect to the MSO formula and the treewidth (or more generally clique-width) of the input graph, and is W[1]-hard even under further severe restrictions.
EVE: Explainable Vector Based Embedding Technique Using Wikipedia
Venue: arXiv cs.CL 2017
Year: 2017

We present an unsupervised explainable word embedding technique, called EVE, which is built upon the structure of Wikipedia. The proposed model defines the dimensions of a semantic vector representing a word using human-readable labels, thereby it readily interpretable. Specifically, each vector is constructed using the Wikipedia category graph structure together with the Wikipedia article link structure. To test the effectiveness of the proposed word embedding model, we consider its usefulness in three fundamental tasks: 1) intruder detection - to evaluate its ability to identify a non-coherent vector from a list of coherent vectors, 2) ability to cluster - to evaluate its tendency to group related vectors together while keeping unrelated vectors in separate clusters, and 3) sorting relevant items first - to evaluate its ability to rank vectors (items) relevant to the query in the top order of the result. For each task, we also propose a strategy to generate a task-specific human-interpretable explanation from the model. These demonstrate the overall effectiveness of the explainable embeddings generated by EVE. Finally, we compare EVE with the Word2Vec, FastText, and GloVe embedding techniques across the three tasks, and report improvements over the state-of-the-art.
Distributed Representation of Subgraphs
Venue: arXiv cs.SI 2017
Year: 2017

Network embeddings have become very popular in learning effective feature representations of networks. Motivated by the recent successes of embeddings in natural language processing, researchers have tried to find network embeddings in order to exploit machine learning algorithms for mining tasks like node classification and edge prediction. However, most of the work focuses on finding distributed representations of nodes, which are inherently ill-suited to tasks such as community detection which are intuitively dependent on subgraphs. Here, we propose sub2vec, an unsupervised scalable algorithm to learn feature representations of arbitrary subgraphs. We provide means to characterize similarties between subgraphs and provide theoretical analysis of sub2vec and demonstrate that it preserves the so-called local proximity. We also highlight the usability of sub2vec by leveraging it for network mining tasks, like community detection. We show that sub2vec gets significant gains over state-of-the-art methods and node-embedding methods. In particular, sub2vec offers an approach to generate a richer vocabulary of features of subgraphs to support representation and reasoning.
A Realistic Dataset for the Smart Home Device Scheduling Problem for DCOPs
Venue: arXiv cs.AI 2017
Year: 2017

The field of Distributed Constraint Optimization has gained momentum in recent years thanks to its ability to address various applications related to multi-agent cooperation. While techniques to solve Distributed Constraint Optimization Problems (DCOPs) are abundant and have matured substantially since the field inception, the number of DCOP realistic applications and benchmark used to asses the performance of DCOP algorithms is lagging behind. To contrast this background we (i) introduce the Smart Home Device Scheduling (SHDS) problem, which describe the problem of coordinating smart devices schedules across multiple homes as a multi-agent system, (ii) detail the physical models adopted to simulate smart sensors, smart actuators, and homes environments, and (iii) introduce a DCOP realistic benchmark for SHDS problems.
Theoretical and Experimental Analysis of the Canadian Traveler Problem
Venue: arXiv cs.AI 2017
Year: 2017

Devising an optimal strategy for navigation in a partially observable environment is one of the key objectives in AI. One of the problem in this context is the Canadian Traveler Problem (CTP). CTP is a navigation problem where an agent is tasked to travel from source to target in a partially observable weighted graph, whose edge might be blocked with a certain probability and observing such blockage occurs only when reaching upon one of the edges end points. The goal is to find a strategy that minimizes the expected travel cost. The problem is known to be P$\#$ hard. In this work we study the CTP theoretically and empirically. First, we study the Dep-CTP, a CTP variant we introduce which assumes dependencies between the edges status. We show that Dep-CTP is intractable, and further we analyze two of its subclasses on disjoint paths graph. Second, we develop a general algorithm Gen-PAO that optimally solve the CTP. Gen-PAO is capable of solving two other types of CTP called Sensing-CTP and Expensive-Edges CTP. Since the CTP is intractable, Gen-PAO use some pruning methods to reduce the space search for the optimal solution. We also define some variants of Gen-PAO, compare their performance and show some benefits of Gen-PAO over existing work.
An Initial Study on Ideal GUI Test Case Replayability
Venue: arXiv cs.SE 2017
Year: 2017

In this paper we investigate the effect of long-term GUI changes occurring during application development on the reusability of existing GUI test cases. We conduct an empirical evaluation on two complex, open-source GUI-driven applications for which we generate test cases of various lengths. We then assess the replayability of generated test cases using simulation on newer versions of the target applications and partition them according to the type of repairing change required for their reuse.
On the Complexity of Simple and Optimal Deterministic Mechanisms for an Additive Buyer
Venue: arXiv cs.GT 2017
Year: 2017

We show that the Revenue-Optimal Deterministic Mechanism Design problem for a single additive buyer is #P-hard, even when the distributions have support size 2 for each item and, more importantly, even when the optimal solution is guaranteed to be of a very simple kind: the seller picks a price for each individual item and a price for the grand bundle of all the items; the buyer can purchase either the grand bundle at its given price or any subset of items at their total individual prices. The following problems are also #P-hard, as immediate corollaries of the proof: 1. determining if individual item pricing is optimal for a given instance, 2. determining if grand bundle pricing is optimal, and 3. computing the optimal (deterministic) revenue. On the positive side, we show that when the distributions are i.i.d. with support size 2, the optimal revenue obtainable by any mechanism, even a randomized one, can be achieved by a simple solution of the above kind (individual item pricing with a discounted price for the grand bundle) and furthermore, it can be computed in polynomial time. The problem can be solved in polynomial time too when the number of items is constant.
Replication of Virtual Network Functions: Optimizing Link Utilization and Resource Costs
Venue: arXiv cs.NI 2017
Year: 2017

Network Function Virtualization (NFV) is enabling the softwarization of traditional network services, commonly deployed in dedicated hardware, into generic hardware in form of Virtual Network Functions (VNFs), which can be located flexibly in the network. However, network load balancing can be critical for an ordered sequence of VNFs, also known as Service Function Chains (SFCs), a common cloud and network service approach today. The placement of these chained functions increases the ping-pong traffic between VNFs, directly affecting to the efficiency of bandwidth utilization. The optimization of the placement of these VNFs is a challenge as also other factors need to be considered, such as the resource utilization. To address this issue, we study the problem of VNF placement with replications, and especially the potential of VNFs replications to help load balance the network, while the server utilization is minimized. In this paper we present a Linear Programming (LP) model for the optimum placement of functions finding a trade-off between the minimization of two objectives: the link utilization and CPU resource usage. The results show how the model load balance the utilization of all links in the network using minimum resources.
Massive MIMO 5G Cellular Networks: mm-wave vs. μ-wave Frequencies
Venue: arXiv cs.IT 2017
Year: 2017

Enhanced mobile broadband (eMBB) is one of the key use-cases for the development of the new standard 5G New Radio for the next generation of mobile wireless networks. Large-scale antenna arrays, a.k.a. Massive MIMO, the usage of carrier frequencies in the range 10-100 GHz, the so-called millimeter wave (mm-wave) band, and the network densification with the introduction of small-sized cells are the three technologies that will permit implementing eMBB services and realizing the Gbit/s mobile wireless experience. This paper is focused on the massive MIMO technology; initially conceived for conventional cellular frequencies in the sub-6 GHz range (μ-wave), the massive MIMO concept has been then progressively extended to the case in which mm-wave frequencies are used. However, due to different propagation mechanisms in urban scenarios, the resulting MIMO channel models at μ-wave and mm-wave are radically different. Six key basic differences are pinpointed in this paper, along with the implications that they have on the architecture and algorithms of the communication transceivers and on the attainable performance in terms of reliability and multiplexing capabilities.
A Novel Index Coding Scheme and its Application to Coded Caching
Venue: arXiv cs.IT 2017
Year: 2017

This paper proposes a novel achievable scheme for the index problem and applies it to the caching problem. Index coding and caching are noiseless broadcast channel problems where receivers have message side information.In the index coding problem the side information sets are fixed, while in the caching problem the side information sets correspond the cache contents, which are under the control of the system designer. The proposed index coding scheme, based on distributed source coding and non-unique decoding,is shown to strictly enlarge the rate region achievable by composite coding.The novel index coding scheme applied to the caching problem is then shown to match an outer bound (previously proposed by the authors and also based on known results for the index coding problem) under the assumption of uncoded cache placement/prefetching.
Are Emojis Predictable?
Venue: arXiv cs.CL 2017
Year: 2017

Emojis are ideograms which are naturally combined with plain text to visually complement or condense the meaning of a message. Despite being widely used in social media, their underlying semantics have received little attention from a Natural Language Processing standpoint. In this paper, we investigate the relation between words and emojis, studying the novel task of predicting which emojis are evoked by text-based tweet messages. We train several models based on Long Short-Term Memory networks (LSTMs) in this task. Our experimental results show that our neural model outperforms two baselines as well as humans solving the same task, suggesting that computational models are able to better capture the underlying semantics of emojis.
Making Asynchronous Distributed Computations Robust to Noise
Venue: arXiv cs.DS 2017
Year: 2017

We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interactive coding scheme which simulates any asynchronous distributed protocol while tolerating an optimal corruption of a $Θ(1/n)$ fraction of all messages while incurring a moderate blowup of $O(n\log^2 n)$ in the communication complexity. Our result is the first fully distributed interactive coding scheme in which the topology of the communication network is not known in advance. Prior work required either a coordinating node to be connected to all other nodes in the network or assumed a synchronous network in which all nodes already know the complete topology of the network.
Control of the Correlation of Spontaneous Neuron Activity in Biological and Noise-activated CMOS Artificial Neural Microcircuits
Venue: arXiv cs.NE 2017
Year: 2017

There are several indications that brain is organized not on a basis of individual unreliable neurons, but on a micro-circuital scale providing Lego blocks employed to create complex architectures. At such an intermediate scale, the firing activity in the microcircuits is governed by collective effects emerging by the background noise soliciting spontaneous firing, the degree of mutual connections between the neurons, and the topology of the connections. We compare spontaneous firing activity of small populations of neurons adhering to an engineered scaffold with simulations of biologically plausible CMOS artificial neuron populations whose spontaneous activity is ignited by tailored background noise. We provide a full set of flexible and low-power consuming silicon blocks including neurons, excitatory and inhibitory synapses, and both white and pink noise generators for spontaneous firing activation. We achieve a comparable degree of correlation of the firing activity of the biological neurons by controlling the kind and the number of connection among the silicon neurons. The correlation between groups of neurons, organized as a ring of four distinct populations connected by the equivalent of interneurons, is triggered more effectively by adding multiple synapses to the connections than increasing the number of independent point-to-point connections. The comparison between the biological and the artificial systems suggests that a considerable number of synapses is active also in biological populations adhering to engineered scaffolds.
Bandits with Movement Costs and Adaptive Pricing
Venue: arXiv cs.LG 2017
Year: 2017

We extend the model of Multi-armed Bandit with unit switching cost to incorporate a metric between the actions. We consider the case where the metric over the actions can be modeled by a complete binary tree, and the distance between two leaves is the size of the subtree of their least common ancestor, which abstracts the case that the actions are points on the continuous interval $[0,1]$ and the switching cost is their distance. In this setting, we give a new algorithm that establishes a regret of $\widetilde{O}(\sqrt{kT} + T/k)$, where $k$ is the number of actions and $T$ is the time horizon. When the set of actions corresponds to whole $[0,1]$ interval we can exploit our method for the task of bandit learning with Lipschitz loss functions, where our algorithm achieves an optimal regret rate of $\widetildeΘ(T^{2/3})$, which is the same rate one obtains when there is no penalty for movements. As our main application, we use our new algorithm to solve an adaptive pricing problem. Specifically, we consider the case of a single seller faced with a stream of patient buyers. Each buyer has a private value and a window of time in which they are interested in buying, and they buy at the lowest price in the window, if it is below their value. We show that with an appropriate discretization of the prices, the seller can achieve a regret of $\widetilde{O}(T^{2/3})$ compared to the best fixed price in hindsight, which outperform the previous regret bound of $\widetilde{O}(T^{3/4})$ for the problem.