OpenRaiser/Intern-Atlas huggingface dataset:
Uniform CSP Parameterized by Solution Size is in W[1]
Venue: arXiv cs.CC 2019
Year: 2019

We show that the uniform Constraint Satisfaction Problem (CSP) parameterized by the size of the solution is in W[1] (the problem is W[1]-hard and it is easy to place it in W[3]). Given a single "free" element of the domain, denoted by $0$, we define the size of an assignment as the number of variables that are mapped to a value other than $0$. Named by Kolaitis and Vardi (2000), uniform CSP means that the input contains the domain and the list of tuples of each relation in the instance. Uniform CSP is polynomial time equivalent to homomorphism problem and also to evaluation of conjunctive queries on relational databases. It also has applications in artificial intelligence. We do not restrict the problem to any (finite or infinite) family of relations. Marx and Bulatov (2014) showed that Uniform CSP restricted to some finite family of relations (thus with a bound on the arity of relations) and over any finite domain is either W[1]-complete or fixed parameter tractable. We then prove that parameterized Subset Sum with weights bounded by $n^k$ is in W[1]. Abboud et al. (2014) have already proved it, but our proof is much shorter and arguably more intuitive. Lastly, we study the weighted CSP over the Boolean Domain, where each variable is assigned a weight, and given a target value, it should be decided if there is a satisfying assignment of size $k$ (the parameter) such that the weight of its $1$-variables adds up to the target value. We prove that if the weights are bounded by $n^k$, then the problem is in W[1]. Our proofs give a nondeterministic RAM program with special properties deciding the problem. First defined by Chen et al. (2005), such programs characterize W[1].
Towards Lattice Quantum Chromodynamics on FPGA devices
Venue: arXiv cs.DC 2019
Year: 2019

In this paper we describe a single-node, double precision Field Programmable Gate Array (FPGA) implementation of the Conjugate Gradient algorithm in the context of Lattice Quantum Chromodynamics. As a benchmark of our proposal we invert numerically the Dirac-Wilson operator on a 4-dimensional grid on three Xilinx hardware solutions: Zynq Ultrascale+ evaluation board, the Alveo U250 accelerator and the largest device available on the market, the VU13P device. In our implementation we separate software/hardware parts in such a way that the entire multiplication by the Dirac operator is performed in hardware, and the rest of the algorithm runs on the host. We find out that the FPGA implementation can offer a performance comparable with that obtained using current CPU or Intel's many core Xeon Phi accelerators. A possible multiple node FPGA-based system is discussed and we argue that power-efficient High Performance Computing (HPC) systems can be implemented using FPGA devices only.
Assignment Mechanisms under Distributional Constraints
Venue: arXiv cs.DS 2019
Year: 2019

We study the assignment problem of objects to agents with heterogeneous preferences under distributional constraints. Each agent is associated with a publicly known type and has a private ordinal ranking over objects. We are interested in assigning as many agents as possible. Our first contribution is a generalization of the well-known and widely used serial dictatorship. Our mechanism maintains several desirable properties of serial dictatorship, including strategyproofness, Pareto efficiency, and computational tractability while satisfying the distributional constraints with a small error. We also propose a generalization of the probabilistic serial algorithm, which finds an ordinally efficient and envy-free assignment, and also satisfies the distributional constraints with a small error. We show, however, that no ordinally efficient and envy-free mechanism is also weakly strategyproof. Both of our algorithms assign at least the same number of students as the optimum fractional assignment.
Can Determinacy Minimize Age of Information?
Venue: arXiv cs.NI 2019
Year: 2019

