OpenRaiser/Intern-Atlas huggingface dataset:
Triangles to Capture Social Cohesion
Venue: arXiv cs.SI 2011
Year: 2011

Although community detection has drawn tremendous amount of attention across the sciences in the past decades, no formal consensus has been reached on the very nature of what qualifies a community as such. In this article we take an orthogonal approach by introducing a novel point of view to the problem of overlapping communities. Instead of quantifying the quality of a set of communities, we choose to focus on the intrinsic community-ness of one given set of nodes. To do so, we propose a general metric on graphs, the cohesion, based on counting triangles and inspired by well established sociological considerations. The model has been validated through a large-scale online experiment called Fellows in which users were able to compute their social groups on Face- book and rate the quality of the obtained groups. By observing those ratings in relation to the cohesion we assess that the cohesion is a strong indicator of users subjective perception of the community-ness of a set of people.
Duals of Affine Grassmann Codes and their Relatives
Venue: arXiv cs.IT 2011
Year: 2011

Affine Grassmann codes are a variant of generalized Reed-Muller codes and are closely related to Grassmann codes. These codes were introduced in a recent work [2]. Here we consider, more generally, affine Grassmann codes of a given level. We explicitly determine the dual of an affine Grassmann code of any level and compute its minimum distance. Further, we ameliorate the results of [2] concerning the automorphism group of affine Grassmann codes. Finally, we prove that affine Grassmann codes and their duals have the property that they are linear codes generated by their minimum-weight codewords. This provides a clean analogue of a corresponding result for generalized Reed-Muller codes.
A Generalized Poor-Verdu Error Bound for Multihypothesis Testing and the Channel Reliability Function
Venue: arXiv cs.IT 2011
Year: 2011

A lower bound on the minimum error probability for multihypothesis testing is established. The bound, which is expressed in terms of the cumulative distribution function of the tilted posterior hypothesis distribution given the observation with tilting parameter theta larger than or equal to 1, generalizes an earlier bound due the Poor and Verdu (1995). A sufficient condition is established under which the new bound (minus a multiplicative factor) provides the exact error probability in the limit of theta going to infinity. Examples illustrating the new bound are also provided. The application of this generalized Poor-Verdu bound to the channel reliability function is next carried out, resulting in two information-spectrum upper bounds. It is observed that, for a class of channels including the finite-input memoryless Gaussian channel, one of the bounds is tight and gives a multi-letter asymptotic expression for the reliability function, albeit its determination or calculation in single-letter form remains an open challenging problem. Numerical examples regarding the other bound are finally presented.
GPS Signal Acquisition via Compressive Multichannel Sampling
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we propose an efficient acquisition scheme for GPS receivers. It is shown that GPS signals can be effectively sampled and detected using a bank of randomized correlators with much fewer chip-matched filters than those used in existing GPS signal acquisition algorithms. The latter use correlations with all possible shifted replicas of the satellite-specific C/A code and an exhaustive search for peaking signals over the delay-Doppler space. Our scheme is based on the recently proposed analog compressed sensing framework, and consists of a multichannel sampling structure with far fewer correlators. The compressive multichannel sampler outputs are linear combinations of a vector whose support tends to be sparse; by detecting its support one can identify the strongest satellite signals in the field of view and pinpoint the correct code-phase and Doppler shifts for finer resolution during tracking. The analysis in this paper demonstrates that GPS signals can be detected and acquired via the proposed structure at a lower cost in terms of number of correlations that need to be computed in the coarse acquisition phase, which in current GPS technology scales like the product of the number of all possible delays and Doppler shifts. In contrast, the required number of correlators in our compressive multichannel scheme scales as the number of satellites in the field of view of the device times the logarithm of number of delay-Doppler bins explored, as is typical for compressed sensing methods.
A new algebraic and arithmetic framework for interval computations
Venue: arXiv cs.NA 2011
Year: 2011

In this paper we propose some very promissing results in interval arithmetics which permit to build well-defined arithmetics including distributivity of multiplication and division according addition and substraction. Thus, it allows to build all algebraic operations and functions on intervals. This will avoid completely the wrapping effects and data dependance. Some simple applications for matrix eigenvalues calculations, inversion of symmetric matrices and finally optimization are exhibited in the object-oriented programming language python.
Impact of Mobility On QoS of Mobile WiMax Network With CBR Application
Venue: arXiv cs.NI 2011
Year: 2011

The issue of mobility is important in wireless network because internet connectivity can only be effective if it's available during the movement of node. To enhance mobility, wireless access systems are designed such as IEEE 802.16e to operate on the move without any disruption of services. In this paper we are analyzing the impact of mobility on the QoS parameters (Throughput, Average Jitter and Average end to end Delay) of a mobile WiMAX network (IEEE 802.16e) with CBR application.
Context-Capture Multi-Valued Decision Fusion With Fault Tolerant Capability For Wireless Sensor Networks
Venue: arXiv cs.DC 2011
Year: 2011

