OpenRaiser/Intern-Atlas huggingface dataset:
On the Rate of Information Loss in Memoryless Systems
Venue: arXiv cs.IT 2013
Year: 2013

In this work we present results about the rate of (relative) information loss induced by passing a real-valued, stationary stochastic process through a memoryless system. We show that for a special class of systems the information loss rate is closely related to the difference of differential entropy rates of the input and output processes. It is further shown that the rate of (relative) information loss is bounded from above by the (relative) information loss the system induces on a random variable distributed according to the process's marginal distribution. As a side result, in this work we present sufficient conditions such that for a continuous-valued Markovian input process also the output process possesses the Markov property.
Open Tiled Manycore System-on-Chip
Venue: arXiv cs.AR 2013
Year: 2013

Manycore System-on-Chip include an increasing amount of processing elements and have become an important research topic for improvements of both hardware and software. While research can be conducted using system simulators, prototyping requires a variety of components and is very time consuming. With the Open Tiled Manycore System-on-Chip (OpTiMSoC) we aim at building such an environment for use in our and other research projects as prototyping platform. This paper describes the project goals and aspects of OpTiMSoC and summarizes the current status and ideas.
A composition theorem for bisimulation functions
Venue: arXiv cs.SY 2013
Year: 2013

The standard engineering approach to modelling of complex systems is highly compositional. In order to be able to understand (or to control) the behavior of a complex dynamical systems, it is often desirable, if not necessary, to view this system as an interconnection of smaller interacting subsystems, each of these subsystems having its own functionalities. In this paper, we propose a compositional approach to the computation of bisimulation functions for dynamical systems. Bisimulation functions are quantitative generalizations of the classical bisimulation relations. They have been shown useful for simulation-based verification or for the computation of approximate symbolic abstractions of dynamical systems. In this technical note, we present a constructive result for the composition of bisimulation functions. For a complex dynamical system consisting of several interconnected subsystems, it allows us to compute a bisimulation function from the knowledge of a bisimulation function for each of the subsystem.
On Refinements of Boolean and Parametric Modal Transition Systems
Venue: arXiv cs.LO 2013
Year: 2013

We consider the extensions of modal transition systems (MTS), namely Boolean MTS and parametric MTS and we investigate the refinement problems over both classes. Firstly, we reduce the problem of modal refinement over both classes to a problem solvable by a QBF solver and provide experimental results showing our technique scales well. Secondly, we extend the algorithm for thorough refinement of MTS providing better complexity then via reductions to previously studied problems. Finally, we investigate the relationship between modal and thorough refinement on the two classes and show how the thorough refinement can be approximated by the modal refinement.
Automata with Generalized Rabin Pairs for Probabilistic Model Checking and LTL Synthesis
Venue: arXiv cs.LO 2013
Year: 2013

The model-checking problem for probabilistic systems crucially relies on the translation of LTL to deterministic Rabin automata (DRW). Our recent Safraless translation for the LTL(F,G) fragment produces smaller automata as compared to the traditional approach. In this work, instead of DRW we consider deterministic automata with acceptance condition given as disjunction of generalized Rabin pairs (DGRW). The Safraless translation of LTL(F,G) formulas to DGRW results in smaller automata as compared to DRW. We present algorithms for probabilistic model-checking as well as game solving for DGRW conditions. Our new algorithms lead to improvement both in terms of theoretical bounds as well as practical evaluation. We compare PRISM with and without our new translation, and show that the new translation leads to significant improvements.
Quality-Aware Coding and Relaying for 60 GHz Real-Time Wireless Video Broadcasting
Venue: arXiv cs.NI 2013
Year: 2013

