OpenRaiser/Intern-Atlas huggingface dataset:
D2D Multicast in Underlay Cellular Networks with Exclusion Zones
Venue: arXiv cs.NI 2019
Year: 2019

Underlay device-to-device (D2D) multicast communication has potential to improve performance of cellular networks. However, co-channel interference among cellular users (CUs) and D2D multicast groups (MGs) limits the gains of such communication. Allowing the CUs to have exclusion zones around them where no receiver of any MG can exist, is a realistic and pragmatic approach to reduce the co-channel interference of cellular transmission on D2D multicast reception. We use a stochastic geometry based approach to model this scenario. Specifically, we model the locations of CUs and D2D MG receivers with homogeneous Poisson Point Process (PPP), and Poisson Hole Process (PHP), respectively. We formulate the network sum throughput maximization problem in terms of a joint MG channel and power allocation problem with constraints on cellular and MG users maximum transmit and acceptable quality of service. We establish that the MG channel allocation problem has computational complexity that is exponential in both, the number of MGs and the number of available cellular channels. Then, we decompose this problem into two subproblems: subset selection problem and subset channel assignment problem. Based on observations and insights obtained from numerical analysis of the optimal solution of the subset selection problem in wide variety of scenarios, we propose a computationally efficient scheme that achieves almost optimal performance for the subset selection problem. We further provide a computationally efficient algorithm that achieves almost optimal performance for the subset channel assignment problem. Finally, combining these two schemes, we provide a computationally efficient and almost optimal scheme to solve the channel allocation problem, and various results and insights on the variation of the optimal system performance with respect to different system parameters
QKD in Isabelle -- Bayesian Calculation
Venue: arXiv cs.CR 2019
Year: 2019

In this paper, we present a first step towards a formalisation of the Quantum Key Distribution algorithm in Isabelle. We focus on the formalisation of the main probabilistic argument why Bob cannot be certain about the key bit sent by Alice before he does not have the chance to compare the chosen polarization scheme. This means that any adversary Eve is in the same position as Bob and cannot be certain about the transmitted keybits. We introduce the necessary basic probability theory, present a graphical depiction of the protocol steps and their probabilities, and finally how this is translated into a formal proof of the security argument.
How to Color a French Flag--Biologically Inspired Algorithms for Scale-Invariant Patterning
Venue: arXiv cs.DC 2019
Year: 2019

In the French flag problem, initially uncolored cells on a grid must differentiate to become blue, white or red. The goal is for the cells to color the grid as a French flag, i.e., a three-colored triband, in a distributed manner. To solve a generalized version of the problem in a distributed computational setting, we consider two models: a biologically-inspired version that relies on morphogens (diffusing proteins acting as chemical signals) and a more abstract version based on reliable message passing between cellular agents. Much of developmental biology research has focused on concentration-based approaches using morphogens, since morphogen gradients are thought to be an underlying mechanism in tissue patterning. We show that both our model types easily achieve a French ribbon - a French flag in the 1D case. However, extending the ribbon to the 2D flag in the concentration model is somewhat difficult unless each agent has additional positional information. Assuming that cells are are identical, it is impossible to achieve a French flag or even a close approximation. In contrast, using a message-based approach in the 2D case only requires assuming that agents can be represented as constant size state machines. We hope that our insights may lay some groundwork for what kind of message passing abstractions or guarantees, if any, may be useful in analogy to cells communicating at long and short distances to solve patterning problems. In addition, we hope that our models and findings may be of interest in the design of nano-robots.
Web Test Dependency Detection
Venue: arXiv cs.SE 2019
Year: 2019

