OpenRaiser/Intern-Atlas huggingface dataset:
Algorithmic Building Blocks for Asymmetric Memories
Venue: arXiv cs.DS 2018
Year: 2018

The future of main memory appears to lie in the direction of new non-volatile memory technologies that provide strong capacity-to-performance ratios, but have write operations that are much more expensive than reads in terms of energy, bandwidth, and latency. This asymmetry can have a significant effect on algorithm design, and in many cases it is possible to reduce writes at the cost of reads. In this paper, we study which algorithmic techniques are useful in designing practical write-efficient algorithms. We focus on several fundamental algorithmic building blocks including unordered set/map implemented using hash tables, ordered set/map implemented using various binary search trees, comparison sort, and graph traversal algorithms including breadth-first search and Dijkstra's algorithm. We introduce new algorithms and implementations that can reduce writes, and analyze the performance experimentally using a software simulator. Finally we summarize interesting lessons and directions in designing write-efficient algorithms.
Physical Layer Authentication in Mission-Critical MTC Networks: A Security and Delay Performance Analysis
Venue: arXiv cs.CR 2018
Year: 2018

We study the detection and delay performance impacts of a feature-based physical layer authentication (PLA) protocol in mission-critical machine-type communication (MTC) networks. The PLA protocol uses generalized likelihood-ratio testing based on the line-of-sight (LOS), single-input multiple-output channel-state information in order to mitigate impersonation attempts from an adversary node. We study the detection performance, develop a queueing model that captures the delay impacts of erroneous decisions in the PLA (i.e., the false alarms and missed detections), and model three different adversary strategies: data injection, disassociation, and Sybil attacks. Our main contribution is the derivation of analytical delay performance bounds that allow us to quantify the delay introduced by PLA that potentially can degrade the performance in mission-critical MTC networks. For the delay analysis, we utilize tools from stochastic network calculus. Our results show that with a sufficient number of receive antennas (approx. 4-8) and sufficiently strong LOS components from legitimate devices, PLA is a viable option for securing mission-critical MTC systems, despite the low latency requirements associated to corresponding use cases. Furthermore, we find that PLA can be very effective in detecting the considered attacks, and in particular, it can significantly reduce the delay impacts of disassociation and Sybil attacks.
Computing the metric dimension by decomposing graphs into extended biconnected components
Venue: arXiv cs.CC 2018
Year: 2018

A vertex set $U \subseteq V$ of an undirected graph $G=(V,E)$ is a $\textit{resolving set}$ for $G$, if for every two distinct vertices $u,v \in V$ there is a vertex $w \in U$ such that the distances between $u$ and $w$ and the distance between $v$ and $w$ are different. The $\textit{Metric Dimension}$ of $G$ is the size of a smallest resolving set for $G$. Deciding whether a given graph $G$ has Metric Dimension at most $k$ for some integer $k$ is well-known to be NP-complete. Many research has been done to understand the complexity of this problem on restricted graph classes. In this paper, we decompose a graph into its so called $\textit{extended biconnected components}$ and present an efficient algorithm for computing the metric dimension for a class of graphs having a minimum resolving set with a bounded number of vertices in every extended biconnected component. Further we show that the decision problem METRIC DIMENSION remains NP-complete when the above limitation is extended to usual biconnected components.
Elfun18 A collection of Matlab functions for the computation of Elliptical Integrals and Jacobian elliptic functions of real arguments
Venue: arXiv cs.MS 2018
Year: 2018

In the article we outline the set of Matlab functions that enable the computation of elliptic Integrals and Jacobian elliptic functions for real arguments. Correctness, robustness, efficiency and accuracy of the functions are discussed in some details. An example from the elasticity theory illustrates use of the collection.
An Overview of Machine Learning Approaches in Wireless Mesh Networks
Venue: arXiv cs.NI 2018
Year: 2018