Age-of-information (AoI) is a newly proposed performance metric of information freshness. It differs from the traditional delay metric, because it is destination centric and measures the time that elapsed since the last received fresh information update was generated at the source. AoI has been analyzed for several queueing models, and the problem of optimizing AoI over arrival and service rates has been studied in the literature. We consider the problem of minimizing AoI over the space of update generation and service time distributions. In particular, we ask whether determinacy, i.e. periodic generation of update packets and/or deterministic service, optimizes AoI. By considering several queueing systems, we show that in certain settings, deterministic service can in fact result in the worst case AoI, while a heavy-tailed distributed service can yield the minimum AoI. This leads to an interesting conclusion that, in some queueing systems, the service time distribution that minimizes expected packet delay, or variance in packet delay can, in fact, result in the worst case AoI. This exposes a fundamental difference between AoI metrics and packet delay.
Learning to Communicate Implicitly By Actions
Venue: arXiv cs.AI 2019
Year: 2019

In situations where explicit communication is limited, human collaborators act by learning to: (i) infer meaning behind their partner's actions, and (ii) convey private information about the state to their partner implicitly through actions. The first component of this learning process has been well-studied in multi-agent systems, whereas the second --- which is equally crucial for successful collaboration --- has not. To mimic both components mentioned above, thereby completing the learning process, we introduce a novel algorithm: Policy Belief Learning (PBL). PBL uses a belief module to model the other agent's private information and a policy module to form a distribution over actions informed by the belief module. Furthermore, to encourage communication by actions, we propose a novel auxiliary reward which incentivizes one agent to help its partner to make correct inferences about its private information. The auxiliary reward for communication is integrated into the learning of the policy module. We evaluate our approach on a set of environments including a matrix game, particle environment and the non-competitive bidding problem from contract bridge. We show empirically that this auxiliary reward is effective and easy to generalize. These results demonstrate that our PBL algorithm can produce strong pairs of agents in collaborative games where explicit communication is disabled.
A Deep Learning Approach to the Inversion of Borehole Resistivity Measurements
Venue: arXiv cs.LG 2019
Year: 2019

We use borehole resistivity measurements to map the electrical properties of the subsurface and to increase the productivity of a reservoir. When used for geosteering purposes, it becomes essential to invert them in real time. In this work, we explore the possibility of using Deep Neural Network (DNN) to perform a rapid inversion of borehole resistivity measurements. Herein, we build a DNN that approximates the following inverse problem: given a set of borehole resistivity measurements, the DNN is designed to deliver a physically meaningful and data-consistent piecewise one-dimensional layered model of the surrounding subsurface. Once the DNN is built, we can perform the actual inversion of the field measurements in real time. We illustrate the performance of DNN of logging-while-drilling measurements acquired on high-angle wells via synthetic data.
Blockchain access control Ecosystem for Big Data security
Venue: arXiv cs.CR 2019
Year: 2019

In recent years, the advancement in modern technologies has experienced an explosion of huge data sets being captured and recorded in different fields, but also given rise to concerns the security and protection of data storage, transmission, processing, and access to data. The blockchain is a distributed ledger that records transactions in a secure, flexible, verifiable and permanent way. Transactions in a blockchain can be an exchange of an asset, the execution of the terms of a smart contract, or an update to a record. In this paper, we have developed a blockchain access control ecosystem that gives asset owners the sovereign right to effectively manage access control of large data sets and protect against data breaches. The Linux Foundation's Hyperledger Fabric blockchain is used to run the business network while the Hyperledger composer tool is used to implement the smart contracts or transaction processing functions that run on the blockchain network.
A van Benthem Theorem for Quantitative Probabilistic Modal Logic
Venue: arXiv cs.LO 2019
Year: 2019

