OpenRaiser/Intern-Atlas huggingface dataset:
Feedback Reduction for Random Beamforming in Multiuser MIMO Broadcast Channel
Venue: arXiv cs.IT 2011
Year: 2011

For the multiuser multiple-input multiple-output (MIMO) downlink channel, the users feedback their channel state information (CSI) to help the base station (BS) schedule users and improve the system sum rate. However, this incurs a large aggregate feedback bandwidth which grows linearly with the number of users. In this paper, we propose a novel scheme to reduce the feedback load in a downlink orthogonal space division multiple access (SDMA) system with zero-forcing receivers by allowing the users to dynamically determine the number of feedback bits to use according to multiple decision thresholds. Through theoretical analysis, we show that, while keeping the aggregate feedback load of the entire system constant regardless of the number of users, the proposed scheme almost achieves the optimal asymptotic sum rate scaling with respect to the number of users (also known as the multiuser diversity). Specifically, given the number of thresholds, the proposed scheme can achieve a constant portion of the optimal sum rate achievable only by the system where all the users always feedback, and the remaining portion (referred to as the sum rate loss) decreases exponentially to zero as the number of thresholds increases. By deriving a tight upper bound for the sum rate loss, the minimum number of thresholds for a given tolerable sum rate loss is determined. In addition, a fast bit allocation method is discussed for the proposed scheme, and the simulation results show that the sum rate performances with the complex optimal bit allocation method and with the fast algorithm are almost the same. We compare our multi-threshold scheme to some previously proposed feedback schemes. Through simulation, we demonstrate that the proposed scheme can reduce the feedback load and utilize the limited feedback bandwidth more effectively than the existing feedback methods.
Improved Examples of Non-Termination for Ruppert's Algorithm
Venue: arXiv cs.CG 2011
Year: 2011

Improving the best known examples, two planar straight-line graphs which cause the non-termination of Ruppert's algorithm for a minimum angle threshold as low as 29.06 degrees are given.
BoolVar/PB v1.0, a java library for translating pseudo-Boolean constraints into CNF formulae
Venue: arXiv cs.AI 2011
Year: 2011

BoolVar/PB is an open source java library dedicated to the translation of pseudo-Boolean constraints into CNF formulae. Input constraints can be categorized with tags. Several encoding schemes are implemented in a way that each input constraint can be translated using one or several encoders, according to the related tags. The library can be easily extended by adding new encoders and / or new output formats.
Multiple Access Channel with Partial and Controlled Cribbing Encoders
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we consider a multiple access channel (MAC) with partial cribbing encoders. This means that each of two encoders obtains a deterministic function of the other encoder output with or without delay. The partial cribbing scheme is especially motivated by the additive noise Gaussian MAC since perfect cribbing results in the degenerated case of full cooperation between the encoders and requires an infinite entropy link. We derive a single letter characterization of the capacity of the MAC with partial cribbing for the cases of causal and strictly causal partial cribbing. Several numerical examples, such as quantized cribbing, are presented. We further consider and derive the capacity region where the cribbing depends on actions that are functions of the previous cribbed observations. In particular, we consider a scenario where the action is "to crib or not to crib" and show that a naive time-sharing strategy is not optimal.
The geometric stability of Voronoi diagrams with respect to small changes of the sites
Venue: arXiv cs.CG 2011
Year: 2011

