OpenRaiser/Intern-Atlas huggingface dataset:
On the Practicality of Smart Contract PKI
Venue: arXiv cs.DC 2019
Year: 2019

Public key infrastructures (PKIs) are one of the main building blocks for securing communications over the Internet. Currently, PKIs are under the control of centralized authorities, which is problematic as evidenced by numerous incidents where they have been compromised. The distributed, fault tolerant log of transactions provided by blockchains and more recently, smart contract platforms, constitutes a powerful tool for the decentralization of PKIs. To verify the validity of identity records, blockchain-based identity systems store on chain either all identity records, or, a small (or even constant) sized amount of data to verify identity records stored off chain. However, as most of these systems have never been implemented, there is little information regarding the practical implications of each design's tradeoffs. In this work, we first implement and evaluate the only provably secure, smart contract based PKI of [1] on top of Ethereum. This construction incurs constant-sized storage at the expense of computational complexity. To explore this tradeoff, we propose and implement a second construction which, eliminates the need for trusted setup, preserves the security properties of [1] and, as illustrated through our evaluation, is the only version with constant-sized state that can be deployed on the live chain of Ethereum. Furthermore, we compare these two systems with the simple approach of most prior works, e.g., the Ethereum Name Service, where all identity records are stored on the smart contract's state, to illustrate several shortcomings of Ethereum and its cost model. We propose several modifications for fine tuning the model, which would be useful to be considered for any smart contract platform like Ethereum so that it reaches its full potential to support arbitrary distributed applications.
An Alternative Paradigm for Developing and Pricing Storage on Smart Contract Platforms
Venue: arXiv cs.DC 2019
Year: 2019

Smart contract platforms facilitate the development of important and diverse distributed applications in a simple manner. This simplicity stems from the inherent utility of employing the state of smart contracts to store, query and verify the validity of application data. In Ethereum, data storage incurs an underpriced, non-recurring, predefined fee. Furthermore, as there is no incentive for freeing or minimizing the state of smart contracts, Ethereum is faced with a tragedy of the commons problem with regards to its monotonically increasing state. This issue, if left unchecked, may lead to centralization and directly impact Ethereum's security and longevity. In this work, we introduce an alternative paradigm for developing smart contracts in which their state is of constant size and facilitates the verification of application data that are stored to and queried from an external, potentially unreliable, storage network. This approach is relevant for a wide range of applications, such as any key-value store. We evaluate our approach by adapting the most widely deployed standard for fungible tokens, i.e., the ERC20 token standard. We show that Ethereum's current cost model penalizes our approach, even though it minimizes the overhead to Ethereum's state and aligns well with Ethereum's future. We address Ethereum's monotonically increasing state in a two-fold manner. First, we introduce recurring fees that are proportional to the state of smart contracts and adjustable by the miners that maintain the network. Second, we propose a scheme where the cost of storage-related operations reflects the effort that miners have to expend to execute them. Lastly, we show that under such a pricing scheme that encourages economy in the state consumed by smart contracts, our ERC20 token adaptation reduces the incurred transaction fees by up to an order of magnitude.
Discovering Implicational Knowledge in Wikidata
Venue: arXiv cs.AI 2019
Year: 2019

Knowledge graphs have recently become the state-of-the-art tool for representing the diverse and complex knowledge of the world. Examples include the proprietary knowledge graphs of companies such as Google, Facebook, IBM, or Microsoft, but also freely available ones such as YAGO, DBpedia, and Wikidata. A distinguishing feature of Wikidata is that the knowledge is collaboratively edited and curated. While this greatly enhances the scope of Wikidata, it also makes it impossible for a single individual to grasp complex connections between properties or understand the global impact of edits in the graph. We apply Formal Concept Analysis to efficiently identify comprehensible implications that are implicitly present in the data. Although the complex structure of data modelling in Wikidata is not amenable to a direct approach, we overcome this limitation by extracting contextual representations of parts of Wikidata in a systematic fashion. We demonstrate the practical feasibility of our approach through several experiments and show that the results may lead to the discovery of interesting implicational knowledge. Besides providing a method for obtaining large real-world data sets for FCA, we sketch potential applications in offering semantic assistance for editing and curating Wikidata.
MICIK: MIning Cross-Layer Inherent Similarity Knowledge for Deep Model Compression
Venue: arXiv cs.CV 2019
Year: 2019