Wireless streaming of high-definition video is a promising application for 60 GHz links, since multi-Gigabit/s data rates are possible. In particular we consider a sports stadium broadcasting system where video signals from multiple cameras are transmitted to a central location. Due to the high pathloss of 60\,GHz radiation over the large distances encountered in this setting, the use of relays is required. This paper designs a quality-aware coding and relaying algorithm for maximization of the overall video quality. We consider the setting that the source can split its data stream into parallel streams, which can be transmitted via different relays to the destination. For this, we derive the related formulation and re-formulate it as convex programming, which can guarantee optimal solutions.
Parallel Gaussian Process Optimization with Upper Confidence Bound and Pure Exploration
Venue: arXiv cs.LG 2013
Year: 2013

In this paper, we consider the challenge of maximizing an unknown function f for which evaluations are noisy and are acquired with high cost. An iterative procedure uses the previous measures to actively select the next estimation of f which is predicted to be the most useful. We focus on the case where the function can be evaluated in parallel with batches of fixed size and analyze the benefit compared to the purely sequential procedure in terms of cumulative regret. We introduce the Gaussian Process Upper Confidence Bound and Pure Exploration algorithm (GP-UCB-PE) which combines the UCB strategy and Pure Exploration in the same batch of evaluations along the parallel iterations. We prove theoretical upper bounds on the regret with batches of size K for this procedure which show the improvement of the order of sqrt{K} for fixed iteration cost over purely sequential versions. Moreover, the multiplicative constants involved have the property of being dimension-free. We also confirm empirically the efficiency of GP-UCB-PE on real and synthetic problems compared to state-of-the-art competitors.
Simple strategies for Banach-Mazur games and fairly correct systems
Venue: arXiv cs.LO 2013
Year: 2013

In 2006, Varacca and Völzer proved that on finite graphs, omega-regular large sets coincide with omega-regular sets of probability 1, by using the existence of positional strategies in the related Banach-Mazur games. Motivated by this result, we try to understand relations between sets of probability 1 and various notions of simple strategies (including those introduced in a recent paper of Grädel and Lessenich). Then, we introduce a generalisation of the classical Banach-Mazur game and in particular, a probabilistic version whose goal is to characterise sets of probability 1 (as classical Banach-Mazur games characterise large sets). We obtain a determinacy result for these games, when the winning set is a countable intersection of open sets.
A Semantics for Approximate Program Transformations
Venue: arXiv cs.PL 2013
Year: 2013

An approximate program transformation is a transformation that can change the semantics of a program within a specified empirical error bound. Such transformations have wide applications: they can decrease computation time, power consumption, and memory usage, and can, in some cases, allow implementations of incomputable operations. Correctness proofs of approximate program transformations are by definition quantitative. Unfortunately, unlike with standard program transformations, there is as of yet no modular way to prove correctness of an approximate transformation itself. Error bounds must be proved for each transformed program individually, and must be re-proved each time a program is modified or a different set of approximations are applied. In this paper, we give a semantics that enables quantitative reasoning about a large class of approximate program transformations in a local, composable way. Our semantics is based on a notion of distance between programs that defines what it means for an approximate transformation to be correct up to an error bound. The key insight is that distances between programs cannot in general be formulated in terms of metric spaces and real numbers. Instead, our semantics admits natural notions of distance for each type construct; for example, numbers are used as distances for numerical data, functions are used as distances for functional data, an polymorphic lambda-terms are used as distances for polymorphic data. We then show how our semantics applies to two example approximations: replacing reals with floating-point numbers, and loop perforation.
Indexes for Jumbled Pattern Matching in Strings, Trees and Graphs
Venue: arXiv cs.DS 2013
Year: 2013

We consider how to index strings, trees and graphs for jumbled pattern matching when we are asked to return a match if one exists. For example, we show how, given a tree containing two colours, we can build a quadratic-space index with which we can find a match in time proportional to the size of the match. We also show how we need only linear space if we are content with approximate matches.
DORI: Distributed Outdoor Robotic Instruments
Venue: arXiv cs.RO 2013
Year: 2013