Wireless Mesh Networks (WMNs) have been extensively studied for nearly two decades as one of the most promising candidates expected to power the high bandwidth, high coverage wireless networks of the future. However, consumer demand for such networks has only recently caught up, rendering efforts at optimizing WMNs to support high capacities and offer high QoS, while being secure and fault tolerant, more important than ever. To this end, a recent trend has been the application of Machine Learning (ML) to solve various design and management tasks related to WMNs. In this work, we discuss key ML techniques and analyze how past efforts have applied them in WMNs, while noting some existing issues and suggesting potential solutions. We also provide directions on how ML could advance future research and examine recent developments in the field.
Social media metrics for new research evaluation
Venue: arXiv cs.DL 2018
Year: 2018

This chapter approaches, both from a theoretical and practical perspective, the most important principles and conceptual frameworks that can be considered in the application of social media metrics for scientific evaluation. We propose conceptually valid uses for social media metrics in research evaluation. The chapter discusses frameworks and uses of these metrics as well as principles and recommendations for the consideration and application of current (and potentially new) metrics in research evaluation.
Challenges and New Directions in Augmented Reality, Computer Security, and Neuroscience -- Part 1: Risks to Sensation and Perception
Venue: arXiv cs.CR 2018
Year: 2018

Rapidly advancing AR technologies are in a unique position to directly mediate between the human brain and the physical world. Though this tight coupling presents tremendous opportunities for human augmentation, it also presents new risks due to potential adversaries, including AR applications or devices themselves, as well as bugs or accidents. In this paper, we begin exploring potential risks to the human brain from augmented reality. Our initial focus is on sensory and perceptual risks (e.g., accidentally or maliciously induced visual adaptations, motion-induced blindness, and photosensitive epilepsy), but similar risks may span both lower- and higher-level human brain functions, including cognition, memory, and decision-making. Though they have not yet manifested in practice in early-generation AR technologies, we believe that such risks are uniquely dangerous in AR due to the richness and depth with which it interacts with a user's experience of the physical world. We propose a framework, based in computer security threat modeling, to conceptually and experimentally evaluate such risks. The ultimate goal of our work is to aid AR technology developers, researchers, and neuroscientists to consider these issues before AR technologies are widely deployed and become targets for real adversaries. By considering and addressing these issues now, we can help ensure that future AR technologies can meet their full, positive potential.
Sublinear-Time Quadratic Minimization via Spectral Decomposition of Matrices
Venue: arXiv cs.DS 2018
Year: 2018

We design a sublinear-time approximation algorithm for quadratic function minimization problems with a better error bound than the previous algorithm by Hayashi and Yoshida (NIPS'16). Our approximation algorithm can be modified to handle the case where the minimization is done over a sphere. The analysis of our algorithms is obtained by combining results from graph limit theory, along with a novel spectral decomposition of matrices. Specifically, we prove that a matrix $A$ can be decomposed into a structured part and a pseudorandom part, where the structured part is a block matrix with a polylogarithmic number of blocks, such that in each block all the entries are the same, and the pseudorandom part has a small spectral norm, achieving better error bound than the existing decomposition theorem of Frieze and Kannan (FOCS'96). As an additional application of the decomposition theorem, we give a sublinear-time approximation algorithm for computing the top singular values of a matrix.
Performance and Programming Effort Trade-offs of Android Persistence Frameworks
Venue: arXiv cs.SE 2018
Year: 2018

A fundamental building block of a mobile application is the ability to persist program data between different invocations. Referred to as \emph{persistence}, this functionality is commonly implemented by means of persistence frameworks. Without a clear understanding of the energy consumption, execution time, and programming effort of popular Android persistence frameworks, mobile developers lack guidelines for selecting frameworks for their applications. To bridge this knowledge gap, we report on the results of a systematic study of the performance and programming effort trade-offs of eight Android persistence frameworks, and provide practical recommendations for mobile application developers.
Robust Neural Malware Detection Models for Emulation Sequence Learning
Venue: arXiv cs.AI 2018
Year: 2018