State-of-the-art deep model compression methods exploit the low-rank approximation and sparsity pruning to remove redundant parameters from a learned hidden layer. However, they process each hidden layer individually while neglecting the common components across layers, and thus are not able to fully exploit the potential redundancy space for compression. To solve the above problem and enable further compression of a model, removing the cross-layer redundancy and mining the layer-wise inheritance knowledge is necessary. In this paper, we introduce a holistic model compression framework, namely MIning Cross-layer Inherent similarity Knowledge (MICIK), to fully excavate the potential redundancy space. The proposed MICIK framework simultaneously, (1) learns the common and unique weight components across deep neural network layers to increase compression rate; (2) preserves the inherent similarity knowledge of nearby layers and distant layers to minimize the accuracy loss and (3) can be complementary to other existing compression techniques such as knowledge distillation. Extensive experiments on large-scale convolutional neural networks demonstrate that MICIK is superior over state-of-the-art model compression approaches with 16X parameter reduction on VGG-16 and 6X on GoogLeNet, all without accuracy loss.
Bayesian semi-supervised learning for uncertainty-calibrated prediction of molecular properties and active learning
Venue: arXiv cs.LG 2019
Year: 2019

Predicting bioactivity and physical properties of small molecules is a central challenge in drug discovery. Deep learning is becoming the method of choice but studies to date focus on mean accuracy as the main metric. However, to replace costly and mission-critical experiments by models, a high mean accuracy is not enough: Outliers can derail a discovery campaign, thus models need reliably predict when it will fail, even when the training data is biased; experiments are expensive, thus models need to be data-efficient and suggest informative training sets using active learning. We show that uncertainty quantification and active learning can be achieved by Bayesian semi-supervised graph convolutional neural networks. The Bayesian approach estimates uncertainty in a statistically principled way through sampling from the posterior distribution. Semi-supervised learning disentangles representation learning and regression, keeping uncertainty estimates accurate in the low data limit and allowing the model to start active learning from a small initial pool of training data. Our study highlights the promise of Bayesian deep learning for chemistry.
Some Remarks on Real-Time Turing Machines
Venue: arXiv cs.CC 2019
Year: 2019

The power of real-time Turing machines using sublinear space is investigated. In contrast to a claim appearing in the literature, such machines can accept non-regular languages, even if working in deterministic mode. While maintaining a standard binary counter appears to be impossible in real-time, we present a guess and check approach that yields a binary representation of the input length. Based on this technique, we show that unary encodings of languages accepted in exponential time can be recognized by nondeterministic real-time Turing machines.
Risk-Limiting Bayesian Polling Audits for Two Candidate Elections
Venue: arXiv cs.CR 2019
Year: 2019

We propose a simple common framework for Risk-Limiting and Bayesian (polling) audits for two-candidate plurality elections. Using it, we derive an expression for the general Bayesian audit; in particular, we do not restrict the prior to a beta distribution. We observe that the decision rule for the Bayesian audit is a simple comparison test, which enables the use of pre-computation---without simulations---and greatly increases the computational efficiency of the audit. Our main contribution is a general form for an audit that is both Bayesian and risk-limiting: the {\em Bayesian Risk-Limiting Audit}, which enables the use of a Bayesian approach to explore more efficient Risk-Limiting Audits.
3D point cloud registration with shape constraint
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, a shape-constrained iterative algorithm is proposed to register a rigid template point-cloud to a given reference point-cloud. The algorithm embeds a shape-based similarity constraint into the principle of gravitation. The shape-constrained gravitation, as induced by the reference, controls the movement of the template such that at each iteration, the template better aligns with the reference in terms of shape. This constraint enables the alignment in difficult conditions indtroduced by change (presence of outliers and/or missing parts), translation, rotation and scaling. We discuss efficient implementation techniques with least manual intervention. The registration is shown to be useful for change detection in the 3D point-cloud. The algorithm is compared with three state-of-the-art registration approaches. The experiments are done on both synthetic and real-world data. The proposed algorithm is shown to perform better in the presence of big rotation, structured and unstructured outliers and missing data.
2-D Embedding of Large and High-dimensional Data with Minimal Memory and Computational Time Requirements
Venue: arXiv cs.LG 2019
Year: 2019

In the advent of big data era, interactive visualization of large data sets consisting of M*10^5+ high-dimensional feature vectors of length N (N ~ 10^3+), is an indispensable tool for data exploratory analysis. The state-of-the-art data embedding (DE) methods of N-D data into 2-D (3-D) visually perceptible space (e.g., based on t-SNE concept) are too demanding computationally to be efficiently employed for interactive data analytics of large and high-dimensional datasets. Herein we present a simple method, ivhd (interactive visualization of high-dimensional data tool), which radically outperforms the modern data-embedding algorithms in both computational and memory loads, while retaining high quality of N-D data embedding in 2-D (3-D). We show that DE problem is equivalent to the nearest neighbor nn-graph visualization, where only indices of a few nearest neighbors of each data sample has to be known, and binary distance between data samples -- 0 to the nearest and 1 to the other samples -- is defined. These improvements reduce the time-complexity and memory load from O(M log M) to O(M), and ensure minimal O(M) proportionality coefficient as well. We demonstrate high efficiency, quality and robustness of ivhd on popular benchmark datasets such as MNIST, 20NG, NORB and RCV1.
Active Automata Learning with Adaptive Distinguishing Sequences
Venue: arXiv cs.LG 2019
Year: 2019