E2E web test suites are prone to test dependencies due to the heterogeneous multi-tiered nature of modern web apps, which makes it difficult for developers to create isolated program states for each test case. In this paper, we present the first approach for detecting and validating test dependencies present in E2E web test suites. Our approach employs string analysis to extract an approximated set of dependencies from the test code. It then filters potential false dependencies through natural language processing of test names. Finally, it validates all dependencies, and uses a novel recovery algorithm to ensure no true dependencies are missed in the final test dependency graph. Our approach is implemented in a tool called TEDD and evaluated on the test suites of six open-source web apps. Our results show that TEDD can correctly detect and validate test dependencies up to 72% faster than the baseline with the original test ordering in which the graph contains all possible dependencies. The test dependency graphs produced by TEDD enable test execution parallelization, with a speed-up factor of up to 7x.
LDPC Coded Multiuser Shaping for the Gaussian Multiple Access Channel
Venue: arXiv cs.IT 2019
Year: 2019

The joint design of input constellation and low-density parity-check (LDPC) codes to approach the symmetric capacity of the two-user Gaussian multiple access channel is studied. More specifically, multilevel coding is employed at each user to construct a high-order input constellation and the constellations of the users are jointly designed so as to maximize the multiuser shaping gain. At the receiver, each layer of the multilevel coding is jointly decoded among users, while successive cancellation is employed across layers. The LDPC code employed by each user in each layer is designed using EXIT charts to support joint decoding among users for the prescribed per-layer rate and SNR. Numerical simulations are provided to validate the proposed constellation and LDPC code designs.
A Novel Trend Symbolic Aggregate Approximation for Time Series
Venue: arXiv cs.LG 2019
Year: 2019

Symbolic Aggregate approximation (SAX) is a classical symbolic approach in many time series data mining applications. However, SAX only reflects the segment mean value feature and misses important information in a segment, namely the trend of the value change in the segment. Such a miss may cause a wrong classification in some cases, since the SAX representation cannot distinguish different time series with similar average values but different trends. In this paper, we present Trend Feature Symbolic Aggregate approximation (TFSAX) to solve this problem. First, we utilize Piecewise Aggregate Approximation (PAA) approach to reduce dimensionality and discretize the mean value of each segment by SAX. Second, extract trend feature in each segment by using trend distance factor and trend shape factor. Then, design multi-resolution symbolic mapping rules to discretize trend information into symbols. We also propose a modified distance measure by integrating the SAX distance with a weighted trend distance. We show that our distance measure has a tighter lower bound to the Euclidean distance than that of the original SAX. The experimental results on diverse time series data sets demonstrate that our proposed representation significantly outperforms the original SAX representation and an improved SAX representation for classification.
Discrete time stochastic and deterministic Petri box calculus
Venue: arXiv cs.LO 2019
Year: 2019

We propose an extension with deterministically timed multiactions of discrete time stochastic and immediate Petri box calculus (dtsiPBC), previously presented by I.V. Tarasyuk, H. Macià and V. Valero. In dtsdPBC, non-negative integers specify multiactions with fixed (including zero) time delays. The step operational semantics is constructed via labeled probabilistic transition systems. The denotational semantics is defined on the basis of a subclass of labeled discrete time stochastic Petri nets with deterministic transitions. The consistency of both semantics is demonstrated. In order to evaluate performance, the corresponding semi-Markov chains and (reduced) discrete time Markov chains are analyzed.
A system for the 2019 Sentiment, Emotion and Cognitive State Task of DARPAs LORELEI project
Venue: arXiv cs.CL 2019
Year: 2019

During the course of a Humanitarian Assistance-Disaster Relief (HADR) crisis, that can happen anywhere in the world, real-time information is often posted online by the people in need of help which, in turn, can be used by different stakeholders involved with management of the crisis. Automated processing of such posts can considerably improve the effectiveness of such efforts; for example, understanding the aggregated emotion from affected populations in specific areas may help inform decision-makers on how to best allocate resources for an effective disaster response. However, these efforts may be severely limited by the availability of resources for the local language. The ongoing DARPA project Low Resource Languages for Emergent Incidents (LORELEI) aims to further language processing technologies for low resource languages in the context of such a humanitarian crisis. In this work, we describe our submission for the 2019 Sentiment, Emotion and Cognitive state (SEC) pilot task of the LORELEI project. We describe a collection of sentiment analysis systems included in our submission along with the features extracted. Our fielded systems obtained the best results in both English and Spanish language evaluations of the SEC pilot task.
Wildfire Monitoring in Remote Areas using Autonomous Unmanned Aerial Vehicles
Venue: arXiv cs.CY 2019
Year: 2019

