OpenRaiser/Intern-Atlas huggingface dataset:
Exploring the influence of scale on artist attribution
Venue: arXiv cs.CV 2015
Year: 2015

Previous work has shown that the artist of an artwork can be identified by use of computational methods that analyse digital images. However, the digitised artworks are often investigated at a coarse scale discarding many of the important details that may define an artist's style. In recent years high resolution images of artworks have become available, which, combined with increased processing power and new computational techniques, allow us to analyse digital images of artworks at a very fine scale. In this work we train and evaluate a Convolutional Neural Network (CNN) on the task of artist attribution using artwork images of varying resolutions. To this end, we combine two existing methods to enable the application of high resolution images to CNNs. By comparing the attribution performances obtained at different scales, we find that in most cases finer scales are beneficial to the attribution performance, whereas for a minority of the artists, coarser scales appear to be preferable. We conclude that artist attribution would benefit from a multi-scale CNN approach which vastly expands the possibilities for computational art forensics.
Comparison of methods of automatic blood pressure measurement in the same device
Venue: arXiv cs.SY 2015
Year: 2015

Comparison of tacho-oscillographic and oscillometric methods for human blood pressure measurement with cuff occlusion in the same device at the same time is described. For this purpose the measurement system and software for signal processing that realize these methods in the same device was developed. Experiment shows that oscillometric method with photoplethysmographic (PPG) sensors does not require empiric criteria to search systolic and diastolic blood pressure parameters due to possibility to apply correlation analysis. Perspectives of applying oscillometric method with PPG sensors in automatic blood pressure monitors is showed.
HuTO: an Human Time Ontology for Semantic Web Applications
Venue: arXiv cs.AI 2015
Year: 2015

The temporal phenomena have many facets that are studied by different communities. In Semantic Web, large heterogeneous data are handled and produced. These data often have informal, semi-formal or formal temporal information which must be interpreted by software agents. In this paper we present Human Time Ontology (HuTO) an RDFS ontology to annotate and represent temporal data. A major contribution of HuTO is the modeling of non-convex intervals giving the ability to write queries for this kind of interval. HuTO also incorporates normalization and reasoning rules to explicit certain information. HuTO also proposes an approach which associates a temporal dimension to the knowledge base content. This facilitates information retrieval by considering or not the temporal aspect.
Enumerating Cyclic Orientations of a Graph
Venue: arXiv cs.DS 2015
Year: 2015

Acyclic and cyclic orientations of an undirected graph have been widely studied for their importance: an orientation is acyclic if it assigns a direction to each edge so as to obtain a directed acyclic graph (DAG) with the same vertex set; it is cyclic otherwise. As far as we know, only the enumeration of acyclic orientations has been addressed in the literature. In this paper, we pose the problem of efficiently enumerating all the \emph{cyclic} orientations of an undirected connected graph with $n$ vertices and $m$ edges, observing that it cannot be solved using algorithmic techniques previously employed for enumerating acyclic orientations.We show that the problem is of independent interest from both combinatorial and algorithmic points of view, and that each cyclic orientation can be listed with $\tilde{O}(m)$ delay time. Space usage is $O(m)$ with an additional setup cost of $O(n^2)$ time before the enumeration begins, or $O(mn)$ with a setup cost of $\tilde{O}(m)$ time.
Face Prediction Model for an Automatic Age-invariant Face Recognition System
Venue: arXiv cs.CV 2015
Year: 2015

Automated face recognition and identification softwares are becoming part of our daily life; it finds its abode not only with Facebook's auto photo tagging, Apple's iPhoto, Google's Picasa, Microsoft's Kinect, but also in Homeland Security Department's dedicated biometric face detection systems. Most of these automatic face identification systems fail where the effects of aging come into the picture. Little work exists in the literature on the subject of face prediction that accounts for aging, which is a vital part of the computer face recognition systems. In recent years, individual face components' (e.g. eyes, nose, mouth) features based matching algorithms have emerged, but these approaches are still not efficient. Therefore, in this work we describe a Face Prediction Model (FPM), which predicts human face aging or growth related image variation using Principle Component Analysis (PCA) and Artificial Neural Network (ANN) learning techniques. The FPM captures the facial changes, which occur with human aging and predicts the facial image with a few years of gap with an acceptable accuracy of face matching from 76 to 86%.
Non-Uniform Distribution of Nodes in the Spatial Preferential Attachment Model
Venue: arXiv cs.SI 2015
Year: 2015

