OpenRaiser/Intern-Atlas huggingface dataset:
Cooperative Spectrum Sharing Relaying Protocols With Energy Harvesting Cognitive User
Venue: arXiv cs.NI 2018
Year: 2018

The theory of wireless information and power transfer in energy constrained wireless networks has caught the interest of researchers due to its potential in increasing the lifetime of sensor nodes and mitigate the environment hazards caused by conventional cell batteries. Similarly, the advancements in areas of cooperative spectrum sharing protocols has enabled efficient use of frequency spectrum between a licensed primary user and a secondary user. In this paper, we consider an energy constrained secondary user which harvests energy from the primary signal and relays the primary signal in exchange for the spectrum access. We consider Nakagami-m fading model and propose two key protocols, namely time-splitting cooperative spectrum sharing (TS-CSS) and power-sharing cooperative spectrum sharing (PS-CSS), and derive expressions for the outage probabilities of the primary and secondary user in decode-forward and amplify-forward relaying modes. From the obtained results, it has been shown that the secondary user can carry its own transmission without adversely affecting the performance of the primary user and that PS-CSS protocol outperforms the TS-PSS protocol in terms of outage probability over a wide range of Signal to noise ratio(SNRs). The effect of various system parameters on the outage performance of these protocols have also been studied.
A dual descent algorithm for node-capacitated multiflow problems and its applications
Venue: arXiv cs.DS 2018
Year: 2018

In this paper, we develop an $O((m \log k) {\rm MSF} (n,m,1))$-time algorithm to find a half-integral node-capacitated multiflow of the maximum total flow-value in a network with $n$ nodes, $m$ edges, and $k$ terminals, where ${\rm MSF} (n',m',γ)$ denotes the time complexity of solving the maximum submodular flow problem in a network with $n'$ nodes, $m'$ edges, and the complexity $γ$ of computing the exchange capacity of the submodular function describing the problem. By using Fujishige-Zhang algorithm for submodular flow, we can find a maximum half-integral multiflow in $O(m n^3 \log k)$ time. This is the first combinatorial strongly polynomial time algorithm for this problem. Our algorithm is built on a developing theory of discrete convex functions on certain graph structures. Applications include "ellipsoid-free" combinatorial implementations of a 2-approximation algorithm for the minimum node-multiway cut problem by Garg, Vazirani, and Yannakakis.
Automatic Software Diversity in the Light of Test Suites
Venue: arXiv cs.SE 2018
Year: 2018

A few works address the challenge of automating software diversification, and they all share one core idea: using automated test suites to drive diversification. However, there is is lack of solid understanding of how test suites, programs and transformations interact one with another in this process. We explore this intricate interplay in the context of a specific diversification technique called "sosiefication". Sosiefication generates sosie programs, i.e., variants of a program in which some statements are deleted, added or replaced but still pass the test suite of the original program. Our investigation of the influence of test suites on sosiefication exploits the following observation: test suites cover the different regions of programs in very unequal ways. Hence, we hypothesize that sosie synthesis has different performances on a statement that is covered by one hundred test case and on a statement that is covered by a single test case. We synthesize 24583 sosies on 6 popular open-source Java programs. Our results show that there are two dimensions for diversification. The first one lies in the specification: the more test cases cover a statement, the more difficult it is to synthesize sosies. Yet, to our surprise, we are also able to synthesize sosies on highly tested statements (up to 600 test cases), which indicates an intrinsic property of the programs we study. The second dimension is in the code: we manually explore dozens of sosies and characterize new types of forgiving code regions that are prone to diversification.
Using Inclusion Diagrams as an Alternative to Venn Diagrams to Determine the Validity of Categorical Syllogisms
Venue: arXiv cs.LO 2018
Year: 2018

Inclusion diagrams are introduced as an alternative to using Venn diagrams to determine the validity of categorical syllogisms, and are used here for the analysis of diverse categorical syllogisms. As a preliminary example of a possible generalization of the use of inclusion diagrams, consideration is given also to an argument that includes more than two premises and more than three terms, the classic major, middle and minor terms in categorical syllogisms.
Verificarlo: checking floating point accuracy through Monte Carlo Arithmetic
Venue: arXiv cs.MS 2018
Year: 2018

Numerical accuracy of floating point computation is a well studied topic which has not made its way to the end-user in scientific computing. Yet, it has become a critical issue with the recent requirements for code modernization to harness new highly parallel hardware and perform higher resolution computation. To democratize numerical accuracy analysis, it is important to propose tools and methodologies to study large use cases in a reliable and automatic way. In this paper, we propose verificarlo, an extension to the LLVM compiler to automatically use Monte Carlo Arithmetic in a transparent way for the end-user. It supports all the major languages including C, C++, and Fortran. Unlike source-to-source approaches, our implementation captures the influence of compiler optimizations on the numerical accuracy. We illustrate how Monte Carlo Arithmetic using the verificarlo tool outperforms the existing approaches on various use cases and is a step toward automatic numerical analysis.
Modeling and interpolation of the ambient magnetic field by Gaussian processes
Venue: arXiv cs.RO 2018
Year: 2018