In probabilistic transition systems, behavioural metrics provide a more fine-grained and stable measure of system equivalence than crisp notions of bisimilarity. They correlate strongly to quantitative probabilistic logics, and in fact the distance induced by a probabilistic modal logic taking values in the real unit interval has been shown to coincide with behavioural distance. For probabilistic systems, probabilistic modal logic thus plays an analogous role to that of Hennessy-Milner logic on classical labelled transition systems. In the quantitative setting, invariance of modal logic under bisimilarity becomes non-expansivity of formula evaluation w.r.t. behavioural distance. In the present paper, we provide a characterization of the expressive power of probabilistic modal logic based on this observation: We prove a probabilistic analogue of the classical van Benthem theorem, which states that modal logic is precisely the bisimulation-invariant fragment of first-order logic. Specifically, we show that quantitative probabilistic modal logic lies dense in the bisimulation-invariant fragment, in the indicated sense of non-expansive formula evaluation, of quantitative probabilistic first-order logic; more precisely, bisimulation-invariant first-order formulas are approximable by modal formulas of bounded rank. For a description logic perspective on the same result, see arXiv:1906.00784.
Applications of Graph Integration to Function Comparison and Malware Classification
Venue: arXiv cs.AI 2019
Year: 2019

We classify .NET files as either benign or malicious by examining directed graphs derived from the set of functions comprising the given file. Each graph is viewed probabilistically as a Markov chain where each node represents a code block of the corresponding function, and by computing the PageRank vector (Perron vector with transport), a probability measure can be defined over the nodes of the given graph. Each graph is vectorized by computing Lebesgue antiderivatives of hand-engineered functions defined on the vertex set of the given graph against the PageRank measure. Files are subsequently vectorized by aggregating the set of vectors corresponding to the set of graphs resulting from decompiling the given file. The result is a fast, intuitive, and easy-to-compute glass-box vectorization scheme, which can be leveraged for training a standalone classifier or to augment an existing feature space. We refer to this vectorization technique as PageRank Measure Integration Vectorization (PMIV). We demonstrate the efficacy of PMIV by training a vanilla random forest on 2.5 million samples of decompiled .NET, evenly split between benign and malicious, from our in-house corpus and compare this model to a baseline model which leverages a text-only feature space. The median time needed for decompilation and scoring was 24ms.
Model-Based Safety and Security Engineering
Venue: arXiv cs.LO 2019
Year: 2019

By exploiting the increasing surface attack of systems, cyber-attacks can cause catastrophic events, such as, remotely disable safety mechanisms. This means that in order to avoid hazards, safety and security need to be integrated, exchanging information, such as, key hazards/threats, risk evaluations, mechanisms used. This white paper describes some steps towards this integration by using models. We start by identifying some key technical challenges. Then we demonstrate how models, such as Goal Structured Notation (GSN) for safety and Attack Defense Trees (ADT) for security, can address these challenges. In particular, (1) we demonstrate how to extract in an automated fashion security relevant information from safety assessments by translating GSN-Models into ADTs; (2) We show how security results can impact the confidence of safety assessments; (3) We propose a collaborative development process where safety and security assessments are built by incrementally taking into account safety and security analysis; (4) We describe how to carry out trade-off analysis in an automated fashion, such as identifying when safety and security arguments contradict each other and how to solve such contradictions. We conclude pointing out that these are the first steps towards a wide range of techniques to support Safety and Security Engineering. As a white paper, we avoid being too technical, preferring to illustrate features by using examples and thus being more accessible.
Linear $\ell$-Intersection Pairs of Codes and Their Applications
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, a linear $\ell$-intersection pair of codes is introduced as a generalization of linear complementary pairs of codes. Two linear codes are said to be a linear $\ell$-intersection pair if their intersection has dimension $\ell$. Characterizations and constructions of such pairs of codes are given in terms of the corresponding generator and parity-check matrices. Linear $\ell$-intersection pairs of MDS codes over $\mathbb{F}_q$ of length up to $q+1$ are given for all possible parameters. As an application, linear $\ell$-intersection pairs of codes are used to construct entanglement-assisted quantum error correcting codes. This provides a large number of new MDS entanglement-assisted quantum error correcting codes.
Neural Variational Hybrid Collaborative Filtering
Venue: arXiv cs.IR 2019
Year: 2019

