OpenRaiser/Intern-Atlas huggingface dataset:
Approximation algorithms for two-machine flow-shop scheduling with a conflict graph
Venue: arXiv cs.DS 2018
Year: 2018

Path cover is a well-known intractable problem that finds a minimum number of vertex disjoint paths in a given graph to cover all the vertices. We show that a variant, where the objective function is not the number of paths but the number of length-$0$ paths (that is, isolated vertices), turns out to be polynomial-time solvable. We further show that another variant, where the objective function is the total number of length-$0$ and length-$1$ paths, is also polynomial-time solvable. Both variants find applications in approximating the two-machine flow-shop scheduling problem in which job processing has constraints that are formulated as a conflict graph. For the unit jobs, we present a $4/3$-approximation algorithm for the scheduling problem with an arbitrary conflict graph, based on the exact algorithm for the variants of the path cover problem. For the arbitrary jobs while the conflict graph is the union of two disjoint cliques, that is, all the jobs can be partitioned into two groups such that the jobs in a group are pairwise conflicting, we present a simple $3/2$-approximation algorithm.
Distributed Base Station: A Concept System for Long-Range Broadband Wireless Access
Venue: arXiv cs.IT 2018
Year: 2018

We propose a concept system termed distributed base station (DBS), which enables distributed transmit beamforming at large carrier wavelengths to achieve significant range extension and/or increased downlink data rate, providing a low-cost infrastructure for applications such as rural broadband. We consider a frequency division duplexed (FDD) system, using feedback from the receiver to achieve the required phase coherence. At a given range, $N$ cooperating transmitters can achieve $N^2$-fold increase in received power compared to that for a single transmitters, and feedback-based algorithms with near-ideal performance have been prototyped. In this paper, however, we identify and address key technical issues in translating such power gains into range extension via a DBS. First, to combat the drop in per-node SNR with extended range, we design a feedback-based adaptation strategy that is suitably robust to noise. Second, to utilize available system bandwidth, we extend narrowband adaptation algorithms to wideband channels through interpolation over OFDM subcarriers. Third, we observe that the feedback channel may become a bottleneck unless sophisticated distributed reception strategies are employed, but show that acceptable performance can still be obtained with standard uplink reception if channel time variations are slow enough. We quantify system performance compactly via outage capacity analyses.
Synthesis in pMDPs: A Tale of 1001 Parameters
Venue: arXiv cs.AI 2018
Year: 2018

This paper considers parametric Markov decision processes (pMDPs) whose transitions are equipped with affine functions over a finite set of parameters. The synthesis problem is to find a parameter valuation such that the instantiated pMDP satisfies a specification under all strategies. We show that this problem can be formulated as a quadratically-constrained quadratic program (QCQP) and is non-convex in general. To deal with the NP-hardness of such problems, we exploit a convex-concave procedure (CCP) to iteratively obtain local optima. An appropriate interplay between CCP solvers and probabilistic model checkers creates a procedure --- realized in the open-source tool PROPhESY --- that solves the synthesis problem for models with thousands of parameters.
Towards Bi-Directional Communication in Human-Swarm Teaming: A Survey
Venue: arXiv cs.HC 2018
Year: 2018

Swarm systems consist of large numbers of robots that collaborate autonomously. With an appropriate level of human control, swarm systems could be applied in a variety of contexts ranging from search-and-rescue situations to Cyber defence. The two decision making cycles of swarms and humans operate on two different time-scales, where the former is normally orders of magnitude faster than the latter. Closing the loop at the intersection of these two cycles will create fast and adaptive human-swarm teaming networks. This paper brings desperate pieces of the ground work in this research area together to review this multidisciplinary literature. We conclude with a framework to synthesize the findings and summarize the multi-modal indicators needed for closed-loop human-swarm adaptive systems.
On the Complexity of Pointer Arithmetic in Separation Logic (an extended version)
Venue: arXiv cs.LO 2018
Year: 2018

