OpenRaiser/Intern-Atlas huggingface dataset:
The color of smiling: computational synaesthesia of facial expressions
Venue: arXiv cs.CV 2015
Year: 2015

This note gives a preliminary account of the transcoding or rechanneling problem between different stimuli as it is of interest for the natural interaction or affective computing fields. By the consideration of a simple example, namely the color response of an affective lamp to a sensed facial expression, we frame the problem within an information- theoretic perspective. A full justification in terms of the Information Bottleneck principle promotes a latent affective space, hitherto surmised as an appealing and intuitive solution, as a suitable mediator between the different stimuli.
Threes!, Fives, 1024!, and 2048 are Hard
Venue: arXiv cs.CC 2015
Year: 2015

We analyze the computational complexity of the popular computer games Threes!, 1024!, 2048 and many of their variants. For most known versions expanded to an m x n board, we show that it is NP-hard to decide whether a given starting position can be played to reach a specific (constant) tile value.
Time vs. Information Tradeoffs for Leader Election in Anonymous Trees
Venue: arXiv cs.DC 2015
Year: 2015

The leader election task calls for all nodes of a network to agree on a single node. If the nodes of the network are anonymous, the task of leader election is formulated as follows: every node $v$ of the network must output a simple path, coded as a sequence of port numbers, such that all these paths end at a common node, the leader. In this paper, we study deterministic leader election in anonymous trees. Our aim is to establish tradeoffs between the allocated time $τ$ and the amount of information that has to be given $\textit{a priori}$ to the nodes to enable leader election in time $τ$ in all trees for which leader election in this time is at all possible. Following the framework of $\textit{algorithms with advice}$, this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire tree. The length of this string is called the $\textit{size of advice}$. For an allocated time $τ$, we give upper and lower bounds on the minimum size of advice sufficient to perform leader election in time $τ$. We consider $n$-node trees of diameter $diam \leq D$. While leader election in time $diam$ can be performed without any advice, for time $diam-1$ we give tight upper and lower bounds of $Θ(\log D)$. For time $diam-2$ we give tight upper and lower bounds of $Θ(\log D)$ for even values of $diam$, and tight upper and lower bounds of $Θ(\log n)$ for odd values of $diam$. For the time interval $[β\cdot diam, diam-3]$ for constant $β>1/2$, we prove an upper bound of $O(\frac{n\log n}{D})$ and a lower bound of $Ω(\frac{n}{D})$, the latter being valid whenever $diam$ is odd or when the time is at most $diam-4$. Finally, for time $α\cdot diam$ for any constant $α<1/2$ (except for the case of very small diameters), we give tight upper and lower bounds of $Θ(n)$.
Evolving Spiking Networks with Variable Resistive Memories
Venue: arXiv cs.NE 2015
Year: 2015

Neuromorphic computing is a brainlike information processing paradigm that requires adaptive learning mechanisms. A spiking neuro-evolutionary system is used for this purpose; plastic resistive memories are implemented as synapses in spiking neural networks. The evolutionary design process exploits parameter self-adaptation and allows the topology and synaptic weights to be evolved for each network in an autonomous manner. Variable resistive memories are the focus of this research; each synapse has its own conductance profile which modifies the plastic behaviour of the device and may be altered during evolution. These variable resistive networks are evaluated on a noisy robotic dynamic-reward scenario against two static resistive memories and a system containing standard connections only. Results indicate that the extra behavioural degrees of freedom available to the networks incorporating variable resistive memories enable them to outperform the comparative synapse types.
Efficient MUS Enumeration of Horn Formulae with Applications to Axiom Pinpointing
Venue: arXiv cs.LO 2015
Year: 2015

The enumeration of minimal unsatisfiable subsets (MUSes) finds a growing number of practical applications, that includes a wide range of diagnosis problems. As a concrete example, the problem of axiom pinpointing in the EL family of description logics (DLs) can be modeled as the enumeration of the group-MUSes of Horn formulae. In turn, axiom pinpointing for the EL family of DLs finds important applications, such as debugging medical ontologies, of which SNOMED CT is the best known example. The main contribution of this paper is to develop an efficient group-MUS enumerator for Horn formulae, HGMUS, that finds immediate application in axiom pinpointing for the EL family of DLs. In the process of developing HGMUS, the paper also identifies performance bottlenecks of existing solutions. The new algorithm is shown to outperform all alternative approaches when the problem domain targeted by group-MUS enumeration of Horn formulae is axiom pinpointing for the EL family of DLs, with a representative suite of examples taken from different medical ontologies.
The Best of Both Worlds: Combining Data-independent and Data-driven Approaches for Action Recognition
Venue: arXiv cs.CV 2015
Year: 2015

