OpenRaiser/Intern-Atlas huggingface dataset:
New characterizations of minimum spanning trees and of saliency maps based on quasi-flat zones
Venue: arXiv cs.CV 2015
Year: 2015

We study three representations of hierarchies of partitions: dendrograms (direct representations), saliency maps, and minimum spanning trees. We provide a new bijection between saliency maps and hierarchies based on quasi-flat zones as used in image processing and characterize saliency maps and minimum spanning trees as solutions to constrained minimization problems where the constraint is quasi-flat zones preservation. In practice, these results form a toolkit for new hierarchical methods where one can choose the most convenient representation. They also invite us to process non-image data with morphological hierarchies.
On self-dual MRD codes
Venue: arXiv cs.IT 2015
Year: 2015

We determine the automorphism group of Gabidulin codes of full length and characterise when these codes are equivalent to self-dual codes.
An Enumeration of the Equivalence Classes of Self-Dual Matrix Codes
Venue: arXiv cs.IT 2015
Year: 2015

As a result of their applications in network coding, space-time coding, and coding for criss-cross errors, matrix codes have garnered significant attention; in various contexts, these codes have also been termed rank-metric codes, space-time codes over finite fields, and array codes. We focus on characterizing matrix codes that are both efficient (have high rate) and effective at error correction (have high minimum rank-distance). It is well known that the inherent trade-off between dimension and minimum distance for a matrix code is reversed for its dual code; specifically, if a matrix code has high dimension and low minimum distance, then its dual code will have low dimension and high minimum distance. With an aim towards finding codes with a perfectly balanced trade-off, we study self-dual matrix codes. In this work, we develop a framework based on double cosets of the matrix-equivalence maps to provide a complete classification of the equivalence classes of self-dual matrix codes, and we employ this method to enumerate the equivalence classes of these codes for small parameters.
Revisiting Actor Programming in C++
Venue: arXiv cs.PL 2015
Year: 2015

The actor model of computation has gained significant popularity over the last decade. Its high level of abstraction makes it appealing for concurrent applications in parallel and distributed systems. However, designing a real-world actor framework that subsumes full scalability, strong reliability, and high resource efficiency requires many conceptual and algorithmic additives to the original model. In this paper, we report on designing and building CAF, the "C++ Actor Framework". CAF targets at providing a concurrent and distributed native environment for scaling up to very large, high-performance applications, and equally well down to small constrained systems. We present the key specifications and design concepts---in particular a message-transparent architecture, type-safe message interfaces, and pattern matching facilities---that make native actors a viable approach for many robust, elastic, and highly distributed developments. We demonstrate the feasibility of CAF in three scenarios: first for elastic, upscaling environments, second for including heterogeneous hardware like GPGPUs, and third for distributed runtime systems. Extensive performance evaluations indicate ideal runtime behaviour for up to 64 cores at very low memory footprint, or in the presence of GPUs. In these tests, CAF continuously outperforms the competing actor environments Erlang, Charm++, SalsaLite, Scala, ActorFoundry, and even the OpenMPI.
The Mysteries of Lisp -- I: The Way to S-expression Lisp
Venue: arXiv cs.PL 2015
Year: 2015

Despite its old age, Lisp remains mysterious to many of its admirers. The mysteries on one hand fascinate the language, on the other hand also obscure it. Following Stoyan but paying attention to what he has neglected or omitted, in this first essay of a series intended to unravel these mysteries, we trace the development of Lisp back to its origin, revealing how the language has evolved into its nowadays look and feel. The insights thus gained will not only enhance existent understanding of the language but also inspires further improvement of it.
Improving Spatial Codification in Semantic Segmentation
Venue: arXiv cs.CV 2015
Year: 2015

This paper explores novel approaches for improving the spatial codification for the pooling of local descriptors to solve the semantic segmentation problem. We propose to partition the image into three regions for each object to be described: Figure, Border and Ground. This partition aims at minimizing the influence of the image context on the object description and vice versa by introducing an intermediate zone around the object contour. Furthermore, we also propose a richer visual descriptor of the object by applying a Spatial Pyramid over the Figure region. Two novel Spatial Pyramid configurations are explored: Cartesian-based and crown-based Spatial Pyramids. We test these approaches with state-of-the-art techniques and show that they improve the Figure-Ground based pooling in the Pascal VOC 2011 and 2012 semantic segmentation challenges.
Combinatorial Game Complexity: An Introduction with Poset Games
Venue: arXiv cs.CC 2015
Year: 2015

Poset games have been the object of mathematical study for over a century, but little has been written on the computational complexity of determining important properties of these games. In this introduction we develop the fundamentals of combinatorial game theory and focus for the most part on poset games, of which Nim is perhaps the best-known example. We present the complexity results known to date, some discovered very recently.
Explicit RIP Matrices in Compressed Sensing from Algebraic Geometry
Venue: arXiv cs.IT 2015
Year: 2015

