OpenRaiser/Intern-Atlas huggingface dataset:
Space-Efficient DFS and Applications: Simpler, Leaner, Faster
Venue: arXiv cs.DS 2018
Year: 2018

The problem of space-efficient depth-first search (DFS) is reconsidered. A particularly simple and fast algorithm is presented that, on a directed or undirected input graph $G=(V,E)$ with $n$ vertices and $m$ edges, carries out a DFS in $O(n+m)$ time with $n+\sum_{v\in V_{\ge 3}}\lceil{\log_2(d_v-1)}\rceil +O(\log n)\le n+m+O(\log n)$ bits of working memory, where $d_v$ is the (total) degree of $v$, for each $v\in V$, and $V_{\ge 3}=\{v\in V\mid d_v\ge 3\}$. A slightly more complicated variant of the algorithm works in the same time with at most $n+({4/5})m+O(\log n)$ bits. It is also shown that a DFS can be carried out in a graph with $n$ vertices and $m$ edges in $O(n+m\log^*\! n)$ time with $O(n)$ bits or in $O(n+m)$ time with either $O(n\log\log(4+{m/n}))$ bits or, for arbitrary integer $k\ge 1$, $O(n\log^{(k)}\! n)$ bits. These results among them subsume or improve most earlier results on space-efficient DFS. Some of the new time and space bounds are shown to extend to applications of DFS such as the computation of cut vertices, bridges, biconnected components and 2-edge-connected components in undirected graphs.
The One-Shot Crowdfunding Game
Venue: arXiv cs.GT 2018
Year: 2018

The recent success of crowd-funding for supporting new and innovative products has been overwhelming with over 34 Billion Dollars raised in 2015. In many crowd-funding platforms, firms set a campaign goal and contributions are collected only if this goal is reached. At the time of the campaign, consumers are often uncertain as to the ex-post value of the product, the business model viability, or the seller's reliability. Consumer who commit to a contribution therefore gambles. This gamble is effected by the campaign's threshold. Contributions to campaigns with higher thresholds are collected only if a greater number of agents find the offering acceptable. Therefore, high threshold serves as a social insurance and thus in high-threshold campaigns, potential contributors feel more at ease with contributing. We introduce the crowdunding game and explore the contributor's dilemma in the context of experience goods. We discuss equilibrium existence and related social welfare, information aggregation and revenue implications.
Multi-Message Private Information Retrieval with Private Side Information
Venue: arXiv cs.IT 2018
Year: 2018

We consider the problem of private information retrieval (PIR) where a single user with private side information aims to retrieve multiple files from a library stored (uncoded) at a number of servers. We assume the side information at the user includes a subset of files stored privately (i.e., the server does not know the indices of these files). In addition, we require that the identity of the requests and side information at the user are not revealed to any of the servers. The problem involves finding the minimum load to be transmitted from the servers to the user such that the requested files can be decoded with the help of received and side information. By providing matching lower and upper bounds, for certain regimes, we characterize the minimum load imposed to all the servers (i.e., the capacity of this PIR problem). Our result shows that the capacity is the same as the capacity of a multi-message PIR problem without private side information, but with a library of reduced size. The effective size of the library is equal to the original library size minus the size of side information.
Lord of the x86 Rings: A Portable User Mode Privilege Separation Architecture on x86
Venue: arXiv cs.CR 2018
Year: 2018

