OpenRaiser/Intern-Atlas huggingface dataset:
Evaluation of the Intel Xeon Phi 7120 and NVIDIA K80 as accelerators for two-dimensional panel codes
Venue: arXiv cs.DC 2018
Year: 2018

To optimize the geometry of airfoils for a specific application is an important engineering problem. In this context genetic algorithms have enjoyed some success as they are able to explore the search space without getting stuck in local optima. However, these algorithms require the computation of aerodynamic properties for a significant number of airfoil geometries. Consequently, for low-speed aerodynamics, panel methods are most often used as the inner solver. In this paper we evaluate the performance of such an optimization algorithm on modern accelerators (more specifically, the Intel Xeon Phi 7120 and the NVIDIA K80). For that purpose, we have implemented an optimized version of the algorithm on the CPU and Xeon Phi (based on OpenMP, vectorization, and the Intel MKL library) and on the GPU (based on CUDA and the MAGMA library). We present timing results for all codes and discuss the similarities and differences between the three implementations. Overall, we observe a speedup of approximately $2.5$ for adding an Intel Xeon Phi 7120 to a dual socket workstation and a speedup between $3.4$ and $3.8$ for adding a NVIDIA K80 to a dual socket workstation.
On the Combinatorial Version of the Slepian-Wolf Problem
Venue: arXiv cs.IT 2018
Year: 2018

We study the following combinatorial version of the Slepian-Wolf coding scheme. Two isolated Senders are given binary strings $X$ and $Y$ respectively; the length of each string is equal to $n$, and the Hamming distance between the strings is at most $αn$. The Senders compress their strings and communicate the results to the Receiver. Then the Receiver must reconstruct both strings $X$ and $Y$. The aim is to minimise the lengths of the transmitted messages. For an asymmetric variant of this problem (where one of the Senders transmits the input string to the Receiver without compression) with deterministic encoding a nontrivial lower bound was found by A.Orlitsky and K.Viswanathany. In our paper we prove a new lower bound for the schemes with syndrome coding, where at least one of the Senders uses linear encoding of the input string. For the combinatorial Slepian-Wolf problem with randomized encoding the theoretical optimum of communication complexity was recently found by the first author, though effective protocols with optimal lengths of messages remained unknown. We close this gap and present a polynomial time randomized protocol that achieves the optimal communication complexity.
Hardness of RNA Folding Problem with Four Symbols
Venue: arXiv cs.CC 2018
Year: 2018

An RNA sequence is a string composed of four types of nucleotides, $A, C, G$, and $U$. The goal of the RNA folding problem is to find a maximum cardinality set of crossing-free pairs of the form $\{A,U\}$ or $\{C,G\}$ in a given RNA sequence. The problem is central in bioinformatics and has received much attention over the years. Abboud, Backurs, and Williams (FOCS 2015) demonstrated a conditional lower bound for a generalized version of the RNA folding problem based on a conjectured hardness of the $k$-clique problem. Their lower bound requires the RNA sequence to have at least 36 types of symbols, making the result not applicable to the RNA folding problem in real life (i.e., alphabet size 4). In this paper, we present an improved lower bound that works for the alphabet size 4 case. We also investigate the Dyck edit distance problem, which is a string problem closely related to RNA folding. We demonstrate a reduction from RNA folding to Dyck edit distance with alphabet size 10. This leads to a much simpler proof of the conditional lower bound for Dyck edit distance problem given by Abboud, Backurs, and Williams (FOCS 2015), and lowers the alphabet size requirement.
Iterative Refinement of the Approximate Posterior for Directed Belief Networks
Venue: arXiv cs.LG 2018
Year: 2018

