OpenRaiser/Intern-Atlas huggingface dataset:
The Impact of Incomplete Information on Games in Parallel Relay Networks
Venue: arXiv cs.GT 2011
Year: 2011

We consider the impact of incomplete information on incentives for node cooperation in parallel relay networks with one source node, one destination node, and multiple relay nodes. All nodes are selfish and strategic, interested in maximizing their own profit instead of the social welfare. We consider the practical situation where the channel state on any given relay path is not observable to the source or to the other relays. We examine different bargaining relationships between the source and the relays, and propose a framework for analyzing the efficiency loss induced by incomplete information. We analyze the source of the efficiency loss, and quantify the amount of inefficiency which results.
Context Capture in Software Development
Venue: arXiv cs.SE 2011
Year: 2011

The context of a software developer is something hard to define and capture, as it represents a complex network of elements across different dimensions that are not limited to the work developed on an IDE. We propose the definition of a software developer context model that takes into account all the dimensions that characterize the work environment of the developer. We are especially focused on what the software developer context encompasses at the project level and how it can be captured. The experimental work done so far show that useful context information can be extracted from project management tools. The extraction, analysis and availability of this context information can be used to enrich the work environment of the developer with additional knowledge to support her/his work.
The Role of Normalization in the Belief Propagation Algorithm
Venue: arXiv cs.LG 2011
Year: 2011

An important part of problems in statistical physics and computer science can be expressed as the computation of marginal probabilities over a Markov Random Field. The belief propagation algorithm, which is an exact procedure to compute these marginals when the underlying graph is a tree, has gained its popularity as an efficient way to approximate them in the more general case. In this paper, we focus on an aspect of the algorithm that did not get that much attention in the literature, which is the effect of the normalization of the messages. We show in particular that, for a large class of normalization strategies, it is possible to focus only on belief convergence. Following this, we express the necessary and sufficient conditions for local stability of a fixed point in terms of the graph structure and the beliefs values at the fixed point. We also explicit some connexion between the normalization constants and the underlying Bethe Free Energy.
Low-Complexity Detection/Equalization in Large-Dimension MIMO-ISI Channels Using Graphical Models
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we deal with low-complexity near-optimal detection/equalization in large-dimension multiple-input multiple-output inter-symbol interference (MIMO-ISI) channels using message passing on graphical models. A key contribution in the paper is the demonstration that near-optimal performance in MIMO-ISI channels with large dimensions can be achieved at low complexities through simple yet effective simplifications/approximations, although the graphical models that represent MIMO-ISI channels are fully/densely connected (loopy graphs). These include 1) use of Markov Random Field (MRF) based graphical model with pairwise interaction, in conjunction with {\em message/belief damping}, and 2) use of Factor Graph (FG) based graphical model with {\em Gaussian approximation of interference} (GAI). The per-symbol complexities are $O(K^2n_t^2)$ and $O(Kn_t)$ for the MRF and the FG with GAI approaches, respectively, where $K$ and $n_t$ denote the number of channel uses per frame, and number of transmit antennas, respectively. These low-complexities are quite attractive for large dimensions, i.e., for large $Kn_t$. From a performance perspective, these algorithms are even more interesting in large-dimensions since they achieve increasingly closer to optimum detection performance for increasing $Kn_t$. Also, we show that these message passing algorithms can be used in an iterative manner with local neighborhood search algorithms to improve the reliability/performance of $M$-QAM symbol detection.
A Matrix-Analytic Solution for Randomized Load Balancing Models with Phase-Type Service Times
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, we provide a matrix-analytic solution for randomized load balancing models (also known as \emph{supermarket models}) with phase-type (PH) service times. Generalizing the service times to the phase-type distribution makes the analysis of the supermarket models more difficult and challenging than that of the exponential service time case which has been extensively discussed in the literature. We first describe the supermarket model as a system of differential vector equations, and provide a doubly exponential solution to the fixed point of the system of differential vector equations. Then we analyze the exponential convergence of the current location of the supermarket model to its fixed point. Finally, we present numerical examples to illustrate our approach and show its effectiveness in analyzing the randomized load balancing schemes with non-exponential service requirements.
Univariate real root isolation in an extension field
Venue: arXiv cs.SC 2011
Year: 2011