Wireless sensor networks (WSNs) are usually utilized to perform decision fusion of event detection. Current decision fusion schemes are based on binary valued decision and do not consider bursty contextcapture. However, bursty context and multi-valued data are important characteristics of WSNs. One on hand, the local decisions from sensors usually have bursty and contextual characteristics. Fusion center must capture the bursty context information from the sensors. On the other hand, in practice, many applications need to process multi-valued data, such as temperature and reflection level used for lightening prediction. To address these challenges, the Markov modulated Poisson process (MMPP) and multi-valued logic are introduced into WSNs to perform context-capture multi-valued decision fusion. The overall decision fusion is decomposed into two parts. The first part is the context-capture model for WSNs using superposition MMPP. Through this procedure, the fusion center has a higher probability to get useful local decisions from sensors. The second one is focused on multi-valued decision fusion. Fault detection can also be performed based on MVL. Once the fusion center detects the faulty nodes, all their local decisions are removed from the computation of the likelihood ratios. Finally, we evaluate the capability of context-capture and fault tolerant. The result supports the usefulness of our scheme.
Haplotype Inference on Pedigrees with Recombinations, Errors, and Missing Genotypes via SAT solvers
Venue: arXiv cs.DS 2011
Year: 2011

The Minimum-Recombinant Haplotype Configuration problem (MRHC) has been highly successful in providing a sound combinatorial formulation for the important problem of genotype phasing on pedigrees. Despite several algorithmic advances and refinements that led to some efficient algorithms, its applicability to real datasets has been limited by the absence of some important characteristics of these data in its formulation, such as mutations, genotyping errors, and missing data. In this work, we propose the Haplotype Configuration with Recombinations and Errors problem (HCRE), which generalizes the original MRHC formulation by incorporating the two most common characteristics of real data: errors and missing genotypes (including untyped individuals). Although HCRE is computationally hard, we propose an exact algorithm for the problem based on a reduction to the well-known Satisfiability problem. Our reduction exploits recent progresses in the constraint programming literature and, combined with the use of state-of-the-art SAT solvers, provides a practical solution for the HCRE problem. Biological soundness of the phasing model and effectiveness (on both accuracy and performance) of the algorithm are experimentally demonstrated under several simulated scenarios and on a real dairy cattle population.
User Empowerment in the Internet of Things
Venue: arXiv cs.CY 2011
Year: 2011

This paper focuses on the characteristics of two big triggers that facilitated wide user adoption of the Internet: Web 2.0 and online social networks. We detect brakes for reproduction of these events in Internet of things. To support our hypothesis we first compare the difference between the ways of use of the Internet with the future scenarios of Internet of things. We detect barriers that could slow down apparition of this kind of social events during user adoption of Internet of Things and we propose a conceptual framework to solve these problems.
Applying Data Privacy Techniques on Tabular Data in Uganda
Venue: arXiv cs.CR 2011
Year: 2011

The growth of Information Technology(IT) in Africa has led to an increase in the utilization of communication networks for data transaction across the continent. A growing number of entities in the private sector, academia, and government, have deployed the Internet as a medium to transact in data, routinely posting statistical and non statistical data online and thereby making many in Africa increasingly dependent on the Internet for data transactions. In the country of Uganda, exponential growth in data transaction has presented a new challenge: What is the most efficient way to implement data privacy. This article discusses data privacy challenges faced by the country of Uganda and implementation of data privacy techniques for published tabular data. We make the case for data privacy, survey concepts of data privacy, and implementations that could be employed to provide data privacy in Uganda.
Fitting a Model to Data in Loss Tomography
Venue: arXiv cs.NI 2011
Year: 2011

Loss tomography has received considerable attention in recent years and a number of estimators have been proposed. Although most of the estimators claim to be the maximum likelihood estimators, the claim is only partially true since the maximum likelihood estimate can be obtained at most for a class of data sets. Unfortunately, few people are aware of this restriction that leads to a misconception that an estimator is applicable to all data sets as far as it returns a unique solution. To correct this, we in this paper point out the risk of this misconception and illustrate the inconsistency between data and model in the most influential estimators. To ensure the model used in estimation consistent with the data collected from an experiment, the data sets used in estimation are divided into 4 classes according to the characteristics of observations. Based on the classification, the validity of an estimator is defined and the validity of the most influential estimators is evaluated. In addition, a number of estimators are proposed, one for a class of data sets that have been overlooked. Further, a general estimator is proposed that is applicable to all data classes. The discussion starts from the tree topology and end at the general topology.
Reversible arithmetic logic unit
Venue: arXiv cs.AR 2011
Year: 2011