We investigate the complexity consequences of adding pointer arithmetic to separation logic. Specifically, we study extensions of the points-to fragment of symbolic-heap separation logic with various forms of Presburger arithmetic constraints. Most significantly, we find that, even in the minimal case when we allow only conjunctions of simple "difference constraints" (x'\leq x+k) where k is an integer, polynomial-time decidability is already impossible: satisfiability becomes NP-complete, while quantifier-free entailment becomes coNP-complete and quantified entailment becomes P2-complete (P2 is the second class in the polynomial-time hierarchy) In fact we prove that the upper bound is the same, P2, even for the full pointer arithmetic but with a fixed pointer offset, where we allow any Boolean combinations of the elementary formulas (x'=x+k0), (x'\leq x+k0), and (x'<x+k0), and, in addition to the points-to formulas, we allow spatial formulas of the arrays the length of which is bounded by k0 and lists which length is bounded by k0, etc, where k0 is a fixed integer. However, if we allow a significantly more expressive form of pointer arithmetic - namely arbitrary Boolean combinations of elementary formulas over arbitrary pointer sums - then the complexity increase is relatively modest for satisfiability and quantifier-free entailment: they are still NP-complete and coNP-complete respectively, and the complexity appears to increase drastically for quantified entailments.
Automatic Detection of Public Development Projects in Large Open Source Ecosystems: An Exploratory Study on GitHub
Venue: arXiv cs.SE 2018
Year: 2018

Hosting over 10 million of software projects, GitHub is one of the most important data sources to study behavior of developers and software projects. However, with the increase of the size of open source datasets, the potential threats to mining these datasets have also grown. As the dataset grows, it becomes gradually unrealistic for human to confirm quality of all samples. Some studies have investigated this problem and provided solutions to avoid threats in sample selection, but some of these solutions (e.g., finding development projects) require human intervention. When the amount of data to be processed increases, these semi-automatic solutions become less useful since the effort in need for human intervention is far beyond affordable. To solve this problem, we investigated the GHTorrent dataset and proposed a method to detect public development projects. The results show that our method can effectively improve the sample selection process in two ways: (1) We provide a simple model to automatically select samples (with 0.827 precision and 0.947 recall); (2) We also offer a complex model to help researchers carefully screen samples (with 63.2% less effort than manually confirming all samples, and can achieve 0.926 precision and 0.959 recall).
Predicting Software Defects through SVM: An Empirical Approach
Venue: arXiv cs.SE 2018
Year: 2018

Software defect prediction is an important aspect of preventive maintenance of a software. Many techniques have been employed to improve software quality through defect prediction. This paper introduces an approach of defect prediction through a machine learning algorithm, support vector machines (SVM), by using the code smells as the factor. Smell prediction model based on support vector machines was used to predict defects in the subsequent releases of the eclipse software. The results signify the role of smells in predicting the defects of a software. The results can further be used as a baseline to investigate further the role of smells in predicting defects.
Efficient reconfigurable regions management method for adaptive and dynamic FPGA based systems
Venue: arXiv cs.AR 2018
Year: 2018

Adaptive systems based on field programmable gate array (FPGA) architectures can greatly benefi t fro m th e high degree of flexibility offered by dynamic partial reconfiguration (DPR). By using this technique, hardware tasks can be loaded and reloaded on demand depending on the system requirements. In this paper, we propose to use the DPR for dynamic and adaptive implementation of a video cut detection application based on the MPEG-7 color structure descriptor (CSD). In the proposed implementation, different scenarios have been tested. Depending on the application and the system requirements, the CSD module can be loaded at any time with variable module size (corresponding to different version of the CSD) and allocated in different possible reconfigurable regions. Such implementation entails many problems related to communication, relocation and reconfigurable region management. We will demonstrate how we have made this implementation successful through the use of an appropriate design method. This method was proposed to support the management of variable-size hardware tasks on DPR FPGAs based adaptive systems. It permits to efficiently handle the reconfigurable area and to relocate the reconfigurable modules in different possible regions. The implementation results for the considered application show an important optimization in terms of configuration time (until 66 %) and memory storage (until 87 %) and an efficient hardware resources utilization rate (until 90%).
On $k$-error linear complexity of pseudorandom binary sequences derived from Euler quotients
Venue: arXiv cs.CR 2018
Year: 2018

We investigate the $k$-error linear complexity of pseudorandom binary sequences of period $p^{\mathfrak{r}}$ derived from the Euler quotients modulo $p^{\mathfrak{r}-1}$, a power of an odd prime $p$ for $\mathfrak{r}\geq 2$. When $\mathfrak{r}=2$, this is just the case of polynomial quotients (including Fermat quotients) modulo $p$, which has been studied in an earlier work of Chen, Niu and Wu. In this work, we establish a recursive relation on the $k$-error linear complexity of the sequences for the case of $\mathfrak{r}\geq 3$. We also state the exact values of the $k$-error linear complexity for the case of $\mathfrak{r}=3$. From the results, we can find that the $k$-error linear complexity of the sequences (of period $p^{\mathfrak{r}}$) does not decrease dramatically for $k<p^{\mathfrak{r}-2}(p-1)^2/2$.
High-Accuracy Low-Precision Training
Venue: arXiv cs.LG 2018
Year: 2018