Anomalies in the ambient magnetic field can be used as features in indoor positioning and navigation. By using Maxwell's equations, we derive and present a Bayesian non-parametric probabilistic modeling approach for interpolation and extrapolation of the magnetic field. We model the magnetic field components jointly by imposing a Gaussian process (GP) prior on the latent scalar potential of the magnetic field. By rewriting the GP model in terms of a Hilbert space representation, we circumvent the computational pitfalls associated with GP modeling and provide a computationally efficient and physically justified modeling tool for the ambient magnetic field. The model allows for sequential updating of the estimate and time-dependent changes in the magnetic field. The model is shown to work well in practice in different applications: we demonstrate mapping of the magnetic field both with an inexpensive Raspberry Pi powered robot and on foot using a standard smartphone.
Fair and Square: Cake-Cutting in Two Dimensions
Venue: arXiv cs.GT 2018
Year: 2018

We consider the classic problem of fairly dividing a heterogeneous good ("cake") among several agents with different valuations. Classic cake-cutting procedures either allocate each agent a collection of disconnected pieces, or assume that the cake is a one-dimensional interval. In practice, however, the two-dimensional shape of the allotted pieces is important. In particular, when building a house or designing an advertisement in printed or electronic media, squares are more usable than long and narrow rectangles. We thus introduce and study the problem of fair two-dimensional division wherein the allotted pieces must be of some restricted two-dimensional geometric shape(s), particularly squares and fat rectangles. Adding such geometric constraints re-opens most questions and challenges related to cake-cutting. Indeed, even the most elementary fairness criterion --- proportionality --- can no longer be guaranteed. In this paper we thus examine the level of proportionality that can be guaranteed, providing both impossibility results and constructive division procedures.
Random Irregular Block-hierarchical Networks: Algorithms for Computation of Main Properties
Venue: arXiv cs.DS 2018
Year: 2018

In this paper, the class of random irregular block-hierarchical networks is defined and algorithms for generation and calculation of network properties are described. The algorithms presented for this class of networks are more efficient than known algorithms both in computation time and memory usage and can be used to analyze topological properties of such networks. The algorithms are implemented in the system created by the authors for the study of topological and statistical properties of random networks.
SLAP: Simultaneous Localization and Planning Under Uncertainty for Physical Mobile Robots via Dynamic Replanning in Belief Space: Extended version
Venue: arXiv cs.RO 2018
Year: 2018

Simultaneous localization and Planning (SLAP) is a crucial ability for an autonomous robot operating under uncertainty. In its most general form, SLAP induces a continuous POMDP (partially-observable Markov decision process), which needs to be repeatedly solved online. This paper addresses this problem and proposes a dynamic replanning scheme in belief space. The underlying POMDP, which is continuous in state, action, and observation space, is approximated offline via sampling-based methods, but operates in a replanning loop online to admit local improvements to the coarse offline policy. This construct enables the proposed method to combat changing environments and large localization errors, even when the change alters the homotopy class of the optimal trajectory. It further outperforms the state-of-the-art FIRM (Feedback-based Information RoadMap) method by eliminating unnecessary stabilization steps. Applying belief space planning to physical systems brings with it a plethora of challenges. A key focus of this paper is to implement the proposed planner on a physical robot and show the SLAP solution performance under uncertainty, in changing environments and in the presence of large disturbances, such as a kidnapped robot situation.
Vehicle Color Recognition using Convolutional Neural Network
Venue: arXiv cs.CV 2018
Year: 2018

Vehicle color information is one of the important elements in ITS (Intelligent Traffic System). In this paper, we present a vehicle color recognition method using convolutional neural network (CNN). Naturally, CNN is designed to learn classification method based on shape information, but we proved that CNN can also learn classification based on color distribution. In our method, we convert the input image to two different color spaces, HSV and CIE Lab, and run it to some CNN architecture. The training process follow procedure introduce by Krizhevsky, that learning rate is decreasing by factor of 10 after some iterations. To test our method, we use publicly vehicle color recognition dataset provided by Chen. The results, our model outperform the original system provide by Chen with 2% higher overall accuracy.
Minimizing Regret in Discounted-Sum Games
Venue: arXiv cs.GT 2018
Year: 2018