Variational methods that rely on a recognition network to approximate the posterior of directed graphical models offer better inference and learning than previous methods. Recent advances that exploit the capacity and flexibility in this approach have expanded what kinds of models can be trained. However, as a proposal for the posterior, the capacity of the recognition network is limited, which can constrain the representational power of the generative model and increase the variance of Monte Carlo estimates. To address these issues, we introduce an iterative refinement procedure for improving the approximate posterior of the recognition network and show that training with the refined posterior is competitive with state-of-the-art methods. The advantages of refinement are further evident in an increased effective sample size, which implies a lower variance of gradient estimates.
Convex Sparse Spectral Clustering: Single-view to Multi-view
Venue: arXiv cs.CV 2018
Year: 2018

Spectral Clustering (SC) is one of the most widely used methods for data clustering. It first finds a low-dimensonal embedding $U$ of data by computing the eigenvectors of the normalized Laplacian matrix, and then performs k-means on $U^\top$ to get the final clustering result. In this work, we observe that, in the ideal case, $UU^\top$ should be block diagonal and thus sparse. Therefore we propose the Sparse Spectral Clustering (SSC) method which extends SC with sparse regularization on $UU^\top$. To address the computational issue of the nonconvex SSC model, we propose a novel convex relaxation of SSC based on the convex hull of the fixed rank projection matrices. Then the convex SSC model can be efficiently solved by the Alternating Direction Method of \canyi{Multipliers} (ADMM). Furthermore, we propose the Pairwise Sparse Spectral Clustering (PSSC) which extends SSC to boost the clustering performance by using the multi-view information of data. Experimental comparisons with several baselines on real-world datasets testify to the efficacy of our proposed methods.
A Modified Multiple OLS (m$^2$OLS) Algorithm for Signal Recovery in Compressive Sensing
Venue: arXiv cs.IT 2018
Year: 2018

Orthogonal least square (OLS) is an important sparse signal recovery algorithm for compressive sensing, which enjoys superior probability of success over other well-known recovery algorithms under conditions of correlated measurement matrices. Multiple OLS (mOLS) is a recently proposed improved version of OLS which selects multiple candidates per iteration by generalizing the greedy selection principle used in OLS and enjoys faster convergence than OLS. In this paper, we present a refined version of the mOLS algorithm where at each step of the iteration, we first preselect a submatrix of the measurement matrix suitably and then apply the mOLS computations to the chosen submatrix. Since mOLS now works only on a submatrix and not on the overall matrix, computations reduce drastically. Convergence of the algorithm, however, requires ensuring passage of true candidates through the two stages of preselection and mOLS based selection successively. This paper presents convergence conditions for both noisy and noise free signal models. The proposed algorithm enjoys faster convergence properties similar to mOLS, at a much reduced computational complexity.
The Alternating Stock Size Problem and the Gasoline Puzzle
Venue: arXiv cs.DS 2018
Year: 2018

Given a set S of integers whose sum is zero, consider the problem of finding a permutation of these integers such that: (i) all prefix sums of the ordering are nonnegative, and (ii) the maximum value of a prefix sum is minimized. Kellerer et al. referred to this problem as the "Stock Size Problem" and showed that it can be approximated to within 3/2. They also showed that an approximation ratio of 2 can be achieved via several simple algorithms. We consider a related problem, which we call the "Alternating Stock Size Problem", where the number of positive and negative integers in the input set S are equal. The problem is the same as above, but we are additionally required to alternate the positive and negative numbers in the output ordering. This problem also has several simple 2-approximations. We show that it can be approximated to within 1.79. Then we show that this problem is closely related to an optimization version of the gasoline puzzle due to Lovász, in which we want to minimize the size of the gas tank necessary to go around the track. We present a 2-approximation for this problem, using a natural linear programming relaxation whose feasible solutions are doubly stochastic matrices. Our novel rounding algorithm is based on a transformation that yields another doubly stochastic matrix with special properties, from which we can extract a suitable permutation.
Learning Discrete Bayesian Networks from Continuous Data
Venue: arXiv cs.AI 2018
Year: 2018