Voronoi diagrams appear in many areas in science and technology and have numerous applications. They have been the subject of extensive investigation during the last decades. Roughly speaking, they are a certain decomposition of a given space into cells, induced by a distance function and by a tuple of subsets called the generators or the sites. Consider the following question: does a small change of the sites, e.g., of their position or shape, yield a small change in the corresponding Voronoi cells? This question is by all means natural and fundamental, since in practice one approximates the sites either because of inexact information about them, because of inevitable numerical errors in their representation, for simplification purposes and so on, and it is important to know whether the resulting Voronoi cells approximate the real ones well. The traditional approach to Voronoi diagrams, and, in particular, to (variants of) this question, is combinatorial. However, it seems that there has been a very limited discussion in the geometric sense (the shape of the cells), mainly an intuitive one, without proofs, in Euclidean spaces. We formalize this question precisely, and then show that the answer is positive in the case of R^d, or, more generally, in (possibly infinite dimensional) uniformly convex normed spaces, assuming there is a common positive lower bound on the distance between the sites. Explicit bounds are given, and we allow infinitely many sites of a general form. The relevance of this result is illustrated using several pictures and many real-world and theoretical examples and counterexamples.
Gossip PCA
Venue: arXiv cs.DS 2011
Year: 2011

Eigenvectors of data matrices play an important role in many computational problems, ranging from signal processing to machine learning and control. For instance, algorithms that compute positions of the nodes of a wireless network on the basis of pairwise distance measurements require a few leading eigenvectors of the distances matrix. While eigenvector calculation is a standard topic in numerical linear algebra, it becomes challenging under severe communication or computation constraints, or in absence of central scheduling. In this paper we investigate the possibility of computing the leading eigenvectors of a large data matrix through gossip algorithms. The proposed algorithm amounts to iteratively multiplying a vector by independent random sparsification of the original matrix and averaging the resulting normalized vectors. This can be viewed as a generalization of gossip algorithms for consensus, but the resulting dynamics is significantly more intricate. Our analysis is based on controlling the convergence to stationarity of the associated Kesten-Furstenberg Markov chain.
On Nash Dynamics of Matching Market Equilibria
Venue: arXiv cs.GT 2011
Year: 2011

In this paper, we study the Nash dynamics of strategic interplays of n buyers in a matching market setup by a seller, the market maker. Taking the standard market equilibrium approach, upon receiving submitted bid vectors from the buyers, the market maker will decide on a price vector to clear the market in such a way that each buyer is allocated an item for which he desires the most (a.k.a., a market equilibrium solution). While such equilibrium outcomes are not unique, the market maker chooses one (maxeq) that optimizes its own objective --- revenue maximization. The buyers in turn change bids to their best interests in order to obtain higher utilities in the next round's market equilibrium solution. This is an (n+1)-person game where buyers place strategic bids to gain the most from the market maker's equilibrium mechanism. The incentives of buyers in deciding their bids and the market maker's choice of using the maxeq mechanism create a wave of Nash dynamics involved in the market. We characterize Nash equilibria in the dynamics in terms of the relationship between maxeq and mineq (i.e., minimum revenue equilibrium), and develop convergence results for Nash dynamics from the maxeq policy to a mineq solution, resulting an outcome equivalent to the truthful VCG mechanism. Our results imply revenue equivalence between maxeq and mineq, and address the question that why short-term revenue maximization is a poor long run strategy, in a deterministic and dynamic setting.
Undirected Connectivity of Sparse Yao Graphs
Venue: arXiv cs.CG 2011
Year: 2011

Given a finite set S of points in the plane and a real value d > 0, the d-radius disk graph G^d contains all edges connecting pairs of points in S that are within distance d of each other. For a given graph G with vertex set S, the Yao subgraph Y_k[G] with integer parameter k > 0 contains, for each point p in S, a shortest edge pq from G (if any) in each of the k sectors defined by k equally-spaced rays with origin p. Motivated by communication issues in mobile networks with directional antennas, we study the connectivity properties of Y_k[G^d], for small values of k and d. In particular, we derive lower and upper bounds on the minimum radius d that renders Y_k[G^d] connected, relative to the unit radius assumed to render G^d connected. We show that d=sqrt(2) is necessary and sufficient for the connectivity of Y_4[G^d]. We also show that, for d <= ~1.056, the graph Y_3[G^d] can be disconnected, but for d >= 2/sqrt(3), Y_3[G^d] is always connected. Finally, we show that Y_2[G^d] can be disconnected, for any d >= 1.
Security Features of an Asymmetric Cryptosystem based on the Diophantine Equation Hard Problem
Venue: arXiv cs.CR 2011
Year: 2011