Quantum computer requires quantum arithmetic. The sophisticated design of a reversible arithmetic logic unit (reversible ALU) for quantum arithmetic has been investigated in this letter. We provide explicit construction of reversible ALU effecting basic arithmetic operations. By provided the corresponding control unit, the proposed reversible ALU can combine the classical arithmetic and logic operation in a reversible integrated system. This letter provides actual evidence to prove the possibility of the realization of reversible Programmable Logic Device (RPLD) using reversible ALU.
Lost Audio Packets Steganography: The First Practical Evaluation
Venue: arXiv cs.CR 2011
Year: 2011

This paper presents first experimental results for an IP telephony-based steganographic method called LACK (Lost Audio PaCKets steganography). This method utilizes the fact that in typical multimedia communication protocols like RTP (Real-Time Transport Protocol), excessively delayed packets are not used for the reconstruction of transmitted data at the receiver, i.e. these packets are considered useless and discarded. The results presented in this paper were obtained basing on a functional LACK prototype and show the method's impact on the quality of voice transmission. Achievable steganographic bandwidth for the different IP telephony codecs is also calculated.
Event-Clock Automata: From Theory to Practice
Venue: arXiv cs.LO 2011
Year: 2011

Event clock automata (ECA) are a model for timed languages that has been introduced by Alur, Fix and Henzinger as an alternative to timed automata, with better theoretical properties (for instance, ECA are determinizable while timed automata are not). In this paper, we revisit and extend the theory of ECA. We first prove that no finite time abstract language equivalence exists for ECA, thereby disproving a claim in the original work on ECA. This means in particular that regions do not form a time abstract bisimulation. Nevertheless, we show that regions can still be used to build a finite automaton recognizing the untimed language of an ECA. Then, we extend the classical notions of zones and DBMs to let them handle event clocks instead of plain clocks (as in timed automata) by introducing event zones and Event DBMs (EDBMs). We discuss algorithms to handle event zones represented as EDBMs, as well as (semi-) algorithms based on EDBMs to decide language emptiness of ECA.
Jeux stochastiques et contrôle de puissance distribué
Venue: arXiv cs.GT 2011
Year: 2011

Transmitters of a multiple access channel are assumed to freely choose their power control strategy in order to be energy-efficient. We show that in a stochastic game framework, we can develop energy-efficient distributed control strategies which only require partial knowledge of the entire system. Achievable utility equilibrium region is characterized and based on time-sharing, an explicit power control strategy is proposed.
On the Capacity of the Interference Channel with a Cognitive Relay
Venue: arXiv cs.IT 2011
Year: 2011

The InterFerence Channel with a Cognitive Relay (IFC-CR) consists of the classical interference channel with two independent source-destination pairs whose communication is aided by an additional node, referred to as the cognitive relay, that has a priori knowledge of both sources' messages. This a priori message knowledge is termed cognition and idealizes the relay learning the messages of the two sources from their transmissions over a wireless channel. This paper presents new inner and outer bounds for the capacity region of the general memoryless IFC-CR that are shown to be tight for a certain class of channels. The new outer bound follows from arguments originally devised for broadcast channels among which Sato's observation that the capacity region of channels with non-cooperative receivers only depends on the channel output conditional marginal distributions. The new inner bound is shown to include all previously proposed coding schemes and it is thus the largest known achievable rate region to date. The new inner and outer bounds coincide for a subset of channel satisfying a strong interference condition. For these channels there is no loss in optimality if both destinations decode both messages. This result parallels analogous results for the classical IFC and for the cognitive IFC and is the first known capacity result for the general IFC-CR. Numerical evaluations of the proposed inner and outer bounds are presented for the Gaussian noise case.
Efficient variational inference in large-scale Bayesian compressed sensing
Venue: arXiv cs.CV 2011
Year: 2011

We study linear models under heavy-tailed priors from a probabilistic viewpoint. Instead of computing a single sparse most probable (MAP) solution as in standard deterministic approaches, the focus in the Bayesian compressed sensing framework shifts towards capturing the full posterior distribution on the latent variables, which allows quantifying the estimation uncertainty and learning model parameters using maximum likelihood. The exact posterior distribution under the sparse linear model is intractable and we concentrate on variational Bayesian techniques to approximate it. Repeatedly computing Gaussian variances turns out to be a key requisite and constitutes the main computational bottleneck in applying variational techniques in large-scale problems. We leverage on the recently proposed Perturb-and-MAP algorithm for drawing exact samples from Gaussian Markov random fields (GMRF). The main technical contribution of our paper is to show that estimating Gaussian variances using a relatively small number of such efficiently drawn random samples is much more effective than alternative general-purpose variance estimation techniques. By reducing the problem of variance estimation to standard optimization primitives, the resulting variational algorithms are fully scalable and parallelizable, allowing Bayesian computations in extremely large-scale problems with the same memory and time complexity requirements as conventional point estimation techniques. We illustrate these ideas with experiments in image deblurring.
Correlation Estimation from Compressed Images
Venue: arXiv cs.CV 2011
Year: 2011