Compressed sensing was proposed by E. J. Candés, J. Romberg, T. Tao, and D. Donoho for efficient sampling of sparse signals in 2006 and has vast applications in signal processing. The expicit restricted isometry property (RIP) measurement matrices are needed in practice. Since 2007 R. DeVore, J. Bourgain et al and R. Calderbank et al have given several deterministic cosntrcutions of RIP matrices from various mathematical objects. On the other hand the strong coherence property of a measurement matrix was introduced by Bajwa and Calderbank et al for the recovery of signals under the noisy measuremnt. In this paper we propose new explicit construction of real valued RIP measurement matrices in compressed sensing from algebraic geometry. Our construction indicates that using more general algebraic-geometric objects rather than curves (AG codes), RIP measurement matrices in compressed sensing can be constructed with much smaller coherence and much bigger sparsity orders. The RIP matrices from algebraic geometry also have a nice asymptotic bound matching the bound from the previous constructions of Bourgain et al and the small-bias sets. On the negative side, we prove that the RIP matrices from DeVore's construction, its direct algebraic geometric generalization and one of our new construction do not satisfy the strong coherence property. However we give a modified version of AG-RIP matrices which satisfies the strong coherence property. Therefore the new RIP matrices in compressed sensing from our modified algebraic geometric construction can be used for the recovery of signals from the noisy measurement.
Simple sorting algorithm test based on CUDA
Venue: arXiv cs.DC 2015
Year: 2015

With the development of computing technology, CUDA has become a very important tool. In computer programming, sorting algorithm is widely used. There are many simple sorting algorithms such as enumeration sort, bubble sort and merge sort. In this paper, we test some simple sorting algorithm based on CUDA and draw some useful conclusions.
Improved Deep Convolutional Neural Network For Online Handwritten Chinese Character Recognition using Domain-Specific Knowledge
Venue: arXiv cs.CV 2015
Year: 2015

Deep convolutional neural networks (DCNNs) have achieved great success in various computer vision and pattern recognition applications, including those for handwritten Chinese character recognition (HCCR). However, most current DCNN-based HCCR approaches treat the handwritten sample simply as an image bitmap, ignoring some vital domain-specific information that may be useful but that cannot be learnt by traditional networks. In this paper, we propose an enhancement of the DCNN approach to online HCCR by incorporating a variety of domain-specific knowledge, including deformation, non-linear normalization, imaginary strokes, path signature, and 8-directional features. Our contribution is twofold. First, these domain-specific technologies are investigated and integrated with a DCNN to form a composite network to achieve improved performance. Second, the resulting DCNNs with diversity in their domain knowledge are combined using a hybrid serial-parallel (HSP) strategy. Consequently, we achieve a promising accuracy of 97.20% and 96.87% on CASIA-OLHWDB1.0 and CASIA-OLHWDB1.1, respectively, outperforming the best results previously reported in the literature.
Path Graphs, Clique Trees, and Flowers
Venue: arXiv cs.DM 2015
Year: 2015

An \emph{asteroidal triple} is a set of three independent vertices in a graph such that any two vertices in the set are connected by a path which avoids the neighbourhood of the third. A classical result by Lekkerkerker and Boland \cite{6} showed that interval graphs are precisely the chordal graphs that do not have asteroidal triples. Interval graphs are chordal, as are the \emph{directed path graphs} and the \emph{path graphs}. Similar to Lekkerkerker and Boland, Cameron, Hoáng, and Lévêque \cite{4} gave a characterization of directed path graphs by a "special type" of asteroidal triple, and asked whether or not there was such a characterization for path graphs. We give strong evidence that asteroidal triples alone are insufficient to characterize the family of path graphs, and give a new characterization of path graphs via a forbidden induced subgraph family that we call \emph{sun systems}. Key to our new characterization is the study of \emph{asteroidal sets} in sun systems, which are a natural generalization of asteroidal triples. Our characterization of path graphs by forbidding sun systems also generalizes a characterization of directed path graphs by forbidding odd suns that was given by Chaplick et al.~\cite{9}.
Polly's Polyhedral Scheduling in the Presence of Reductions
Venue: arXiv cs.PL 2015
Year: 2015