Malicious software, or malware, presents a continuously evolving challenge in computer security. These embedded snippets of code in the form of malicious files or hidden within legitimate files cause a major risk to systems with their ability to run malicious command sequences. Malware authors even use polymorphism to reorder these commands and create several malicious variations. However, if executed in a secure environment, one can perform early malware detection on emulated command sequences. The models presented in this paper leverage this sequential data derived via emulation in order to perform Neural Malware Detection. These models target the core of the malicious operation by learning the presence and pattern of co-occurrence of malicious event actions from within these sequences. Our models can capture entire event sequences and be trained directly using the known target labels. These end-to-end learning models are powered by two commonly used structures - Long Short-Term Memory (LSTM) Networks and Convolutional Neural Networks (CNNs). Previously proposed sequential malware classification models process no more than 200 events. Attackers can evade detection by delaying any malicious activity beyond the beginning of the file. We present specialized models that can handle extremely long sequences while successfully performing malware detection in an efficient way. We present an implementation of the Convoluted Partitioning of Long Sequences approach in order to tackle this vulnerability and operate on long sequences. We present our results on a large dataset consisting of 634,249 file sequences, with extremely long file sequences.
A Computational Theory for Life-Long Learning of Semantics
Venue: arXiv cs.AI 2018
Year: 2018

Semantic vectors are learned from data to express semantic relationships between elements of information, for the purpose of solving and informing downstream tasks. Other models exist that learn to map and classify supervised data. However, the two worlds of learning rarely interact to inform one another dynamically, whether across types of data or levels of semantics, in order to form a unified model. We explore the research problem of learning these vectors and propose a framework for learning the semantics of knowledge incrementally and online, across multiple mediums of data, via binary vectors. We discuss the aspects of this framework to spur future research on this approach and problem.
Entanglement-assisted quantum error-correcting codes from units
Venue: arXiv cs.IT 2018
Year: 2018

Entanglement-assisted quantum error-correcting codes (EAQECCs) to desired rate, error-correcting capability and maximum shared entanglement are constructed. Thus for a required rate $R$, required error-correcting capability to correct $t$ errors, mds (maximum distance separable) EAQECCs of the form $[[n,r,d;c]]$ with $R=\frac{r}{n}, d\geq (2t+1), c = (n-r), d= (n-r+1)$ are constructed. Series of such codes may be constructed where the rate and the relative distance approach non-zero constants as $n$ approaches infinity. The codes may also be constructed over prime order fields in which modular arithmetic may be employed.
High Diversity Attribute Guided Face Generation with GANs
Venue: arXiv cs.CV 2018
Year: 2018

In this work we focused on GAN-based solution for the attribute guided face synthesis. Previous works exploited GANs for generation of photo-realistic face images and did not pay attention to the question of diversity of the resulting images. The proposed solution in its turn introducing novel latent space of unit complex numbers is able to provide the diversity on the "birthday paradox" score 3 times higher than the size of the training dataset. It is important to emphasize that our result is shown on relatively small dataset (20k samples vs 200k) while preserving photo-realistic properties of generated faces on significantly higher resolution (128x128 in comparison to 32x32 of previous works).
Up-To Techniques for Behavioural Metrics via Fibrations
Venue: arXiv cs.LO 2018
Year: 2018

Up-to techniques are a well-known method for enhancing coinductive proofs of behavioural equivalences. We introduce up-to techniques for behavioural metrics between systems modelled as coalgebras and we provide abstract results to prove their oundness in a compositional way. In order to obtain a general framework, we need a systematic way to lift functors: we show that the Wasserstein lifting of a functor, introduced in a previous work, corresponds to a change of base in a fibrational sense. This observation enables us to reuse existing results about soundness of up-to techniques in a fibrational setting. We focus on the fibrations of predicates and relations valued in a quantale, for which pseudo-metric spaces are an example. To illustrate our approach we provide an example on distances between regular languages.
Predicting CEFRL levels in learner English on the basis of metrics and full texts
Venue: arXiv cs.CL 2018
Year: 2018