This document investigates the integration of adaptive distinguishing sequences into the process of active automata learning (AAL). A novel AAL algorithm "ADT" (adaptive discrimination tree) is developed and presented. Since the submission of the original thesis, the presented algorithm has been integrated into LearnLib - an open-source library for active automata learning - and has been successfully used in related fields of research.
Performance Analysis of Joint Radar and Communication using OFDM and OTFS
Venue: arXiv cs.IT 2019
Year: 2019

We consider a joint radar estimation and communication system using orthogonal frequency division multiplexing (OFDM) and orthogonal time frequency space (OTFS) modulations. The scenario is motivated by vehicular applications where a vehicle equipped with a mono-static radar wishes to communicate data to its target receiver, while estimating parameters of interest related to this receiver. By focusing on the case of a single target, we derive the maximum likelihood (ML) estimator and the Cramér-Rao lower bound on joint velocity and range estimation. Numerical examples demonstrate that both digital modulation formats can achieve as accurate range/velocity estimation as state-of-the-art radar waveforms such as frequency modulated continuous wave (FMCW) while sending digital information at their full achievable rate. We conclude that it is possible to obtain significant data transmission rate without compromising the radar estimation capabilities of the system.
Model-Based Detector for SSDs in the Presence of Inter-cell Interference
Venue: arXiv cs.IT 2019
Year: 2019

In this paper, we consider the problem of reducing the bit error rate of flash-based solid state drives (SSDs) when cells are subject to inter-cell interference (ICI). By observing that the outputs of adjacent victim cells can be correlated due to common aggressors, we propose a novel channel model to accurately represent the true flash channel. This model, equivalent to a finite-state Markov channel model, allows the use of the sum-product algorithm to calculate more accurate posterior distributions of individual cell inputs given the joint outputs of victim cells. These posteriors can be easily mapped to the log-likelihood ratios that are passed as inputs to the soft LDPC decoder. When the output is available with high precision, our simulation showed that a significant reduction in the bit-error rate can be obtained, reaching $99.99\%$ reduction compared to current methods, when the diagonal coupling is very strong. In the realistic case of low-precision output, our scheme provides less impressive improvements due to information loss in the process of quantization. To improve the performance of the new detector in the quantized case, we propose a new iterative scheme that alternates multiple times between the detector and the decoder. Our simulations showed that the iterative scheme can significantly improve the bit error rate even in the quantized case.
Distances between Data Sets Based on Summary Statistics
Venue: arXiv cs.DS 2019
Year: 2019

The concepts of similarity and distance are crucial in data mining. We consider the problem of defining the distance between two data sets by comparing summary statistics computed from the data sets. The initial definition of our distance is based on geometrical notions of certain sets of distributions. We show that this distance can be computed in cubic time and that it has several intuitive properties. We also show that this distance is the unique Mahalanobis distance satisfying certain assumptions. We also demonstrate that if we are dealing with binary data sets, then the distance can be represented naturally by certain parity functions, and that it can be evaluated in linear time. Our empirical tests with real world data show that the distance works well.
Insertion-based Decoding with automatically Inferred Generation Order
Venue: arXiv cs.CL 2019
Year: 2019

Conventional neural autoregressive decoding commonly assumes a fixed left-to-right generation order, which may be sub-optimal. In this work, we propose a novel decoding algorithm -- InDIGO -- which supports flexible sequence generation in arbitrary orders through insertion operations. We extend Transformer, a state-of-the-art sequence generation model, to efficiently implement the proposed approach, enabling it to be trained with either a pre-defined generation order or adaptive orders obtained from beam-search. Experiments on four real-world tasks, including word order recovery, machine translation, image caption and code generation, demonstrate that our algorithm can generate sequences following arbitrary orders, while achieving competitive or even better performance compared to the conventional left-to-right generation. The generated sequences show that InDIGO adopts adaptive generation orders based on input information.
End-to-End Single Image Fog Removal using Enhanced Cycle Consistent Adversarial Networks
Venue: arXiv cs.CV 2019
Year: 2019