The Diophantine Equation Hard Problem (DEHP) is a potential cryptographic problem on the Diophantine equation $U=\sum \limits_{i=1}^n {V_i x_{i}}$. A proper implementation of DEHP would render an attacker to search for private parameters amongst the exponentially many solutions. However, an improper implementation would provide an attacker exponentially many choices to solve the DEHP. The AA\,$_β$-cryptosystem is an asymmetric cryptographic scheme that utilizes this concept together with the factorization problem of two large primes and is implemented only by using the multiplication operation for both encryption and decryption. With this simple mathematical structure, it would have low computational requirements and would enable communication devices with low computing power to deploy secure communication procedures efficiently.
Classification of Sets using Restricted Boltzmann Machines
Venue: arXiv cs.LG 2011
Year: 2011

We consider the problem of classification when inputs correspond to sets of vectors. This setting occurs in many problems such as the classification of pieces of mail containing several pages, of web sites with several sections or of images that have been pre-segmented into smaller regions. We propose generalizations of the restricted Boltzmann machine (RBM) that are appropriate in this context and explore how to incorporate different assumptions about the relationship between the input sets and the target class within the RBM. In experiments on standard multiple-instance learning datasets, we demonstrate the competitiveness of approaches based on RBMs and apply the proposed variants to the problem of incoming mail classification.
Medical Image Denoising using Adaptive Threshold Based on Contourlet Transform
Venue: arXiv cs.OH 2011
Year: 2011

Image denoising has become an essential exercise in medical imaging especially the Magnetic Resonance Imaging (MRI). This paper proposes a medical image denoising algorithm using contourlet transform. Numerical results show that the proposed algorithm can obtained higher peak signal to noise ratio (PSNR) than wavelet based denoising algorithms using MR Images in the presence of AWGN.
Link Prediction in Complex Networks: A Clustering Perspective
Venue: arXiv cs.SI 2011
Year: 2011

Link prediction is an open problem in the complex network, which attracts much research interest currently. However, little attention has been paid to the relation between network structure and the performance of prediction methods. In order to fill this vital gap, we try to understand how the network structure affects the performance of link prediction methods in the view of clustering. Our experiments on both synthetic and real-world networks show that as the clustering grows, the precision of these methods could be improved remarkably, while for the sparse and weakly clustered network, they perform poorly. We explain this through the distinguishment caused by increased clustering between the score distribution of positive and negative instances. Our finding also sheds light on the problem of how to select appropriate approaches for different networks with various densities and clusterings.
An Empirical Study of Real-World SPARQL Queries
Venue: arXiv cs.IR 2011
Year: 2011

Understanding how users tailor their SPARQL queries is crucial when designing query evaluation engines or fine-tuning RDF stores with performance in mind. In this paper we analyze 3 million real-world SPARQL queries extracted from logs of the DBPedia and SWDF public endpoints. We aim at finding which are the most used language elements both from syntactical and structural perspectives, paying special attention to triple patterns and joins, since they are indeed some of the most expensive SPARQL operations at evaluation phase. We have determined that most of the queries are simple and include few triple patterns and joins, being Subject-Subject, Subject-Object and Object-Object the most common join types. The graph patterns are usually star-shaped and despite triple pattern chains exist, they are generally short.
Game theoretic modeling of pilot behavior during mid-air encounters
Venue: arXiv cs.GT 2011
Year: 2011