The spatial preferential attachment (SPA) is a model for complex networks. In the SPA model, nodes are embedded in a metric space, and each node has a sphere of influence whose size increases if the node gains an in-link, and otherwise decreases with time. In this paper, we study the behaviour of the SPA model when the distribution of the nodes is non-uniform. Specifically, the space is divided into dense and sparse regions, where it is assumed that the dense regions correspond to coherent communities. We prove precise theoretical results regarding the degree of a node, the number of common neighbours, and the average out-degree in a region. Moreover, we show how these theoretically derived results about the graph properties of the model can be used to formulate a reliable estimator for the distance between certain pairs of nodes, and to estimate the density of the region containing a given node.
On skew polynomial codes and lattices from quotients of cyclic division algebras
Venue: arXiv cs.IT 2015
Year: 2015

We propose a variation of Construction A of lattices from linear codes defined using the quotient $Λ/\mathfrak pΛ$ of some order $Λ$ inside a cyclic division $F$-algebra, for $\mathfrak p$ a prime ideal of a number field $F$. To obtain codes over this quotient, we first give an isomorphism between $Λ/\mathfrak pΛ$ and a ring of skew polynomials. We then discuss definitions and basic properties of skew polynomial codes, which are needed for Construction A, but also explore further properties of the dual of such codes. We conclude by providing an application to space-time coding, which is the original motivation to consider cyclic division $F$-algebras as a starting point for this variation of Construction A.
Secure Degrees of Freedom of One-hop Wireless Networks with No Eavesdropper CSIT
Venue: arXiv cs.IT 2015
Year: 2015

We consider three channel models: the wiretap channel with $M$ helpers, the $K$-user multiple access wiretap channel, and the $K$-user interference channel with an external eavesdropper, when no eavesdropper's channel state information (CSI) is available at the transmitters. In each case, we establish the optimal sum secure degrees of freedom (s.d.o.f.) by providing achievable schemes and matching converses. We show that the unavailability of the eavesdropper's CSIT does not reduce the s.d.o.f. of the wiretap channel with helpers. However, there is loss in s.d.o.f. for both the multiple access wiretap channel and the interference channel with an external eavesdropper. In particular, we show that in the absence of eavesdropper's CSIT, the $K$-user multiple access wiretap channel reduces to a wiretap channel with $(K-1)$ helpers from a sum s.d.o.f. perspective, and the optimal sum s.d.o.f. reduces from $\frac{K(K-1)}{K(K-1)+1}$ to $\frac{K-1}{K}$. For the interference channel with an external eavesdropper, the optimal sum s.d.o.f. decreases from $\frac{K(K-1)}{2K-1}$ to $\frac{K-1}{2}$ in the absence of the eavesdropper's CSIT. Our results show that the lack of eavesdropper's CSIT does not have a significant impact on the optimal s.d.o.f. for any of the three channel models, especially when the number of users is large. This implies that physical layer security can be made robust to the unavailability of eavesdropper CSIT at high signal to noise ratio (SNR) regimes by careful modification of the achievable schemes as demonstrated in this paper.
Typologies of the Popular Science Web Video
Venue: arXiv cs.CY 2015
Year: 2015

