OpenRaiser/Intern-Atlas huggingface dataset:
Mathematical Analysis and Algorithms for Federated Byzantine Agreement Systems
Venue: arXiv cs.DC 2019
Year: 2019

We give an introduction to federated Byzantine agreement systems (FBAS) with many examples ranging from small "academic" cases to the current Stellar network. We then analyze the main concepts from a mathematical and an algorithmic point of view. Based on work of Lachowski we derive algorithms for quorum enumeration, checking quorum intersection, and computing the intact nodes with respect to a given set of ill-behaved (Byzantine) nodes. We also show that from the viewpoint of the intactness probability of nodes, which we introduce in this paper, a hierarchical setup of nodes is inferior to an arrangement that we call a symmetric simple FBAS. All algorithms described in this paper are implemented in the Python package Stellar Observatory, which is also used in some of the computed examples.
TU Wien @ TREC Deep Learning '19 -- Simple Contextualization for Re-ranking
Venue: arXiv cs.IR 2019
Year: 2019

The usage of neural network models puts multiple objectives in conflict with each other: Ideally we would like to create a neural model that is effective, efficient, and interpretable at the same time. However, in most instances we have to choose which property is most important to us. We used the opportunity of the TREC 2019 Deep Learning track to evaluate the effectiveness of a balanced neural re-ranking approach. We submitted results of the TK (Transformer-Kernel) model: a neural re-ranking model for ad-hoc search using an efficient contextualization mechanism. TK employs a very small number of lightweight Transformer layers to contextualize query and document word embeddings. To score individual term interactions, we use a document-length enhanced kernel-pooling, which enables users to gain insight into the model. Our best result for the passage ranking task is: 0.420 MAP, 0.671 nDCG, 0.598 P@10 (TUW19-p3 full). Our best result for the document ranking task is: 0.271 MAP, 0.465 nDCG, 0.730 P@10 (TUW19-d3 re-ranking).
Fast and Scalable Estimator for Sparse and Unit-Rank Higher-Order Regression Models
Venue: arXiv cs.LG 2019
Year: 2019

Because tensor data appear more and more frequently in various scientific researches and real-world applications, analyzing the relationship between tensor features and the univariate outcome becomes an elementary task in many fields. To solve this task, we propose \underline{Fa}st \underline{S}parse \underline{T}ensor \underline{R}egression model (FasTR) based on so-called unit-rank CANDECOMP/PARAFAC decomposition. FasTR first decomposes the tensor coefficient into component vectors and then estimates each vector with $\ell_1$ regularized regression. Because of the independence of component vectors, FasTR is able to solve in a parallel way and the time complexity is proved to be superior to previous models. We evaluate the performance of FasTR on several simulated datasets and a real-world fMRI dataset. Experiment results show that, compared with four baseline models, in every case, FasTR can compute a better solution within less time.
Grant-Free Massive Random Access With a Massive MIMO Receiver
Venue: arXiv cs.IT 2019
Year: 2019

We consider the problem of unsourced random access (U-RA), a grant-free uncoordinated form of random access, in a wireless channel with a massive MIMO base station equipped with a large number $M$ of antennas and a large number of wireless single-antenna devices (users). We consider a block fading channel model where the $M$-dimensional channel vector of each user remains constant over a coherence block containing $L$ signal dimensions in time-frequency. In the considered setting, the number of potential users $K_\text{tot}$ is much larger than $L$ but at each time slot only $K_a \ll K_\text{tot}$ of them are active. Previous results, based on compressed sensing, require that $K_a < L$, which is a bottleneck in massive deployment scenarios such as Internet-of-Things and U-RA. In the context of activity detection it is known that such a limitation can be overcome when the number of base station antennas $M$ is sufficiently large and a covariance based recovery algorithm is employed at the receiver. We show that, in the context of U-RA, the same concept allows to achieve high spectral efficiencies in the order of $\mathcal{O}(L \log L)$, although at an exponentially growing complexity. We show also that a concatenated coding scheme can be used to reduce the complexity to an acceptable level while still achieving total spectral efficiencies in the order of $\mathcal{O}(L/\log L)$.
A Hybrid Graph Coloring Algorithm for GPUs
Venue: arXiv cs.DC 2019
Year: 2019