Low-precision computation is often used to lower the time and energy cost of machine learning, and recently hardware accelerators have been developed to support it. Still, it has been used primarily for inference - not training. Previous low-precision training algorithms suffered from a fundamental tradeoff: as the number of bits of precision is lowered, quantization noise is added to the model, which limits statistical accuracy. To address this issue, we describe a simple low-precision stochastic gradient descent variant called HALP. HALP converges at the same theoretical rate as full-precision algorithms despite the noise introduced by using low precision throughout execution. The key idea is to use SVRG to reduce gradient variance, and to combine this with a novel technique called bit centering to reduce quantization error. We show that on the CPU, HALP can run up to $4 \times$ faster than full-precision SVRG and can match its convergence trajectory. We implemented HALP in TensorQuant, and show that it exceeds the validation performance of plain low-precision SGD on two deep learning tasks.
MOSQUITO: Covert Ultrasonic Transmissions between Two Air-Gapped Computers using Speaker-to-Speaker Communication
Venue: arXiv cs.CR 2018
Year: 2018

In this paper we show how two (or more) airgapped computers in the same room, equipped with passive speakers, headphones, or earphones can covertly exchange data via ultrasonic waves. Microphones are not required. Our method is based on the capability of a malware to exploit a specific audio chip feature in order to reverse the connected speakers from output devices into input devices - unobtrusively rendering them microphones. We discuss the attack model and provide technical background and implementation details. We show that although the reversed speakers/headphones/earphones were not originally designed to perform as microphones, they still respond well to the near-ultrasonic range (18kHz to 24kHz). We evaluate the communication channel with different equipment, and at various distances and transmission speeds, and also discuss some practical considerations. Our results show that the speaker-to-speaker communication can be used to covertly transmit data between two air-gapped computers positioned a maximum of nine meters away from one another. Moreover, we show that two (microphone-less) headphones can exchange data from a distance of three meters apart. This enables 'headphones-to-headphones' covert communication, which is discussed for the first time in this paper.
Coalitions & Voting Power in the Greek Parliament of 2012: A Case-Study
Venue: arXiv cs.GT 2018
Year: 2018

We revisit the May and June 2012 Greek Parliamentary elections and the December 2014 Presidential election that was held by the June-elected Parliament. The three voting instances provide a political field experiment for the application of power indices and their interpretation in context. We model the Greek Parliament as a weighted majority game and assess voting power with the Shapley-Shubik, Holler and when relevant, Coleman's indices. Also, based on the actual events, we establish connections between parties and evaluate the Myerson index. We focus on the influence of institutional rules on the distribution of power among the elected political parties and add an alternative input to the ongoing political debate about the reform of both the Parliamentary and Presidential electoral system in Greece. Additionally, our findings contribute to the understanding of the coalition formation process in the particular context and provide empirical evidence on the performance of non-selective indices in parliamentary multi-party settings which can be used for comparison by similar case-studies in the future.
The many faces of mobility: Using bibliometric data to measure the movement of scientists
Venue: arXiv cs.DL 2018
Year: 2018

This paper presents a methodological framework for developing scientific mobility indicators based on bibliometric data. We identify nearly 16 million individual authors from publications covered in the Web of Science for the 2008-2015 period. Based on the information provided across individuals' publication records, we propose a general classification for analyzing scientific mobility using institutional affiliation changes. We distinguish between migrants--authors who have ruptures with their country of origin--and travelers--authors who gain additional affiliations while maintaining affiliation with their country of origin. We find that 3.7 percent of researchers who have published at least one paper over the period are mobile. Travelers represent 72.7 percent of all mobile scholars, but migrants have higher scientific impact. We apply this classification at the country level, expanding the classification to incorporate the directionality of scientists' mobility (i.e., incoming and outgoing). We provide a brief analysis to highlight the utility of the proposed taxonomy to study scholarly mobility and discuss the implications for science policy.
Improving lifecycle query in integrated toolchains using linked data and MQTT-based data warehousing
Venue: arXiv cs.SE 2018
Year: 2018