The creation of popular science web videos on the Internet has increased in recent years. The diversity of formats, genres, and producers makes it difficult to formulate a universal definition of science web videos since not every producer considers him- or herself to be a science communicator in an institutional sense, and professionalism and success on video platforms no longer depend exclusively on technical excellence or production costs. Entertainment, content quality, and authenticity have become the keys to community building and success. The democratization of science video production allows a new variety of genres, styles, and forms. This article provides a first overview of the typologies and characteristics of popular science web videos. To avoid a misleading identification of science web videos with institutionally produced videos, we steer clear of the term science communication video, since many of the actual producers are not even familiar with the academic discussion on science communication, and since the subject matter does not depend on political or educational strategies. A content analysis of 200 videos from 100 online video channels was conducted. Several factors such as narrative strategies, video editing techniques, and design tendencies with regard to cinematography, the number of shots, the kind of montage used, and even the spread use of sound design and special FX point to an increasing professionalism among science communicators independent of institutional or personal commitments: in general, it can be said that supposed amateurs are creating the visual language of science video communication. This study represents an important step in understanding the essence of current popular science web videos and provides an evidence-based definition as a helpful cornerstone for further studies on science communication within this kind of new media.
Complexity of a Disjoint Matching Problem on Bipartite Graphs
Venue: arXiv cs.DS 2015
Year: 2015

We consider the following question: given an $(X,Y)$-bigraph $G$ and a set $S \subset X$, does $G$ contain two disjoint matchings $M_1$ and $M_2$ such that $M_1$ saturates $X$ and $M_2$ saturates $S$? When $|S|\geq |X|-1$, this question is solvable by finding an appropriate factor of the graph. In contrast, we show that when $S$ is allowed to be an arbitrary subset of $X$, the problem is NP-hard.
Abstract Model Repair
Venue: arXiv cs.LO 2015
Year: 2015

Given a Kripke structure M and CTL formula $φ$, where M does not satisfy $φ$, the problem of Model Repair is to obtain a new model M' such that M' satisfies $φ$. Moreover, the changes made to M to derive M' should be minimum with respect to all such M'. As in model checking, state explosion can make it virtually impossible to carry out model repair on models with infinite or even large state spaces. In this paper, we present a framework for model repair that uses abstraction refinement to tackle state explosion. Our framework aims to repair Kripke Structure models based on a Kripke Modal Transition System abstraction and a 3-valued semantics for CTL. We introduce an abstract-model-repair algorithm for which we prove soundness and semi-completeness, and we study its complexity class. Moreover, a prototype implementation is presented to illustrate the practical utility of abstract-model-repair on an Automatic Door Opener system model and a model of the Andrew File System 1 protocol.
A Type-Theoretic Approach to Structural Resolution
Venue: arXiv cs.LO 2015
Year: 2015

Structural resolution (or S-resolution) is a newly proposed alternative to SLD-resolution that allows a systematic separation of derivations into term-matching and unification steps. Productive logic programs are those for which term-matching reduction on any query must terminate. For productive programs with coinductive meaning, finite term-rewriting reductions can be seen as measures of observation in an infinite derivation. Ability of handling corecursion in a productive way is an attractive computational feature of S-resolution. In this paper, we make first steps towards a better conceptual understanding of operational properties of S-resolution as compared to SLD-resolution. To this aim, we propose a type system for the analysis of both SLD-resolution and S-resolution. We formulate S-resolution and SLD-resolution as reduction systems, and show their soundness relative to the type system. One of the central methods of this paper is realizability transformation, which makes logic programs productive and non-overlapping. We show that S-resolution and SLD-resolution are only equivalent for programs with these two properties.
Resilience for Multigrid Software at the Extreme Scale
Venue: arXiv cs.MS 2015
Year: 2015