We present algorithmic, complexity and implementation results for the problem of isolating the real roots of a univariate polynomial in $B_α \in L[y]$, where $L=\QQ(α)$ is a simple algebraic extension of the rational numbers. We consider two approaches for tackling the problem. In the first approach using resultant computations we perform a reduction to a polynomial with integer coefficients. We compute separation bounds for the roots, and using them we deduce that we can isolate the real roots of $B_α$ in $\sOB(N^{10})$, where $N$ is an upper bound on all the quantities (degree and bitsize) of the input polynomials. In the second approach we isolate the real roots working directly on the polynomial of the input. We compute improved separation bounds for real roots and we prove that they are optimal, under mild assumptions. For isolating the roots we consider a modified Sturm's algorithm, and a modified version of \func{descartes}' algorithm introduced by Sagraloff. For the former we prove a complexity bound of $\sOB(N^8)$ and for the latter a bound of $\sOB(N^{7})$. We implemented the algorithms in \func{C} as part of the core library of \mathematica and we illustrate their efficiency over various data sets. Finally, we present complexity results for the general case of the first approach, where the coefficients belong to multiple extensions.
BitTorrent Swarm Analysis through Automation and Enhanced Logging
Venue: arXiv cs.NI 2011
Year: 2011

Peer-to-Peer protocols currently form the most heavily used protocol class in the Internet, with BitTorrent, the most popular protocol for content distribution, as its flagship. A high number of studies and investigations have been undertaken to measure, analyse and improve the inner workings of the BitTorrent protocol. Approaches such as tracker message analysis, network probing and packet sniffing have been deployed to understand and enhance BitTorrent's internal behaviour. In this paper we present a novel approach that aims to collect, process and analyse large amounts of local peer information in BitTorrent swarms. We classify the information as periodic status information able to be monitored in real time and as verbose logging information to be used for subsequent analysis. We have designed and implemented a retrieval, storage and presentation infrastructure that enables easy analysis of BitTorrent protocol internals. Our approach can be employed both as a comparison tool, as well as a measurement system of how network characteristics and protocol implementation influence the overall BitTorrent swarm performance. We base our approach on a framework that allows easy swarm creation and control for different BitTorrent clients. With the help of a virtualized infrastructure and a client-server software layer we are able to create, command and manage large sized BitTorrent swarms. The framework allows a user to run, schedule, start, stop clients within a swarm and collect information regarding their behavior.
Intersection Logic in sequent calculus style
Venue: arXiv cs.LO 2011
Year: 2011

The intersection type assignment system has been designed directly as deductive system for assigning formulae of the implicative and conjunctive fragment of the intuitionistic logic to terms of lambda-calculus. But its relation with the logic is not standard. Between all the logics that have been proposed as its foundation, we consider ISL, which gives a logical interpretation of the intersection by splitting the intuitionistic conjunction into two connectives, with a local and global behaviour respectively, being the intersection the local one. We think ISL is a logic interesting by itself, and in order to support this claim we give a sequent calculus formulation of it, and we prove that it enjoys the cut elimination property.
Sound and Complete Typing for lambda-mu
Venue: arXiv cs.LO 2011
Year: 2011

In this paper we define intersection and union type assignment for Parigot's calculus lambda-mu. We show that this notion is complete (i.e. closed under subject-expansion), and show also that it is sound (i.e. closed under subject-reduction). This implies that this notion of intersection-union type assignment is suitable to define a semantics.
Spectrum Management for Cognitive Radio based on Genetics Algorithm
Venue: arXiv cs.NE 2011
Year: 2011

Spectrum scarceness is one of the major challenges that the present world is facing. The efficient use of existing licensed spectrum is becoming most critical as growing demand of the radio spectrum. Different researches show that the use of licensed are not utilized inefficiently. It has been also shown that primary user does not use more than 70% of the licensed frequency band most of the time. Many researchers are trying to found the techniques that efficiently utilize the under-utilized licensed spectrum. One of the approaches is the use of "Cognitive Radio". This allows the radio to learn from its environment, changing certain parameters. Based on this knowledge the radio can dynamically exploit the spectrum holes in the licensed band of the spectrum. This paper w i l l focus on the performance of spectrum allocation technique, based on popular meta-heuristics Genetics Algorithm and analyzing the performance of this technique using Mat Lab.
Limited Feedback Over Temporally Correlated Channels for the Downlink of a Femtocell Network
Venue: arXiv cs.IT 2011
Year: 2011