In this paper, we study the problem of minimizing regret in discounted-sum games played on weighted game graphs. We give algorithms for the general problem of computing the minimal regret of the controller (Eve) as well as several variants depending on which strategies the environment (Adam) is permitted to use. We also consider the problem of synthesizing regret-free strategies for Eve in each of these scenarios.
Privacy by Design: On the Formal Design and Conformance Check of Personal Data Protection Policies and Architectures
Venue: arXiv cs.CR 2018
Year: 2018

The new General Data Protection Regulation (GDPR) will take effect in May 2018, and hence, designing compliant data protection policies and system architectures became crucial for organizations to avoid penalties. Unfortunately, the regulations given in a textual format can be easily misinterpreted by the policy and system designers, which also making the conformance check error-prone for auditors. In this paper, we apply formal approach to facilitate systematic design of policies and architectures in an unambiguous way, and provide a framework for mathematically sound conformance checks against the current data protection regulations. We propose a (semi-)formal approach for specifying and reasoning about data protection policies and architectures as well as defining conformance relations between architectures and policies. The usability of our proposed approach is demonstrated on a smart metering service case study.
Reorganizing topologies of Steiner trees to accelerate their elimination
Venue: arXiv cs.DS 2018
Year: 2018

We describe a technique to reorganize topologies of Steiner trees by exchanging neighbors of adjacent Steiner points. We explain how to use the systematic way of building trees, and therefore topologies, to find the correct topology after nodes have been exchanged. Topology reorganizations can be inserted into the enumeration scheme commonly used by exact algorithms for the Euclidean Steiner tree problem in $d$-space, providing a method of improvement different than the usual approaches. As an example, we show how topology reorganizations can be used to dynamically change the exploration of the usual branch-and-bound tree when two Steiner points collide during the optimization process. We also turn our attention to the erroneous use of a pre-optimization lower bound in the original algorithm and give an example to confirm its usage is incorrect. In order to provide numerical results on correct solutions, we use planar equilateral points to quickly compute this lower bound, even in dimensions higher than two. Finally, we describe planar twin trees, identical trees yielded by different topologies, whose generalization to higher dimensions could open a new way of building Steiner trees.
Diffusion-like recommendation with enhanced similarity of objects
Venue: arXiv cs.IR 2018
Year: 2018

In last decades, diversity and accuracy have been regarded as two important measures in evaluating a recommendation model. However, a clear concern is that a model focusing excessively on one measure will put the other one at risk, thus it is not easy to greatly improve diversity and accuracy simultaneously. In this paper, we propose to enhance the Resource-Allocation (RA) similarity in resource transfer equations of diffusion-like models, by giving a tunable exponent to the RA similarity, and traversing the value of the exponent to achieve the optimal recommendation results. In this way, we can increase the recommendation scores (allocated resource) of many unpopular objects. Experiments on three benchmark data sets, MovieLens, Netflix, and RateYourMusic show that the modified models can yield remarkable performance improvement compared with the original ones.
Cross-scale predictive dictionaries
Venue: arXiv cs.CV 2018
Year: 2018

Sparse representations using data dictionaries provide an efficient model particularly for signals that do not enjoy alternate analytic sparsifying transformations. However, solving inverse problems with sparsifying dictionaries can be computationally expensive, especially when the dictionary under consideration has a large number of atoms. In this paper, we incorporate additional structure on to dictionary-based sparse representations for visual signals to enable speedups when solving sparse approximation problems. The specific structure that we endow onto sparse models is that of a multi-scale modeling where the sparse representation at each scale is constrained by the sparse representation at coarser scales. We show that this cross-scale predictive model delivers significant speedups, often in the range of 10-60$\times$, with little loss in accuracy for linear inverse problems associated with images, videos, and light fields.
A Simple Hierarchical Pooling Data Structure for Loop Closure
Venue: arXiv cs.CV 2018
Year: 2018

We propose a data structure obtained by hierarchically averaging bag-of-word descriptors during a sequence of views that achieves average speedups in large-scale loop closure applications ranging from 4 to 20 times on benchmark datasets. Although simple, the method works as well as sophisticated agglomerative schemes at a fraction of the cost with minimal loss of performance.
Uniqueness of Equilibria in Atomic Splittable Polymatroid Congestion Games
Venue: arXiv cs.GT 2018
Year: 2018

We study uniqueness of Nash equilibria in atomic splittable congestion games and derive a uniqueness result based on polymatroid theory: when the strategy space of every player is a bidirectional flow polymatroid, then equilibria are unique. Bidirectional flow polymatroids are introduced as a subclass of polymatroids possessing certain exchange properties. We show that important cases such as base orderable matroids can be recovered as a special case of bidirectional flow polymatroids. On the other hand we show that matroidal set systems are in some sense necessary to guarantee uniqueness of equilibria: for every atomic splittable congestion game with at least three players and nonmatroidal set systems per player, there is an isomorphic game having multiple equilibria. Our results leave a gap between base orderable matroids and general matroids for which we do not know whether equilibria are unique.
Social Network Analysis of the Caste-Based Reservation System in India
Venue: arXiv cs.SI 2018
Year: 2018