Fault tolerant algorithms for the numerical approximation of elliptic partial differential equations on modern supercomputers play a more and more important role in the future design of exa-scale enabled iterative solvers. Here, we combine domain partitioning with highly scalable geometric multigrid schemes to obtain fast and fault-robust solvers in three dimensions. The recovery strategy is based on a hierarchical hybrid concept where the values on lower dimensional primitives such as faces are stored redundantly and thus can be recovered easily in case of a failure. The lost volume unknowns in the faulty region are re-computed approximately with multigrid cycles by solving a local Dirichlet problem on the faulty subdomain. Different strategies are compared and evaluated with respect to performance, computational cost, and speed up. Especially effective are strategies in which the local recovery in the faulty region is executed in parallel with global solves and when the local recovery is additionally accelerated. This results in an asynchronous multigrid iteration that can fully compensate faults. Excellent parallel performance on a current peta-scale system is demonstrated.
Unstructured Overlapping Mesh Distribution in Parallel
Venue: arXiv cs.MS 2015
Year: 2015

We present a simple mathematical framework and API for parallel mesh and data distribution, load balancing, and overlap generation. It relies on viewing the mesh as a Hasse diagram, abstracting away information such as cell shape, dimension, and coordinates. The high level of abstraction makes our interface both concise and powerful, as the same algorithm applies to any representable mesh, such as hybrid meshes, meshes embedded in higher dimension, and overlapped meshes in parallel. We present evidence, both theoretical and experimental, that the algorithms are scalable and efficient. A working implementation can be found in the latest release of the PETSc libraries.
Competitive Selection of Ephemeral Relays in Wireless Networks
Venue: arXiv cs.NI 2015
Year: 2015

We consider a setting in which two nodes (referred to as forwarders) compete to choose a relay node from a set of relays, as they ephemerally become available (e.g., wake up from a sleep state). Each relay, when it arrives, offers a (possibly different) "reward" to each forwarder. Each forwarder's objective is to minimize a combination of the delay incurred in choosing a relay and the reward offered by the chosen relay. As an example, we develop the reward structure for the specific problem of geographical forwarding over a network of sleep-wake cycling relays. We study two variants of the generic relay selection problem, namely, the completely observable (CO) case where, when a relay arrives, both forwarders get to observe both rewards, and the partially observable (PO) case where each forwarder can only observe its own reward. Formulating the problem as a two person stochastic game, we characterize solution in terms of Nash Equilibrium Policy Pairs (NEPPs). For the CO case we provide a general structure of the NEPPs. For the PO case we prove that there exists an NEPP within the class of threshold policy pairs. We then consider the particular application of geographical forwarding of packets in a shared network of sleep-wake cycling wireless relays. For this problem, for a particular reward structure, using realistic parameter values corresponding to TelosB wireless mote, we numerically compare the performance (in terms of cost to both forwarders) of the various NEPPs and draw the following key insight: even for moderate separation between the two forwarders, the performance of the various NEPPs is close to the performance of a simple strategy where each forwarder behaves as if the other forwarder is not present. We also conduct simulation experiments to study the end-to-end performance of the simple forwarding policy.
An analytical framework for analysis and design of networked control systems with random delays and packet losses
Venue: arXiv cs.SY 2015
Year: 2015

Delays and data losses are undesirable from a control system perspective as they tend to adversely affect performance Networked Control Systems (NCSs) are a class of control systems wherein control components exchange information using a shared communication channel. Delays and packet losses in the communication channels are usually random, thereby making the analysis and design of control loops more complex. The usual assumptions in classical control theory, such as delay free sensing and synchronous actuation, assume lesser significance when it comes to NCSs. Hence, this necessitates a reformulation/relook into the existing models used for NCS control loop analysis and design. In this paper, we study and present the reformulations required for NCSs to include random delays and packet loss in the channel. This paper thereby gives a complete overview of what has been accomplished thus far in NCS research and puts forth a unified framework for analyzing a host of problems that can be captured as NCSs subjected to random delays and packet losses.
Aligning where to see and what to tell: image caption with region-based attention and scene factorization
Venue: arXiv cs.CV 2015
Year: 2015