Motivated by the success of data-driven convolutional neural networks (CNNs) in object recognition on static images, researchers are working hard towards developing CNN equivalents for learning video features. However, learning video features globally has proven to be quite a challenge due to its high dimensionality, the lack of labelled data and the difficulty in processing large-scale video data. Therefore, we propose to leverage effective techniques from both data-driven and data-independent approaches to improve action recognition system. Our contribution is three-fold. First, we propose a two-stream Stacked Convolutional Independent Subspace Analysis (ConvISA) architecture to show that unsupervised learning methods can significantly boost the performance of traditional local features extracted from data-independent models. Second, we demonstrate that by learning on video volumes detected by Improved Dense Trajectory (IDT), we can seamlessly combine our novel local descriptors with hand-crafted descriptors. Thus we can utilize available feature enhancing techniques developed for hand-crafted descriptors. Finally, similar to multi-class classification framework in CNNs, we propose a training-free re-ranking technique that exploits the relationship among action classes to improve the overall performance. Our experimental results on four benchmark action recognition datasets show significantly improved performance.
Xoxa: a lightweight approach to normalizing and signing XML
Venue: arXiv cs.CR 2015
Year: 2015

Cryptographically signing XML, and normalizing it prior to signing, are forbiddingly intricate problems in the general case. This is largely because of the complexities of the XML Information Set. We can define a more aggressive normalization, which dispenses with distinctions and features which are unimportant in a large class of cases, and thus define a straightforwardly implementable and portable signature framework.
Visual Semantic Role Labeling
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we introduce the problem of Visual Semantic Role Labeling: given an image we want to detect people doing actions and localize the objects of interaction. Classical approaches to action recognition either study the task of action classification at the image or video clip level or at best produce a bounding box around the person doing the action. We believe such an output is inadequate and a complete understanding can only come when we are able to associate objects in the scene to the different semantic roles of the action. To enable progress towards this goal, we annotate a dataset of 16K people instances in 10K images with actions they are doing and associate objects in the scene with different semantic roles for each action. Finally, we provide a set of baseline algorithms for this task and analyze error modes providing directions for future work.
Fractally-organized Connectionist Networks: Conjectures and Preliminary Results
Venue: arXiv cs.NE 2015
Year: 2015

A strict interpretation of connectionism mandates complex networks of simple components. The question here is, is this simplicity to be interpreted in absolute terms? I conjecture that absolute simplicity might not be an essential attribute of connectionism, and that it may be effectively exchanged with a requirement for relative simplicity, namely simplicity with respect to the current organizational level. In this paper I provide some elements to the analysis of the above question. In particular I conjecture that fractally organized connectionist networks may provide a convenient means to achive what Leibniz calls an "art of complication", namely an effective way to encapsulate complexity and practically extend the applicability of connectionism to domains such as sociotechnical system modeling and design. Preliminary evidence to my claim is brought by considering the design of the software architecture designed for the telemonitoring service of Flemish project "Little Sister".
Placement Of Energy Aware Wireless Mesh Nodes For E-Learning In Green Campuses
Venue: arXiv cs.NI 2015
Year: 2015

Energy efficiency solutions are more vital for Green Mesh Network (GMN) campuses. Today students are benefited using these e-learning methodologies. Renewable energies such as solar, wind, hydro has tremendous applications on energy efficient wireless networks for sustaining the ever growing traffic demands. One of the major issues in designing a GMN is minimizing the number of deployed mesh routers and gateways and satisfying the sustainable QOS based energy constraints. During low traffic periods the mesh routers are switched to power save or sleep mode. In this paper we have mathematically formulated a single objective function with multi constraints to optimize the energy. The objective is to place minimum number of Mesh routers and gateways in a set of candidate location. The mesh nodes are powered using the solar energy to meet the traffic demands. Two global optimisation algorithms are compared in this paper to optimize the energy sustainability, to guarantee seamless connectivity.
Angelic Processes
Venue: arXiv cs.LO 2015
Year: 2015

In the formal modelling of systems, demonic and angelic nondeterminism play fundamental roles as abstraction mechanisms. The angelic nature of a choice pertains to the property of avoiding failure whenever possible. As a concept, angelic choice first appeared in automata theory and Turing machines, where it can be implemented via backtracking. It has traditionally been studied in the refinement calculus, and has proved to be useful in a variety of applications and refinement techniques. Recently it has been studied within relational, multirelational and higher-order models. It has been employed for modelling user interactions, game-like scenarios, theorem proving tactics, constraint satisfaction problems and control systems. When the formal modelling of state-rich reactive systems is considered, it only seems natural that both types of nondeterministic choice should be considered. However, despite several treatments of angelic nondeterminism in the context of process algebras, namely Communicating Sequential Processes, the counterpart to the angelic choice of the refinement calculus has been elusive. In this thesis, we develop a semantics in the relational setting of Hoare and He's Unifying Theories of Programming that enables the characterisation of angelic nondeterminism in CSP. Since CSP processes are given semantics in the UTP via designs, that is, pre and postcondition pairs, we first introduce a theory of angelic designs, and an isomorphic multirelational model, that is suitable for characterising processes. We then develop a theory of reactive angelic designs by enforcing the healthiness conditions of CSP. Finally, by introducing a notion of divergence that can undo the history of events, we obtain a model where angelic choice avoids divergence.
On the tightness of an SDP relaxation of k-means
Venue: arXiv cs.IT 2015
Year: 2015