Collaborative Filtering (CF) is one of the most used methods for Recommender System. Because of the Bayesian nature and nonlinearity, deep generative models, e.g. Variational Autoencoder (VAE), have been applied into CF task, and have achieved great performance. However, most VAE-based methods suffer from matrix sparsity and consider the prior of users' latent factors to be the same, which leads to poor latent representations of users and items. Additionally, most existing methods model latent factors of users only and but not items, which makes them not be able to recommend items to a new user. To tackle these problems, we propose a Neural Variational Hybrid Collaborative Filtering, NVHCF. Specifically, we consider both the generative processes of users and items, and the prior of latent factors of users and items to be side informationspecific, which enables our model to alleviate matrix sparsity and learn better latent representations of users and items. For inference purpose, we derived a Stochastic Gradient Variational Bayes (SGVB) algorithm to analytically approximate the intractable distributions of latent factors of users and items. Experiments conducted on two large datasets have showed our methods significantly outperform the state-of-the-art CF methods, including the VAE-based methods.
On the Existence and Uniqueness of Poincaré Maps for Systems with Impulse Effects
Venue: arXiv cs.SY 2019
Year: 2019

The Poincaré map is widely used to study the qualitative behavior of dynamical systems. For instance, it can be used to describe the existence of periodic solutions. The Poincaré map for dynamical systems with impulse effects was introduced in the last decade and mainly employed to study the existence of limit cycles (periodic gaits) for the locomotion of bipedal robots. We investigate sufficient conditions for the existence and uniqueness of Poincaré maps for dynamical systems with impulse effects evolving on a differentiable manifold. We apply the results to show the existence and uniqueness of Poincaré maps for systems with multiple domains.
Low-Complexity Detection of M-ary PSK Faster-than-Nyquist Signaling
Venue: arXiv cs.IT 2019
Year: 2019

Faster-than-Nyquist (FTN) signaling is a promising non-orthogonal physical layer transmission technique to improve the spectral efficiency of future communication systems but at the expense of intersymbol-interference (ISI). In this paper, we investigate the detection problem of FTN signaling and formulate the sequence estimation problem of any $M$-ary phase shift keying (PSK) FTN signaling as an optimization problem that turns out to be non-convex and nondeterministic polynomial time (NP)-hard to solve. We propose a novel algorithm, based on concepts from semidefinite relaxation (SDR) and Gaussian randomization, to detect any $M$-ary PSK FTN signaling in polynomial time complexity regardless of the constellation size $M$ or the ISI length. Simulation results show that the proposed algorithm strikes a balance between the achieved performance and the computational complexity. Additionally, results show the merits of the proposed algorithm in improving the spectral efficiency when compared to Nyquist signaling and the state-of-the-art schemes from the literature. In particular, when compared to Nyquist signaling at the same error rate and signal-to-noise ratio, our scheme provides around $17\%$ increase in the spectral efficiency at a roll-off factor of 0.3.
Compact NUMA-Aware Locks
Venue: arXiv cs.OS 2019
Year: 2019

Modern multi-socket architectures exhibit non-uniform memory access (NUMA) behavior, where access by a core to data cached locally on a socket is much faster than access to data cached on a remote socket. Prior work offers several efficient NUMA-aware locks that exploit this behavior by keeping the lock ownership on the same socket, thus reducing remote cache misses and inter-socket communication. Virtually all those locks, however, are hierarchical in their nature, thus requiring space proportional to the number of sockets. The increased memory cost renders NUMA-aware locks unsuitable for systems that are conscious to space requirements of their synchronization constructs, with the Linux kernel being the chief example. In this work, we present a compact NUMA-aware lock that requires only one word of memory, regardless of the number of sockets in the underlying machine. The new lock is a variant of an efficient (NUMA-oblivious) MCS lock, and inherits its performant features, such as local spinning and a single atomic instruction in the acquisition path. Unlike MCS, the new lock organizes waiting threads in two queues, one composed of threads running on the same socket as the current lock holder, and another composed of threads running on a different socket(s). We integrated the new lock in the Linux kernel's qspinlock, one of the major synchronization constructs in the kernel. Our evaluation using both user-space and kernel benchmarks shows that the new lock has a single-thread performance of MCS, but significantly outperforms the latter under contention, achieving a similar level of performance when compared to other, state-of-the-art NUMA-aware locks that require substantially more space.
Linear Program Reconstruction in Practice
Venue: arXiv cs.CR 2019
Year: 2019

