OpenRaiser/Intern-Atlas huggingface dataset:
Binary Decision Diagrams: from Tree Compaction to Sampling
Venue: arXiv cs.DS 2020
Year: 2020

Any Boolean function corresponds with a complete full binary decision tree. This tree can in turn be represented in a maximally compact form as a direct acyclic graph where common subtrees are factored and shared, keeping only one copy of each unique subtree. This yields the celebrated and widely used structure called reduced ordered binary decision diagram (ROBDD). We propose to revisit the classical compaction process to give a new way of enumerating ROBDDs of a given size without considering fully expanded trees and the compaction step. Our method also provides an unranking procedure for the set of ROBDDs. As a by-product we get a random uniform and exhaustive sampler for ROBDDs for a given number of variables and size.
Steganography using a 3 player game
Venue: arXiv cs.MM 2020
Year: 2020

Image steganography aims to securely embed secret information into cover images. Until now, adaptive embedding algorithms such as S-UNIWARD or Mi-POD, are among the most secure and most used methods for image steganography. With the arrival of deep learning and more specifically the Generative Adversarial Networks (GAN), new techniques have appeared. Among these techniques, there is the 3 player game approaches, where three networks compete against each other.In this paper, we propose three different architectures based on the 3 player game. The first-architecture is proposed as a rigorous alternative to two recent publications. The second takes into account stego noise power. Finally, our third architecture enriches the second one with a better interaction between the embedding and extracting networks. Our method achieves better results compared to the existing works GSIVAT, HiDDeN, and paves the way for future research on this topic.
Step-by-Step Community Detection in Volume-Regular Graphs
Venue: arXiv cs.DC 2020
Year: 2020

Spectral techniques have proved amongst the most effective approaches to graph clustering. However, in general they require explicit computation of the main eigenvectors of a suitable matrix (usually the Laplacian matrix of the graph). Recent work (e.g., Becchetti et al., SODA 2017) suggests that observing the temporal evolution of the power method applied to an initial random vector may, at least in some cases, provide enough information on the space spanned by the first two eigenvectors, so as to allow recovery of a hidden partition without explicit eigenvector computations. While the results of Becchetti et al. apply to perfectly balanced partitions and/or graphs that exhibit very strong forms of regularity, we extend their approach to graphs containing a hidden $k$ partition and characterized by a milder form of volume-regularity. We show that the class of $k$-volume-regular graphs is the largest class of undirected (possibly weighted) graphs whose transition matrix admits $k$ "stepwise" eigenvectors (i.e., vectors that are constant over each set of the hidden partition). To obtain this result, we highlight a connection between volume regularity and lumpability of Markov chains. Moreover, we prove that if the stepwise eigenvectors are those associated to the first $k$ eigenvalues and the gap between the $k$-th and the ($k$+1)-th eigenvalues is sufficiently large, the averaging dynamics of Becchetti et al. recovers the underlying community structure of the graph in logarithmic time, with high probability.
Leveraging online learning for CSS in frugal IoT network
Venue: arXiv cs.IT 2020
Year: 2020

We present a novel method for centralized collaborative spectrum sensing for IoT network leveraging cognitive radio network. Based on an online learning framework, we propose an algorithm to efficiently combine the individual sensing results based on the past performance of each detector. Additionally, we show how to utilize the learned normalized weights as a proxy metric of detection accuracy and selectively enable the sensing at detectors. Our results show improved performance in terms of inter-user collision and misdetection. Further, by selectively enabling some of the devices in the network, we propose a strategy to extend the field life of devices without compromising on detection accuracy.
Scheduling to Minimize Age of Synchronization in Wireless Broadcast Networks with Random Updates
Venue: arXiv cs.IT 2020
Year: 2020

In this work, a wireless broadcast network with a base station (BS) sending random time-sensitive information updates to multiple users with interference constraints is considered. The Age of Synchronization (AoS), namely the amount of time elapsed since the information stored at the network user becomes desynchronized, is adopted to measure data freshness from the perspective of network users. Compared with the more widely used metric---the Age of Information (AoI), AoS accounts for the freshness of the randomly changing content. The AoS minimization scheduling problem is formulated into a discrete time Markov decision process and the optimal solution is approximated through structural finite state policy iteration. An index based heuristic scheduling policy based on restless multi-arm bandit (RMAB) is provided to further reduce computational complexity. Simulation results show that the proposed index policy can achieve compatible performance with the MDP and close to the AoS lower bound. Moreover, theoretic analysis and simulations reveal the differences between AoS and AoI. AoI minimization scheduling policy cannot guarantee a good AoS performance.
Constrained Concealment Attacks against Reconstruction-based Anomaly Detectors in Industrial Control Systems
Venue: arXiv cs.CR 2020
Year: 2020