Recently, Awasthi et al. introduced an SDP relaxation of the $k$-means problem in $\mathbb R^m$. In this work, we consider a random model for the data points in which $k$ balls of unit radius are deterministically distributed throughout $\mathbb R^m$, and then in each ball, $n$ points are drawn according to a common rotationally invariant probability distribution. For any fixed ball configuration and probability distribution, we prove that the SDP relaxation of the $k$-means problem exactly recovers these planted clusters with probability $1-e^{-Ω(n)}$ provided the distance between any two of the ball centers is $>2+ε$, where $ε$ is an explicit function of the configuration of the ball centers, and can be arbitrarily small when $m$ is large.
Sublinear Approximation Algorithms for Boxicity and Related Problems
Venue: arXiv cs.DM 2015
Year: 2015

Boxicity of a graph G(V, E) is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes in $\mathbb{R}^k$. Cubicity is a variant of boxicity, where the axis parallel boxes in the intersection representation are restricted to be of unit length sides. Deciding whether boxicity (resp. cubicity) of a graph is at most k is NP-hard, even for k=2 or 3. Computing these parameters is inapproximable within $O(n^{1 - ε})$-factor, for any $ε>0$ in polynomial time unless NP=ZPP, even for many simple graph classes. In this paper, we give a polynomial time $κ(n)$ factor approximation algorithm for computing boxicity and a $κ(n)\lceil \log \log n\rceil$ factor approximation algorithm for computing the cubicity, where $κ(n) =2\left\lceil\frac{n\sqrt{\log \log n}}{\sqrt{\log n}}\right\rceil$. These o(n) factor approximation algorithms also produce the corresponding box (resp. cube) representations. As a special case, this resolves the question paused by Spinrad about polynomial time construction of o(n) dimensional box representations for boxicity 2 graphs. Other consequences of our approximation algorithm include $O(κ(n))$ factor approximation algorithms for computing the following parameters: the partial order dimension of finite posets, the interval dimension of finite posets, minimum chain cover of bipartite graphs, threshold dimension of split graphs and Ferrer's dimension of digraphs. Each of these parameters is inapproximable within an $O(n^{1 - ε})$-factor, for any $ε>0$ in polynomial time unless NP=ZPP and the algorithms we derive seem to be the first o(n) factor approximation algorithms known for all these problems.
Recursion in RDF Data Shape Languages
Venue: arXiv cs.DB 2015
Year: 2015

An RDF data shape is a description of the expected contents of an RDF document (aka graph) or dataset. A major part of this description is the set of constraints that the document or dataset is required to satisfy. W3C recently (2014) chartered the RDF Data Shapes Working Group to define SHACL, a standard RDF data shape language. We refer to the ability to name and reference shape language elements as recursion. This article provides a precise definition of the meaning of recursion as used in Resource Shape 2.0. The definition of recursion presented in this article is largely independent of language-specific details. We speculate that it also applies to ShEx and to all three of the current proposals for SHACL. In particular, recursion is not permitted in the SHACL-SPARQL proposal, but we conjecture that recursion could be added by using the definition proposed here as a top-level control structure.
Automatic and Transparent Transfer of Theorems along Isomorphisms in the Coq Proof Assistant
Venue: arXiv cs.LO 2015
Year: 2015

In mathematics, it is common practice to have several constructions for the same objects. Mathematicians will identify them modulo isomorphism and will not worry later on which construction they use, as theorems proved for one construction will be valid for all. When working with proof assistants, it is also common to see several data-types representing the same objects. This work aims at making the use of several isomorphic constructions as simple and as transparent as it can be done informally in mathematics. This requires inferring automatically the missing proof-steps. We are designing an algorithm which finds and fills these missing proof-steps and we are implementing it as a plugin for Coq.
A Table-Binning Approach for Visualizing the Past
Venue: arXiv cs.IR 2015
Year: 2015

Large amounts of data are available due to low-cost and high-capacity data storage equipments. We propose a data exploration/visualization method for tabular multi-dimensional, time-varying datasets to present selected items in their global context. The approach is simple and uses a rank-based visualization and a pattern matching functionality based on temporal profiles. Ranking categories can be specified in a flexible way and are used instead of actual values (value reduction into bins) and plotting it over time in an unevenly quantized representation. Patterns that emerge are matched against a set of eight predefined temporal profiles. The graphical summarization of large-scale temporal data is proposed and applicability is tested qualitatively on about eight data sets and the approach is compared to classic line plots and SAX representation
Measuring and mitigating AS-level adversaries against Tor
Venue: arXiv cs.CR 2015
Year: 2015