DORI (Distributed Outdoor Robotic Instruments) is a remotely controlled vehicle that is designed to simulate a planetary exploration mission. DORI is equipped with over 20 environmental sensors and can perform basic data analysis, logging and remote upload. The individual components are distributed across a fault-tolerant bus for redundancy. A partial sensor list includes atmospheric pressure, rainfall, wind speed, GPS, gyroscopic inertia, linear acceleration, magnetic field strength, temperature, laser and ultrasonic distance sensing, as well as digital audio and video capture. The project uses recycled consumer electronics devices as a low-cost source for sensor components. This report describes the hardware design of DORI including sensor electronics, embedded firmware, and physical construction.
Maximum-rate Transmission with Improved Diversity Gain for Interference Networks
Venue: arXiv cs.IT 2013
Year: 2013

Interference alignment (IA) was shown effective for interference management to improve transmission rate in terms of the degree of freedom (DoF) gain. On the other hand, orthogonal space-time block codes (STBCs) were widely used in point-to-point multi-antenna channels to enhance transmission reliability in terms of the diversity gain. In this paper, we connect these two ideas, i.e., IA and space-time block coding, to improve the designs of alignment precoders for multi-user networks. Specifically, we consider the use of Alamouti codes for IA because of its rate-one transmission and achievability of full diversity in point-to-point systems. The Alamouti codes protect the desired link by introducing orthogonality between the two symbols in one Alamouti codeword, and create alignment at the interfering receiver. We show that the proposed alignment methods can maintain the maximum DoF gain and improve the ergodic mutual information in the long-term regime, while increasing the diversity gain to 2 in the short-term regime. The presented examples of interference networks have two antennas at each node and include the two-user X channel, the interferring multi-access channel (IMAC), and the interferring broadcast channel (IBC).
Parameterized Complexity of 1-Planarity
Venue: arXiv cs.DS 2013
Year: 2013

We consider the problem of finding a 1-planar drawing for a general graph, where a 1-planar drawing is a drawing in which each edge participates in at most one crossing. Since this problem is known to be NP-hard we investigate the parameterized complexity of the problem with respect to the vertex cover number, tree-depth, and cyclomatic number. For these parameters we construct fixed-parameter tractable algorithms. However, the problem remains NP-complete for graphs of bounded bandwidth, pathwidth, or treewidth.
Isomorphic Strategy Spaces in Game Theory
Venue: arXiv cs.GT 2013
Year: 2013

This book summarizes ongoing research introducing probability space isomorphic mappings into the strategy spaces of game theory. This approach is motivated by discrepancies between probability theory and game theory when applied to the same strategic situation. In particular, probability theory and game theory can disagree on calculated values of the Fisher information, the log likelihood function, entropy gradients, the rank and Jacobian of variable transforms, and even the dimensionality and volume of the underlying probability parameter spaces. These differences arise as probability theory employs structure preserving isomorphic mappings when constructing strategy spaces to analyze games. In contrast, game theory uses weaker mappings which change some of the properties of the underlying probability distributions within the mixed strategy space. Here, we explore how using strong isomorphic mappings to define game strategy spaces can alter rational outcomes in simple games . Specific example games considered are the chain store paradox, the trust game, the ultimatum game, the public goods game, the centipede game, and the iterated prisoner's dilemma. In general, our approach provides rational outcomes which are consistent with observed human play and might thereby resolve some of the paradoxes of game theory.
A Survey on Multi-view Learning
Venue: arXiv cs.LG 2013
Year: 2013