It has been argued that the reservation system in India, which has existed since the time of Indian Independence (1947), has caused more havoc and degradation than progress. This being a popular public opinion, has not been based on any rigorous scientific study or research. In this paper, we revisit the cultural divide among the Indian population from a purely social network based approach. We study the distinct cluster formation that takes place in the Indian community and find that this is largely due to the effect of caste-based homophily. To study the impact of the reservation system, we define a new parameter called social distance that represents the social capital associated with each individual in the backward class. We study the changes that take place with regard to the average social distance of a cluster when a new link is established between the clusters which in its essence, is what the reservation system is accomplishing. Our extensive study calls for the change in the mindset of people in India. Although the animosity towards the reservation system could be rooted due to historical influence, hero worship and herd mentality, our results make it clear that the system has had a considerable impact on the country's overall development by bridging the gap between the conflicting social groups. The results also have been verified using the survey and are discussed in the paper.
Live Exploration of Dynamic Rings
Venue: arXiv cs.DC 2018
Year: 2018

In the graph exploration problem, a team of mobile computational entities, called agents, arbitrarily positioned at some nodes of a graph, must cooperate so that each node is eventually visited by at least one agent. In the literature, the main focus has been on graphs that are static; that is, the topology is either invariant in time or subject to localized changes. The few studies on exploration of dynamic graphs have been almost all limited to the centralized case (i.e., assuming complete a priori knowledge of the changes and the times of their occurrence). We investigate the decentralized exploration of dynamic graphs (i.e., when the agents are unaware of the location and timing of the changes) focusing, in this paper, on dynamic systems whose underlying graph is a ring. We first consider the fully-synchronous systems traditionally assumed in the literature; i.e., all agents are active at each time step. We then introduce the notion of semi-synchronous systems, where only a subset of agents might be active at each time step (the choice of the subset is made by an adversary); this model is common in the context of mobile agents in continuous spaces but has never been studied before for agents moving in graphs. Our main focus is on the impact that the level of synchrony as well as other factors such as anonymity, knowledge of the size of the ring, and chirality (i.e., common orientation) have on the solvability of the problem, focusing on the minimum number of agents necessary. We draw an extensive map of feasibility, and of complexity in terms of minimum number of agent movements. All our sufficiency proofs are constructive, and almost all our solution protocols are asymptotically optimal.
Discontinuous Galerkin Deterministic Solvers for a Boltzmann-Poisson Model of Hot Electron Transport by Averaged Empirical Pseudopotential Band Structures
Venue: arXiv cs.CE 2018
Year: 2018

The purpose of this work is to incorporate numerically, in a discontinuous Galerkin (DG) solver of a Boltzmann-Poisson model for hot electron transport, an electronic conduction band whose values are obtained by the spherical averaging of the full band structure given by a local empirical pseudopotential method (EPM) around a local minimum of the conduction band for silicon, as a midpoint between a radial band model and an anisotropic full band, in order to provide a more accurate physical description of the electron group velocity and conduction energy band structure in a semiconductor. This gives a better quantitative description of the transport and collision phenomena that fundamentally define the behaviour of the Boltzmann - Poisson model for electron transport used in this work. The numerical values of the derivatives of this conduction energy band, needed for the description of the electron group velocity, are obtained by means of a cubic spline interpolation. The EPM-Boltzmann-Poisson transport with this spherically averaged EPM calculated energy surface is numerically simulated and compared to the output of traditional analytic band models such as the parabolic and Kane bands, numerically implemented too, for the case of 1D $n^+-n-n^+$ silicon diodes with 400nm and 50nm channels. Quantitative differences are observed in the kinetic moments related to the conduction energy band used, such as mean velocity, average energy, and electric current (momentum).
Dynamic Game Semantics
Venue: arXiv cs.LO 2018
Year: 2018

The present paper gives a mathematical, in particular, syntax-independent, formulation of intensionality and dynamics of computation in terms of games and strategies. Specifically, we give a game semantics for a higher-order programming language that distinguishes programs with the same value yet different algorithms (or intensionality), equipped with the hiding operation on strategies that precisely corresponds to the (small-step) operational semantics (or dynamics) of the language. Categorically, our games and strategies give rise to a cartesian closed bicategory, and our game semantics forms an instance of a generalization of the standard interpretation of functional programming languages in cartesian closed categories. This work is intended to be the first step towards a mathematical (both categorical and game-semantic) foundation of intensional and dynamic aspects of logic and computation; our approach should be applicable to a wide range of logics and computations.