The popularity of Tor as an anonymity system has made it a popular target for a variety of attacks. We focus on traffic correlation attacks, which are no longer solely in the realm of academic research with recent revelations about the NSA and GCHQ actively working to implement them in practice. Our first contribution is an empirical study that allows us to gain a high fidelity snapshot of the threat of traffic correlation attacks in the wild. We find that up to 40% of all circuits created by Tor are vulnerable to attacks by traffic correlation from Autonomous System (AS)-level adversaries, 42% from colluding AS-level adversaries, and 85% from state-level adversaries. In addition, we find that in some regions (notably, China and Iran) there exist many cases where over 95% of all possible circuits are vulnerable to correlation attacks, emphasizing the need for AS-aware relay-selection. To mitigate the threat of such attacks, we build Astoria--an AS-aware Tor client. Astoria leverages recent developments in network measurement to perform path-prediction and intelligent relay selection. Astoria reduces the number of vulnerable circuits to 2% against AS-level adversaries, under 5% against colluding AS-level adversaries, and 25% against state-level adversaries. In addition, Astoria load balances across the Tor network so as to not overload any set of relays.
Image Reconstruction from Bag-of-Visual-Words
Venue: arXiv cs.CV 2015
Year: 2015

The objective of this work is to reconstruct an original image from Bag-of-Visual-Words (BoVW). Image reconstruction from features can be a means of identifying the characteristics of features. Additionally, it enables us to generate novel images via features. Although BoVW is the de facto standard feature for image recognition and retrieval, successful image reconstruction from BoVW has not been reported yet. What complicates this task is that BoVW lacks the spatial information for including visual words. As described in this paper, to estimate an original arrangement, we propose an evaluation function that incorporates the naturalness of local adjacency and the global position, with a method to obtain related parameters using an external image database. To evaluate the performance of our method, we reconstruct images of objects of 101 kinds. Additionally, we apply our method to analyze object classifiers and to generate novel images via BoVW.
Barcode Annotations for Medical Image Retrieval: A Preliminary Investigation
Venue: arXiv cs.CV 2015
Year: 2015

This paper proposes to generate and to use barcodes to annotate medical images and/or their regions of interest such as organs, tumors and tissue types. A multitude of efficient feature-based image retrieval methods already exist that can assign a query image to a certain image class. Visual annotations may help to increase the retrieval accuracy if combined with existing feature-based classification paradigms. Whereas with annotations we usually mean textual descriptions, in this paper barcode annotations are proposed. In particular, Radon barcodes (RBC) are introduced. As well, local binary patterns (LBP) and local Radon binary patterns (LRBP) are implemented as barcodes. The IRMA x-ray dataset with 12,677 training images and 1,733 test images is used to verify how barcodes could facilitate image retrieval.
Cooperation for interference management: A GDoF perspective
Venue: arXiv cs.IT 2015
Year: 2015

The impact of cooperation on interference management is investigated by studying an elemental wireless network, the so called symmetric interference relay channel (IRC), from a generalized degrees of freedom (GDoF) perspective. This is motivated by the fact that the deployment of relays is considered as a remedy to overcome the bottleneck of current systems in terms of achievable rates. The focus of this work is on the regime in which the interference link is weaker than the source-relay link in the IRC. Our approach towards studying the GDoF goes through the capacity analysis of the linear deterministic IRC (LD-IRC). New upper bounds on the sum-capacity of the LD-IRC based on genie-aided approaches are established. These upper bounds together with some existing upper bounds are achieved by using four novel transmission schemes. Extending the upper bounds and the transmission schemes to the Gaussian case, the GDoF of the Gaussian IRC is characterized for the aforementioned regime. This completes the GDoF results available in the literature for the symmetric GDoF. It is shown that in the strong interference regime, in contrast to the IC, the GDoF is not a monotonically increasing function of the interference level.
Measuring Visibility using Atmospheric Transmission and Digital Surface Model
Venue: arXiv cs.CV 2015
Year: 2015

Reliable and exact assessment of visibility is essential for safe air traffic. In order to overcome the drawbacks of the currently subjective reports from human observers, we present an approach to automatically derive visibility measures by means of image processing. It first exploits image based estimation of the atmospheric transmission describing the portion of the light that is not scattered by atmospheric phenomena (e.g., haze, fog, smoke) and reaches the camera. Once the atmospheric transmission is estimated, a 3D representation of the vicinity (digital surface model: DMS) is used to compute depth measurements for the haze-free pixels and then derive a global visibility estimation for the airport. Results on foggy images demonstrate the validity of the proposed method.