The polyhedral model provides a powerful mathematical abstraction to enable effective optimization of loop nests with respect to a given optimization goal, e.g., exploiting parallelism. Unexploited reduction properties are a frequent reason for polyhedral optimizers to assume parallelism prohibiting dependences. To our knowledge, no polyhedral loop optimizer available in any production compiler provides support for reductions. In this paper, we show that leveraging the parallelism of reductions can lead to a significant performance increase. We give a precise, dependence based, definition of reductions and discuss ways to extend polyhedral optimization to exploit the associativity and commutativity of reduction computations. We have implemented a reduction-enabled scheduling approach in the Polly polyhedral optimizer and evaluate it on the standard Polybench 3.2 benchmark suite. We were able to detect and model all 52 arithmetic reductions and achieve speedups up to 2.21$\times$ on a quad core machine by exploiting the multidimensional reduction in the BiCG benchmark.
Micro protocol engineering for unstructured carriers: On the embedding of steganographic control protocols into audio transmissions
Venue: arXiv cs.MM 2015
Year: 2015

Network steganography conceals the transfer of sensitive information within unobtrusive data in computer networks. So-called micro protocols are communication protocols placed within the payload of a network steganographic transfer. They enrich this transfer with features such as reliability, dynamic overlay routing, or performance optimization --- just to mention a few. We present different design approaches for the embedding of hidden channels with micro protocols in digitized audio signals under consideration of different requirements. On the basis of experimental results, our design approaches are compared, and introduced into a protocol engineering approach for micro protocols.
A Faster Algorithm to Build New Users Similarity List in Neighbourhood-based Collaborative Filtering
Venue: arXiv cs.IR 2015
Year: 2015

Neighbourhood-based Collaborative Filtering (CF) has been applied in the industry for several decades, because of the easy implementation and high recommendation accuracy. As the core of neighbourhood-based CF, the task of dynamically maintaining users' similarity list is challenged by cold-start problem and scalability problem. Recently, several methods are presented on solving the two problems. However, these methods applied an $O(n^2)$ algorithm to compute the similarity list in a special case, where the new users, with enough recommendation data, have the same rating list. To address the problem of large computational cost caused by the special case, we design a faster ($O(\frac{1}{125}n^2)$) algorithm, TwinSearch Algorithm, to avoid computing and sorting the similarity list for the new users repeatedly to save the computational resources. Both theoretical and experimental results show that the TwinSearch Algorithm achieves better running time than the traditional method.
Codes over subsets of algebras obtained by the Cayley-Dickson process
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we define binary block codes over subsets of real algebras obtained by the Cayley-Dickson process and we provide an algorithm to obtain codes with a better rate. This algorithm offers more flexibility than other methods known until now, similar to Lenstra algorithm on elliptic curves compared with Pollard algorithm.
Ad hoc Cloud Computing: From Concept to Realization
Venue: arXiv cs.DC 2015
Year: 2015

This paper presents the first complete, integrated and end-to-end solution for ad hoc cloud computing environments. Ad hoc clouds harvest resources from existing sporadically available, non-exclusive (i.e. primarily used for some other purpose) and unreliable infrastructures. In this paper we discuss the problems ad hoc cloud computing solves and outline our architecture which is based on BOINC.
A Security-assured Accuracy-maximised Privacy Preserving Collaborative Filtering Recommendation Algorithm
Venue: arXiv cs.CR 2015
Year: 2015

The neighbourhood-based Collaborative Filtering is a widely used method in recommender systems. However, the risks of revealing customers' privacy during the process of filtering have attracted noticeable public concern recently. Specifically, $k$NN attack discloses the target user's sensitive information by creating $k$ fake nearest neighbours by non-sensitive information. Among the current solutions against $k$NN attack, the probabilistic methods showed a powerful privacy preserving effect. However, the existing probabilistic methods neither guarantee enough prediction accuracy due to the global randomness, nor provide assured security enforcement against $k$NN attack. To overcome the problems of current probabilistic methods, we propose a novel approach, Partitioned Probabilistic Neighbour Selection, to ensure a required security guarantee while achieving the optimal prediction accuracy against $k$NN attack. In this paper, we define the sum of $k$ neighbours' similarity as the accuracy metric $α$, the number of user partitions, across which we select the $k$ neighbours, as the security metric $β$. Differing from the present methods that globally selected neighbours, our method selects neighbours from each group with exponential differential privacy to decrease the magnitude of noise. Theoretical and experimental analysis show that to achieve the same security guarantee against $k$NN attack, our approach ensures the optimal prediction accuracy.
The Application of Non-Cooperative Stackelberg Game Theory in Behavioral Science: Social Optimality with any Number of Players
Venue: arXiv cs.GT 2015
Year: 2015

Here we present a ground-breaking new postulate for game theory. The first part of this postulate contains the axiomatic observation that all games are created by a designer, whether they are: e.g., (dynamic/static) or (stationary/non-stationary) or (sequential/one-shot) non-cooperative games, and importantly, whether or not they are intended to represent a non-cooperative Stackelberg game, they can be mapped to a Stackelberg game. I.e., the game designer is the leader who is totally rational and honest, and the followers are mapped to the players of the designed game. If now the game designer, or "the leader" in the Stackelberg context, adopts a pure strategy, we postulate the following second part following from axiomatic observation of ultimate game leadership, where empirical insight leads to the second part of this postulate. Importantly, implementing a non-cooperative Stackelberg game, with a very honest and rational leader results in social optimality for all players (followers), assuming pure strategy across all followers and leader, and that the leader is totally rational, honest, and is able to achieve a minimum amount of competency in leading this game, with any finite number of iterations of leading this finite game.
Hiding Information in Noise: Fundamental Limits of Covert Wireless Communication
Venue: arXiv cs.IT 2015
Year: 2015