In this paper, we propose a drone-based wildfire monitoring system for remote and hard-to-reach areas. This system utilizes autonomous unmanned aerial vehicles (UAVs) with the main advantage of providing on-demand monitoring service faster than the current approaches of using satellite images, manned aircraft and remotely controlled drones. Furthermore, using autonomous drones facilitates minimizing human intervention in risky wildfire zones. In particular, to develop a fully autonomous system, we propose a distributed leader-follower coalition formation model to cluster a set of drones into multiple coalitions that collectively cover the designated monitoring field. The coalition leader is a drone %with longer communication range that employs observer drones potentially with different sensing and imaging %actuation capabilities to hover in circular paths and collect imagery information from the impacted areas. The objectives of the proposed system include i) to cover the entire fire zone with a minimum number of drones, and ii) to minimize the energy consumption and latency of the available drones to fly to the fire zone. Simulation results confirm that the performance of the proposed system -- without the need for inter-coalition communications -- approaches that of a centrally-optimized system.
Adaptive Coding for Information Freshness in a Two-user Broadcast Erasure Channel
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we investigate the impact of coding on the Age of Information (AoI) in a two-user broadcast symbol erasure channel with feedback. We assume each update consists of $K$ symbols and the source is able to broadcast one symbol in each time slot. Due to random channel noise, the intended symbol at each user will be erased according to an independent and identically distributed (i.i.d.) Bernoulli process. A user is able to successfully decode an update if it accumulates sufficient information and successfully decodes the $K$ symbols of the update. Assuming prefect feedback information at the source right after the transmission of each symbol, our objective is to design an adaptive coding scheme to achieve small AoI at both users. We propose a novel coding scheme to judiciously combine symbols from different updates together, and analyze the AoI at both users. Compared with a baseline greedy scheme, the proposed adaptive coding scheme improves the AoI at the weak user by orders of magnitude without compromising the AoI at the strong user.
Stabilized SVRG: Simple Variance Reduction for Nonconvex Optimization
Venue: arXiv cs.LG 2019
Year: 2019

Variance reduction techniques like SVRG provide simple and fast algorithms for optimizing a convex finite-sum objective. For nonconvex objectives, these techniques can also find a first-order stationary point (with small gradient). However, in nonconvex optimization it is often crucial to find a second-order stationary point (with small gradient and almost PSD hessian). In this paper, we show that Stabilized SVRG (a simple variant of SVRG) can find an $ε$-second-order stationary point using only $\widetilde{O}(n^{2/3}/ε^2+n/ε^{1.5})$ stochastic gradients. To our best knowledge, this is the first second-order guarantee for a simple variant of SVRG. The running time almost matches the known guarantees for finding $ε$-first-order stationary points.
Empirically Analyzing Ethereum's Gas Mechanism
Venue: arXiv cs.CR 2019
Year: 2019

Ethereum's Gas mechanism attempts to set transaction fees in accordance with the computational cost of transaction execution: a cost borne by default by every node on the network to ensure correct smart contract execution. Gas encourages users to author transactions that are efficient to execute and in so doing encourages node diversity, allowing modestly resourced nodes to join and contribute to the security of the network. However, the effectiveness of this scheme relies on Gas costs being correctly aligned with observed computational costs in reality. In this work, we performed the first large scale empirical study to understand to what degree this alignment exists in practice, by collecting and analyzing Tera-bytes worth of nanosecond-precision transaction execution traces. Besides confirming potential denial-of-service vectors, our results also shed light on the role of I/O in transaction costs which remains poorly captured by the current Gas cost model. Finally, our results suggest that under the current Gas cost model, nodes with modest computational resources are disadvantaged compared to their better resourced peers, which we identify as an ongoing threat to node diversity and network decentralization.
Argument Identification in Public Comments from eRulemaking
Venue: arXiv cs.CL 2019
Year: 2019