Modern applications are increasingly advanced and complex, and inevitably contain exploitable software bugs despite the ongoing efforts. The applications today often involve processing of sensitive information. However, the lack of privilege separation within the user space leaves sensitive application secret such as cryptographic keys just as unprotected as a "hello world" string. Cutting-edge hardware-supported security features are being introduced. However, the features are often vendor-specific or lack compatibility with older generations of the processors. The situation leaves developers with no portable solution to incorporate protection for the sensitive application component. We propose LOTRx86, a fundamental and portable approach for user space privilege separation. Our approach creates a more privileged user execution layer called PrivUser through harnessing the underused intermediate privilege levels on the x86 architecture. The PrivUser memory space, a set of pages within process address space that are inaccessible to user mode, is a safe place for application secrets and routines that access them. We implement the LOTRx86 ABI that exports the privilege-based, accessing the protected application secret only requires a change in the privilege, eliminating the need for costly remote procedure calls or change in address space. We evaluated our platform by developing a proof-of-concept LOTRx86-enabled web server that employs our architecture to securely access its private key during SSL connection and thereby mitigating the HeartBleed vulnerability by design. We conducted a set of experiments including a performance measurement on the PoC on both Intel and AMD PCs, and confirmed that LOTRx86 incurs only a limited performance overhead.
Iterative Antenna Selection for Secrecy Enhancement in Massive MIMO Wiretap Channels
Venue: arXiv cs.IT 2018
Year: 2018

The growth of interest in massive MIMO systems is accompanied with hardware cost and computational complexity. Antenna selection is an efficient approach to overcome this cost-plus-complexity issue which also enhances the secrecy performance in wiretap settings. Optimal antenna selection requires exhaustive search which is computationally infeasible for settings with large dimensions. This paper develops an iterative algorithm for antenna selection in massive multiuser MIMO wiretap settings. The algorithm takes a stepwise approach to find a suitable subset of transmit antennas. Numerical investigations depict a significant enhancement in the secrecy performance.
Learning to Generate Facial Depth Maps
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, an adversarial architecture for facial depth map estimation from monocular intensity images is presented. By following an image-to-image approach, we combine the advantages of supervised learning and adversarial training, proposing a conditional Generative Adversarial Network that effectively learns to translate intensity face images into the corresponding depth maps. Two public datasets, namely Biwi database and Pandora dataset, are exploited to demonstrate that the proposed model generates high-quality synthetic depth images, both in terms of visual appearance and informative content. Furthermore, we show that the model is capable of predicting distinctive facial details by testing the generated depth maps through a deep model trained on authentic depth maps for the face verification task.
Optimizing Sparse Matrix-Vector Multiplication on Emerging Many-Core Architectures
Venue: arXiv cs.MS 2018
Year: 2018

Sparse matrix vector multiplication (SpMV) is one of the most common operations in scientific and high-performance applications, and is often responsible for the application performance bottleneck. While the sparse matrix representation has a significant impact on the resulting application performance, choosing the right representation typically relies on expert knowledge and trial and error. This paper provides the first comprehensive study on the impact of sparse matrix representations on two emerging many-core architectures: the Intel's Knights Landing (KNL) XeonPhi and the ARM-based FT-2000Plus (FTP). Our large-scale experiments involved over 9,500 distinct profiling runs performed on 956 sparse datasets and five mainstream SpMV representations. We show that the best sparse matrix representation depends on the underlying architecture and the program input. To help developers to choose the optimal matrix representation, we employ machine learning to develop a predictive model. Our model is first trained offline using a set of training examples. The learned model can be used to predict the best matrix representation for any unseen input for a given architecture. We show that our model delivers on average 95% and 91% of the best available performance on KNL and FTP respectively, and it achieves this with no runtime profiling overhead.
Adjacency and Tensor Representation in General Hypergraphs.Part 2: Multisets, Hb-graphs and Related e-adjacency Tensors
Venue: arXiv cs.DM 2018
Year: 2018

HyperBagGraphs (hb-graphs as short) extend hypergraphs by allowing the hyperedges to be multisets. Multisets are composed of elements that have a multiplicity. When this multiplicity has positive integer values, it corresponds to non ordered lists of potentially duplicated elements. We define hb-graphs as family of multisets over a vertex set; natural hb-graphs correspond to hb-graphs that have multiplicity function with positive integer values. Extending the definition of e-adjacency to natural hb-graphs, we define different way of building an e-adjacency tensor, that we compare before having a final choice of the tensor. This hb-graph e-adjacency tensor is used with hypergraphs.
Robotics and Integrated Formal Methods: Necessity meets Opportunity
Venue: arXiv cs.SE 2018
Year: 2018