Recently, reconstruction-based anomaly detection was proposed as an effective technique to detect attacks in dynamic industrial control networks. Unlike classical network anomaly detectors that observe the network traffic, reconstruction-based detectors operate on the measured sensor data, leveraging physical process models learned a priori. In this work, we investigate different approaches to evade prior-work reconstruction-based anomaly detectors by manipulating sensor data so that the attack is concealed. We find that replay attacks (commonly assumed to be very strong) show bad performance (i.e., increasing the number of alarms) if the attacker is constrained to manipulate less than 95% of all features in the system, as hidden correlations between the features are not replicated well. To address this, we propose two novel attacks that manipulate a subset of the sensor readings, leveraging learned physical constraints of the system. Our attacks feature two different attacker models: A white box attacker, which uses an optimization approach with a detection oracle, and a black box attacker, which uses an autoencoder to translate anomalous data into normal data. We evaluate our implementation on two different datasets from the water distribution domain, showing that the detector's Recall drops from 0.68 to 0.12 by manipulating 4 sensors out of 82 in WADI dataset. In addition, we show that our black box attacks are transferable to different detectors: They work against autoencoder-, LSTM-, and CNN-based detectors. Finally, we implement and demonstrate our attacks on a real industrial testbed to demonstrate their feasibility in real-time.
Tactile Model O: Fabrication and testing of a 3d-printed, three-fingered tactile robot hand
Venue: arXiv cs.RO 2020
Year: 2020

Bringing tactile sensation to robotic hands will allow for more effective grasping, along with the wide range of benefits of human-like touch. Here we present a 3D-printed, three-fingered tactile robot hand comprising an OpenHand Model O customized to house a TacTip soft biomimetic tactile sensor in the distal phalanx of each finger. We expect that combining the grasping capabilities of this underactuated hand with sophisticated tactile sensing will result in an effective platform for robot hand research -- the Tactile Model O (T-MO). The design uses three JeVois machine vision systems, each comprising a miniature camera in the tactile fingertip with a processing module in the base of the hand. To evaluate the capabilities of the T-MO, we benchmark its grasping performance using the Gripper Assessment Benchmark on the YCB object set. Tactile sensing capabilities are evaluated by performing tactile object classification on 26 objects and predicting whether a grasp will successfully lift each object. Results are consistent with the state of the art, taking advantage of advances in deep learning applied to tactile image outputs. Overall, this work demonstrates that the T-MO is an effective platform for robot hand research and we expect it to open-up a range of applications in autonomous object handling. Supplemental video: https://youtu.be/RTcCpgffCrQ.
Self-Attentive Hawkes Processes
Venue: arXiv cs.LG 2020
Year: 2020

Asynchronous events on the continuous time domain, e.g., social media actions and stock transactions, occur frequently in the world. The ability to recognize occurrence patterns of event sequences is crucial to predict which typeof events will happen next and when. A de facto standard mathematical framework to do this is the Hawkes process. In order to enhance expressivity of multivariate Hawkes processes, conventional statistical methods and deep recurrent networks have been employed to modify its intensity function. The former is highly interpretable and requires small size of training data but relies on correct model design while the latter has less dependency on prior knowledge and is more powerful in capturing complicated patterns. We leverage pros and cons of these models and propose a self-attentive Hawkes process(SAHP). The proposed method adapts self-attention to fit the intensity function of Hawkes processes. This design has two benefits:(1) compared with conventional statistical methods, the SAHP is more powerful to identify complicated dependency relationships between temporal events; (2)compared with deep recurrent networks, the self-attention mechanism is able to capture longer historical information, and is more interpretable because the learnt attention weight tensor shows contributions of each historical event. Experiments on four real-world datasets demonstrate the effectiveness of the proposed method.
Analysis of Word Embeddings Using Fuzzy Clustering
Venue: arXiv cs.CL 2020
Year: 2020

In data dominated systems and applications, a concept of representing words in a numerical format has gained a lot of attention. There are a few approaches used to generate such a representation. An interesting issue that should be considered is the ability of such representations - called embeddings - to imitate human-based semantic similarity between words. In this study, we perform a fuzzy-based analysis of vector representations of words, i.e., word embeddings. We use two popular fuzzy clustering algorithms on count-based word embeddings, known as GloVe, of different dimensionality. Words from WordSim-353, called the gold standard, are represented as vectors and clustered. The results indicate that fuzzy clustering algorithms are very sensitive to high-dimensional data, and parameter tuning can dramatically change their performance. We show that by adjusting the value of the fuzzifier parameter, fuzzy clustering can be successfully applied to vectors of high - up to one hundred - dimensions. Additionally, we illustrate that fuzzy clustering allows to provide interesting results regarding membership of words to different clusters.
A Sequential Composition Framework for Coordinating Multi-Robot Behaviors
Venue: arXiv cs.RO 2020
Year: 2020

