OpenRaiser/Intern-Atlas huggingface dataset:
Exact Localisations of Feedback Sets
Venue: arXiv cs.DM 2017
Year: 2017

The feedback arc (vertex) set problem, shortened FASP (FVSP), is to transform a given multi digraph $G=(V,E)$ into an acyclic graph by deleting as few arcs (vertices) as possible. Due to the results of Richard M. Karp in 1972 it is one of the classic NP-complete problems. An important contribution of this paper is that the subgraphs $G_{\mathrm{el}}(e)$, $G_{\mathrm{si}}(e)$ of all elementary cycles or simple cycles running through some arc $e \in E$, can be computed in $\mathcal{O}\big(|E|^2\big)$ and $\mathcal{O}(|E|^4)$, respectively. We use this fact and introduce the notion of the essential minor and isolated cycles, which yield a priori problem size reductions and in the special case of so called resolvable graphs an exact solution in $\mathcal{O}(|V||E|^3)$. We show that weighted versions of the FASP and FVSP possess a Bellman decomposition, which yields exact solutions using a dynamic programming technique in times $\mathcal{O}\big(2^{m}|E|^4\log(|V|)\big)$ and $\mathcal{O}\big(2^{n}Δ(G)^4|V|^4\log(|E|)\big)$, where $m \leq |E|-|V| +1$, $n \leq (Δ(G)-1)|V|-|E| +1$, respectively. The parameters $m,n$ can be computed in $\mathcal{O}(|E|^3)$, $\mathcal{O}(Δ(G)^3|V|^3)$, respectively and denote the maximal dimension of the cycle space of all appearing meta graphs, decoding the intersection behavior of the cycles. Consequently, $m,n$ equal zero if all meta graphs are trees. Moreover, we deliver several heuristics and discuss how to control their variation from the optimum. Summarizing, the presented results allow us to suggest a strategy for an implementation of a fast and accurate FASP/FVSP-SOLVER.
Multipath Error Correction in Radio Interferometric Positioning Systems
Venue: arXiv cs.IT 2017
Year: 2017

The radio interferometric positioning system (RIPS) is an accurate node localization method featuring a novel phase-based ranging process. Multipath is the limiting error source for RIPS in ground-deployed scenarios or indoor applications. There are four distinct channels involved in the ranging process for RIPS. Multipath reflections affect both the phase and amplitude of the ranging signal for each channel. By exploiting untapped amplitude information, we put forward a scheme to estimate each channel's multipath profile, which is then subsequently used to correct corresponding errors in phase measurements. Simulations show that such a scheme is very effective in reducing multipath phase errors, which are essentially brought down to the level of receiver noise under moderate multipath conditions. It is further demonstrated that ranging errors in RIPS are also greatly reduced via the proposed scheme.
Does Quality of Requirements Specifications matter? Combined Results of Two Empirical Studies
Venue: arXiv cs.SE 2017
Year: 2017

Background: Requirements Engineering is crucial for project success, and to this end, many measures for quality assurance of the software requirements specification (SRS) have been proposed. Goal: However, we still need an empirical understanding on the extent to which SRS are created and used in practice, as well as the degree to which the quality of an SRS matters to subsequent development activities. Method: We studied the relevance of SRS by relying on survey research and explored the impact of quality defects in SRS by relying on a controlled experiment. Results: Our results suggest that the relevance of SRS quality depends both on particular project characteristics and what is considered as a quality defect; for instance, the domain of safety critical systems seems to motivate for an intense usage of SRS as a means for communication whereas defects hampering the pragmatic quality do not seem to be as relevant as initially thought. Conclusion: Efficient and effective quality assurance measures must be specific for carefully characterized contexts and carefully select defect classes.
Modulation and Multiple Access for 5G Networks
Venue: arXiv cs.OH 2017
Year: 2017