We show how to combine Bayes nets and game theory to predict the behavior of hybrid systems involving both humans and automated components. We call this novel framework "Semi Network-Form Games," and illustrate it by predicting aircraft pilot behavior in potential near mid-air collisions. At present, at the beginning of such potential collisions, a collision avoidance system in the aircraft cockpit advises the pilots what to do to avoid the collision. However studies of mid-air encounters have found wide variability in pilot responses to avoidance system advisories. In particular, pilots rarely perfectly execute the recommended maneuvers, despite the fact that the collision avoidance system's effectiveness relies on their doing so. Rather pilots decide their actions based on all information available to them (advisory, instrument readings, visual observations). We show how to build this aspect into a semi network-form game model of the encounter and then present computational simulations of the resultant model.
Differential Privacy: on the trade-off between Utility and Information Leakage
Venue: arXiv cs.CR 2011
Year: 2011

Differential privacy is a notion of privacy that has become very popular in the database community. Roughly, the idea is that a randomized query mechanism provides sufficient privacy protection if the ratio between the probabilities that two adjacent datasets give the same answer is bound by e^epsilon. In the field of information flow there is a similar concern for controlling information leakage, i.e. limiting the possibility of inferring the secret information from the observables. In recent years, researchers have proposed to quantify the leakage in terms of Rényi min mutual information, a notion strictly related to the Bayes risk. In this paper, we show how to model the query system in terms of an information-theoretic channel, and we compare the notion of differential privacy with that of mutual information. We show that differential privacy implies a bound on the mutual information (but not vice-versa). Furthermore, we show that our bound is tight. Then, we consider the utility of the randomization mechanism, which represents how close the randomized answers are, in average, to the real ones. We show that the notion of differential privacy implies a bound on utility, also tight, and we propose a method that under certain conditions builds an optimal randomization mechanism, i.e. a mechanism which provides the best utility while guaranteeing differential privacy.
Generalized Symmetric Divergence Measures and the Probability of Error
Venue: arXiv cs.IT 2011
Year: 2011

There are three classical divergence measures exist in the literature on information theory and statistics. These are namely, Jeffryes-Kullback-Leiber J-divergence. Sibson-Burbea-Rao Jensen-Shannon divegernce and Taneja Arithmetic-Geometric divergence. These three measures bear an interesting relationship among each other. The divergence measures like Hellinger discrimination, symmetric chi-square divergence, and triangular discrimination are also known in the literature. In this paper, we have considered generalized symmetric divergence measures having the measures given above as particular cases. Bounds on the probability of error are obtained in terms of generalized symmetric divergence measures. Study of bounds on probability of error is extended for the difference of divergence measures.
Sparsity Enhanced Decision Feedback Equalization
Venue: arXiv cs.IT 2011
Year: 2011

For single-carrier systems with frequency domain equalization, decision feedback equalization (DFE) performs better than linear equalization and has much lower computational complexity than sequence maximum likelihood detection. The main challenge in DFE is the feedback symbol selection rule. In this paper, we give a theoretical framework for a simple, sparsity based thresholding algorithm. We feed back multiple symbols in each iteration, so the algorithm converges fast and has a low computational cost. We show how the initial solution can be obtained via convex relaxation instead of linear equalization, and illustrate the impact that the choice of the initial solution has on the bit error rate performance of our algorithm. The algorithm is applicable in several existing wireless communication systems (SC-FDMA, MC-CDMA, MIMO-OFDM). Numerical results illustrate significant performance improvement in terms of bit error rate compared to the MMSE solution.
Load Balancing in a Networked Environment through Homogenization
Venue: arXiv cs.DC 2011
Year: 2011

Distributed processing across a networked environment suffers from unpredictable behavior of speedup due to heterogeneous nature of the hardware and software in the remote machines. It is challenging to get a better performance from a distributed system by distributing task in an intelligent manner such that the heterogeneous nature of the system do not have any effect on the speedup ratio. This paper introduces homogenization, a technique that distributes and balances the workload in such a manner that the user gets the highest speedup possible from a distributed environment. Along with providing better performance, homogenization is totally transparent to the user and requires no interaction with the system.
Computational Complexity Results for Genetic Programming and the Sorting Problem
Venue: arXiv cs.NE 2011
Year: 2011