A number of coordinated behaviors have been proposed for achieving specific tasks for multi-robot systems. However, since most applications require more than one such behavior, one needs to be able to compose together sequences of behaviors while respecting local information flow constraints. Specifically, when the inter-agent communication depends on inter-robot distances, these constraints translate into particular configurations that must be reached in finite time in order for the system to be able to transition between the behaviors. To this end, we develop a distributed framework based on finite-time convergence control barrier functions that enables a team of robots to adjust its configuration in order to meet the communication requirements for the different tasks. In order to demonstrate the significance of the proposed framework, we implemented a full-scale scenario where a team of eight planar robots explore an urban environment in order to localize and rescue a subject.
A Survey on the Use of Preferences for Virtual Machine Placement in Cloud Data Centers
Venue: arXiv cs.DC 2020
Year: 2020

With the rapid development of virtualization techniques, cloud data centers allow for cost effective, flexible, and customizable deployments of applications on virtualized infrastructure. Virtual machine (VM) placement aims to assign each virtual machine to a server in the cloud environment. VM Placement is of paramount importance to the design of cloud data centers. Typically, VM placement involves complex relations and multiple design factors as well as local policies that govern the assignment decisions. It also involves different constituents including cloud administrators and customers that might have disparate preferences while opting for a placement solution. Thus, it is often valuable to not only return an optimized solution to the VM placement problem but also a solution that reflects the given preferences of the constituents. In this paper, we provide a detailed review on the role of preferences in the recent literature on VM placement. We further discuss key challenges and identify possible research opportunities to better incorporate preferences within the context of VM placement.
FBLAS: Streaming Linear Algebra on FPGA
Venue: arXiv cs.DC 2020
Year: 2020

Spatial computing architectures pose an attractive alternative to mitigate control and data movement overheads typical of load-store architectures. In practice, these devices are rarely considered in the HPC community due to the steep learning curve, low productivity and lack of available libraries for fundamental operations. High-level synthesis (HLS) tools are facilitating hardware programming, but optimizing for these architectures requires factoring in new transformations and resources/performance trade-offs. We present FBLAS, an open-source HLS implementation of BLAS for FPGAs, that enables reusability, portability and easy integration with existing software and hardware codes. FBLAS' implementation allows scaling hardware modules to exploit on-chip resources, and module interfaces are designed to natively support streaming on-chip communications, allowing them to be composed to reduce off-chip communication. With FBLAS, we set a precedent for FPGA library design, and contribute to the toolbox of customizable hardware components necessary for HPC codes to start productively targeting reconfigurable platforms.
Analog content addressable memories with memristors
Venue: arXiv cs.ET 2020
Year: 2020

A content-addressable-memory compares an input search word against all rows of stored words in an array in a highly parallel manner. While supplying a very powerful functionality for many applications in pattern matching and search, it suffers from large area, cost and power consumption, limiting its use. Past improvements have been realized by using memristors to replace the static-random-access-memory cell in conventional designs, but employ similar schemes based only on binary or ternary states for storage and search. We propose a new analog content-addressable-memory concept and circuit to overcome these limitations by utilizing the analog conductance tunability of memristors. Our analog content-addressable-memory stores data within the programmable conductance and can take as input either analog or digital search values. Experimental demonstrations, scaled simulations and analysis show that our analog content-addressable-memory can reduce area and power consumption, which enables the acceleration of existing applications, but also new computing application areas.
Who is Afraid of Big Bad Minima? Analysis of Gradient-Flow in a Spiked Matrix-Tensor Model
Venue: arXiv cs.LG 2020
Year: 2020

Gradient-based algorithms are effective for many machine learning tasks, but despite ample recent effort and some progress, it often remains unclear why they work in practice in optimising high-dimensional non-convex functions and why they find good minima instead of being trapped in spurious ones. Here we present a quantitative theory explaining this behaviour in a spiked matrix-tensor model. Our framework is based on the Kac-Rice analysis of stationary points and a closed-form analysis of gradient-flow originating from statistical physics. We show that there is a well defined region of parameters where the gradient-flow algorithm finds a good global minimum despite the presence of exponentially many spurious local minima. We show that this is achieved by surfing on saddles that have strong negative direction towards the global minima, a phenomenon that is connected to a BBP-type threshold in the Hessian describing the critical points of the landscapes.
Convergence of Edge Computing and Deep Learning: A Comprehensive Survey
Venue: arXiv cs.NI 2020
Year: 2020