Graph algorithms mainly belong to two categories, topology-driven and data-driven. Data-driven approach maintains a worklist of active nodes, the nodes on which work has to be done. Topology-driven approach sweeps over the entire graph to find active nodes. Hybridization is an optimization technique where in each iteration, the computation is done in a topology-driven or data-driven manner based on worklist size. In hybrid implementations, there is a need to switch between topology-driven and data-driven approaches. Typically, a worklist is maintained just in the data-driven part of the algorithm and discarded in the topology-driven part. We propose a variant of hybridization, wherein a worklist is maintained throughout all iterations of the algorithm and still show it to be faster than both, topology-driven and data-driven approaches. We consider a graph coloring algorithm called IPGC (Iterative Parallel Graph Coloring) and implement a hybrid version for the same in a graph domain specific language called IrGL. We observe a mean speedup of 2.13x over a data-driven implementation of IPGC on a suite of 10 large graphs on a NVIDIA GPU.
Context Adaptivity as Enabler for Meaningful Pervasive Advertising
Venue: arXiv cs.OH 2019
Year: 2019

Socio-demographic user profiles are currently regarded as the most convenient base for successful personalized advertising. However, signs point to the dormant power of context recognition. While technologies that can sense the environment are increasingly advanced, questions such as what to sense and how to adapt to a consumer's context are largely unanswered. Research in the field is scattered and frequently prototype-driven. What the community lacks is a thorough methodology to provide the basis for any context-adaptive system: conceptualizing context. This position paper describes our current research of conceptualizing context for pervasive advertising. It summarizes findings from literature analysis and proposes a methodology for context conceptualization, which is currently work-in-progress.
Supervised and Unsupervised End-to-End Deep Learning for Gene Ontology Classification of Neural In Situ Hybridization Images
Venue: arXiv cs.CV 2019
Year: 2019

In recent years, large datasets of high-resolution mammalian neural images have become available, which has prompted active research on the analysis of gene expression data. Traditional image processing methods are typically applied for learning functional representations of genes, based on their expressions in these brain images. In this paper, we describe a novel end-to-end deep learning-based method for generating compact representations of in situ hybridization (ISH) images, which are invariant-to-translation. In contrast to traditional image processing methods, our method relies, instead, on deep convolutional denoising autoencoders (CDAE) for processing raw pixel inputs, and generating the desired compact image representations. We provide an in-depth description of our deep learning-based approach, and present extensive experimental results, demonstrating that representations extracted by CDAE can help learn features of functional gene ontology categories for their classification in a highly accurate manner. Our methods improve the previous state-of-the-art classification rate (Liscovitch, et al.) from an average AUC of 0.92 to 0.997, i.e., it achieves 96% reduction in error rate. Furthermore, the representation vectors generated due to our method are more compact in comparison to previous state-of-the-art methods, allowing for a more efficient high-level representation of images. These results are obtained with significantly downsampled images in comparison to the original high-resolution ones, further underscoring the robustness of our proposed method.
Self-Learned Formula Synthesis in Set Theory
Venue: arXiv cs.AI 2019
Year: 2019

A reinforcement learning algorithm accomplishes the task of synthesizing a set-theoretical formula that evaluates to given truth values for given assignments.
Classifying Pattern and Feature Properties to Get a $Θ(n)$ Checker and Reformulation for Sliding Time-Series Constraints
Venue: arXiv cs.FL 2019
Year: 2019

Given, a sequence $\mathcal{X}$ of $n$ variables, a time-series constraint ctr using the Sum aggregator, and a sliding time-series constraint enforcing the constraint ctr on each sliding window of $\mathcal{X}$ of $m$ consecutive variables, we describe a $Θ(n)$ time complexity checker, as well as a $Θ(n)$ space complexity reformulation for such sliding constraint.
Experimental Evidence for Asymptotic Non-Optimality of Comb Adversary Strategy
Venue: arXiv cs.GT 2019
Year: 2019