Genetic Programming (GP) has found various applications. Understanding this type of algorithm from a theoretical point of view is a challenging task. The first results on the computational complexity of GP have been obtained for problems with isolated program semantics. With this paper, we push forward the computational complexity analysis of GP on a problem with dependent program semantics. We study the well-known sorting problem in this context and analyze rigorously how GP can deal with different measures of sortedness.
Using Short Message Service (SMS) to Support Business Continuity
Venue: arXiv cs.NI 2011
Year: 2011

Now a day's many organizations are required to communicate online on a daily basis, 24-hour, seven-days-a-week, to gain the desired competitive advantages and profits; although there are a variety of disruptions that may occur within business application such as broken (off-line) database-links and unhanded database exceptions. Such cases will end the automated business work, and force business users to continue business procedures and functionalities via paper work, which causes additional resources with less business competitive advantages. In this paper, we will propose a new model in which we embed short message services (SMS) within business applications using the SMS Gateway such as "Ozeki Message Server", and programmed application packages. By using our proposed model, we can maintain business continuity when a partial disruption occurs and then switch to our application model. As a result to the experimental work, we conclude that our model supports business continuity since it supports the account balance modification while the database link is disrupted. In addition, we carried out each step twice and the scenario was reliable since all of its steps were reliable.
Abstract Processes of Place/Transition Systems
Venue: arXiv cs.LO 2011
Year: 2011

A well-known problem in Petri net theory is to formalise an appropriate causality-based concept of process or run for place/transition systems. The so-called individual token interpretation, where tokens are distinguished according to their causal history, giving rise to the processes of Goltz and Reisig, is often considered too detailed. The problem of defining a fully satisfying more abstract concept of process for general place/transition systems has so-far not been solved. In this paper, we recall the proposal of defining an abstract notion of process, here called BD-process, in terms of equivalence classes of Goltz-Reisig processes, using an equivalence proposed by Best and Devillers. It yields a fully satisfying solution for at least all one-safe nets. However, for certain nets which intuitively have different conflicting behaviours, it yields only one maximal abstract process. Here we identify a class of place/transition systems, called structural conflict nets, where conflict and concurrency due to token multiplicity are clearly separated. We show that, in the case of structural conflict nets, the equivalence proposed by Best and Devillers yields a unique maximal abstract process only for conflict-free nets. Thereby BD-processes constitute a simple and fully satisfying solution in the class of structural conflict nets.
The Impact of Memory Models on Software Reliability in Multiprocessors
Venue: arXiv cs.DC 2011
Year: 2011

The memory consistency model is a fundamental system property characterizing a multiprocessor. The relative merits of strict versus relaxed memory models have been widely debated in terms of their impact on performance, hardware complexity and programmability. This paper adds a new dimension to this discussion: the impact of memory models on software reliability. By allowing some instructions to reorder, weak memory models may expand the window between critical memory operations. This can increase the chance of an undesirable thread-interleaving, thus allowing an otherwise-unlikely concurrency bug to manifest. To explore this phenomenon, we define and study a probabilistic model of shared-memory parallel programs that takes into account such reordering. We use this model to formally derive bounds on the \emph{vulnerability} to concurrency bugs of different memory models. Our results show that for 2 (or a small constant number of) concurrent threads, weaker memory models do indeed have a higher likelihood of allowing bugs. On the other hand, we show that as the number of parallel threads increases, the gap between the different memory models becomes proportionally insignificant. This suggests the counter-intuitive rule that \emph{as the number of parallel threads in the system increases, the importance of using a strict memory model diminishes}; which potentially has major implications on the choice of memory consistency models in future multi-core systems.
Cook's Theory and the Twentieth Century Mathematics
Venue: arXiv cs.CY 2011
Year: 2011

A comprehensive review on Cook's contribution in the theory of NP-Completeness with relations to modern mathematics.