Robotic systems are multi-dimensional entities, combining both hardware and software, that are heavily dependent on, and influenced by, interactions with the real world. They can be variously categorised as embedded, cyberphysical, real-time, hybrid, adaptive and even autonomous systems, with a typical robotic system being likely to contain all of these aspects. The techniques for developing and verifying each of these system varieties are often quite distinct. This, together with the sheer complexity of robotic systems, leads us to argue that diverse formal techniques must be integrated in order to develop, verify, and provide certification evidence for, robotic systems. Furthermore, we propose the fast evolving field of robotics as an ideal catalyst for the advancement of integrated formal methods research, helping to drive the field in new and exciting directions and shedding light on the development of large-scale, dynamic, complex systems.
BUNDLEP: Prioritizing Conflict Free Regions in Multi-Threaded Programs to Improve Cache Reuse -- Extended Results and Technical Report
Venue: arXiv cs.DC 2018
Year: 2018

In BUNDLE: Real-Time Multi-Threaded Scheduling to Reduce Cache Contention, Tessler and Fisher propose a scheduling mechanism and combined worst-case execution time calculation method that treats the instruction cache as a beneficial resource shared between threads. Object analysis produces a worst-case execution time bound and separates code segments into regions. Threads are dynamically placed in bundles as- sociated with regions at run time by the BUNDLE scheduling algorithm where they benefit from shared cache values. In the evaluation of the previous work, tasks were created with a predetermined worst-case execution time path through the control flow graph. Apriori knowledge of the worst-case path is an impractical restriction on any analysis. At the time, the only other solution available was an all-paths search of the graph, which is an equally impractical approach due to its complexity. The primary focus of this work is to build upon BUNDLE, expanding its applicability beyond a proof of concept. We present a complete a worst-case execution time calculation method that includes thread level context switch costs, operating on real programs, with representative architecture parameters, and compare our results to those produced by Heptane's state of the art method. To these ends, we propose a modification to the BUNDLE scheduling algorithm called BUNDLEP. Bundles are assigned priorities that enforce an ordered flow of threads through the control flow graph -- avoiding the need for multiple all-paths searches through the graph. In many cases, our evaluation shows a run-time and analytical benefit for BUNLDEP compared to serialized thread execution and state of the art WCET analysis.
Stochastic Deep Compressive Sensing for the Reconstruction of Diffusion Tensor Cardiac MRI
Venue: arXiv cs.CV 2018
Year: 2018

Understanding the structure of the heart at the microscopic scale of cardiomyocytes and their aggregates provides new insights into the mechanisms of heart disease and enables the investigation of effective therapeutics. Diffusion Tensor Cardiac Magnetic Resonance (DT-CMR) is a unique non-invasive technique that can resolve the microscopic structure, organisation, and integrity of the myocardium without the need for exogenous contrast agents. However, this technique suffers from relatively low signal-to-noise ratio (SNR) and frequent signal loss due to respiratory and cardiac motion. Current DT-CMR techniques rely on acquiring and averaging multiple signal acquisitions to improve the SNR. Moreover, in order to mitigate the influence of respiratory movement, patients are required to perform many breath holds which results in prolonged acquisition durations (e.g., ~30 mins using the existing technology). In this study, we propose a novel cascaded Convolutional Neural Networks (CNN) based compressive sensing (CS) technique and explore its applicability to improve DT-CMR acquisitions. Our simulation based studies have achieved high reconstruction fidelity and good agreement between DT-CMR parameters obtained with the proposed reconstruction and fully sampled ground truth. When compared to other state-of-the-art methods, our proposed deep cascaded CNN method and its stochastic variation demonstrated significant improvements. To the best of our knowledge, this is the first study using deep CNN based CS for the DT-CMR reconstruction. In addition, with relatively straightforward modifications to the acquisition scheme, our method can easily be translated into a method for online, at-the-scanner reconstruction enabling the deployment of accelerated DT-CMR in various clinical applications.
Social Signals in the Ethereum Trading Network
Venue: arXiv cs.SI 2018
Year: 2018