Fifth generation (5G) wireless networks face various challenges in order to support large-scale heterogeneous traffic and users, therefore new modulation and multiple access (MA) schemes are being developed to meet the changing demands. As this research space is ever increasing, it becomes more important to analyze the various approaches, therefore in this article we present a comprehensive overview of the most promising modulation and MA schemes for 5G networks. We first introduce the different types of modulation that indicate their potential for orthogonal multiple access (OMA) schemes and compare their performance in terms of spectral efficiency, out-of-band leakage, and bit-error rate. We then pay close attention to various types of non-orthogonal multiple access (NOMA) candidates, including power-domain NOMA, code-domain NOMA, and NOMA multiplexing in multiple domains. From this exploration we can identify the opportunities and challenges that will have significant impact on the design of modulation and MA for 5G networks.
Bayes, not Naïve: Security Bounds on Website Fingerprinting Defenses
Venue: arXiv cs.CR 2017
Year: 2017

Website Fingerprinting (WF) attacks raise major concerns about users' privacy. They employ Machine Learning (ML) to allow a local passive adversary to uncover the Web browsing behavior of a user, even if she browses through an encrypted tunnel (e.g. Tor, VPN). Numerous defenses have been proposed in the past; however, it is typically difficult to have formal guarantees on their security, which is most often evaluated empirically against state-of-the-art attacks. In this paper, we present a practical method to derive security bounds for any WF defense, which depend on a chosen feature set. This result derives from reducing WF attacks to an ML classification task, where we can determine the smallest achievable error (the Bayes error); such error can be estimated in practice, and is a lower bound for a WF adversary, for any classification algorithm he may use. Our work has two main consequences: i) it allows determining the security of WF defenses, in a black-box manner, with respect to the state-of-the-art feature set and ii) it favors shifting the focus of future WF research to the identification of optimal feature sets. The generality of the approach further suggests that the method could be used to define security bounds for other ML-based attacks.
Better Predictors for Issue Lifetime
Venue: arXiv cs.SE 2017
Year: 2017

Predicting issue lifetime can help software developers, managers, and stakeholders effectively prioritize work, allocate development resources, and better understand project timelines. Progress had been made on this prediction problem, but prior work has reported low precision and high false alarms. The latest results also use complex models such as random forests that detract from their readability. We solve both issues by using small, readable decision trees (under 20 lines long) and correlation feature selection to predict issue lifetime, achieving high precision and low false alarms (medians of 71% and 13% respectively). We also address the problem of high class imbalance within issue datasets - when local data fails to train a good model, we show that cross-project data can be used in place of the local data. In fact, cross-project data works so well that we argue it should be the default approach for learning predictors for issue lifetime.
Decoding Generalized Reed-Solomon Codes and Its Application to RLCE Encryption Schemes
Venue: arXiv cs.IT 2017
Year: 2017

This paper compares the efficiency of various algorithms for implementing quantum resistant public key encryption scheme RLCE on 64-bit CPUs. By optimizing various algorithms for polynomial and matrix operations over finite fields, we obtained several interesting (or even surprising) results. For example, it is well known (e.g., Moenck 1976 \cite{moenck1976practical}) that Karatsuba's algorithm outperforms classical polynomial multiplication algorithm from the degree 15 and above (practically, Karatsuba's algorithm only outperforms classical polynomial multiplication algorithm from the degree 35 and above ). Our experiments show that 64-bit optimized Karatsuba's algorithm will only outperform 64-bit optimized classical polynomial multiplication algorithm for polynomials of degree 115 and above over finite field $GF(2^{10})$. The second interesting (surprising) result shows that 64-bit optimized Chien's search algorithm ourperforms all other 64-bit optimized polynomial root finding algorithms such as BTA and FFT for polynomials of all degrees over finite field $GF(2^{10})$. The third interesting (surprising) result shows that 64-bit optimized Strassen matrix multiplication algorithm only outperforms 64-bit optimized classical matrix multiplication algorithm for matrices of dimension 750 and above over finite field $GF(2^{10})$. It should be noted that existing literatures and practices recommend Strassen matrix multiplication algorithm for matrices of dimension 40 and above. All our experiments are done on a 64-bit MacBook Pro with i7 CPU and single thread C codes. It should be noted that the reported results should be appliable to 64 or larger bits CPU architectures. For 32 or smaller bits CPUs, these results may not be applicable. The source code and library for the algorithms covered in this paper are available at http://quantumca.org/.
Convolutional Gated Recurrent Neural Network Incorporating Spatial Features for Audio Tagging
Venue: arXiv cs.SD 2017
Year: 2017

