OpenRaiser/Intern-Atlas huggingface dataset:
HySIM: A Hybrid Spectrum and Information Market for TV White Space Networks
Venue: arXiv cs.GT 2016
Year: 2016

We propose a hybrid spectrum and information market for a database-assisted TV white space network, where the geo-location database serves as both a spectrum market platform and an information market platform. We study the inter- actions among the database operator, the spectrum licensee, and unlicensed users systematically, using a three-layer hierarchical model. In Layer I, the database and the licensee negotiate the commission fee that the licensee pays for using the spectrum market platform. In Layer II, the database and the licensee compete for selling information or channels to unlicensed users. In Layer III, unlicensed users determine whether they should buy the exclusive usage right of licensed channels from the licensee, or the information regarding unlicensed channels from the database. Analyzing such a three-layer model is challenging due to the co-existence of both positive and negative network externalities in the information market. We characterize how the network externalities affect the equilibrium behaviours of all parties involved. Our numerical results show that the proposed hybrid market can improve the network profit up to 87%, compared with a pure information market. Meanwhile, the achieved network profit is very close to the coordinated benchmark solution (the gap is less than 4% in our simulation).
An Approach for Self-Adaptive Path Loss Modeling for Accurate Positioning in Underground Environments
Venue: arXiv cs.NI 2016
Year: 2016

This paper proposes a real-time self-adaptive approach for accurate path loss estimation in underground mines or tunnels based on signal strength measurements from heterogeneous radio communication technologies. The proposed model features simplicity of implementation. The methodology was validated in simulations as well as was verified by measurements taken in real environments. The proposed method leverages accuracy of positioning matching to the existing approaches while requiring smaller engineering efforts.
Some Gabidulin Codes cannot be List Decoded Efficiently at any Radius
Venue: arXiv cs.IT 2016
Year: 2016

Gabidulin codes can be seen as the rank-metric equivalent of Reed-Solomon codes. It was recently proven, using subspace polynomials, that Gabidulin codes cannot be list decoded beyond the so-called Johnson radius. In another result, cyclic subspace codes were constructed by inspecting the connection between subspaces and their subspace polynomials. In this paper, these subspace codes are used to prove two bounds on the list size in decoding certain Gabidulin codes. The first bound is an existential one, showing that exponentially-sized lists exist for codes with specific parameters. The second bound presents exponentially-sized lists explicitly, for a different set of parameters. Both bounds rule out the possibility of efficiently list decoding several families of Gabidulin codes for any radius beyond half the minimum distance. Such a result was known so far only for non-linear rank-metric codes, and not for Gabidulin codes. Using a standard operation called lifting, identical results also follow for an important class of constant dimension subspace codes.
Multistatic Cloud Radar Systems: Joint Sensing and Communication Design
Venue: arXiv cs.IT 2016
Year: 2016

In a multistatic cloud radar system, receive sensors measure signals sent by a transmit element and reflected from a target and possibly clutter, in the presence of interference and noise. The receive sensors communicate over non-ideal backhaul links with a fusion center, or cloud processor, where the presence or absence of the target is determined. The backhaul architecture can be characterized either by an orthogonal-access channel or by a non-orthogonal multiple-access channel. Two backhaul transmission strategies are considered, namely compress-and-forward (CF), which is well suited for the orthogonal-access backhaul, and amplify-and-forward (AF), which leverages the superposition property of the non-orthogonal multiple-access channel. In this paper, the joint optimization of the sensing and backhaul communication functions of the cloud radar system is studied. Specifically, the transmitted waveform is jointly optimized with backhaul quantization in the case of CF backhaul transmission and with the amplifying gains of the sensors for the AF backhaul strategy. In both cases, the information-theoretic criterion of the Bhattacharyya distance is adopted as a metric for the detection performance. Algorithmic solutions based on successive convex approximation are developed under different assumptions on the available channel state information (CSI). Numerical results demonstrate that the proposed schemes outperform conventional solutions that perform separate optimizations of the waveform and backhaul operation, as well as the standard distributed detection approach.
Active Mean Fields for Probabilistic Image Segmentation: Connections with Chan-Vese and Rudin-Osher-Fatemi Models
Venue: arXiv cs.CV 2016
Year: 2016