Recent progress on automatic generation of image captions has shown that it is possible to describe the most salient information conveyed by images with accurate and meaningful sentences. In this paper, we propose an image caption system that exploits the parallel structures between images and sentences. In our model, the process of generating the next word, given the previously generated ones, is aligned with the visual perception experience where the attention shifting among the visual regions imposes a thread of visual ordering. This alignment characterizes the flow of "abstract meaning", encoding what is semantically shared by both the visual scene and the text description. Our system also makes another novel modeling contribution by introducing scene-specific contexts that capture higher-level semantic information encoded in an image. The contexts adapt language models for word generation to specific scene types. We benchmark our system and contrast to published results on several popular datasets. We show that using either region-based attention or scene-specific contexts improves systems without those components. Furthermore, combining these two modeling ingredients attains the state-of-the-art performance.
Pose Estimation Based on 3D Models
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we proposed a pose estimation system based on rendered image training set, which predicts the pose of objects in real image, with knowledge of object category and tight bounding box. We developed a patch-based multi-class classification algorithm, and an iterative approach to improve the accuracy. We achieved state-of-the-art performance on pose estimation task.
Modeling of Resilience Properties in Oscillatory Biological Systems using Parametric Time Petri Nets, Supplementary Information
Venue: arXiv cs.LO 2015
Year: 2015

Automated verification of living organism models allows us to gain previously unknown knowledge about underlying biological processes. In this paper, we show the benefits to use parametric time Petri nets in order to analyze precisely the dynamic behavior of biological oscillatory systems. In particular, we focus on the resilience properties of such systems. This notion is crucial to understand the behavior of biological systems (e.g. the mammalian circadian rhythm) that are reactive and adaptive enough to endorse major changes in their environment (e.g. jet-lags, day-night alternating work-time). We formalize these properties through parametric TCTL and demonstrate how changes of the environmental conditions can be tackled to guarantee the resilience of living organisms. In particular, we are able to discuss the influence of various perturbations, e.g. artificial jet-lag or components knock-out, with regard to quantitative delays. This analysis is crucial when it comes to model elicitation for dynamic biological systems. We demonstrate the applicability of this technique using a simplified model of circadian clock.
Inapproximability of $H$-Transversal/Packing
Venue: arXiv cs.CC 2015
Year: 2015

Given an undirected graph $G = (V_G, E_G)$ and a fixed "pattern" graph $H = (V_H, E_H)$ with $k$ vertices, we consider the $H$-Transversal and $H$-Packing problems. The former asks to find the smallest $S \subseteq V_G$ such that the subgraph induced by $V_G \setminus S$ does not have $H$ as a subgraph, and the latter asks to find the maximum number of pairwise disjoint $k$-subsets $S_1, ..., S_m \subseteq V_G$ such that the subgraph induced by each $S_i$ has $H$ as a subgraph. We prove that if $H$ is 2-connected, $H$-Transversal and $H$-Packing are almost as hard to approximate as general $k$-Hypergraph Vertex Cover and $k$-Set Packing, so it is NP-hard to approximate them within a factor of $Ω(k)$ and $\widetilde Ω(k)$ respectively. We also show that there is a 1-connected $H$ where $H$-Transversal admits an $O(\log k)$-approximation algorithm, so that the connectivity requirement cannot be relaxed from 2 to 1. For a special case of $H$-Transversal where $H$ is a (family of) cycles, we mention the implication of our result to the related Feedback Vertex Set problem, and give a different hardness proof for directed graphs.
Experimental Study of DIGIPASS GO3 and the Security of Authentication
Venue: arXiv cs.CR 2015
Year: 2015

Based on the analysis of $6$-digit one-time passwords(OTP) generated by DIGIPASS GO3 we were able to reconstruct the synchronisation system of the token, the OTP generating algorithm and the verification protocol in details essential for an attack. The OTPs are more predictable than expected. A forgery attack is described. We argue the attack success probability is $8^{-5}$. That is much higher than $10^{-6}$ which may be expected if all the digits are independent and uniformly distributed. Under natural assumptions even in a relatively small bank or company with $10^4$ customers the number of compromised accounts during a year may be more than $100$.