Widely-deployed encryption-based security prevents unauthorized decoding, but does not ensure undetectability of communication. However, covert, or low probability of detection/intercept (LPD/LPI) communication is crucial in many scenarios ranging from covert military operations and the organization of social unrest, to privacy protection for users of wireless networks. In addition, encrypted data or even just the transmission of a signal can arouse suspicion, and even the most theoretically robust encryption can often be defeated by a determined adversary using non-computational methods such as side-channel analysis. Various covert communication techniques were developed to address these concerns, including steganography for finite-alphabet noiseless applications and spread-spectrum systems for wireless communications. After reviewing these covert communication systems, this article discusses new results on the fundamental limits of their capabilities, as well as provides a vision for the future of such systems.
A Web Environment for Geometry
Venue: arXiv cs.CY 2015
Year: 2015

The Web Geometry Laboratory, (WGL), is a blended-learning, collaborative and adaptive, Web environment for geometry. It integrates a well known dynamic geometry system. In a collaborative session, exchange of geometrical and textual information between the user engaged in the session is possible. In a normal work session (stand-alone mode), all the geometric steps done by the students are recorded, alongside the navigation information, allowing, in a latter stage, their teachers to "play back" the students sessions, using that info to assert the students level and adjust the teaching strategies to each individual student. Teachers can register and begin using one of the public servers, defining students, preparing materials to be released to the students, open collaborative sessions, etc. Using an action research methodology the WGL system is being developed, validated through case-studies, and further improved, in a cycle where the implementation steps are intertwined with case studies.
Using curvature to distinguish between surface reflections and vessel contents in computer vision based recognition of materials in transparent vessels
Venue: arXiv cs.CV 2015
Year: 2015

The recognition of materials and objects inside transparent containers using computer vision has a wide range of applications, ranging from industrial bottles filling to the automation of chemistry laboratory. One of the main challenges in such recognition is the ability to distinguish between image features resulting from the vessels surface and image features resulting from the material inside the vessel. Reflections and the functional parts of a vessels surface can create strong edges that can be mistakenly identified as corresponding to the vessel contents, and cause recognition errors. The ability to evaluate whether a specific edge in an image stems from the vessels surface or from its contents can considerably improve the ability to identify materials inside transparent vessels. This work will suggest a method for such evaluation, based on the following two assumptions: 1) Areas of high curvature on the vessel surface are likely to cause strong edges due to changes in reflectivity, as is the appearance of functional parts (e.g. corks or valves). 2) Most transparent vessels (bottles, glasses) have high symmetry (cylindrical). As a result the curvature angle of the vessels surface at each point of the image is similar to the curvature angle of the contour line of the vessel in the same row in the image. These assumptions, allow the identification of image regions with strong edges corresponding to the vessel surface reflections. Combining this method with existing image analysis methods for detecting materials inside transparent containers allows considerable improvement in accuracy.
Gaussian Secure Source Coding and Wyner's Common Information
Venue: arXiv cs.IT 2015
Year: 2015

We study secure source-coding with causal disclosure, under the Gaussian distribution. The optimality of Gaussian auxiliary random variables is shown in various scenarios. We explicitly characterize the tradeoff between the rates of communication and secret key. This tradeoff is the result of a mutual information optimization under Markov constraints. As a corollary, we deduce a general formula for Wyner's Common Information in the Gaussian setting.
Minimum MS. E. Gerber's Lemma
Venue: arXiv cs.IT 2015
Year: 2015

Mrs. Gerber's Lemma lower bounds the entropy at the output of a binary symmetric channel in terms of the entropy of the input process. In this paper, we lower bound the output entropy via a different measure of input uncertainty, pertaining to the minimum mean squared error (MMSE) prediction cost of the input process. We show that in many cases our bound is tighter than the one obtained from Mrs. Gerber's Lemma. As an application, we evaluate the bound for binary hidden Markov processes, and obtain new estimates for the entropy rate.
Interactive Knowledge Base Population
Venue: arXiv cs.AI 2015
Year: 2015

Most work on building knowledge bases has focused on collecting entities and facts from as large a collection of documents as possible. We argue for and describe a new paradigm where the focus is on a high-recall extraction over a small collection of documents under the supervision of a human expert, that we call Interactive Knowledge Base Population (IKBP).