Segmentation is a fundamental task for extracting semantically meaningful regions from an image. The goal of segmentation algorithms is to accurately assign object labels to each image location. However, image-noise, shortcomings of algorithms, and image ambiguities cause uncertainty in label assignment. Estimating the uncertainty in label assignment is important in multiple application domains, such as segmenting tumors from medical images for radiation treatment planning. One way to estimate these uncertainties is through the computation of posteriors of Bayesian models, which is computationally prohibitive for many practical applications. On the other hand, most computationally efficient methods fail to estimate label uncertainty. We therefore propose in this paper the Active Mean Fields (AMF) approach, a technique based on Bayesian modeling that uses a mean-field approximation to efficiently compute a segmentation and its corresponding uncertainty. Based on a variational formulation, the resulting convex model combines any label-likelihood measure with a prior on the length of the segmentation boundary. A specific implementation of that model is the Chan-Vese segmentation model (CV), in which the binary segmentation task is defined by a Gaussian likelihood and a prior regularizing the length of the segmentation boundary. Furthermore, the Euler-Lagrange equations derived from the AMF model are equivalent to those of the popular Rudin-Osher-Fatemi (ROF) model for image denoising. Solutions to the AMF model can thus be implemented by directly utilizing highly-efficient ROF solvers on log-likelihood ratio fields. We qualitatively assess the approach on synthetic data as well as on real natural and medical images. For a quantitative evaluation, we apply our approach to the icgbench dataset.
Virtual Full-Duplex Buffer-Aided Relaying in the Presence of Inter-Relay Interference
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we study virtual full-duplex (FD) buffer-aided relaying to recover the loss of multiplexing gain caused by half-duplex (HD) relaying in a multiple relay network, where each relay is equipped with a buffer and multiple antennas, through joint opportunistic relay selection (RS) and beamforming (BF) design. The main idea of virtual FD buffer-aided relaying is that the source and one of the relays simultaneously transmit their own information to another relay and the destination, respectively. In such networks, inter-relay interference (IRI) is a crucial problem which has to be resolved like self-interference in the FD relaying. In contrast to previous work that neglected IRI, we propose joint RS and BF schemes taking IRI into consideration by using multiple antennas at the relays. In order to maximize average end-to-end rate, we propose a weighted sum-rate maximization strategy assuming that adaptive rate transmission is employed in both the source to relay and relay to destination links. Then, we propose several BF schemes cancelling or suppressing IRI in order to maximize the weighted sum-rate. Numerical results show that our proposed optimal, zero forcing, and minimum mean square error BF-based RS schemes asymptotically approach the ideal FD relaying upper bound when increasing the number of antennas and/or the number of relays.
The Arbitrarily Varying Wiretap Channel - Secret Randomness, Stability and Super-Activation
Venue: arXiv cs.IT 2016
Year: 2016

We define the common randomness assisted capacity of an arbitrarily varying channel (AVWC) when the Eavesdropper is kept ignorant about the common randomness. We prove a multi-letter capacity formula for this model. We prove that, if enough common randomness is used, the capacity formula can be given a single-shot form again. We then consider the opposite extremal case, where no common randomness is available. It is known that the capacity of the system can be discontinuous under these circumstances. We prove here that it is still stable in the sense that it is continuous around its positivity points. We further prove that discontinuities can only arise if the legal link is symmetrizable and characterize the points where it is positive. These results shed new light on the design principles of communication systems with embedded security features. At last we investigate the effect of super-activation of the message transmission capacity of AVWCs under the average error criterion. We give a complete characterization of those AVWCs that may be super-activated. The effect is thereby also related to the (conjectured) super-activation of the common randomness assisted capacity of AVWCs with an eavesdropper that gets to know the common randomness. Super-activation is based on the idea of "wasting" a few bits of non-secret messages in order to enable provably secret transmission of a large bulk of data, a concept that may prove to be of further importance in the design of communication systems. In this work we provide further insight into this phenomenon by providing a class of codes that is capacity-achieving and does not convey any information to the Eavesdropper.
Towards a Practical Architecture for the Next Generation Internet of Things
Venue: arXiv cs.CY 2016
Year: 2016