This paper analyses the contribution of language metrics and, potentially, of linguistic structures, to classify French learners of English according to levels of the Common European Framework of Reference for Languages (CEFRL). The purpose is to build a model for the prediction of learner levels as a function of language complexity features. We used the EFCAMDAT corpus, a database of one million written assignments by learners. After applying language complexity metrics on the texts, we built a representation matching the language metrics of the texts to their assigned CEFRL levels. Lexical and syntactic metrics were computed with LCA, LSA, and koRpus. Several supervised learning models were built by using Gradient Boosted Trees and Keras Neural Network methods and by contrasting pairs of CEFRL levels. Results show that it is possible to implement pairwise distinctions, especially for levels ranging from A1 to B1 (A1=>A2: 0.916 AUC and A2=>B1: 0.904 AUC). Model explanation reveals significant linguistic features for the predictiveness in the corpus. Word tokens and word types appear to play a significant role in determining levels. This shows that levels are highly dependent on specific semantic profiles.
Comment on: Decomposition of structural learning about directed acyclic graphs [1]
Venue: arXiv cs.AI 2018
Year: 2018

We propose an alternative proof concerning necessary and sufficient conditions to split the problem of searching for d-separators and building the skeleton of a DAG into small problems for every node of a separation tree T. The proof is simpler than the original [1]. The same proof structure has been used in [2] for learning the structure of multivariate regression chain graphs (MVR CGs).
Syntax Error Recovery in Parsing Expression Grammars
Venue: arXiv cs.PL 2018
Year: 2018

Parsing Expression Grammars (PEGs) are a formalism used to describe top-down parsers with backtracking. As PEGs do not provide a good error recovery mechanism, PEG-based parsers usually do not recover from syntax errors in the input, or recover from syntax errors using ad-hoc, implementation-specific features. The lack of proper error recovery makes PEG parsers unsuitable for using with Integrated Development Environments (IDEs), which need to build syntactic trees even for incomplete, syntactically invalid programs. We propose a conservative extension, based on PEGs with labeled failures, that adds a syntax error recovery mechanism for PEGs. This extension associates recovery expressions to labels, where a label now not only reports a syntax error but also uses this recovery expression to reach a synchronization point in the input and resume parsing. We give an operational semantics of PEGs with this recovery mechanism, and use an implementation based on such semantics to build a robust parser for the Lua language. We evaluate the effectiveness of this parser, alone and in comparison with a Lua parser with automatic error recovery generated by ANTLR, a popular parser generator.
On the Decoding of Polar Codes on Permuted Factor Graphs
Venue: arXiv cs.IT 2018
Year: 2018

Polar codes are a channel coding scheme for the next generation of wireless communications standard (5G). The belief propagation (BP) decoder allows for parallel decoding of polar codes, making it suitable for high throughput applications. However, the error-correction performance of polar codes under BP decoding is far from the requirements of 5G. It has been shown that the error-correction performance of BP can be improved if the decoding is performed on multiple permuted factor graphs of polar codes. However, a different BP decoding scheduling is required for each factor graph permutation which results in the design of a different decoder for each permutation. Moreover, the selection of the different factor graph permutations is at random, which prevents the decoder to achieve a desirable error-correction performance with a small number of permutations. In this paper, we first show that the permutations on the factor graph can be mapped into suitable permutations on the codeword positions. As a result, we can make use of a single decoder for all the permutations. In addition, we introduce a method to construct a set of predetermined permutations which can provide the correct codeword if the decoding fails on the original permutation. We show that for the 5G polar code of length $1024$, the error-correction performance of the proposed decoder is more than $0.25$ dB better than that of the BP decoder with the same number of random permutations at the frame error rate of $10^{-4}$.
Proxy Fairness
Venue: arXiv cs.LG 2018
Year: 2018