The development of increasingly complex IoT systems requires large engineering environments. These environments generally consist of tools from different vendors and are not necessarily integrated well with each other. In order to automate various analyses, queries across resources from multiple tools have to be executed in parallel to the engineering activities. In this paper, we identify the necessary requirements on such a query capability and evaluate different architectures according to these requirements. We propose an improved lifecycle query architecture, which builds upon the existing Tracked Resource Set (TRS) protocol, and complements it with the MQTT messaging protocol in order to allow the data in the warehouse to be kept updated in real-time. As part of the case study focusing on the development of an IoT automated warehouse, this architecture was implemented for a toolchain integrated using RESTful microservices and linked data.
Explaining Black-box Android Malware Detection
Venue: arXiv cs.LG 2018
Year: 2018

Machine-learning models have been recently used for detecting malicious Android applications, reporting impressive performances on benchmark datasets, even when trained only on features statically extracted from the application, such as system calls and permissions. However, recent findings have highlighted the fragility of such in-vitro evaluations with benchmark datasets, showing that very few changes to the content of Android malware may suffice to evade detection. How can we thus trust that a malware detector performing well on benchmark data will continue to do so when deployed in an operating environment? To mitigate this issue, the most popular Android malware detectors use linear, explainable machine-learning models to easily identify the most influential features contributing to each decision. In this work, we generalize this approach to any black-box machine- learning model, by leveraging a gradient-based approach to identify the most influential local features. This enables using nonlinear models to potentially increase accuracy without sacrificing interpretability of decisions. Our approach also highlights the global characteristics learned by the model to discriminate between benign and malware applications. Finally, as shown by our empirical analysis on a popular Android malware detection task, it also helps identifying potential vulnerabilities of linear and nonlinear models against adversarial manipulations.
On Optimal Polyline Simplification using the Hausdorff and Fréchet Distance
Venue: arXiv cs.CG 2018
Year: 2018

We revisit the classical polygonal line simplification problem and study it using the Hausdorff distance and Fréchet distance. Interestingly, no previous authors studied line simplification under these measures in its pure form, namely: for a given $\varepsilon$ > 0, choose a minimum size subsequence of the vertices of the input such that the Hausdorff or Fréchet distance between the input and output polylines is at most $\varepsilon$. We analyze how the well-known Douglas-Peucker and Imai-Iri simplification algorithms perform compared to the optimum possible, also in the situation where the algorithms are given a considerably larger error threshold than $\varepsilon$. Furthermore, we show that computing an optimal simplification using the undirected Hausdorff distance is NP-hard. The same holds when using the directed Hausdorff distance from the input to the output polyline, whereas the reverse can be computed in polynomial time. Finally, to compute the optimal simplification from a polygonal line consisting of $n$ vertices under the Fréchet distance, we give an $O(kn^5)$ time algorithm that requires $O(kn^2)$ space, where $k$ is the output complexity of the simplification.
Towards 5G Enabled Tactile Robotic Telesurgery
Venue: arXiv cs.NI 2018
Year: 2018

Robotic telesurgery has a potential to provide extreme and urgent health care services and bring unprecedented opportunities to deliver highly specialized skills globally. It has a significant societal impact and is regarded as one of the appealing use cases of Tactile Internet and 5G applications. However, the performance of robotic telesurgery largely depends on the network performance in terms of latency, jitter and packet loss, especially when telesurgical system is equipped with haptic feedback. This imposes significant challenges to design a reliable and secure but cost-effective communication solution. This article aims to give a better understanding of the characteristics of robotic telesurgical system, and the limiting factors, the possible telesurgery services and the communication quality of service (QoS) requirements of the multi-modal sensory data. Based on this, a viable network architecture enabled by the converged edge and core cloud is presented and the relevant research challenges, open issues and enabling technologies in the 5G communication system are discussed.
A Dynamic Jamming Game for Real-Time Status Updates
Venue: arXiv cs.IT 2018
Year: 2018

We study timely status updates of a real-time system in an adversarial setting. The system samples a physical process, and sends the samples from the source (e.g., a sensor) to the destination (e.g, a control center) through a channel. For real-time monitoring/control tasks, it is crucial for the system to update the status of the physical process "timely". We measure the timeliness of status updates by the time elapsed since the latest update at the destination was generated at the source, and define the time elapsed as age of information, or age in short. To sabotage the system, an attacker aims to maximize the age by jamming the channel and hence causing delay in status updates. The system aims to minimize the age by judiciously choosing when to sample and send the updates. We model the ongoing repeated interaction between the attacker and the system as a dynamic game. In each stage game, the attacker chooses the jamming time according to the jamming time distribution, and the system responds by delaying the sampling according to the sampling policy. We prove that there exists a unique stationary equilibrium in the game, and provide a complete analytical characterization of the equilibrium. Our results shed lights on how the attacker sabotages the system and how the system should defend against the attacker.