In recent years, a great many methods of learning from multi-view data by considering the diversity of different views have been proposed. These views may be obtained from multiple sources or different feature subsets. In trying to organize and highlight similarities and differences between the variety of multi-view learning approaches, we review a number of representative multi-view learning algorithms in different areas and classify them into three groups: 1) co-training, 2) multiple kernel learning, and 3) subspace learning. Notably, co-training style algorithms train alternately to maximize the mutual agreement on two distinct views of the data; multiple kernel learning algorithms exploit kernels that naturally correspond to different views and combine kernels either linearly or non-linearly to improve learning performance; and subspace learning algorithms aim to obtain a latent subspace shared by multiple views by assuming that the input views are generated from this latent subspace. Though there is significant variance in the approaches to integrating multiple views to improve learning performance, they mainly exploit either the consensus principle or the complementary principle to ensure the success of multi-view learning. Since accessing multiple views is the fundament of multi-view learning, with the exception of study on learning a model from multiple views, it is also valuable to study how to construct multiple views and how to evaluate these views. Overall, by exploring the consistency and complementary properties of different views, multi-view learning is rendered more effective, more promising, and has better generalization ability than single-view learning.
A Framework for Reproducible, Interactive Research: Application to health and social sciences
Venue: arXiv cs.DL 2013
Year: 2013

The aim of this article is to introduce a reporting framework for reproducible, interactive research applied to Big Clinical Data, based on open source technologies. The framework is constituted by the following three axes: (i) data, (ii) analytical codes and (iii) dissemination. In this paper, different documentation formats and online repositories are introduced. To integrate and manage the reproducible contents, we propose the R Language as the tool of choice. All the information is then published and gathered in a website for different projects. This framework is free and user friendly and is proposed to enhance reproducibility of health-science reports.
Mapping EINS -- An exercise in mapping the Network of Excellence in Internet Science
Venue: arXiv cs.DL 2013
Year: 2013

This paper demonstrates the application of bibliometric mapping techniques in the area of funded research networks. We discuss how science maps can be used to facilitate communication inside newly formed communities, but also to account for their activities to funding agencies. We present the mapping of EINS as case -- an FP7 funded Network of Excellence. Finally, we discuss how these techniques can be used to serve as knowledge maps for interdisciplinary working experts.
Request Complexity of VNet Topology Extraction: Dictionary-Based Attacks
Venue: arXiv cs.NI 2013
Year: 2013

The network virtualization paradigm envisions an Internet where arbitrary virtual networks (VNets) can be specified and embedded over a shared substrate (e.g., the physical infrastructure). As VNets can be requested at short notice and for a desired time period only, the paradigm enables a flexible service deployment and an efficient resource utilization. This paper investigates the security implications of such an architecture. We consider a simple model where an attacker seeks to extract secret information about the substrate topology, by issuing repeated VNet embedding requests. We present a general framework that exploits basic properties of the VNet embedding relation to infer the entire topology. Our framework is based on a graph motif dictionary applicable for various graph classes. Moreover, we provide upper bounds on the request complexity, the number of requests needed by the attacker to succeed.
Nonlinear Basis Pursuit
Venue: arXiv cs.IT 2013
Year: 2013

In compressive sensing, the basis pursuit algorithm aims to find the sparsest solution to an underdetermined linear equation system. In this paper, we generalize basis pursuit to finding the sparsest solution to higher order nonlinear systems of equations, called nonlinear basis pursuit. In contrast to the existing nonlinear compressive sensing methods, the new algorithm that solves the nonlinear basis pursuit problem is convex and not greedy. The novel algorithm enables the compressive sensing approach to be used for a broader range of applications where there are nonlinear relationships between the measurements and the unknowns.
Large System Analysis of Linear Precoding in MISO Broadcast Channels with Confidential Messages
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we study the performance of regularized channel inversion (RCI) precoding in large MISO broadcast channels with confidential messages (BCC). We obtain a deterministic approximation for the achievable secrecy sum-rate which is almost surely exact as the number of transmit antennas $M$ and the number of users $K$ grow to infinity in a fixed ratio $β=K/M$. We derive the optimal regularization parameter $ξ$ and the optimal network load $β$ that maximize the per-antenna secrecy sum-rate. We then propose a linear precoder based on RCI and power reduction (RCI-PR) that significantly increases the high-SNR secrecy sum-rate for $1<β<2$. Our proposed precoder achieves a per-user secrecy rate which has the same high-SNR scaling factor as both the following upper bounds: (i) the rate of the optimum RCI precoder without secrecy requirements, and (ii) the secrecy capacity of a single-user system without interference. Furthermore, we obtain a deterministic approximation for the secrecy sum-rate achievable by RCI precoding in the presence of channel state information (CSI) error. We also analyze the performance of our proposed RCI-PR precoder with CSI error, and we determine how the error must scale with the SNR in order to maintain a given rate gap to the case with perfect CSI.
Fundamental Limits of Distributed Caching in D2D Wireless Networks
Venue: arXiv cs.IT 2013
Year: 2013