Environmental audio tagging is a newly proposed task to predict the presence or absence of a specific audio event in a chunk. Deep neural network (DNN) based methods have been successfully adopted for predicting the audio tags in the domestic audio scene. In this paper, we propose to use a convolutional neural network (CNN) to extract robust features from mel-filter banks (MFBs), spectrograms or even raw waveforms for audio tagging. Gated recurrent unit (GRU) based recurrent neural networks (RNNs) are then cascaded to model the long-term temporal structure of the audio signal. To complement the input information, an auxiliary CNN is designed to learn on the spatial features of stereo recordings. We evaluate our proposed methods on Task 4 (audio tagging) of the Detection and Classification of Acoustic Scenes and Events 2016 (DCASE 2016) challenge. Compared with our recent DNN-based method, the proposed structure can reduce the equal error rate (EER) from 0.13 to 0.11 on the development set. The spatial features can further reduce the EER to 0.10. The performance of the end-to-end learning on raw waveforms is also comparable. Finally, on the evaluation set, we get the state-of-the-art performance with 0.12 EER while the performance of the best existing system is 0.15 EER.
On the Origin of Deep Learning
Venue: arXiv cs.LG 2017
Year: 2017

This paper is a review of the evolutionary history of deep learning models. It covers from the genesis of neural networks when associationism modeling of the brain is studied, to the models that dominate the last decade of research in deep learning like convolutional neural networks, deep belief networks, and recurrent neural networks. In addition to a review of these models, this paper primarily focuses on the precedents of the models above, examining how the initial ideas are assembled to construct the early models and how these preliminary models are developed into their current forms. Many of these evolutionary paths last more than half a century and have a diversity of directions. For example, CNN is built on prior knowledge of biological vision system; DBN is evolved from a trade-off of modeling power and computation complexity of graphical models and many nowadays models are neural counterparts of ancient linear models. This paper reviews these evolutionary paths and offers a concise thought flow of how these models are developed, and aims to provide a thorough background for deep learning. More importantly, along with the path, this paper summarizes the gist behind these milestones and proposes many directions to guide the future research of deep learning.
Rationalization: A Neural Machine Translation Approach to Generating Natural Language Explanations
Venue: arXiv cs.AI 2017
Year: 2017

We introduce AI rationalization, an approach for generating explanations of autonomous system behavior as if a human had performed the behavior. We describe a rationalization technique that uses neural machine translation to translate internal state-action representations of an autonomous agent into natural language. We evaluate our technique in the Frogger game environment, training an autonomous game playing agent to rationalize its action choices using natural language. A natural language training corpus is collected from human players thinking out loud as they play the game. We motivate the use of rationalization as an approach to explanation generation and show the results of two experiments evaluating the effectiveness of rationalization. Results of these evaluations show that neural machine translation is able to accurately generate rationalizations that describe agent behavior, and that rationalizations are more satisfying to humans than other alternative methods of explanation.
New constructions of MDS codes with complementary duals
Venue: arXiv cs.IT 2017
Year: 2017

Linear complementary-dual (LCD for short) codes are linear codes that intersect with their duals trivially. LCD codes have been used in certain communication systems. It is recently found that LCD codes can be applied in cryptography. This application of LCD codes renewed the interest in the construction of LCD codes having a large minimum distance. MDS codes are optimal in the sense that the minimum distance cannot be improved for given length and code size. Constructing LCD MDS codes is thus of significance in theory and practice. Recently, Jin (\cite{Jin}, IEEE Trans. Inf. Theory, 2016) constructed several classes of LCD MDS codes through generalized Reed-Solomon codes. In this paper, a different approach is proposed to obtain new LCD MDS codes from generalized Reed-Solomon codes. Consequently, new code constructions are provided and certain previously known results in \cite{Jin} are extended.
An Algebraic Treatment of Recursion
Venue: arXiv cs.LO 2017
Year: 2017