For the problem of prediction with expert advice in the adversarial setting with finite stopping time, we give strong computer evidence that the comb strategy for $k=5$ experts is not asymptotically optimal, thereby giving strong evidence against a conjecture of Gravin, Peres, and Sivan.
On the connection between Deutsch-Jozsa algorithm and bent functions
Venue: arXiv cs.IT 2019
Year: 2019

It is presently shown that the Deutsch-Jozsa algorithm is connected to the concept of bent function. Particularly, it is noticeable that the quantum circuit used to denote the well known quantum algorithm is by itself the quantum computer which performs the Walsh transform of a Boolean function. Consequently, the output from Deutsch-Jozsa algorithm, when the hidden function is bent, corresponds to a flat spectrum of quantum states.
An Introduction to Communication Efficient Edge Machine Learning
Venue: arXiv cs.IT 2019
Year: 2019

In the near future, Internet-of-Things (IoT) is expected to connect billions of devices (e.g., smartphones and sensors), which generate massive real-time data at the network edge. Intelligence can be distilled from the data to support next-generation AI-powered applications, which is called edge machine learning. One challenge faced by edge learning is the communication bottleneck, which is caused by the transmission of high-dimensional data from many edge devices to edge servers for learning. Traditional wireless techniques focusing only on efficient radio access are ineffective in tackling the challenge. Solutions should be based on a new approach that seamlessly integrates communication and computation. This has led to the emergence of a new cross-disciplinary paradigm called communication efficient edge learning. The main theme in the area is to design new communication techniques and protocols for efficient implementation of different distributed learning frameworks (i.e., federated learning) in wireless networks. This article provides an overview of the emerging area by introducing new design principles, discussing promising research opportunities, and providing design examples based on recent work.
Evaluating Reliability of SSD-Based I/O Caches in Enterprise Storage Systems
Venue: arXiv cs.DC 2019
Year: 2019

In this paper, we present a comprehensive analysis investigating the reliability of SSD-based I/O caching architectures used in enterprise storage systems under power failure and high-operating temperature. We explore variety of SSDs from top vendors and investigate the cache reliability in mirrored configuration. To this end, we first develop a physical fault injection and failure detection platform and then investigate the impact of workload dependent parameters on the reliability of I/O cache in the presence of two common failure types in data centers, power outage and high temperature faults. We implement an I/O cache scheme using an open-source I/O cache module in Linux operating system. The experimental results obtained by conducting more than twenty thousand of physical fault injections on the implemented I/O cache with different write policies reveal that the failure rate of the I/O cache is significantly affected by workload dependent parameters. Our results show that unlike workload requests access pattern, the other workload dependent parameters such as request size, Working Set Size (WSS), and sequence of the accesses have considerable impact on the I/O cache failure rate. We observe a significant growth in the failure rate in the workloads by decreasing the size of the requests (by more than 14X). Furthermore, we observe that in addition to writes, the read accesses to the I/O cache are subjected to failure in presence of sudden power outage (the failure mainly occurs during promoting data to the cache). In addition, we observe that I/O cache experiences no data failure upon high temperature faults.
Drndalo: Lightweight Control Flow Obfuscation Through Minimal Processor/Compiler Co-Design
Venue: arXiv cs.DC 2019
Year: 2019