Administrative agencies in the United States receive millions of comments each year concerning proposed agency actions during the eRulemaking process. These comments represent a diversity of arguments in support and opposition of the proposals. While agencies are required to identify and respond to substantive comments, they have struggled to keep pace with the volume of information. In this work we address the tasks of identifying argumentative text, classifying the type of argument claims employed, and determining the stance of the comment. First, we propose a taxonomy of argument claims based on an analysis of thousands of rules and millions of comments. Second, we collect and semi-automatically bootstrap annotations to create a dataset of millions of sentences with argument claim type annotation at the sentence level. Third, we build a system for automatically determining argumentative spans and claim type using our proposed taxonomy in a hierarchical classification model.
InternalBlue - Bluetooth Binary Patching and Experimentation Framework
Venue: arXiv cs.CR 2019
Year: 2019

Bluetooth is one of the most established technologies for short range digital wireless data transmission. With the advent of wearables and the Internet of Things (IoT), Bluetooth has again gained importance, which makes security research and protocol optimizations imperative. Surprisingly, there is a lack of openly available tools and experimental platforms to scrutinize Bluetooth. In particular, system aspects and close to hardware protocol layers are mostly uncovered. We reverse engineer multiple Broadcom Bluetooth chipsets that are widespread in off-the-shelf devices. Thus, we offer deep insights into the internal architecture of a popular commercial family of Bluetooth controllers used in smartphones, wearables, and IoT platforms. Reverse engineered functions can then be altered with our InternalBlue Python framework---outperforming evaluation kits, which are limited to documented and vendor-defined functions. The modified Bluetooth stack remains fully functional and high-performance. Hence, it provides a portable low-cost research platform. InternalBlue is a versatile framework and we demonstrate its abilities by implementing tests and demos for known Bluetooth vulnerabilities. Moreover, we discover a novel critical security issue affecting a large selection of Broadcom chipsets that allows executing code within the attacked Bluetooth firmware. We further show how to use our framework to fix bugs in chipsets out of vendor support and how to add new security features to Bluetooth firmware.
RetinaFace: Single-stage Dense Face Localisation in the Wild
Venue: arXiv cs.CV 2019
Year: 2019

Though tremendous strides have been made in uncontrolled face detection, accurate and efficient face localisation in the wild remains an open challenge. This paper presents a robust single-stage face detector, named RetinaFace, which performs pixel-wise face localisation on various scales of faces by taking advantages of joint extra-supervised and self-supervised multi-task learning. Specifically, We make contributions in the following five aspects: (1) We manually annotate five facial landmarks on the WIDER FACE dataset and observe significant improvement in hard face detection with the assistance of this extra supervision signal. (2) We further add a self-supervised mesh decoder branch for predicting a pixel-wise 3D shape face information in parallel with the existing supervised branches. (3) On the WIDER FACE hard test set, RetinaFace outperforms the state of the art average precision (AP) by 1.1% (achieving AP equal to 91.4%). (4) On the IJB-C test set, RetinaFace enables state of the art methods (ArcFace) to improve their results in face verification (TAR=89.59% for FAR=1e-6). (5) By employing light-weight backbone networks, RetinaFace can run real-time on a single CPU core for a VGA-resolution image. Extra annotations and code have been made available at: https://github.com/deepinsight/insightface/tree/master/RetinaFace.
A Review on Dyadic Conversation Visualizations - Purposes, Data, Lens of Analysis
Venue: arXiv cs.HC 2019
Year: 2019