We consider a wireless Device-to-Device (D2D) network where communication is restricted to be single-hop, users make arbitrary requests from a finite library of possible files and user devices cache information in the form of linear combinations of packets from the files in the library (coded caching). We consider the combined effect of coding in the caching and delivery phases, achieving "coded multicast gain", and of spatial reuse due to local short-range D2D communication. Somewhat counterintuitively, we show that the coded multicast gain and the spatial reuse gain do not cumulate, in terms of the throughput scaling laws. In particular, the spatial reuse gain shown in our previous work on uncoded random caching and the coded multicast gain shown in this paper yield the same scaling laws behavior, but no further scaling law gain can be achieved by using both coded caching and D2D spatial reuse.
Commonsense Reasoning and Large Network Analysis: A Computational Study of ConceptNet 4
Venue: arXiv cs.AI 2013
Year: 2013

In this report a computational study of ConceptNet 4 is performed using tools from the field of network analysis. Part I describes the process of extracting the data from the SQL database that is available online, as well as how the closure of the input among the assertions in the English language is computed. This part also performs a validation of the input as well as checks for the consistency of the entire database. Part II investigates the structural properties of ConceptNet 4. Different graphs are induced from the knowledge base by fixing different parameters. The degrees and the degree distributions are examined, the number and sizes of connected components, the transitivity and clustering coefficient, the cores, information related to shortest paths in the graphs, and cliques. Part III investigates non-overlapping, as well as overlapping communities that are found in ConceptNet 4. Finally, Part IV describes an investigation on rules.
Visual Room-Awareness for Humanoid Robot Self-Localization
Venue: arXiv cs.RO 2013
Year: 2013

Humanoid robots without internal sensors such as a compass tend to lose their orientation after a fall. Furthermore, re-initialisation is often ambiguous due to symmetric man-made environments. The room-awareness module proposed here is inspired by the results of psychological experiments and improves existing self-localization strategies by mapping and matching the visual background with colour histograms. The matching algorithm uses a particle-filter to generate hypotheses of the viewing directions independent of the self-localization algorithm and generates confidence values for various possible poses. The robot's behaviour controller uses those confidence values to control self-localization algorithm to converge to the most likely pose and prevents the algorithm from getting stuck in local minima. Experiments with a symmetric Standard Platform League RoboCup playing field with a simulated and a real humanoid NAO robot show the significant improvement of the system.
Conceptual Understanding of Computer Program Execution: Application to C++
Venue: arXiv cs.PL 2013
Year: 2013

A visual programming language uses pictorial tools such as diagrams to represent its structural units and control stream. It is useful for enhancing understanding, maintenance, verification, testing, and parallelism. This paper proposes a diagrammatic methodology that produces a conceptual representation of instructions for programming source codes. Without loss of generality in the potential for using the methodology in a wider range of applications, this paper focuses on using these diagrams in teaching of C++ programming. C++ programming constructs are represented in the proposed method in order to show that it can provide a foundation for understanding the behavior of running programs. Applying the method to actual C++ classes demonstrates that it improves understanding of the activities in the computer system corresponding to a C++ program.