OpenRaiser/Intern-Atlas huggingface dataset:
Practical, Linear-time, Fully Distributed Algorithms for Irregular Gather and Scatter
Venue: arXiv cs.DC 2017
Year: 2017

We present new, simple, fully distributed, practical algorithms with linear time communication cost for irregular gather and scatter operations in which processors contribute or consume possibly different amounts of data. In a linear cost transmission model with start-up latency $α$ and cost per unit $β$, the new algorithms take time $3|{\log_2 p}|α+β\sum_{i\neq r}m_i$ where $p$ is the number of processors, $m_i$ the amount of data for processor $i, 0\leq i<p$, and processor $r, 0\leq r<p$ a root processor determined by the algorithm. For a fixed, externally given root processor $r$, there is an additive penalty of at most $β(M_{d'}-m_{r_{d'}}-\sum_{0\leq j<d'}M_j)$ time steps where each $M_j$ is the total amount of data in a tree of $2^j$ different processors with roots $r_j$ as constructed by the algorithm. The worst-case penalty is less than $β\sum_{i\neq r}m_i$ time steps. The algorithms have attractive properties for implementing the operations for MPI (the Message-Passing Interface). Standard algorithms using fixed trees take time either $|{\log_2 p}|(α+β\sum_{i\neq r} m_i)$ in the worst case, or $\sum_{i\neq r}(α+βm_i)$. We have used the new algorithms to give prototype implementations for the MPI_Gatherv and MPI_Scatterv collectives of MPI, and present benchmark results from a small and a medium-large InfiniBand cluster. In order to structure the experimental evaluation we formulate new performance guidelines for irregular collectives that can be used to assess the performance in relation to the corresponding regular collectives. We show that the new algorithms can fulfill these performance expectations with a large margin, and that standard implementations do not.
Refinement-based Specification and Security Analysis of Separation Kernels
Venue: arXiv cs.SE 2017
Year: 2017

Assurance of information-flow security by formal methods is mandated in security certification of separation kernels. As an industrial standard for improving safety, ARINC 653 has been complied with by mainstream separation kernels. Due to the new trend of integrating safe and secure functionalities into one separation kernel, security analysis of ARINC 653 as well as a formal specification with security proofs are thus significant for the development and certification of ARINC 653 compliant Separation Kernels (ARINC SKs). This paper presents a specification development and security analysis method for ARINC SKs based on refinement. We propose a generic security model and a stepwise refinement framework. Two levels of functional specification are developed by the refinement. A major part of separation kernel requirements in ARINC 653 are modeled, such as kernel initialization, two-level scheduling, partition and process management, and inter-partition communication. The formal specification and its security proofs are carried out in the Isabelle/HOL theorem prover. We have reviewed the source code of one industrial and two open-source ARINC SK implementations, i.e. VxWorks 653, XtratuM, and POK, in accordance with the formal specification. During the verification and code review, six security flaws, which can cause information leakage, are found in the ARINC 653 standard and the implementations.
'Viral' Turing Machines, Computation from Noise and Combinatorial Hierarchies
Venue: arXiv cs.AI 2017
Year: 2017

The interactive computation paradigm is reviewed and a particular example is extended to form the stochastic analog of a computational process via a transcription of a minimal Turing Machine into an equivalent asynchronous Cellular Automaton with an exponential waiting times distribution of effective transitions. Furthermore, a special toolbox for analytic derivation of recursive relations of important statistical and other quantities is introduced in the form of an Inductive Combinatorial Hierarchy.
RESPARC: A Reconfigurable and Energy-Efficient Architecture with Memristive Crossbars for Deep Spiking Neural Networks
Venue: arXiv cs.ET 2017
Year: 2017

Neuromorphic computing using post-CMOS technologies is gaining immense popularity due to its promising abilities to address the memory and power bottlenecks in von-Neumann computing systems. In this paper, we propose RESPARC - a reconfigurable and energy efficient architecture built-on Memristive Crossbar Arrays (MCA) for deep Spiking Neural Networks (SNNs). Prior works were primarily focused on device and circuit implementations of SNNs on crossbars. RESPARC advances this by proposing a complete system for SNN acceleration and its subsequent analysis. RESPARC utilizes the energy-efficiency of MCAs for inner-product computation and realizes a hierarchical reconfigurable design to incorporate the data-flow patterns in an SNN in a scalable fashion. We evaluate the proposed architecture on different SNNs ranging in complexity from 2k-230k neurons and 1.2M-5.5M synapses. Simulation results on these networks show that compared to the baseline digital CMOS architecture, RESPARC achieves 500X (15X) efficiency in energy benefits at 300X (60X) higher throughput for multi-layer perceptrons (deep convolutional networks). Furthermore, RESPARC is a technology-aware architecture that maps a given SNN topology to the most optimized MCA size for the given crossbar technology.
Shannon-inspired Statistical Computing to Enable Spintronics
Venue: arXiv cs.ET 2017
Year: 2017

Modern computing systems based on the von Neumann architecture are built from silicon complementary metal oxide semiconductor (CMOS) transistors that need to operate under practically error free conditions with 1 error in $10^{15}$ switching events. The physical dimensions of CMOS transistors have scaled down over the past five decades leading to exponential increases in functional density and energy consumption. Today, the energy and delay reductions from scaling have stagnated, motivating the search for a CMOS replacement. Of these, spintronics offers a path for enhancing the functional density and scaling the energy down to fundamental thermodynamic limits of 100kT to 1000kT. However, spintronic devices exhibit high error rates of 1 in 10 or more when operating at these limits, rendering them incompatible with deterministic nature of the von Neumann architecture. We show that a Shannon-inspired statistical computing framework can be leveraged to design a computer made from such stochastic spintronic logic gates to provide a computational accuracy close to that of a deterministic computer. This extraordinary result allowing a $10^{13}$ fold relaxation in acceptable error rates is obtained by engineering the error distribution coupled with statistical error compensation.
Community Detection with Colored Edges
Venue: arXiv cs.SI 2017
Year: 2017

In this paper, we prove a sharp limit on the community detection problem with colored edges. We assume two equal-sized communities and there are $m$ different types of edges. If two vertices are in the same community, the distribution of edges follows $p_i=α_i\log{n}/n$ for $1\leq i \leq m$, otherwise the distribution of edges is $q_i=β_i\log{n}/n$ for $1\leq i \leq m$, where $α_i$ and $β_i$ are positive constants and $n$ is the total number of vertices. Under these assumptions, a fundamental limit on community detection is characterized using the Hellinger distance between the two distributions. If $\sum_{i=1}^{m} {(\sqrt{α_i} - \sqrt{β_i})}^2 >2$, then the community detection via maximum likelihood (ML) estimator is possible with high probability. If $\sum_{i=1}^m {(\sqrt{α_i} - \sqrt{β_i})}^2 < 2$, the probability that the ML estimator fails to detect the communities does not go to zero.
Robust Phase Retrieval via ADMM with Outliers
Venue: arXiv cs.IT 2017
Year: 2017

An outlier-resistance phase retrieval algorithm based on alternating direction method of multipliers (ADMM) is devised in this letter. Instead of the widely used least squares criterion that is only optimal for Gaussian noise environment, we adopt the least absolute deviation criterion to enhance the robustness against outliers. Considering both intensity- and amplitude-based observation models, the framework of ADMM is developed to solve the resulting non-differentiable optimization problems. It is demonstrated that the core subproblem of ADMM is the proximity operator of the L1-norm, which can be computed efficiently by soft-thresholding in each iteration. Simulation results are provided to validate the accuracy and efficiency of the proposed approach compared to the existing schemes.
Forest understory trees can be segmented accurately within sufficiently dense airborne laser scanning point clouds
Venue: arXiv cs.CV 2017
Year: 2017

Airborne laser scanning (LiDAR) point clouds over large forested areas can be processed to segment individual trees and subsequently extract tree-level information. Existing segmentation procedures typically detect more than 90% of overstory trees, yet they barely detect 60% of understory trees because of the occlusion effect of higher canopy layers. Although understory trees provide limited financial value, they are an essential component of ecosystem functioning by offering habitat for numerous wildlife species and influencing stand development. Here we model the occlusion effect in terms of point density. We estimate the fractions of points representing different canopy layers (one overstory and multiple understory) and also pinpoint the required density for reasonable tree segmentation (where accuracy plateaus). We show that at a density of ~170 pt/m-sqr understory trees can likely be segmented as accurately as overstory trees. Given the advancements of LiDAR sensor technology, point clouds will affordably reach this required density. Using modern computational approaches for big data, the denser point clouds can efficiently be processed to ultimately allow accurate remote quantification of forest resources. The methodology can also be adopted for other similar remote sensing or advanced imaging applications such as geological subsurface modelling or biomedical tissue analysis.
The Power of Sparsity in Convolutional Neural Networks
Venue: arXiv cs.CV 2017
Year: 2017

Deep convolutional networks are well-known for their high computational and memory demands. Given limited resources, how does one design a network that balances its size, training time, and prediction accuracy? A surprisingly effective approach to trade accuracy for size and speed is to simply reduce the number of channels in each convolutional layer by a fixed fraction and retrain the network. In many cases this leads to significantly smaller networks with only minimal changes to accuracy. In this paper, we take a step further by empirically examining a strategy for deactivating connections between filters in convolutional layers in a way that allows us to harvest savings both in run-time and memory for many network architectures. More specifically, we generalize 2D convolution to use a channel-wise sparse connection structure and show that this leads to significantly better results than the baseline approach for large networks including VGG and Inception V3.
On the (Statistical) Detection of Adversarial Examples
Venue: arXiv cs.CR 2017
Year: 2017

Machine Learning (ML) models are applied in a variety of tasks such as network intrusion detection or Malware classification. Yet, these models are vulnerable to a class of malicious inputs known as adversarial examples. These are slightly perturbed inputs that are classified incorrectly by the ML model. The mitigation of these adversarial inputs remains an open problem. As a step towards understanding adversarial examples, we show that they are not drawn from the same distribution than the original data, and can thus be detected using statistical tests. Using thus knowledge, we introduce a complimentary approach to identify specific inputs that are adversarial. Specifically, we augment our ML model with an additional output, in which the model is trained to classify all adversarial inputs. We evaluate our approach on multiple adversarial example crafting methods (including the fast gradient sign and saliency map methods) with several datasets. The statistical test flags sample sets containing adversarial inputs confidently at sample sizes between 10 and 100 data points. Furthermore, our augmented model either detects adversarial examples as outliers with high accuracy (> 80%) or increases the adversary's cost - the perturbation added - by more than 150%. In this way, we show that statistical properties of adversarial examples are essential to their detection.
Convolution Aware Initialization
Venue: arXiv cs.LG 2017
Year: 2017

Initialization of parameters in deep neural networks has been shown to have a big impact on the performance of the networks (Mishkin & Matas, 2015). The initialization scheme devised by He et al, allowed convolution activations to carry a constrained mean which allowed deep networks to be trained effectively (He et al., 2015a). Orthogonal initializations and more generally orthogonal matrices in standard recurrent networks have been proved to eradicate the vanishing and exploding gradient problem (Pascanu et al., 2012). Majority of current initialization schemes do not take fully into account the intrinsic structure of the convolution operator. Using the duality of the Fourier transform and the convolution operator, Convolution Aware Initialization builds orthogonal filters in the Fourier space, and using the inverse Fourier transform represents them in the standard space. With Convolution Aware Initialization we noticed not only higher accuracy and lower loss, but faster convergence. We achieve new state of the art on the CIFAR10 dataset, and achieve close to state of the art on various other tasks.
Mimicking Ensemble Learning with Deep Branched Networks
Venue: arXiv cs.CV 2017
Year: 2017

This paper proposes a branched residual network for image classification. It is known that high-level features of deep neural network are more representative than lower-level features. By sharing the low-level features, the network can allocate more memory to high-level features. The upper layers of our proposed network are branched, so that it mimics the ensemble learning. By mimicking ensemble learning with single network, we have achieved better performance on ImageNet classification task.
Correct Convergence of Min-Sum Loopy Belief Propagation in a Block Interpolation Problem
Venue: arXiv cs.OH 2017
Year: 2017

This work proves a new result on the correct convergence of Min-Sum Loopy Belief Propagation (LBP) in an interpolation problem on a square grid graph. The focus is on the notion of local solutions, a numerical quantity attached to each site of the graph that can be used for obtaining MAP estimates. The main result is that over an $N\times N$ grid graph with a one-run boundary configuration, the local solutions at each $i \in B$ can be calculated using Min-Sum LBP by passing difference messages in $2N$ iterations, which parallels the well-known convergence time in trees.
A Discriminative Event Based Model for Alzheimer's Disease Progression Modeling
Venue: arXiv cs.CV 2017
Year: 2017

The event-based model (EBM) for data-driven disease progression modeling estimates the sequence in which biomarkers for a disease become abnormal. This helps in understanding the dynamics of disease progression and facilitates early diagnosis by staging patients on a disease progression timeline. Existing EBM methods are all generative in nature. In this work we propose a novel discriminative approach to EBM, which is shown to be more accurate as well as computationally more efficient than existing state-of-the art EBM methods. The method first estimates for each subject an approximate ordering of events, by ranking the posterior probabilities of individual biomarkers being abnormal. Subsequently, the central ordering over all subjects is estimated by fitting a generalized Mallows model to these approximate subject-specific orderings based on a novel probabilistic Kendall's Tau distance. To evaluate the accuracy, we performed extensive experiments on synthetic data simulating the progression of Alzheimer's disease. Subsequently, the method was applied to the Alzheimer's Disease Neuroimaging Initiative (ADNI) data to estimate the central event ordering in the dataset. The experiments benchmark the accuracy of the new model under various conditions and compare it with existing state-of-the-art EBM methods. The results indicate that discriminative EBM could be a simple and elegant approach to disease progression modeling.
Contract-Theoretic Resource Allocation for Critical Infrastructure Protection
Venue: arXiv cs.CR 2017
Year: 2017

Critical infrastructure protection (CIP) is envisioned to be one of the most challenging security problems in the coming decade. One key challenge in CIP is the ability to allocate resources, either personnel or cyber, to critical infrastructures with different vulnerability and criticality levels. In this work, a contract-theoretic approach is proposed to solve the problem of resource allocation in critical infrastructure with asymmetric information. A control center (CC) is used to design contracts and offer them to infrastructures' owners. A contract can be seen as an agreement between the CC and infrastructures using which the CC allocates resources and gets rewards in return. Contracts are designed in a way to maximize the CC's benefit and motivate each infrastructure to accept a contract and obtain proper resources for its protection. Infrastructures are defined by both vulnerability levels and criticality levels which are unknown to the CC. Therefore, each infrastructure can claim that it is the most vulnerable or critical to gain more resources. A novel mechanism is developed to handle such an asymmetric information while providing the optimal contract that motivates each infrastructure to reveal its actual type. The necessary and sufficient conditions for such resource allocation contracts under asymmetric information are derived. Simulation results show that the proposed contract-theoretic approach maximizes the CC's utility while ensuring that no infrastructure has an incentive to ask for another contract, despite the lack of exact information at the CC.
Personality Traits and Ego-network Dynamics
Venue: arXiv cs.SI 2017
Year: 2017

Strong and supportive social relationships are fundamental to our well-being. However, there are costs to their maintenance, resulting in a trade-off between quality and quantity, a typical strategy being to put a lot of effort on a few high-intensity relationships while maintaining larger numbers of less close relationships. It has also been shown that there are persistent individual differences in this pattern; some individuals allocate their efforts more uniformly across their networks, while others strongly focus on their closest relationships. Furthermore, some individuals maintain more stable networks than others. Here, we focus on how personality traits of individuals affect this picture, using mobile phone calls records and survey data from the Mobile Territorial Lab (MTL) study. In particular, we look at the relationship between personality traits and the (i) persistence of social signatures, namely the similarity of the social signature shape of an individual measured in different time intervals; (ii) the turnover in egocentric networks, that is, differences in the set of alters present at two consecutive temporal intervals; and (iii) the rank dynamics defined as the variation of alter rankings in egocentric networks in consecutive intervals. We observe that some traits have effects on the stability of the social signatures as well as network turnover and rank dynamics. As an example, individuals who score highly in the Openness to Experience trait tend to have higher levels of network turnover and larger alter rank variations. On broader terms, our study shows that personality traits clearly affect the ways in which individuals maintain their personal networks.
Mathematical Backdoors in Symmetric Encryption Systems - Proposal for a Backdoored AES-like Block Cipher
Venue: arXiv cs.CR 2017
Year: 2017

Recent years have shown that more than ever governments and intelligence agencies try to control and bypass the cryptographic means used for the protection of data. Backdooring encryption algorithms is considered as the best way to enforce cryptographic control. Until now, only implementation backdoors (at the protocol/implementation/management level) are generally considered. In this paper we propose to address the most critical issue of backdoors: mathematical backdoors or by-design backdoors, which are put directly at the mathematical design of the encryption algorithm. While the algorithm may be totally public, proving that there is a backdoor, identifying it and exploiting it, may be an intractable problem. We intend to explain that it is probably possible to design and put such backdoors. Considering a particular family (among all the possible ones), we present BEA-1, a block cipher algorithm which is similar to the AES and which contains a mathematical backdoor enabling an operational and effective cryptanalysis. The BEA-1 algorithm (80-bit block size, 120-bit key, 11 rounds) is designed to resist to linear and differential cryptanalyses. A challenge will be proposed to the cryptography community soon. Its aim is to assess whether our backdoor is easily detectable and exploitable or not.
Timely CSI Acquisition Exploiting Full Duplex
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we propose a method for acquiring accurate and timely channel state information (CSI) by leveraging full-duplex transmission. Specifically, we propose a mobile communication system in which base stations continuously transmit a pilot sequence in the uplink frequency band, while terminals use self-interference cancellation capabilities to obtain CSI at any time. Our proposal outperforms its half-duplex counterpart by at least 50% in terms of throughput while ensuring the same (or even lower) outage probability. Remarkably, it also outperforms using full duplex for downlink data transmission for low values of downlink bandwidth and received power.
When can Graph Hyperbolicity be computed in Linear Time?
Venue: arXiv cs.CC 2017
Year: 2017

Hyperbolicity measures, in terms of (distance) metrics, how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen intensive research over the last years. Unfortunately, the best known algorithms for computing the hyperbolicity number of a graph (the smaller, the more tree-like) have running time $O(n^4)$, where $n$ is the number of graph vertices. Exploiting the framework of parameterized complexity analysis, we explore possibilities for "linear-time FPT" algorithms to compute hyperbolicity. For instance, we show that hyperbolicity can be computed in time $O(2^{O(k)} + n +m)$ ($m$ being the number of graph edges) while at the same time, unless the SETH fails, there is no $2^{o(k)}n^2$-time algorithm.