Blockchain technology, which has been known by mostly small technological circles up until recently, is bursting throughout the globe, with a potential economic and social impact that could fundamentally alter traditional financial and social structures. Issuing cryptocurrencies on top of the Blockchain system by startups and private sector companies is becoming a ubiquitous phenomenon, inducing the trading of these crypto-coins among their holders using dedicated exchanges. Apart from being a trading ledger for tokens, Blockchain can also be observed as a social network. Analyzing and modeling the dynamics of the "social signals" of this network can contribute to our understanding of this ecosystem and the forces acting within in. This work is the first analysis of the network properties of the ERC20 protocol compliant crypto-coins' trading data. Considering all trading wallets as a network's nodes, and constructing its edges using buy--sell trades, we can analyze the network properties of the ERC20 network. Examining several periods of time, and several data aggregation variants, we demonstrate that the network displays strong power-law properties. These results coincide with current network theory expectations, however nonetheless, are the first scientific validation of it, for the ERC20 trading data. The data we examined is composed of over 30 million ERC20 tokens trades, performed by over 6.8 million unique wallets, lapsing over a two years period between February 2016 and February 2018.
Context-aware Cascade Attention-based RNN for Video Emotion Recognition
Venue: arXiv cs.CV 2018
Year: 2018

Emotion recognition can provide crucial information about the user in many applications when building human-computer interaction (HCI) systems. Most of current researches on visual emotion recognition are focusing on exploring facial features. However, context information including surrounding environment and human body can also provide extra clues to recognize emotion more accurately. Inspired by "sequence to sequence model" for neural machine translation, which models input and output sequences by an encoder and a decoder in recurrent neural network (RNN) architecture respectively, a novel architecture, "CACA-RNN", is proposed in this work. The proposed network consists of two RNNs in a cascaded architecture to process both context and facial information to perform video emotion classification. Results of the model were submitted to video emotion recognition sub-challenge in Multimodal Emotion Recognition Challenge (MEC2017). CACA-RNN outperforms the MEC2017 baseline (mAP of 21.7%): it achieved mAP of 45.51% on the testing set in the video only challenge.
An Improved Active Disturbance Rejection Control for a Differential Drive Mobile Robot with Mismatched Disturbances and Uncertainties
Venue: arXiv cs.SY 2018
Year: 2018

In this paper a new strategy based on disturbance and uncertainty (DU) estimation and attenuation technique is proposed and tested on the nonlinear kinematic model of the differential drive mobile robot (DDMR). The proposed technique is an improved version of the Active Disturbance Rejection Control (ADRC) strategy suggested by J. Han. The ADRC is used to actively reject disturbances caused by the unknown exogenous signals and the matched uncertainties of the system model, which are lumped all together and attributed as a total disturbance. In this work, the considered system is assumed to be affine and the total disturbance and the input are considered to be on different channels. To deal with the mismatched disturbances and uncertainties, the total disturbance has been converted into a matched one. Then, based on the improved ADRC (IADRC), the dynamic performance of the DDMR has been enhanced by estimating the total disturbance and canceling it from the system. Through digital simulations, different performance measures are applied, and they all indicate the effectiveness of the proposed IADRC by almost removing the chattering phenomenon and providing a high immunity in the closed-loop system against torque disturbance.
Opinion Forming in Erdos-Renyi Random Graph and Expanders
Venue: arXiv cs.DS 2018
Year: 2018