Many professional services are provided through text and voice systems, from voice calls over the internet to messaging and emails. There is a growing need for both individuals and organizations to understand these online conversations better and find actionable insights. One method that allows the user to explore insights is to build intuitive and rich visualizations that illustrate the content of the conversation. In this paper, we present a systematic survey of the various methods of visualizing a conversation and research papers involving interactive visualizations and human participants. Findings from the survey show that there have been attempts to visualize most, if not all, of the types of conversation that are taking place digitally, from speech to messages and emails. Through this survey, we make two contributions. One, we summarize the current practices in the domain of visualizing dyadic conversations. Two, we provide suggestions for future dialogue visualization research.
Understanding Urban Dynamics via Context-aware Tensor Factorization with Neighboring Regularization
Venue: arXiv cs.LG 2019
Year: 2019

Recent years have witnessed the world-wide emergence of mega-metropolises with incredibly huge populations. Understanding residents mobility patterns, or urban dynamics, thus becomes crucial for building modern smart cities. In this paper, we propose a Neighbor-Regularized and context-aware Non-negative Tensor Factorization model (NR-cNTF) to discover interpretable urban dynamics from urban heterogeneous data. Different from many existing studies concerned with prediction tasks via tensor completion, NR-cNTF focuses on gaining urban managerial insights from spatial, temporal, and spatio-temporal patterns. This is enabled by high-quality Tucker factorizations regularized by both POI-based urban contexts and geographically neighboring relations. NR-cNTF is also capable of unveiling long-term evolutions of urban dynamics via a pipeline initialization approach. We apply NR-cNTF to a real-life data set containing rich taxi GPS trajectories and POI records of Beijing. The results indicate: 1) NR-cNTF accurately captures four kinds of city rhythms and seventeen spatial communities; 2) the rapid development of Beijing, epitomized by the CBD area, indeed intensifies the job-housing imbalance; 3) the southern areas with recent government investments have shown more healthy development tendency. Finally, NR-cNTF is compared with some baselines on traffic prediction, which further justifies the importance of urban contexts awareness and neighboring regulations.
From Specifications to Behavior: Maneuver Verification in a Semantic State Space
Venue: arXiv cs.RO 2019
Year: 2019

To realize a market entry of autonomous vehicles in the foreseeable future, the behavior planning system will need to abide by the same rules that humans follow. Product liability cannot be enforced without a proper solution to the approval trap. In this paper, we define a semantic abstraction of the continuous space and formalize traffic rules in linear temporal logic (LTL). Sequences in the semantic state space represent maneuvers a high-level planner could choose to execute. We check these maneuvers against the formalized traffic rules using runtime verification. By using the standard model checker NuSMV, we demonstrate the effectiveness of our approach and provide runtime properties for the maneuver verification. We show that high-level behavior can be verified in a semantic state space to fulfill a set of formalized rules, which could serve as a step towards safety of the intended functionality.
KnowBias: A Novel AI Method to Detect Polarity in Online Content
Venue: arXiv cs.CL 2019
Year: 2019

We propose a novel training and inference method for detecting political bias in long text content such as newspaper opinion articles. Obtaining long text data and annotations at sufficient scale for training is difficult, but it is relatively easy to extract political polarity from tweets through their authorship; as such, we train on tweets and perform inference on articles. Universal sentence encoders and other existing methods that aim to address this domain-adaptation scenario deliver inaccurate and inconsistent predictions on articles, which we show is due to a difference in opinion concentration between tweets and articles. We propose a two-step classification scheme that utilizes a neutral detector trained on tweets to remove neutral sentences from articles in order to align opinion concentration and therefore improve accuracy on that domain. We evaluate our two-step approach using a variety of test suites, including a set of tweets and long-form articles where annotations were crowd-sourced to decrease label noise, measuring accuracy and Spearman-rho rank correlation. In practice, KnowBias achieves a high accuracy of 86 (rho = 0.65) on these tweets and 75 (rho = 0.69) on long-form articles. While we validate our method on political bias, our scheme is general and can be readily applied to other settings, where there exist such domain mismatches between source and target domains. Our implementation is available for public use at https://knowbias.ml.