I review the three principal methods to assign meaning to recursion in process algebra: the denotational, the operational and the algebraic approach, and I extend the latter to unguarded recursion.
CHAOS: A Parallelization Scheme for Training Convolutional Neural Networks on Intel Xeon Phi
Venue: arXiv cs.DC 2017
Year: 2017

Deep learning is an important component of big-data analytic tools and intelligent applications, such as, self-driving cars, computer vision, speech recognition, or precision medicine. However, the training process is computationally intensive, and often requires a large amount of time if performed sequentially. Modern parallel computing systems provide the capability to reduce the required training time of deep neural networks. In this paper, we present our parallelization scheme for training convolutional neural networks (CNN) named Controlled Hogwild with Arbitrary Order of Synchronization (CHAOS). Major features of CHAOS include the support for thread and vector parallelism, non-instant updates of weight parameters during back-propagation without a significant delay, and implicit synchronization in arbitrary order. CHAOS is tailored for parallel computing systems that are accelerated with the Intel Xeon Phi. We evaluate our parallelization approach empirically using measurement techniques and performance modeling for various numbers of threads and CNN architectures. Experimental results for the MNIST dataset of handwritten digits using the total number of threads on the Xeon Phi show speedups of up to 103x compared to the execution on one thread of the Xeon Phi, 14x compared to the sequential execution on Intel Xeon E5, and 58x compared to the sequential execution on Intel Core i5.
Increasing Peer Pressure on any Connected Graph Leads to Consensus
Venue: arXiv cs.SI 2017
Year: 2017

In this paper, we study a model of opinion dynamics in a social network in the presence increasing interpersonal influence, i.e., increasing peer pressure. Each agent in the social network has a distinct social stress function given by a weighted sum of internal and external behavioral pressures. We assume a weighted average update rule and prove conditions under which a connected group of agents converge to a fixed opinion distribution, and under which conditions the group reaches consensus. We show that the update rule is a gradient descent and explain its transient and asymptotic convergence properties. Through simulation, we study the rate of convergence on a scale-free network and then validate the assumption of increasing peer pressure in a simple empirical model.
A New Taxonomy for Symbiotic EM Sensors
Venue: arXiv cs.NI 2017
Year: 2017