Binary analysis is traditionally used in the realm of malware detection. However, the same technique may be employed by an attacker to analyze the original binaries in order to reverse engineer them and extract exploitable weaknesses. When a binary is distributed to end users, it becomes a common remotely exploitable attack point. Code obfuscation is used to hinder reverse engineering of executable programs. In this paper, we focus on securing binary distribution, where attackers gain access to binaries distributed to end devices, in order to reverse engineer them and find potential vulnerabilities. Attackers do not however have means to monitor the execution of said devices. In particular, we focus on the control flow obfuscation --- a technique that prevents an attacker from restoring the correct reachability conditions for the basic blocks of a program. By doing so, we thwart attackers in their effort to infer the inputs that cause the program to enter a vulnerable state (e.g., buffer overrun). We propose a compiler extension for obfuscation and a minimal hardware modification for dynamic deobfuscation that takes advantage of a secret key stored in hardware. We evaluate our experiments on the LLVM compiler toolchain and the BRISC-V open source processor. On PARSEC benchmarks, our deobfuscation technique incurs only a 5\% runtime overhead. We evaluate the security of Drndalo by training classifiers on pairs of obfuscated and unobfuscated binaries. Our results shine light on the difficulty of producing obfuscated binaries of arbitrary programs in such a way that they are statistically indistinguishable from plain binaries.
A journey in applying blockchain for cyberphysical systems
Venue: arXiv cs.CR 2019
Year: 2019

Cyberphysical Systems (CPS) are transforming the way we interact with the physical world around us. However, centralised approaches for CPS systems are not capable of addressing the unique challenges of CPS due to the complexity, constraints, and dynamic nature of the interactions. To realize the true potential of CPS, a decentralized approach that takes into account these unique features is required. Recently, blockchain-based solutions have been proposed to address CPS challenges.Yet, applying blockchain for diverse CPS domains is not straight-forward and has its own challenges. In this paper, we share our experiences in applying blockchain technology for CPS to provide insights and highlight the challenges and future opportunities.
SWIPT with Practical Modulation and RF Energy Harvesting Sensitivity
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we investigate the performance of simultaneous wireless information and power transfer (SWIPT) in a point-to-point system, adopting practical $M$-ary modulation. We take into account the fact that the receiver's radio-frequency (RF) energy harvesting circuit can only harvest energy when the received signal power is greater than a certain sensitivity level. For both power-splitting (PS) and time-switching (TS) schemes, we derive the energy harvesting performance as well as the information decoding performance for the Nakagami-$m$ fading channel. We also analyze the performance tradeoff between energy harvesting and information decoding by studying an optimization problem, which maximizes the information decoding performance and satisfies a constraint on the minimum harvested energy. Our analysis shows that (i) for the PS scheme, modulations with high peak-to-average power ratio achieve better energy harvesting performance, (ii) for the TS scheme, it is desirable to concentrate the power for wireless power transfer in order to minimize the non-harvested energy caused by the RF energy harvesting sensitivity level, and (iii) channel fading is beneficial for energy harvesting in both PS and TS schemes.
A Dataset Schema for Cooperative Learning from Demonstration in Multi-robots Systems
Venue: arXiv cs.RO 2019
Year: 2019

Multi-Agent Systems (MASs) have been used to solve complex problems that demand intelligent agents working together to reach the desired goals. These Agents should effectively synchronize their individual behaviors so that they can act as a team in a coordinated manner to achieve the common goal of the whole system. One of the main issues in MASs is the agents' coordination, being common domain experts observing MASs execution disapprove agents' decisions. Even if the MAS was designed using the best methods and tools for agents' coordination, this difference of decisions between experts and MAS is confirmed. Therefore, this paper proposes a new dataset schema to support learning the coordinated behavior in MASs from demonstration. The results of the proposed solution are validated in a Multi-Robot System (MRS) organizing a collection of new cooperative plans recommendations from the demonstration by domain experts.
Deep Physiological State Space Model for Clinical Forecasting
Venue: arXiv cs.LG 2019
Year: 2019

Clinical forecasting based on electronic medical records (EMR) can uncover the temporal correlations between patients' conditions and outcomes from sequences of longitudinal clinical measurements. In this work, we propose an intervention-augmented deep state space generative model to capture the interactions among clinical measurements and interventions by explicitly modeling the dynamics of patients' latent states. Based on this model, we are able to make a joint prediction of the trajectories of future observations and interventions. Empirical evaluations show that our proposed model compares favorably to several state-of-the-art methods on real EMR data.
Faster Lattice Enumeration
Venue: arXiv cs.DS 2019
Year: 2019