This paper addresses the problem of correlation estimation in sets of compressed images. We consider a framework where images are represented under the form of linear measurements due to low complexity sensing or security requirements. We assume that the images are correlated through the displacement of visual objects due to motion or viewpoint change and the correlation is effectively represented by optical flow or motion field models. The correlation is estimated in the compressed domain by jointly processing the linear measurements. We first show that the correlated images can be efficiently related using a linear operator. Using this linear relationship we then describe the dependencies between images in the compressed domain. We further cast a regularized optimization problem where the correlation is estimated in order to satisfy both data consistency and motion smoothness objectives with a Graph Cut algorithm. We analyze in detail the correlation estimation performance and quantify the penalty due to image compression. Extensive experiments in stereo and video imaging applications show that our novel solution stays competitive with methods that implement complex image reconstruction steps prior to correlation estimation. We finally use the estimated correlation in a novel joint image reconstruction scheme that is based on an optimization problem with sparsity priors on the reconstructed images. Additional experiments show that our correlation estimation algorithm leads to an effective reconstruction of pairs of images in distributed image coding schemes that outperform independent reconstruction algorithms by 2 to 4 dB.
Finding All Allowed Edges in a Bipartite Graph
Venue: arXiv cs.DM 2011
Year: 2011

We consider the problem of finding all allowed edges in a bipartite graph $G=(V,E)$, i.e., all edges that are included in some maximum matching. We show that given any maximum matching in the graph, it is possible to perform this computation in linear time $O(n+m)$ (where $n=|V|$ and $m=|E|$). Hence, the time complexity of finding all allowed edges reduces to that of finding a single maximum matching, which is $O(n^{1/2}m)$ [Hopcroft and Karp 1973], or $O((n/\log n)^{1/2}m)$ for dense graphs with $m=Θ(n^2)$ [Alt et al. 1991]. This time complexity improves upon that of the best known algorithms for the problem, which is $O(nm)$ ([Costa 1994] for bipartite graphs, and [Carvalho and Cheriyan 2005] for general graphs). Other algorithms for solving that problem are randomized algorithms due to [Rabin and Vazirani 1989] and [Cheriyan 1997], the runtime of which is $\tilde{O}(n^{2.376})$. Our algorithm, apart from being deterministic, improves upon that time complexity for bipartite graphs when $m=O(n^r)$ and $r<1.876$. In addition, our algorithm is elementary, conceptually simple, and easy to implement.
Optimal Selective Feedback Policies for Opportunistic Beamforming
Venue: arXiv cs.IT 2011
Year: 2011

This paper studies the structure of downlink sum-rate maximizing selective decentralized feedback policies for opportunistic beamforming under finite feedback constraints on the average number of mobile users feeding back. Firstly, it is shown that any sum-rate maximizing selective decentralized feedback policy must be a threshold feedback policy. This result holds for all fading channel models with continuous distribution functions. Secondly, the resulting optimum threshold selection problem is analyzed in detail. This is a non-convex optimization problem over finite dimensional Euclidean spaces. By utilizing the theory of majorization, an underlying Schur-concave structure in the sum-rate function is identified, and the sufficient conditions for the optimality of homogenous threshold feedback policies are obtained. Applications of these results are illustrated for well known fading channel models such as Rayleigh, Nakagami and Rician fading channels, along with various engineering and design insights. Rather surprisingly, it is shown that using the same threshold value at all mobile users is not always a rate-wise optimal feedback strategy, even for a network with identical mobile users experiencing statistically the same channel conditions. For the Rayleigh fading channel model, on the other hand, homogenous threshold feedback policies are proven to be rate-wise optimal if multiple orthonormal data carrying beams are used to communicate with multiple mobile users simultaneously.
AWRP: Adaptive Weight Ranking Policy for Improving Cache Performance
Venue: arXiv cs.PF 2011
Year: 2011

Due to the huge difference in performance between the computer memory and processor, the virtual memory management plays a vital role in system performance. A Cache memory is the fast memory which is used to compensate the speed difference between the memory and processor. This paper gives an adaptive replacement policy over the traditional policy which has low overhead, better performance and is easy to implement. Simulations show that our algorithm performs better than Least-Recently-Used (LRU), First-In-First-Out (FIFO) and Clock with Adaptive Replacement (CAR).
Some Non-Classical Approaches to the Branderburger-Keisler Paradox
Venue: arXiv cs.GT 2011
Year: 2011

In this paper, we discuss a well-known self-referential paradox in foundational game theory, the Brandenburger - Keisler paradox. We approach the paradox from two different perspectives: non-well-founded set theory and paraconsistent logic. We show that the paradox persists in both frameworks for category theoretical reasons, but, with different properties.