Learning Bayesian networks from raw data can help provide insights into the relationships between variables. While real data often contains a mixture of discrete and continuous-valued variables, many Bayesian network structure learning algorithms assume all random variables are discrete. Thus, continuous variables are often discretized when learning a Bayesian network. However, the choice of discretization policy has significant impact on the accuracy, speed, and interpretability of the resulting models. This paper introduces a principled Bayesian discretization method for continuous variables in Bayesian networks with quadratic complexity instead of the cubic complexity of other standard techniques. Empirical demonstrations show that the proposed method is superior to the established minimum description length algorithm. In addition, this paper shows how to incorporate existing methods into the structure learning process to discretize all continuous variables and simultaneously learn Bayesian network structures.
An Extension of Moebius--Lie Geometry with Conformal Ensembles of Cycles and Its Implementation in a GiNaC Library
Venue: arXiv cs.CG 2018
Year: 2018

We propose to consider ensembles of cycles (quadrics), which are interconnected through conformal-invariant geometric relations (e.g. "to be orthogonal", "to be tangent", etc.), as new objects in an extended Moebius--Lie geometry. It was recently demonstrated in several related papers, that such ensembles of cycles naturally parameterise many other conformally-invariant objects, e.g. loxodromes or continued fractions. The paper describes a method, which reduces a collection of conformally invariant geometric relations to a system of linear equations, which may be accompanied by one fixed quadratic relation. To show its usefulness, the method is implemented as a C++ library. It operates with numeric and symbolic data of cycles in spaces of arbitrary dimensionality and metrics with any signatures. Numeric calculations can be done in exact or approximate arithmetic. In the two- and three-dimensional cases illustrations and animations can be produced. An interactive Python wrapper of the library is provided as well.
Sentence Entailment in Compositional Distributional Semantics
Venue: arXiv cs.CL 2018
Year: 2018

Distributional semantic models provide vector representations for words by gathering co-occurrence frequencies from corpora of text. Compositional distributional models extend these from words to phrases and sentences. In categorical compositional distributional semantics, phrase and sentence representations are functions of their grammatical structure and representations of the words therein. In this setting, grammatical structures are formalised by morphisms of a compact closed category and meanings of words are formalised by objects of the same category. These can be instantiated in the form of vectors or density matrices. This paper concerns the applications of this model to phrase and sentence level entailment. We argue that entropy-based distances of vectors and density matrices provide a good candidate to measure word-level entailment, show the advantage of density matrices over vectors for word level entailments, and prove that these distances extend compositionally from words to phrases and sentences. We exemplify our theoretical constructions on real data and a toy entailment dataset and provide preliminary experimental evidence.
A Co-evolution Model of Network Structure and User Behavior in Online Social Networks: The Case of Network-Driven Content Generation
Venue: arXiv cs.SI 2018
Year: 2018

With the rapid growth of online social network sites (SNS), it has become imperative for platform owners and online marketers to investigate what drives content production on these platforms. However, previous research has found it difficult to statistically model these factors from observational data due to the inability to separately assess the effects of network formation and network influence. In this paper, we adopt and enhance an actor-oriented continuous-time model to jointly estimate the co-evolution of the users' social network structure and their content production behavior using a Markov Chain Monte Carlo (MCMC)- based simulation approach. Specifically, we offer a method to analyze non-stationary and continuous behavior with network effects in the presence of observable and unobservable covariates, similar to what is observed in social media ecosystems. Leveraging a unique dataset from a large social network site, we apply our model to data on university students across six months to find that: 1) users tend to connect with others that have similar posting behavior, 2) however, after doing so, users tend to diverge in posting behavior, and 3) peer influences are sensitive to the strength of the posting behavior. Further, our method provides researchers and practitioners with a statistically rigorous approach to analyze network effects in observational data. These results provide insights and recommendations for SNS platforms to sustain an active and viable community.
Mobile Cloud Business Process Management System for the Internet of Things: A Survey
Venue: arXiv cs.CY 2018
Year: 2018