Heterogeneous networks are a flexible deployment model that rely on low power nodes to improve the user broadband experience in a cost effective manner. Femtocells are an integral part of heterogeneous networks, whose main purpose is to improve the indoor capacity. When restricting access to home users, femtocells cause a substantial interference problem that cannot be mitigated through coordination with the macrocell base station. In this paper, we analyze multiple antenna communication on the downlink of a macrocell network, with femtocell overlay. We evaluate the feasibility of limited feedback beamforming given delay on the feedback channel, quantization error and uncoordinated interference from the femtocells. We model the femtocell spatial distribution as a Poisson point process and the temporal correlation of the channel according to a Gauss-Markov model. We derive the probability of outage at the macrocell users as a function of the temporal correlation, the femtocell density, and the feedback rate. We propose rate backoff to maximize the average achievable rate in the network. Simulation results show that limited feedback beamforming is a viable solution for femtocell networks despite the CSI inaccuracy and the interference. They illustrate how properly designed rate backoff improves the achievable rate of the macrocell system.
Tight bounds on the randomized communication complexity of symmetric XOR functions in one-way and SMP models
Venue: arXiv cs.CC 2011
Year: 2011

We study the communication complexity of symmetric XOR functions, namely functions $f: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}$ that can be formulated as $f(x,y)=D(|x\oplus y|)$ for some predicate $D: \{0,1,...,n\} \rightarrow \{0,1\}$, where $|x\oplus y|$ is the Hamming weight of the bitwise XOR of $x$ and $y$. We give a public-coin randomized protocol in the Simultaneous Message Passing (SMP) model, with the communication cost matching the known lower bound for the \emph{quantum} and \emph{two-way} model up to a logarithm factor. As a corollary, this closes a quadratic gap between quantum lower bound and randomized upper bound for the one-way model, answering an open question raised in Shi and Zhang \cite{SZ09}.
A Message-Passing Receiver for BICM-OFDM over Unknown Clustered-Sparse Channels
Venue: arXiv cs.IT 2011
Year: 2011

We propose a factor-graph-based approach to joint channel-estimation-and-decoding (JCED) of bit- interleaved coded orthogonal frequency division multiplexing (BICM-OFDM). In contrast to existing designs, ours is capable of exploiting not only sparsity in sampled channel taps but also clustering among the large taps, behaviors which are known to manifest at larger communication bandwidths. In order to exploit these channel-tap structures, we adopt a two-state Gaussian mixture prior in conjunction with a Markov model on the hidden state. For loopy belief propagation, we exploit a "generalized approximate message passing" (GAMP) algorithm recently developed in the context of compressed sensing, and show that it can be successfully coupled with soft-input soft-output decoding, as well as hidden Markov inference, through the standard sum-product framework. For N subcarriers and any channel length L < N, the resulting JCED-GAMP scheme has a computational complexity of only O(N log2 N + N|S|), where |S| is the constellation size. Numerical experiments using IEEE 802.15.4a channels show that our scheme yields BER performance within 1 dB of the known-channel bound and 3-4 dB better than soft equalization based on LMMSE and LASSO.
Contracts for Abstract Processes in Service Composition
Venue: arXiv cs.PL 2011
Year: 2011

Contracts are a well-established approach for describing and analyzing behavioral aspects of web service compositions. The theory of contracts comes equipped with a notion of compatibility between clients and servers that ensures that every possible interaction between compatible clients and servers will complete successfully. It is generally agreed that real applications often require the ability of exposing just partial descriptions of their behaviors, which are usually known as abstract processes. We propose a formal characterization of abstraction as an extension of the usual symbolic bisimulation and we recover the notion of abstraction in the context of contracts.
Distributed Algorithm to Locate Critical Nodes to Network Robustness based on Spectral Analysis
Venue: arXiv cs.NI 2011
Year: 2011

We propose an algorithm to locate the most critical nodes to network robustness. Such critical nodes may be thought of as those most related to the notion of network centrality. Our proposal relies only on a localized spectral analysis of a limited subnetwork centered at each node in the network. We also present a procedure allowing the navigation from any node towards a critical node following only local information computed by the proposed algorithm. Experimental results confirm the effectiveness of our proposal considering networks of different scales and topological characteristics.
A Novel Template-Based Learning Model
Venue: arXiv cs.LG 2011
Year: 2011