Assume for a graph $G=(V,E)$ and an initial configuration, where each node is blue or red, in each discrete-time round all nodes simultaneously update their color to the most frequent color in their neighborhood and a node keeps its color in case of a tie. We study the behavior of this basic process, which is called majority model, on the binomial random graph $\mathcal{G}_{n,p}$ and regular expanders. First we consider the behavior of the majority model in $\mathcal{G}_{n,p}$ with an initial random configuration, where each node is blue independently with probability $p_b$ and red otherwise. It is shown that in this setting the process goes through a phase transition at the connectivity threshold, namely $\frac{\log n}{n}$. Furthermore, we discuss the majority model is a `good' and `fast' density classifier on regular expanders. More precisely, we prove if the second-largest absolute eigenvalue of the adjacency matrix of an $n$-node $Δ$-regular graph is sufficiently smaller than $Δ$ then the majority model by starting from $(\frac{1}{2}-δ)n$ blue nodes (for an arbitrarily small constant $δ>0$) results in fully red configuration in sub-logarithmically many rounds. As a by-product of our results, we show Ramanujan graphs are asymptotically optimally immune, that is for an $n$-node $Δ$-regular Ramanujan graph if the initial number of blue nodes is $s\leq βn$, the number of blue nodes in the next round is at most $\frac{cs}Δ$ for some constants $c,β>0$. This settles an open problem by Peleg.
Deep Segment Hash Learning for Music Generation
Venue: arXiv cs.LG 2018
Year: 2018

Music generation research has grown in popularity over the past decade, thanks to the deep learning revolution that has redefined the landscape of artificial intelligence. In this paper, we propose a novel approach to music generation inspired by musical segment concatenation methods and hash learning algorithms. Given a segment of music, we use a deep recurrent neural network and ranking-based hash learning to assign a forward hash code to the segment to retrieve candidate segments for continuation with matching backward hash codes. The proposed method is thus called Deep Segment Hash Learning (DSHL). To the best of our knowledge, DSHL is the first end-to-end segment hash learning method for music generation, and the first to use pair-wise training with segments of music. We demonstrate that this method is capable of generating music which is both original and enjoyable, and that DSHL offers a promising new direction for music generation research.
How Important Is a Neuron?
Venue: arXiv cs.LG 2018
Year: 2018

The problem of attributing a deep network's prediction to its \emph{input/base} features is well-studied. We introduce the notion of \emph{conductance} to extend the notion of attribution to the understanding the importance of \emph{hidden} units. Informally, the conductance of a hidden unit of a deep network is the \emph{flow} of attribution via this hidden unit. We use conductance to understand the importance of a hidden unit to the prediction for a specific input, or over a set of inputs. We evaluate the effectiveness of conductance in multiple ways, including theoretical properties, ablation studies, and a feature selection task. The empirical evaluations are done using the Inception network over ImageNet data, and a sentiment analysis network over reviews. In both cases, we demonstrate the effectiveness of conductance in identifying interesting insights about the internal workings of these networks.
On the Impact of Various Types of Noise on Neural Machine Translation
Venue: arXiv cs.CL 2018
Year: 2018

We examine how various types of noise in the parallel training data impact the quality of neural machine translation systems. We create five types of artificial noise and analyze how they degrade performance in neural and statistical machine translation. We find that neural models are generally more harmed by noise than statistical models. For one especially egregious type of noise they learn to just copy the input sentence.
Reinforced Continual Learning
Venue: arXiv cs.LG 2018
Year: 2018

Most artificial intelligence models have limiting ability to solve new tasks faster, without forgetting previously acquired knowledge. The recently emerging paradigm of continual learning aims to solve this issue, in which the model learns various tasks in a sequential fashion. In this work, a novel approach for continual learning is proposed, which searches for the best neural architecture for each coming task via sophisticatedly designed reinforcement learning strategies. We name it as Reinforced Continual Learning. Our method not only has good performance on preventing catastrophic forgetting but also fits new tasks well. The experiments on sequential classification tasks for variants of MNIST and CIFAR-100 datasets demonstrate that the proposed approach outperforms existing continual learning alternatives for deep networks.