The Internet of Things, or the IoT is a vision for a ubiquitous society wherein people and "Things" are connected in an immersively networked computing environment, with the connected "Things" providing utility to people/enterprises and their digital shadows, through intelligent social and commercial services. Translating this idea to a conceivable reality is a work in progress for more than a decade. Current IoT architectures are predicated on optimistic assumptions on the evolution and deployment of IoT technologies. We believe many of these assumptions will not be met, consequently impeding the practical and sustainable deployment of IoT. In this article, we explore use-cases across different applications domains that can potentially benefit from an IoT infrastructure, and analyze them in the context of an alternative world-view that is more grounded in reality. Despite this more conservative approach, we argue that adopting certain design paradigms when architecting an IoT ecosystem can achieve much of the promised benefits in a practical and sustainable manner.
Computing maximal cliques in link streams
Venue: arXiv cs.DS 2016
Year: 2016

A link stream is a collection of triplets $(t, u, v)$ indicating that an interaction occurred between u and v at time t. We generalize the classical notion of cliques in graphs to such link streams: for a given $Δ$, a $Δ$-clique is a set of nodes and a time interval such that all pairs of nodes in this set interact at least once during each sub-interval of duration $Δ$. We propose an algorithm to enumerate all maximal (in terms of nodes or time interval) cliques of a link stream, and illustrate its practical relevance on a real-world contact trace.
A gap analysis of Internet-of-Things platforms
Venue: arXiv cs.CY 2016
Year: 2016

We are experiencing an abundance of Internet-of-Things (IoT) middleware solutions that provide connectivity for sensors and actuators to the Internet. To gain a widespread adoption, these middleware solutions, referred to as platforms, have to meet the expectations of different players in the IoT ecosystem, including device providers, application developers, and end-users, among others. In this article, we evaluate a representative sample of these platforms, both proprietary and open-source, on the basis of their ability to meet the expectations of different IoT users. The evaluation is thus more focused on how ready and usable these platforms are for IoT ecosystem players, rather than on the peculiarities of the underlying technological layers. The evaluation is carried out as a gap analysis of the current IoT landscape with respect to (i) the support for heterogeneous sensing and actuating technologies, (ii) the data ownership and its implications for security and privacy, (iii) data processing and data sharing capabilities, (iv) the support offered to application developers, (v) the completeness of an IoT ecosystem, and (vi) the availability of dedicated IoT marketplaces. The gap analysis aims to highlight the deficiencies of today's solutions to improve their integration to tomorrow's ecosystems. In order to strengthen the finding of our analysis, we conducted a survey among the partners of the Finnish IoT program, counting over 350 experts, to evaluate the most critical issues for the development of future IoT platforms. Based on the results of our analysis and our survey, we conclude this article with a list of recommendations for extending these IoT platforms in order to fill in the gaps.
Prices Matter for the Parameterized Complexity of Shift Bribery
Venue: arXiv cs.MA 2016
Year: 2016