We consider the problem of improving fairness when one lacks access to a dataset labeled with protected groups, making it difficult to take advantage of strategies that can improve fairness but require protected group labels, either at training or runtime. To address this, we investigate improving fairness metrics for proxy groups, and test whether doing so results in improved fairness for the true sensitive groups. Results on benchmark and real-world datasets demonstrate that such a proxy fairness strategy can work well in practice. However, we caution that the effectiveness likely depends on the choice of fairness metric, as well as how aligned the proxy groups are with the true protected groups in terms of the constrained model parameters.
Adversarial and Perceptual Refinement for Compressed Sensing MRI Reconstruction
Venue: arXiv cs.CV 2018
Year: 2018

Deep learning approaches have shown promising performance for compressed sensing-based Magnetic Resonance Imaging. While deep neural networks trained with mean squared error (MSE) loss functions can achieve high peak signal to noise ratio, the reconstructed images are often blurry and lack sharp details, especially for higher undersampling rates. Recently, adversarial and perceptual loss functions have been shown to achieve more visually appealing results. However, it remains an open question how to (1) optimally combine these loss functions with the MSE loss function and (2) evaluate such a perceptual enhancement. In this work, we propose a hybrid method, in which a visual refinement component is learnt on top of an MSE loss-based reconstruction network. In addition, we introduce a semantic interpretability score, measuring the visibility of the region of interest in both ground truth and reconstructed images, which allows us to objectively quantify the usefulness of the image quality for image post-processing and analysis. Applied on a large cardiac MRI dataset simulated with 8-fold undersampling, we demonstrate significant improvements ($p<0.01$) over the state-of-the-art in both a human observer study and the semantic interpretability score.
Tight Prediction Intervals Using Expanded Interval Minimization
Venue: arXiv cs.LG 2018
Year: 2018

Prediction intervals are a valuable way of quantifying uncertainty in regression problems. Good prediction intervals should be both correct, containing the actual value between the lower and upper bound at least a target percentage of the time; and tight, having a small mean width of the bounds. Many prior techniques for generating prediction intervals make assumptions on the distribution of error, which causes them to work poorly for problems with asymmetric distributions. This paper presents Expanded Interval Minimization (EIM), a novel loss function for generating prediction intervals using neural networks. This loss function uses minibatch statistics to estimate the coverage and optimize the width of the prediction intervals. It does not make the same assumptions on the distributions of data and error as prior work. We compare to three published techniques and show EIM produces on average 1.37x tighter prediction intervals and in the worst case 1.06x tighter intervals across two large real-world datasets and varying coverage levels.
Gruut: A Fully-Decentralized P2P Public Ledger
Venue: arXiv cs.CR 2018
Year: 2018

Owing to Satoshi Nakamoto's brilliant idea, a P2P public ledger is shown to be implementable in anonymous network. Any Internet user can then join the anonymous network and contribute to the P2P public ledger by providing their computing power or proof-of-work. The proof-of-work is a clever implementation of one-CPU-one-vote by anonymous participants, and it protects the Bitcoin ledger from illegal modification. To compensate the nodes for their work, a cryptocurrency called Bitcoin is issued and given to nodes. However, the very nature of anonymity of the ledger and the cryptocurrency prevent the technology from being used in fiat money economy. Cryptocurrencies are not traceable even if they are used for money laundering or tax evasion, and the value of cryptocurrencies is not stable but fluctuates wildly. In this white paper, we introduce Gruut, a P2P ledger to implement a universal financial platform for fiat money. For this purpose, we introduce a new consensus algorithm called `proof-of-population,' which is one instance of `proof of public collaboration.' It can be used for multiple purposes; as a P2P ledger for banks, as a powerful tool for payment, including micropayment, and as a tool for any type of financial transactions. Even better, it distributes the profit obtained from transaction fee, currently dominated by a third party, to peers that cannot be centralized. Energy requirements of Gruut are so low that it is possible to run our software on a smartphone or on a personal computer without a graphic card.