We briefly report on a successful linear program reconstruction attack performed on a production statistical queries system and using a real dataset. The attack was deployed in test environment in the course of the Aircloak Challenge bug bounty program and is based on the reconstruction algorithm of Dwork, McSherry, and Talwar. We empirically evaluate the effectiveness of the algorithm and a related algorithm by Dinur and Nissim with various dataset sizes, error rates, and numbers of queries in a Gaussian noise setting.
DeepWeeds: A Multiclass Weed Species Image Dataset for Deep Learning
Venue: arXiv cs.CV 2019
Year: 2019

Robotic weed control has seen increased research of late with its potential for boosting productivity in agriculture. Majority of works focus on developing robotics for croplands, ignoring the weed management problems facing rangeland stock farmers. Perhaps the greatest obstacle to widespread uptake of robotic weed control is the robust classification of weed species in their natural environment. The unparalleled successes of deep learning make it an ideal candidate for recognising various weed species in the complex rangeland environment. This work contributes the first large, public, multiclass image dataset of weed species from the Australian rangelands; allowing for the development of robust classification methods to make robotic weed control viable. The DeepWeeds dataset consists of 17,509 labelled images of eight nationally significant weed species native to eight locations across northern Australia. This paper presents a baseline for classification performance on the dataset using the benchmark deep learning models, Inception-v3 and ResNet-50. These models achieved an average classification accuracy of 95.1% and 95.7%, respectively. We also demonstrate real time performance of the ResNet-50 architecture, with an average inference time of 53.4 ms per image. These strong results bode well for future field implementation of robotic weed control methods in the Australian rangelands.
Embedded deep learning in ophthalmology: Making ophthalmic imaging smarter
Venue: arXiv cs.CV 2019
Year: 2019

Deep learning has recently gained high interest in ophthalmology, due to its ability to detect clinically significant features for diagnosis and prognosis. Despite these significant advances, little is known about the ability of various deep learning systems to be embedded within ophthalmic imaging devices, allowing automated image acquisition. In this work, we will review the existing and future directions for "active acquisition" embedded deep learning, leading to as high quality images with little intervention by the human operator. In clinical practice, the improved image quality should translate into more robust deep learning-based clinical diagnostics. Embedded deep learning will be enabled by the constantly improving hardware performance with low cost. We will briefly review possible computation methods in larger clinical systems. Briefly, they can be included in a three-layer framework composed of edge, fog and cloud layers, the former being performed at a device-level. Improved edge layer performance via "active acquisition" serves as an automatic data curation operator translating to better quality data in electronic health records (EHRs), as well as on the cloud layer, for improved deep learning-based clinical data mining.
Deep Learning-Based Channel Estimation
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we present a deep learning (DL) algorithm for channel estimation in communication systems. We consider the time-frequency response of a fast fading communication channel as a two-dimensional image. The aim is to find the unknown values of the channel response using some known values at the pilot locations. To this end, a general pipeline using deep image processing techniques, image super-resolution (SR) and image restoration (IR) is proposed. This scheme considers the pilot values, altogether, as a low-resolution image and uses an SR network cascaded with a denoising IR network to estimate the channel. Moreover, an implementation of the proposed pipeline is presented. The estimation error shows that the presented algorithm is comparable to the minimum mean square error (MMSE) with full knowledge of the channel statistics and it is better than ALMMSE (an approximation to linear MMSE). The results confirm that this pipeline can be used efficiently in channel estimation.