The Internet of Things (IoT) represents a comprehensive environment that consists of a large number of smart devices interconnecting heterogeneous physical objects to the Internet. Many domains such as logistics, manufacturing, agriculture, urban computing, home automation, ambient assisted living and various ubiquitous computing applications have utilised IoT technologies. Meanwhile, Business Process Management Systems (BPMS) have become a successful and efficient solution for coordinated management and optimised utilisation of resources/entities. However, past BPMS have not considered many issues they will face in managing large scale connected heterogeneous IoT entities. Without fully understanding the behaviour, capability and state of the IoT entities, the BPMS can fail to manage the IoT integrated information systems. In this paper, we analyse existing BPMS for IoT and identify the limitations and their drawbacks based on Mobile Cloud Computing perspective. Later, we discuss a number of open challenges in BPMS for IoT.
Modeling Variations of First-Order Horn Abduction in Answer Set Programming
Venue: arXiv cs.AI 2018
Year: 2018

We study abduction in First Order Horn logic theories where all atoms can be abduced and we are looking for preferred solutions with respect to three objective functions: cardinality minimality, coherence, and weighted abduction. We represent this reasoning problem in Answer Set Programming (ASP), in order to obtain a flexible framework for experimenting with global constraints and objective functions, and to test the boundaries of what is possible with ASP. Realizing this problem in ASP is challenging as it requires value invention and equivalence between certain constants, because the Unique Names Assumption does not hold in general. To permit reasoning in cyclic theories, we formally describe fine-grained variations of limiting Skolemization. We identify term equivalence as a main instantiation bottleneck, and improve the efficiency of our approach with on-demand constraints that were used to eliminate the same bottleneck in state-of-the-art solvers. We evaluate our approach experimentally on the ACCEL benchmark for plan recognition in Natural Language Understanding. Our encodings are publicly available, modular, and our approach is more efficient than state-of-the-art solvers on the ACCEL benchmark.
Common tangents of two disjoint polygons in linear time and constant workspace
Venue: arXiv cs.CG 2018
Year: 2018

We provide a remarkably simple algorithm to compute all (at most four) common tangents of two disjoint simple polygons. Given each polygon as a read-only array of its corners in cyclic order, the algorithm runs in linear time and constant workspace and is the first to achieve the two complexity bounds simultaneously. The set of common tangents provides basic information about the convex hulls of the polygons---whether they are nested, overlapping, or disjoint---and our algorithm thus also decides this relationship.
Fixed-parameter Approximability of Boolean MinCSPs
Venue: arXiv cs.CC 2018
Year: 2018

The minimum unsatisfiability version of a constraint satisfaction problem (MinCSP) asks for an assignment where the number of unsatisfied constraints is minimum possible, or equivalently, asks for a minimum-size set of constraints whose deletion makes the instance satisfiable. For a finite set $Γ$ of constraints, we denote by MinCSP($Γ$) the restriction of the problem where each constraint is from $Γ$. The polynomial-time solvability and the polynomial-time approximability of MinCSP($Γ$) were fully characterized by Khanna et al. [Siam J. Comput. '00]. Here we study the fixed-parameter (FP-) approximability of the problem: given an instance and an integer $k$, one has to find a solution of size at most $g(k)$ in time $f(k)n^{O(1)}$ if a solution of size at most $k$ exists. We especially focus on the case of constant-factor FP-approximability. We show the following dichotomy: for each finite constraint language $Γ$, either we exhibit a constant-factor FP-approximation for MinCSP($Γ$); or we prove that MinCSP($Γ$) has no constant-factor FP-approximation unless FPT$=$W[1]. In particular, we show that approximating the so-called Nearest Codeword within some constant factor is W[1]-hard. Recently, Arnab et al. [ICALP '18] showed that such a W[1]-hardness of approximation implies that Even Set is W[1]-hard under randomized reductions. Combining our results, we therefore settle the parameterized complexity of Even Set, a famous open question in the field.
Robust Privacy-Utility Tradeoffs under Differential Privacy and Hamming Distortion
Venue: arXiv cs.IT 2018
Year: 2018