It is clear that the EM spectrum is now rapidly reaching saturation, especially for frequencies below 10~GHz. Governments, who influence the regulatory authorities around the world, have resorted to auctioning the use of spectrum, in a sense to gauge the importance of a particular user. Billions of USD are being paid for modest bandwidths. The earth observation, astronomy and similar science driven communities cannot compete financially with such a pressure system, so this is where governments have to step in and assess /regulate the situation. It has been a pleasure to see a situation where the communications and broadcast communities have come together to formulate sharing of an important part of the spectrum (roughly, 50 MHz to 800 MHz) in an IEEE standard, IEEE802.22. This standard (known as the "TV White Space Network" (built on lower level standards) shows a way that fixed and mobile users can collaborate in geographically widespread regions, using cognitive radio and geographic databases of users. This White Space (WS) standard is well described in the literature and is not the major topic of this short paper. We wish to extend the idea of the WS concept to include the idea of EM sensors (such as Radar) adopting this approach to spectrum sharing, providing a quantum leap in access to spectrum. We postulate that networks of sensors, using the tools developed by the WS community, can replace and enhance our present set of EM sensors. We first define what Networks of Sensors entail (with some history), and then go on to define, based on a Taxonomy of Symbiosis defined by de Bary\cite{symb}, how these sensors and other users (especially communications) can co-exist. This new taxonomy is important for understanding, and should replace somewhat outdated terminologies from the radar world.
Complexity Classification of the Eight-Vertex Model
Venue: arXiv cs.CC 2017
Year: 2017

We prove a complexity dichotomy theorem for the eight-vertex model. For every setting of the parameters of the model, we prove that computing the partition function is either solvable in polynomial time or \#P-hard. The dichotomy criterion is explicit. For tractability, we find some new classes of problems computable in polynomial time. For \#P-hardness, we employ Möbius transformations to prove the success of interpolations.
BARCHAN: Blob Alignment for Robust CHromatographic ANalysis
Venue: arXiv cs.CV 2017
Year: 2017

Comprehensive Two dimensional gas chromatography (GCxGC) plays a central role into the elucidation of complex samples. The automation of the identification of peak areas is of prime interest to obtain a fast and repeatable analysis of chromatograms. To determine the concentration of compounds or pseudo-compounds, templates of blobs are defined and superimposed on a reference chromatogram. The templates then need to be modified when different chromatograms are recorded. In this study, we present a chromatogram and template alignment method based on peak registration called BARCHAN. Peaks are identified using a robust mathematical morphology tool. The alignment is performed by a probabilistic estimation of a rigid transformation along the first dimension, and a non-rigid transformation in the second dimension, taking into account noise, outliers and missing peaks in a fully automated way. Resulting aligned chromatograms and masks are presented on two datasets. The proposed algorithm proves to be fast and reliable. It significantly reduces the time to results for GCxGC analysis.
JETracer - A Framework for Java GUI Event Tracing
Venue: arXiv cs.SE 2017
Year: 2017

The present paper introduces the open-source Java Event Tracer (JETracer) framework for real-time tracing of GUI events within applications based on the AWT, Swing or SWT graphical toolkits. Our framework provides a common event model for supported toolkits, the possibility of receiving GUI events in real-time, good performance in the case of complex target applications and the possibility of deployment over a network. The present paper provides the rationale for JETracer, presents related research and details its technical implementation. An empirical evaluation where JETracer is used to trace GUI events within five popular, open-source applications is also presented.
Live Visualization of GUI Application Code Coverage with GUITracer
Venue: arXiv cs.SE 2017
Year: 2017

The present paper introduces the initial implementation of a software exploration tool targeting graphical user interface (GUI) driven applications. GUITracer facilitates the comprehension of GUI-driven applications by starting from their most conspicuous artefact - the user interface itself. The current implementation of the tool can be used with any Java-based target application that employs one of the AWT, Swing or SWT toolkits. The tool transparently instruments the target application and provides real time information about the GUI events fired. For each event, call relations within the application are displayed at method, class or package level, together with detailed coverage information. The tool facilitates feature location, program comprehension as well as GUI test creation by revealing the link between the application's GUI and its underlying code. As such, GUITracer is intended for software practitioners developing or maintaining GUI-driven applications. We believe our tool to be especially useful for entry-level practitioners as well as students seeking to understand complex GUI-driven software systems. The present paper details the rationale as well as the technical implementation of the tool. As a proof-of-concept implementation, we also discuss further development that can lead to our tool's integration into a software development workflow.
Bisimulation Metrics for Weighted Automata
Venue: arXiv cs.FL 2017
Year: 2017

We develop a new bisimulation (pseudo)metric for weighted finite automata (WFA) that generalizes Boreale's linear bisimulation relation. Our metrics are induced by seminorms on the state space of WFA. Our development is based on spectral properties of sets of linear operators. In particular, the joint spectral radius of the transition matrices of WFA plays a central role. We also study continuity properties of the bisimulation pseudometric, establish an undecidability result for computing the metric, and give a preliminary account of applications to spectral learning of weighted automata.
General Upper Bounds for Gate Complexity and Depth of Reversible Circuits Consisting of NOT, CNOT and 2-CNOT Gates
Venue: arXiv cs.CC 2017
Year: 2017

The paper discusses the gate complexity and the depth of reversible circuits consisting of NOT, CNOT and 2-CNOT gates in the case, when the number of additional inputs is limited. We study Shannon's gate complexity function $L(n, q)$ and depth function $D(n, q)$ for a reversible circuit implementing a Boolean transformation $f\colon \mathbb Z_2^n \to \mathbb Z_2^n$ with $8n < q \lesssim n2^{n-o(n)}$ additional inputs. The general upper bounds $L(n,q) \lesssim 2^n + 8n2^n \mathop / (\log_2 (q-4n) - \log_2 n - 2)$ and $D(n,q) \lesssim 2^{n+1}(2,5 + \log_2 n - \log_2 (\log_2 (q - 4n) - \log_2 n - 2))$ are proved for this case.