In the Shift Bribery problem, we are given an election (based on preference orders), a preferred candidate $p$, and a budget. The goal is to ensure that $p$ wins by shifting $p$ higher in some voters' preference orders. However, each such shift request comes at a price (depending on the voter and on the extent of the shift) and we must not exceed the given budget. We study the parameterized computational complexity of Shift Bribery with respect to a number of parameters (pertaining to the nature of the solution sought and the size of the election) and several classes of price functions. When we parameterize Shift Bribery by the number of affected voters, then for each of our voting rules (Borda, Maximin, Copeland) the problem is W[2]-hard. If, instead, we parameterize by the number of positions by which $p$ is shifted in total,then the problem is fixed-parameter tractable for Borda and Maximin,and is W[1]-hard for Copeland. If we parameterize by the budget, then the results depend on the price function class. We also show that Shift Bribery tends to be tractable when parameterized by the number of voters, but that the results for the number of candidates are more enigmatic.
INRIASAC: Simple Hypernym Extraction Methods
Venue: arXiv cs.CL 2016
Year: 2016

Given a set of terms from a given domain, how can we structure them into a taxonomy without manual intervention? This is the task 17 of SemEval 2015. Here we present our simple taxonomy structuring techniques which, despite their simplicity, ranked first in this 2015 benchmark. We use large quantities of text (English Wikipedia) and simple heuristics such as term overlap and document and sentence co-occurrence to produce hypernym lists. We describe these techniques and pre-sent an initial evaluation of results.
Why Transactional Memory Should Not Be Obstruction-Free
Venue: arXiv cs.DC 2016
Year: 2016

Transactional memory (TM) is an inherently optimistic abstraction: it allows concurrent processes to execute sequences of shared-data accesses (transactions) speculatively, with an option of aborting them in the future. Early TM designs avoided using locks and relied on non-blocking synchronization to ensure obstruction-freedom: a transaction that encounters no step contention is not allowed to abort. However, it was later observed that obstruction-free TMs perform poorly and, as a result, state-of-the-art TM implementations are nowadays blocking, allowing aborts because of data conflicts rather than step contention. In this paper, we explain this shift in the TM practice theoretically, via complexity bounds. We prove a few important lower bounds on obstruction-free TMs. Then we present a lock-based TM implementation that beats all of these lower bounds. In sum, our results exhibit a considerable complexity gap between non-blocking and blocking TM implementations.
Show, Attend and Tell: Neural Image Caption Generation with Visual Attention
Venue: arXiv cs.LG 2016
Year: 2016

Inspired by recent work in machine translation and object detection, we introduce an attention based model that automatically learns to describe the content of images. We describe how we can train this model in a deterministic manner using standard backpropagation techniques and stochastically by maximizing a variational lower bound. We also show through visualization how the model is able to automatically learn to fix its gaze on salient objects while generating the corresponding words in the output sequence. We validate the use of attention with state-of-the-art performance on three benchmark datasets: Flickr8k, Flickr30k and MS COCO.
A Mechanism for Fair Distribution of Resources without Payments
Venue: arXiv cs.GT 2016
Year: 2016

We design a mechanism for Fair and Efficient Distribution of Resources (FEDoR) in the presence of strategic agents. We consider a multiple-instances, Bayesian setting, where in each round the preference of an agent over the set of resources is a private information. We assume that in each of r rounds n agents are competing for k non-identical indivisible goods, (n > k). In each round the strategic agents declare how much they value receiving any of the goods in the specific round. The agent declaring the highest valuation receives the good with the highest value, the agent with the second highest valuation receives the second highest valued good, etc. Hence we assume a decision function that assigns goods to agents based on their valuations. The novelty of the mechanism is that no payment scheme is required to achieve truthfulness in a setting with rational/strategic agents. The FEDoR mechanism takes advantage of the repeated nature of the framework, and through a statistical test is able to punish the misreporting agents and be fair, truthful, and socially efficient. FEDoR is fair in the sense that, in expectation over the course of the rounds, all agents will receive the same good the same amount of times. FEDoR is an eligible candidate for applications that require fair distribution of resources over time. For example, equal share of bandwidth for nodes through the same point of access. But further on, FEDoR can be applied in less trivial settings like sponsored search, where payment is necessary and can be given in the form of a flat participation fee. To this extent we perform a comparison with traditional mechanisms applied to sponsored search, presenting the advantage of FEDoR.
Collaborative Filtering Bandits
Venue: arXiv cs.LG 2016
Year: 2016