A privacy-utility tradeoff is developed for an arbitrary set of finite-alphabet source distributions. Privacy is quantified using differential privacy (DP), and utility is quantified using expected Hamming distortion maximized over the set of distributions. The family of source distribution sets (source sets) is categorized into three classes, based on different levels of prior knowledge they capture. For source sets whose convex hull includes the uniform distribution, symmetric DP mechanisms are optimal. For source sets whose probability values have a fixed monotonic ordering, asymmetric DP mechanisms are optimal. For all other source sets, general upper and lower bounds on the optimal privacy leakage are developed and a necessary and sufficient condition for tightness are established. Differentially private leakage is an upper bound on mutual information (MI) leakage: the two criteria are compared analytically and numerically to illustrate the effect of adopting a stronger privacy criterion.
Ensemble Estimation of Information Divergence
Venue: arXiv cs.IT 2018
Year: 2018

Recent work has focused on the problem of nonparametric estimation of information divergence functionals. Many existing approaches are restrictive in their assumptions on the density support set or require difficult calculations at the support boundary which must be known a priori. The MSE convergence rate of a leave-one-out kernel density plug-in divergence functional estimator for general bounded density support sets is derived where knowledge of the support boundary is not required. The theory of optimally weighted ensemble estimation is generalized to derive a divergence estimator that achieves the parametric rate when the densities are sufficiently smooth. The asymptotic distribution of this estimator and some guidelines for tuning parameter selection are provided. Based on the theory, an empirical estimator of Rényi-$α$ divergence is proposed that outperforms the standard kernel density plug-in estimator, especially in high dimension. The estimator is shown to be robust to the choice of tuning parameters. As an illustration, we use the estimator to estimate bounds on the Bayes error rate of a classification problem.
Codes in the Damerau Distance for DNA Storage
Venue: arXiv cs.IT 2018
Year: 2018

Motivated by applications in DNA-based storage, we introduce the new problem of code design in the Damerau metric. The Damerau metric is a generalization of the Levenshtein distance which, in addition to deletions, insertions and substitution errors also accounts for adjacent transposition edits. We first provide constructions for codes that may correct either a single deletion or a single adjacent transposition and then proceed to extend these results to codes that can simultaneously correct a single deletion and multiple adjacent transpositions. We conclude with constructions for joint block deletion and adjacent block transposition error-correcting codes.
On the Functions Generated by the General Purpose Analog Computer
Venue: arXiv cs.CC 2018
Year: 2018

We consider the General Purpose Analog Computer (GPAC), introduced by Claude Shannon in 1941 as a mathematical model of Differential Analysers, that is to say as a model of continuous-time analog (mechanical, and later one electronic) machines of that time. We extend the model properly to a model of computation not restricted to univariate functions (i.e. functions $f: \mathbb{R} \to \mathbb{R}$) but also to the multivariate case of (i.e. functions $f: \mathbb{R}^n \to \mathbb{R}^m$), and establish some basic properties. In particular, we prove that a very wide class of (continuous and discontinuous) functions can be uniformly approximated over their full domain. Technically: we generalize some known results about the GPAC to the multidimensional case: we extend naturally the notion of \emph{generable} function, from the unidimensional to the multidimensional case. We prove a few stability properties of this class, mostly stability by arithmetic operations, composition and ODE solving. We establish that generable functions are always analytic. We prove that generable functions include some basic (useful) generable functions, and that we can (uniformly) approximate a wide range of functions this way. This extends some of the results from \cite{Sha41} to the multidimensional case, and this also strengths the approximation result from \cite{Sha41} over a compact domain to a uniform approximation result over unbounded domains. We also discuss the issue of constants, and we prove that involved constants can basically assumed to always be polynomial time computable numbers.