A lattice reduction is an algorithm that transforms the given basis of the lattice to another lattice basis such that problems like finding a shortest vector and closest vector become easier to solve. Some of the famous lattice reduction algorithms are LLL and BKZ reductions. We define a class of bases called \emph{obtuse bases} and show that any lattice basis can be transformed to an obtuse basis in $\mathcal{O}(n^4)$ time. A shortest vector s can be written as $v_1b_1+\cdots+v_nb_n$ where $b_1,\dots,b_n$ are the input basis vectors and $v_1,\dots,v_n$ are integers. When the input basis is obtuse, all these integers can be chosen to be positive for a shortest vector. This property of the obtuse basis makes lattice enumeration algorithm for finding a shortest vector exponentially faster. Moreover, extreme pruning, the current fastest algorithm for lattice enumeration, can be run on an obtuse basis.
Knee Cartilage Segmentation Using Diffusion-Weighted MRI
Venue: arXiv cs.CV 2019
Year: 2019

The integrity of articular cartilage is a crucial aspect in the early diagnosis of osteoarthritis (OA). Many novel MRI techniques have the potential to assess compositional changes of the cartilage extracellular matrix. Among these techniques, diffusion tensor imaging (DTI) of cartilage provides a simultaneous assessment of the two principal components of the solid matrix: collagen structure and proteoglycan concentration. DTI, as for any other compositional MRI technique, require a human expert to perform segmentation manually. The manual segmentation is error-prone and time-consuming ($\sim$ few hours per subject). We use an ensemble of modified U-Nets to automate this segmentation task. We benchmark our model against a human expert test-retest segmentation and conclude that our model is superior for Patellar and Tibial cartilage using dice score as the comparison metric. In the end, we do a perturbation analysis to understand the sensitivity of our model to the different components of our input. We also provide confidence maps for the predictions so that radiologists can tweak the model predictions as required. The model has been deployed in practice. In conclusion, cartilage segmentation on DW-MRI images with modified U-Nets achieves accuracy that outperforms the human segmenter. Code is available at https://github.com/aakashrkaku/knee-cartilage-segmentation
Game Description Logic with Integers: A GDL Numerical Extension
Venue: arXiv cs.LO 2019
Year: 2019

Many problems can be viewed as games, where one or more agents try to ensure that certain objectives hold no matter the behavior from the environment and other agents. In recent years, a number of logical formalisms have been proposed for specifying games among which the Game Description Language (GDL) was established as the official language for General Game Playing. Although numbers are recurring in games, the description of games with numerical features in GDL requires the enumeration from all possible numeric values and the relation among them. Thereby, in this paper, we introduce the Game Description Logic with Integers (GDLZ) to describe games with numerical variables, numerical parameters, as well as to perform numerical comparisons. We compare our approach with GDL and show that when describing the same game, GDLZ is more compact.
A Method of Detecting End-To-End Curves of Limited Curvature
Venue: arXiv cs.CV 2019
Year: 2019

In this paper we consider a method for detecting end-to-end curves of limited curvature like the k-link polylines with bending angle between adjacent segments in a given range. The approximation accuracy is achieved by maximization of the quality function in the image matrix. The method is based on a dynamic programming scheme constructed over Fast Hough Transform calculation results for image bands. The proposed method asymptotic complexity is $O(h \cdot (w+ \frac{h}{k}) \cdot log(\frac{h}{k}))$, where $h$ and $w$ are the image size, and $k$ is the approximating polyline links number, which is an analogue of the complexity of the fast Fourier transform or the fast Hough transform. We also show the results of the proposed method on synthetic and real data.
The most frequent programming mistakes that cause software vulnerabilities
Venue: arXiv cs.SE 2019
Year: 2019

All computer programs have flaws, some of which can be exploited to gain unauthorized access to computer systems. We conducted a field study on publicly reported vulnerabilities affecting three open source software projects in widespread use. This paper highlights the main observations and conclusions from the field data collected in the study.