Ubiquitous sensors and smart devices from factories and communities are generating massive amounts of data, and ever-increasing computing power is driving the core of computation and services from the cloud to the edge of the network. As an important enabler broadly changing people's lives, from face recognition to ambitious smart factories and cities, developments of artificial intelligence (especially deep learning, DL) based applications and services are thriving. However, due to efficiency and latency issues, the current cloud computing service architecture hinders the vision of "providing artificial intelligence for every person and every organization at everywhere". Thus, unleashing DL services using resources at the network edge near the data sources has emerged as a desirable solution. Therefore, edge intelligence, aiming to facilitate the deployment of DL services by edge computing, has received significant attention. In addition, DL, as the representative technique of artificial intelligence, can be integrated into edge computing frameworks to build intelligent edge for dynamic, adaptive edge maintenance and management. With regard to mutually beneficial edge intelligence and intelligent edge, this paper introduces and discusses: 1) the application scenarios of both; 2) the practical implementation methods and enabling technologies, namely DL training and inference in the customized edge computing framework; 3) challenges and future trends of more pervasive and fine-grained intelligence. We believe that by consolidating information scattered across the communication, networking, and DL areas, this survey can help readers to understand the connections between enabling technologies while promoting further discussions on the fusion of edge intelligence and intelligent edge, i.e., Edge DL.
Some Polycubes Have No Edge Zipper Unfolding
Venue: arXiv cs.CG 2020
Year: 2020

It is unknown whether every polycube (polyhedron constructed by gluing cubes face-to-face) has an edge unfolding, that is, cuts along edges of the cubes that unfolds the polycube to a single nonoverlapping polygon in the plane. Here we construct polycubes that have no *edge zipper unfolding* where the cut edges are further restricted to form a path.
ASYNC: A Cloud Engine with Asynchrony and History for Distributed Machine Learning
Venue: arXiv cs.DC 2020
Year: 2020

ASYNC is a framework that supports the implementation of asynchrony and history for optimization methods on distributed computing platforms. The popularity of asynchronous optimization methods has increased in distributed machine learning. However, their applicability and practical experimentation on distributed systems are limited because current bulk-processing cloud engines do not provide a robust support for asynchrony and history. With introducing three main modules and bookkeeping system-specific and application parameters, ASYNC provides practitioners with a framework to implement asynchronous machine learning methods. To demonstrate ease-of-implementation in ASYNC, the synchronous and asynchronous variants of two well-known optimization methods, stochastic gradient descent and SAGA, are demonstrated in ASYNC.
A Comprehensive Analysis of Twitter Trending Topics
Venue: arXiv cs.SI 2020
Year: 2020

In Twitter, a name, phrase, or topic that is mentioned at a greater rate than others is called a "trending topic" or simply "trend". Twitter trends list has a powerful ability to promote public events such as natural events, political scandals, market changes and other types of breaking news. Nevertheless, there have been very few works focused on the dynamics of these trending topics. In this article, we thoroughly examined the Twitter's trending topics of 2018. To this end, we automatically accessed Twitter's trends API and stored the resulting 50 top trending topics in a novel dataset. We propose and analyze our dataset according to six criteria: lexical analysis, time to reach, trend reoccurrence, trending time, tweets count, and language analysis. Based on our results, 77.6% of the topics that reached the Top-10 list were trending with less than 100k tweets. More than 50% of the topics could not hold the position for more than an hour. English and Arabic languages comprised close to 40% and 20% of the first rank topics, respectively.
Multiple Server SRPT with speed scaling is competitive
Venue: arXiv cs.PF 2020
Year: 2020

Can the popular shortest remaining processing time (SRPT) algorithm achieve a constant competitive ratio on multiple servers when server speeds are adjustable (speed scaling) with respect to the flow time plus energy consumption metric? This question has remained open for a while, where a negative result in the absence of speed scaling is well known. The main result of this paper is to show that multi-server SRPT can be constant competitive, with a competitive ratio that only depends on the power-usage function of the servers, but not on the number of jobs/servers or the job sizes (unlike when speed scaling is not allowed). When all job sizes are unity, we show that round-robin routing is optimal and can achieve the same competitive ratio as the best known algorithm for the single server problem. Finally, we show that a class of greedy dispatch policies, including policies that route to the least loaded or the shortest queue, do not admit a constant competitive ratio. When job arrivals are stochastic, with Poisson arrivals and i.i.d. job sizes, we show that random routing and a simple gated-static speed scaling algorithm achieves a constant competitive ratio.