Classical collaborative filtering, and content-based filtering methods try to learn a static recommendation model given training data. These approaches are far from ideal in highly dynamic recommendation domains such as news recommendation and computational advertisement, where the set of items and users is very fluid. In this work, we investigate an adaptive clustering technique for content recommendation based on exploration-exploitation strategies in contextual multi-armed bandit settings. Our algorithm takes into account the collaborative effects that arise due to the interaction of the users with the items, by dynamically grouping users based on the items under consideration and, at the same time, grouping items based on the similarity of the clusterings induced over the users. The resulting algorithm thus takes advantage of preference patterns in the data in a way akin to collaborative filtering methods. We provide an empirical analysis on medium-size real-world datasets, showing scalability and increased prediction performance (as measured by click-through rate) over state-of-the-art methods for clustering bandits. We also provide a regret analysis within a standard linear stochastic noise setting.
Reassembling trees for the traveling salesman
Venue: arXiv cs.DM 2016
Year: 2016

Many recent approximation algorithms for different variants of the traveling salesman problem (asymmetric TSP, graph TSP, s-t-path TSP) exploit the well-known fact that a solution of the natural linear programming relaxation can be written as convex combination of spanning trees. The main argument then is that randomly sampling a tree from such a distribution and then completing the tree to a tour at minimum cost yields a better approximation guarantee than simply taking a minimum cost spanning tree (as in Christofides' algorithm). We argue that an additional step can help: reassembling the spanning trees before sampling. Exchanging two edges in a pair of spanning trees can improve their properties under certain conditions. We demonstrate the usefulness for the metric s-t-path TSP by devising a deterministic polynomial-time algorithm that improves on Sebő's previously best approximation ratio of 8/5.
Improving Imprecise Compressive Sensing Models
Venue: arXiv cs.IT 2016
Year: 2016

Random sampling in compressive sensing (CS) enables the compression of large amounts of input signals in an efficient manner, which is useful for many applications. CS reconstructs the compressed signals exactly with overwhelming probability when incoming data can be sparsely represented with a few components. However, the theory of CS framework including random sampling has been focused on exact recovery of signal; impreciseness in signal recovery has been neglected. This can be problematic when there is uncertainty in the number of sparse components such as signal sparsity in dynamic systems that can change over time. We present a new theoretical framework that handles uncertainty in signal recovery from the perspective of recovery success and quality. We show that the signal recovery success in our model is more accurate than the success probability analysis in the CS framework. Our model is then extended to the case where the success or failure of signal recovery can be relaxed. We represent the number of components included in signal recovery with a right-tailed distribution and focus on recovery quality. Experimental results confirm the accuracy of our model in dynamic systems.
A PTAS for the Weighted Unit Disk Cover Problem
Venue: arXiv cs.CG 2016
Year: 2016

We are given a set of weighted unit disks and a set of points in Euclidean plane. The minimum weight unit disk cover (\UDC) problem asks for a subset of disks of minimum total weight that covers all given points. \UDC\ is one of the geometric set cover problems, which have been studied extensively for the past two decades (for many different geometric range spaces, such as (unit) disks, halfspaces, rectangles, triangles). It is known that the unweighted \UDC\ problem is NP-hard and admits a polynomial-time approximation scheme (PTAS). For the weighted \UDC\ problem, several constant approximations have been developed. However, whether the problem admits a PTAS has been an open question. In this paper, we answer this question affirmatively by presenting the first PTAS for \UDC. Our result implies the first PTAS for the minimum weight dominating set problem in unit disk graphs. Combining with existing ideas, our result can also be used to obtain the first PTAS for the maxmimum lifetime coverage problem and an improved constant approximation ratio for the connected dominating set problem in unit disk graphs.