Single image defogging is a classical and challenging problem in computer vision. Existing methods towards this problem mainly include handcrafted priors based methods that rely on the use of the atmospheric degradation model and learning based approaches that require paired fog-fogfree training example images. In practice, however, prior-based methods are prone to failure due to their own limitations and paired training data are extremely difficult to acquire. Inspired by the principle of CycleGAN network, we have developed an end-to-end learning system that uses unpaired fog and fogfree training images, adversarial discriminators and cycle consistency losses to automatically construct a fog removal system. Similar to CycleGAN, our system has two transformation paths; one maps fog images to a fogfree image domain and the other maps fogfree images to a fog image domain. Instead of one stage mapping, our system uses a two stage mapping strategy in each transformation path to enhance the effectiveness of fog removal. Furthermore, we make explicit use of prior knowledge in the networks by embedding the atmospheric degradation principle and a sky prior for mapping fogfree images to the fog images domain. In addition, we also contribute the first real world nature fog-fogfree image dataset for defogging research. Our multiple real fog images dataset (MRFID) contains images of 200 natural outdoor scenes. For each scene, there are one clear image and corresponding four foggy images of different fog densities manually selected from a sequence of images taken by a fixed camera over the course of one year. Qualitative and quantitative comparison against several state-of-the-art methods on both synthetic and real world images demonstrate that our approach is effective and performs favorably for recovering a clear image from a foggy image.
T-PFC: A Trajectory-Optimized Perturbation Feedback Control Approach
Venue: arXiv cs.SY 2019
Year: 2019

Traditional stochastic optimal control methods that attempt to obtain an optimal feedback policy for nonlinear systems are computationally intractable. In this paper, we derive a decoupling principle between the open loop plan, and the closed loop feedback gains, that leads to a perturbation feedback control based solution to optimal control problems under action uncertainty, that is near-optimal to the third order. Extensive numerical simulations validate the theory, revealing a wide range of applicability, coping with medium levels of noise. The performance is compared with Nonlinear Model Predictive Control in several difficult robotic planning and control examples that show near identical performance to NMPC while requiring much lesser computational effort. It also leads us to raise the bigger question as to why NMPC should be used in robotic control as opposed to perturbation feedback approaches.
Partial Fingerprint Detection Using Core Point Location
Venue: arXiv cs.CV 2019
Year: 2019

In Biometric identification, fingerprints based identification has been the widely accepted mechanism. Automated fingerprints identification/verification techniques are widely adopted in many civilian and forensic applications. In forensic applications fingerprints are usually incomplete, broken, unclear or degraded which are known as partial fingerprints. Fingerprints identification/verification largely suffer from the problem of handling partial fingerprints. In this paper a novel and simple approach is presented for detecting partial fingerprints using core point location. Our techniques is particularly useful during the acquisition stage as to determine whether a user needs to re-align the finger to ensure a complete capture of fingerprint area.This technique is tested on FVC-2002 DB1A. The results are very accurate which are presented in the Results sections.
COME TOGETHER: Multi-Agent Geometric Consensus (Gathering, Rendezvous, Clustering, Aggregation)
Venue: arXiv cs.MA 2019
Year: 2019

This report surveys results on distributed systems comprising mobile agents that are identical and anonymous, oblivious and interact solely by adjusting their motion according to the relative location of their neighbours. The agents are assumed capable of sensing the presence of other agents within a given sensing range and able to implement rules of motion based on full or partial information on the geometric constellation of their neighbouring agents. Eight different problems that cover assumptions of finite vs infinite sensing range, direction and distance vs direction only sensing and discrete vs continuous motion, are analyzed in the context of geometric consensus, clustering or gathering tasks.
(Near) Optimal Adaptivity Gaps for Stochastic Multi-Value Probing
Venue: arXiv cs.DS 2019
Year: 2019

Consider a kidney-exchange application where we want to find a max-matching in a random graph. To find whether an edge $e$ exists, we need to perform an expensive test, in which case the edge $e$ appears independently with a \emph{known} probability $p_e$. Given a budget on the total cost of the tests, our goal is to find a testing strategy that maximizes the expected maximum matching size. The above application is an example of the stochastic probing problem. In general the optimal stochastic probing strategy is difficult to find because it is \emph{adaptive}---decides on the next edge to probe based on the outcomes of the probed edges. An alternate approach is to show the \emph{adaptivity gap} is small, i.e., the best \emph{non-adaptive} strategy always has a value close to the best adaptive strategy. This allows us to focus on designing non-adaptive strategies that are much simpler. Previous works, however, have focused on Bernoulli random variables that can only capture whether an edge appears or not. In this work we introduce a multi-value stochastic probing problem, which can also model situations where the weight of an edge has a probability distribution over multiple values. Our main technical contribution is to obtain (near) optimal bounds for the (worst-case) adaptivity gaps for multi-value stochastic probing over prefix-closed constraints. For a monotone submodular function, we show the adaptivity gap is at most $2$ and provide a matching lower bound. For a weighted rank function of a $k$-extendible system (a generalization of intersection of $k$ matroids), we show the adaptivity gap is between $O(k\log k)$ and $k$. None of these results were known even in the Bernoulli case where both our upper and lower bounds also apply, thereby resolving an open question of Gupta et al.