This article presents a model which is capable of learning and abstracting new concepts based on comparing observations and finding the resemblance between the observations. In the model, the new observations are compared with the templates which have been derived from the previous experiences. In the first stage, the objects are first represented through a geometric description which is used for finding the object boundaries and a descriptor which is inspired by the human visual system and then they are fed into the model. Next, the new observations are identified through comparing them with the previously-learned templates and are used for producing new templates. The comparisons are made based on measures like Euclidean or correlation distance. The new template is created by applying onion-pealing algorithm. The algorithm consecutively uses convex hulls which are made by the points representing the objects. If the new observation is remarkably similar to one of the observed categories, it is no longer utilized in creating a new template. The existing templates are used to provide a description of the new observation. This description is provided in the templates space. Each template represents a dimension of the feature space. The degree of the resemblance each template bears to each object indicates the value associated with the object in that dimension of the templates space. In this way, the description of the new observation becomes more accurate and detailed as the time passes and the experiences increase. We have used this model for learning and recognizing the new polygons in the polygon space. Representing the polygons was made possible through employing a geometric method and a method inspired by human visual system. Various implementations of the model have been compared. The evaluation results of the model prove its efficiency in learning and deriving new templates.
Infinite Multiple Membership Relational Modeling for Complex Networks
Venue: arXiv cs.SI 2011
Year: 2011

Learning latent structure in complex networks has become an important problem fueled by many types of networked data originating from practically all fields of science. In this paper, we propose a new non-parametric Bayesian multiple-membership latent feature model for networks. Contrary to existing multiple-membership models that scale quadratically in the number of vertices the proposed model scales linearly in the number of links admitting multiple-membership analysis in large scale networks. We demonstrate a connection between the single membership relational model and multiple membership models and show on "real" size benchmark network data that accounting for multiple memberships improves the learning of latent structure as measured by link prediction while explicitly accounting for multiple membership result in a more compact representation of the latent structure of networks.
A Color Image Digital Watermarking Scheme Based on SOFM
Venue: arXiv cs.MM 2011
Year: 2011

Digital watermarking technique has been presented and widely researched to solve some important issues in the digital world, such as copyright protection, copy protection and content authentication. Several robust watermarking schemes based on vector quantization (VQ) have been presented. In this paper, we present a new digital image watermarking method based on SOFM vector quantizer for color images. This method utilizes the codebook partition technique in which the watermark bit is embedded into the selected VQ encoded block. The main feature of this scheme is that the watermark exists both in VQ compressed image and in the reconstructed image. The watermark extraction can be performed without the original image. The watermark is hidden inside the compressed image, so much transmission time and storage space can be saved when the compressed data are transmitted over the Internet. Simulation results demonstrate that the proposed method has robustness against various image processing operations without sacrificing compression performance and the computational speed.
Maintaining Arrays of Contiguous Objects
Venue: arXiv cs.DS 2011
Year: 2011

In this paper we consider methods for dynamically storing a set of different objects ("modules") in a physical array. Each module requires one free contiguous subinterval in order to be placed. Items are inserted or removed, resulting in a fragmented layout that makes it harder to insert further modules. It is possible to relocate modules, one at a time, to another free subinterval that is contiguous and does not overlap with the current location of the module. These constraints clearly distinguish our problem from classical memory allocation. We present a number of algorithmic results, including a bound of Theta(n^2) on physical sorting if there is a sufficiently large free space and sum up NP-hardness results for arbitrary initial layouts. For online scenarios in which modules arrive one at a time, we present a method that requires O(1) moves per insertion or deletion and amortized cost O(m_i log M) per insertion or deletion, where m_i is the module's size, M is the size of the largest module and costs for moves are linear in the size of a module.
On Various Negative Translations
Venue: arXiv cs.LO 2011
Year: 2011

Several proof translations of classical mathematics into intuitionistic mathematics have been proposed in the literature over the past century. These are normally referred to as negative translations or double-negation translations. Among those, the most commonly cited are translations due to Kolmogorov, Godel, Gentzen, Kuroda and Krivine (in chronological order). In this paper we propose a framework for explaining how these different translations are related to each other. More precisely, we define a notion of a (modular) simplification starting from Kolmogorov translation, which leads to a partial order between different negative translations. In this derived ordering, Kuroda and Krivine are minimal elements. Two new minimal translations are introduced, with Godel and Gentzen translations sitting in between Kolmogorov and one of these new translations.
An applicative theory for FPH
Venue: arXiv cs.LO 2011
Year: 2011

In this paper we introduce an applicative theory which characterizes the polynomial hierarchy of time.
Failure of A Mix Network
Venue: arXiv cs.CR 2011
Year: 2011

A mix network by Wikstrom fails in correctness, provable privacy and soundness. Its claimed advantages in security and efficiency are compromised. The analysis in this paper illustrates that although the first two failures may be fixed by modifying the shuffling protocol, the last one is too serious to fix at a tolerable cost. Especially, an attack is proposed to show how easily soundness of the shuffling scheme can be compromised. Moreover, the most surprising discovery in this paper is that it is formally illustrated that in practice it is impossible to fix soundness of the shuffling scheme by Wikstrom.