OpenRaiser/Intern-Atlas huggingface dataset:
Node Sampling using Random Centrifugal Walks
Venue: arXiv cs.DC 2012
Year: 2012

Sampling a network with a given probability distribution has been identified as a useful operation. In this paper we propose distributed algorithms for sampling networks, so that nodes are selected by a special node, called the \emph{source}, with a given probability distribution. All these algorithms are based on a new class of random walks, that we call Random Centrifugal Walks (RCW). A RCW is a random walk that starts at the source and always moves away from it. Firstly, an algorithm to sample any connected network using RCW is proposed. The algorithm assumes that each node has a weight, so that the sampling process must select a node with a probability proportional to its weight. This algorithm requires a preprocessing phase before the sampling of nodes. In particular, a minimum diameter spanning tree (MDST) is created in the network, and then nodes' weights are efficiently aggregated using the tree. The good news are that the preprocessing is done only once, regardless of the number of sources and the number of samples taken from the network. After that, every sample is done with a RCW whose length is bounded by the network diameter. Secondly, RCW algorithms that do not require preprocessing are proposed for grids and networks with regular concentric connectivity, for the case when the probability of selecting a node is a function of its distance to the source. The key features of the RCW algorithms (unlike previous Markovian approaches) are that (1) they do not need to warm-up (stabilize), (2) the sampling always finishes in a number of hops bounded by the network diameter, and (3) it selects a node with the exact probability distribution.
Locally monotone Boolean and pseudo-Boolean functions
Venue: arXiv cs.DM 2012
Year: 2012

We propose local versions of monotonicity for Boolean and pseudo-Boolean functions: say that a pseudo-Boolean (Boolean) function is p-locally monotone if none of its partial derivatives changes in sign on tuples which differ in less than p positions. As it turns out, this parameterized notion provides a hierarchy of monotonicities for pseudo-Boolean (Boolean) functions. Local monotonicities are shown to be tightly related to lattice counterparts of classical partial derivatives via the notion of permutable derivatives. More precisely, p-locally monotone functions are shown to have p-permutable lattice derivatives and, in the case of symmetric functions, these two notions coincide. We provide further results relating these two notions, and present a classification of p-locally monotone functions, as well as of functions having p-permutable derivatives, in terms of certain forbidden "sections", i.e., functions which can be obtained by substituting constants for variables. This description is made explicit in the special case when p=2.
On counting untyped lambda terms
Venue: arXiv cs.LO 2012
Year: 2012

We present several results on counting untyped lambda terms, i.e., on telling how many terms belong to such or such class, according to the size of the terms and/or to the number of free variables.
Scale-Free Opportunistic Networks: is it Possible?
Venue: arXiv cs.DC 2012
Year: 2012

The coupling of scale-free networks with mobile unstructured networks is certainly unusual. In mobile networks, connections active at a given instant are constrained by the geographical distribution of mobile nodes, and by the limited signal strength of the wireless technology employed to build the ad-hoc overlay. This is in contrast with the presence of hubs, typical of scale-free nets. However, opportunistic (mobile) networks possess the distinctive feature to be delay tolerant; mobile nodes implement a store, carry and forward strategy that permits to disseminate data based on a multi-hop route, which is built in time, when nodes encounter other ones while moving. In this paper, we consider opportunistic networks as evolving graphs where links represent contacts among nodes arising during a (non-instantaneous) time interval. We discuss a strategy to control the way nodes manage contacts and build "opportunistic overlays". Based on such an approach, interesting overlays can be obtained, shaped following given desired topologies, such as scale-free ones.
Improving Energy Efficiency Through Multimode Transmission in the Downlink MIMO Systems
Venue: arXiv cs.IT 2012
Year: 2012

Adaptively adjusting system parameters including bandwidth, transmit power and mode to maximize the "Bits per-Joule" energy efficiency (BPJ-EE) in the downlink MIMO systems with imperfect channel state information at the transmitter (CSIT) is considered in this paper. By mode we refer to choice of transmission schemes i.e. singular value decomposition (SVD) or block diagonalization (BD), active transmit/receive antenna number and active user number. We derive optimal bandwidth and transmit power for each dedicated mode at first. During the derivation, accurate capacity estimation strategies are proposed to cope with the imperfect CSIT caused capacity prediction problem. Then, an ergodic capacity based mode switching strategy is proposed to further improve the BPJ-EE, which provides insights on the preferred mode under given scenarios. Mode switching compromises different power parts, exploits the tradeoff between the multiplexing gain and the imperfect CSIT caused inter-user interference, improves the BPJ-EE significantly.
On the Sensitivity of Continuous-Time Noncoherent Fading Channel Capacity
Venue: arXiv cs.IT 2012
Year: 2012

The noncoherent capacity of stationary discrete-time fading channels is known to be very sensitive to the fine details of the channel model. More specifically, the measure of the support of the fading-process power spectral density (PSD) determines if noncoherent capacity grows logarithmically in SNR or slower than logarithmically. Such a result is unsatisfactory from an engineering point of view, as the support of the PSD cannot be determined through measurements. The aim of this paper is to assess whether, for general continuous-time Rayleigh-fading channels, this sensitivity has a noticeable impact on capacity at SNR values of practical interest. To this end, we consider the general class of band-limited continuous-time Rayleigh-fading channels that satisfy the wide-sense stationary uncorrelated-scattering (WSSUS) assumption and are, in addition, underspread. We show that, for all SNR values of practical interest, the noncoherent capacity of every channel in this class is close to the capacity of an AWGN channel with the same SNR and bandwidth, independently of the measure of the support of the scattering function (the two-dimensional channel PSD). Our result is based on a lower bound on noncoherent capacity, which is built on a discretization of the channel input-output relation induced by projecting onto Weyl-Heisenberg (WH) sets. This approach is interesting in its own right as it yields a mathematically tractable way of dealing with the mutual information between certain continuous-time random signals.
Hybrid Noncoherent Network Coding
Venue: arXiv cs.IT 2012
Year: 2012

We describe a novel extension of subspace codes for noncoherent networks, suitable for use when the network is viewed as a communication system that introduces both dimension and symbol errors. We show that when symbol erasures occur in a significantly large number of different basis vectors transmitted through the network and when the min-cut of the networks is much smaller then the length of the transmitted codewords, the new family of codes outperforms their subspace code counterparts. For the proposed coding scheme, termed hybrid network coding, we derive two upper bounds on the size of the codes. These bounds represent a variation of the Singleton and of the sphere-packing bound. We show that a simple concatenated scheme that represents a combination of subspace codes and Reed-Solomon codes is asymptotically optimal with respect to the Singleton bound. Finally, we describe two efficient decoding algorithms for concatenated subspace codes that in certain cases have smaller complexity than subspace decoders.
An Algebraic Approach for Decoding Spread Codes
Venue: arXiv cs.IT 2012
Year: 2012

In this paper we study spread codes: a family of constant-dimension codes for random linear network coding. In other words, the codewords are full-rank matrices of size (k x n) with entries in a finite field F_q. Spread codes are a family of optimal codes with maximal minimum distance. We give a minimum-distance decoding algorithm which requires O((n-k)k^3) operations over an extension field F_{q^k}. Our algorithm is more efficient than the previous ones in the literature, when the dimension k of the codewords is small with respect to n. The decoding algorithm takes advantage of the algebraic structure of the code, and it uses original results on minors of a matrix and on the factorization of polynomials over finite fields.
A characterization of entanglement-assisted quantum low-density parity-check codes
Venue: arXiv cs.IT 2012
Year: 2012

As in classical coding theory, quantum analogues of low-density parity-check (LDPC) codes have offered good error correction performance and low decoding complexity by employing the Calderbank-Shor-Steane (CSS) construction. However, special requirements in the quantum setting severely limit the structures such quantum codes can have. While the entanglement-assisted stabilizer formalism overcomes this limitation by exploiting maximally entangled states (ebits), excessive reliance on ebits is a substantial obstacle to implementation. This paper gives necessary and sufficient conditions for the existence of quantum LDPC codes which are obtainable from pairs of identical LDPC codes and consume only one ebit, and studies the spectrum of attainable code parameters.
Understanding need of "Uncertainty Analysis" in the system Design process
Venue: arXiv cs.SE 2012
Year: 2012

Software project development process is requiring accurate software cost and schedule estimation for achieve goal or success. A lot it referred to as the "Intricate brainteaser" because of its conscience attribute which is impact by complexity and uncertainty, Generally estimation is not as difficult or puzzling as people think. In fact, generating accurate estimates is straightforward-once you understand the intensity of uncertainty and module which contribute itself process. In our everyday life, we enhance our estimation based on past experience in which problem solve by which method and in which condition and which opportune provide that method to produce better result . So, Instead of unexplained treatises and inflexible modeling techniques, this will guide highlights a proven set of procedures, understandable formulas, and heuristics that individuals and complete team can apply to their projects to help achieve estimation ability with choose appropriate development approaches In the early stage of software life cycle project manager are inefficient to estimate the effort, schedule, cost estimation and its development approach .This in turn, confuses the manager to bid effectively on software project and choose incorrect development approach. That will directly effect on productivity cycle and increase level of uncertainty. This becomes a strong cause of project failure. So to avoid such problem if we know level and sources of uncertainty in model design, It will directive the developer to design accurate software cost and schedule estimation. which are require l for software project success. This paper demonstrates need of uncertainty analysis module at the modeling process for assist to recognize modular uncertainty system development process and the role of uncertainty at different stages in the modeling
On Noncoherent Fading Relay Channels at High Signal-to-Noise Ratio
Venue: arXiv cs.IT 2012
Year: 2012

The capacity of noncoherent fading relay channels is studied where all terminals are aware of the fading statistics but not of their realizations. It is shown that if the fading coefficient of the channel between the transmitter and the receiver can be predicted more accurately from its infinite past than the fading coefficient of the channel between the relay and the receiver, then at high signal-to-noise ratio (SNR) the relay does not increase capacity. It is further shown that if the fading coefficient of the channel between the transmitter and the relay can be predicted more accurately from its infinite past than the fading coefficient of the channel between the relay and the receiver, then at high SNR one can achieve communication rates that are within one bit of the capacity of the multiple-input single-output fading channel that results when the transmitter and the relay can cooperate.
Premise Selection for Mathematics by Corpus Analysis and Kernel Methods
Venue: arXiv cs.LG 2012
Year: 2012

Smart premise selection is essential when using automated reasoning as a tool for large-theory formal proof development. A good method for premise selection in complex mathematical libraries is the application of machine learning to large corpora of proofs. This work develops learning-based premise selection in two ways. First, a newly available minimal dependency analysis of existing high-level formal mathematical proofs is used to build a large knowledge base of proof dependencies, providing precise data for ATP-based re-verification and for training premise selection algorithms. Second, a new machine learning algorithm for premise selection based on kernel methods is proposed and implemented. To evaluate the impact of both techniques, a benchmark consisting of 2078 large-theory mathematical problems is constructed,extending the older MPTP Challenge benchmark. The combined effect of the techniques results in a 50% improvement on the benchmark over the Vampire/SInE state-of-the-art system for automated reasoning in large theories.
Degrees of Freedom of the Network MIMO Channel With Distributed CSI
Venue: arXiv cs.IT 2012
Year: 2012

In this work, we discuss the joint precoding with finite rate feedback in the so-called network MIMO where the TXs share the knowledge of the data symbols to be transmitted. We introduce a distributed channel state information (DCSI) model where each TX has its own local estimate of the overall multi-user MIMO channel and must make a precoding decision solely based on the available local CSI. We refer to this channel as the DCSI-MIMO channel and the precoding problem as distributed precoding. We extend to the DCSI setting the work from Jindal for the conventional MIMO Broadcast Channel (BC) in which the number of Degrees of Freedom (DoFs) achieved by Zero Forcing (ZF) was derived as a function of the scaling in the logarithm of the Signal-to-Noise Ratio (SNR) of the number of quantizing bits. Particularly, we show the seemingly pessimistic result that the number of DoFs at each user is limited by the worst CSI across all users and across all TXs. This is in contrast to the conventional MIMO BC where the number of DoFs at one user is solely dependent on the quality of the estimation of his own feedback. Consequently, we provide precoding schemes improving on the achieved number of DoFs. For the two-user case, the derived novel precoder achieves a number of DoFs limited by the best CSI accuracy across the TXs instead of the worst with conventional ZF. We also advocate the use of hierarchical quantization of the CSI, for which we show that considerable gains are possible. Finally, we use the previous analysis to derive the DoFs optimal allocation of the feedback bits to the various TXs under a constraint on the size of the aggregate feedback in the network, in the case where conventional ZF is used.
On Quasi-Cyclic Codes as a Generalization of Cyclic Codes
Venue: arXiv cs.IT 2012
Year: 2012

In this article we see quasi-cyclic codes as block cyclic codes. We generalize some properties of cyclic codes to quasi-cyclic ones such as generator polynomials and ideals. Indeed we show a one-to-one correspondence between l-quasi-cyclic codes of length m and ideals of M_l(Fq)[X]/(X^m-1). This permits to construct new classes of codes, namely quasi-BCH and quasi-evaluation codes. We study the parameters of such codes and propose a decoding algorithm up to half the designed minimum distance. We even found one new quasi-cyclic code with better parameters than known [189, 11, 125]_F4 and 48 derivated codes beating the known bounds as well.
An Efficient Algorithm for Finding Dominant Trapping Sets of LDPC Codes
Venue: arXiv cs.IT 2012
Year: 2012

This paper presents an efficient algorithm for finding the dominant trapping sets of a low-density parity-check (LDPC) code. The algorithm can be used to estimate the error floor of LDPC codes or to be part of the apparatus to design LDPC codes with low error floors. For regular codes, the algorithm is initiated with a set of short cycles as the input. For irregular codes, in addition to short cycles, variable nodes with low degree and cycles with low approximate cycle extrinsic message degree (ACE) are also used as the initial inputs. The initial inputs are then expanded recursively to dominant trapping sets of increasing size. At the core of the algorithm lies the analysis of the graphical structure of dominant trapping sets and the relationship of such structures to short cycles, low-degree variable nodes and cycles with low ACE. The algorithm is universal in the sense that it can be used for an arbitrary graph and that it can be tailored to find other graphical objects, such as absorbing sets and Zyablov-Pinsker (ZP) trapping sets, known to dominate the performance of LDPC codes in the error floor region over different channels and for different iterative decoding algorithms. Simulation results on several LDPC codes demonstrate the accuracy and efficiency of the proposed algorithm. In particular, the algorithm is significantly faster than the existing search algorithms for dominant trapping sets.
Designing Practical Distributed Exchange for Online Communities
Venue: arXiv cs.GT 2012
Year: 2012

In many online systems, individuals provide services for each other; the recipient of the service obtains a benefit but the provider of the service incurs a cost. If benefit exceeds cost, provision of the service increases social welfare and should therefore be encouraged -- but the individuals providing the service gain no (immediate) benefit from providing the service and hence have an incentive to withhold service. Hence there is scope for designing a system that improves welfare by encouraging exchange. To operate successfully within the confines of the online environment, such a system should be distributed, practicable, and consistent with individual incentives. This paper proposes and analyzes a simple such system that relies on the exchange of {\em tokens}; the emphasis is on the design of a protocol (number of tokens and suggested strategies). We provide estimates for the efficiency of such protocols and show that choosing the right protocol will lead to almost full efficiency if agents are sufficiently patient. However, choosing the wrong protocols may lead to an enormous loss of efficiency.
Foundations of Traversal Based Query Execution over Linked Data (Extended Version)
Venue: arXiv cs.DB 2012
Year: 2012

Query execution over the Web of Linked Data has attracted much attention recently. A particularly interesting approach is link traversal based query execution which proposes to integrate the traversal of data links into the construction of query results. Hence -in contrast to traditional query execution paradigms- this approach does not assume a fixed set of relevant data sources beforehand; instead, it discovers data on the fly and, thus, enables applications to tap the full potential of the Web. While several authors study possibilities to implement the idea of link traversal based query execution and to optimize query execution in this context, no work exists that discusses the theoretical foundations of the approach in general. Our paper fills this gap. We introduce a well-defined semantics for queries that may be executed using the link traversal based approach. Based on this semantics we formally analyze properties of such queries. In particular, we study the computability of queries as well as the implications of querying a potentially infinite Web of Linked Data. Our results show that query computation in general is not guaranteed to terminate and that for any given query it is undecidable whether the execution terminates. Furthermore, we define an abstract execution model that captures the integration of link traversal into the query execution process. Based on this model we prove the soundness and completeness of link traversal based query execution and analyze an existing implementation approach..
Directed Information, Causal Estimation, and Communication in Continuous Time
Venue: arXiv cs.IT 2012
Year: 2012

A notion of directed information between two continuous-time processes is proposed. A key component in the definition is taking an infimum over all possible partitions of the time interval, which plays a role no less significant than the supremum over "space" partitions inherent in the definition of mutual information. Properties and operational interpretations in estimation and communication are then established for the proposed notion of directed information. For the continuous-time additive white Gaussian noise channel, it is shown that Duncan's classical relationship between causal estimation and information continues to hold in the presence of feedback upon replacing mutual information by directed information. A parallel result is established for the Poisson channel. The utility of this relationship is then demonstrated in computing the directed information rate between the input and output processes of a continuous-time Poisson channel with feedback, where the channel input process is constrained to be constant between events at the channel output. Finally, the capacity of a wide class of continuous-time channels with feedback is established via directed information, characterizing the fundamental limit on reliable communication.
Fixed point forms of the parallel symmetric sandpile model
Venue: arXiv cs.DM 2012
Year: 2012

This paper presents a generalization of the sandpile model, called the parallel symmetric sandpile model, which inherits the rules of the symmetric sandpile model and implements them in parallel. In this new model, at each step the collapsing of the collapsible columns happens at the same time and one collapsible column is able to collapse on the left or on the right but not both. We prove that the set of forms of fixed points of the symmetric sandpile model is the same as the one of that model using parallel update scheme by constructing explicitly the way (in the parallel update scheme) to reach the form of an arbitrary fixed point of the sequential model.
Tolerant identification with Euclidean balls
Venue: arXiv cs.IT 2012
Year: 2012

The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. The identifying codes can be applied, for example, to sensor networks. In this paper, we consider as sensors the set Z^2 where one sensor can check its neighbours within Euclidean distance r. We construct tolerant identifying codes in this network that are robust against some changes in the neighbourhood monitored by each sensor. We give bounds for the smallest density of a tolerant identifying code for general values of r and Delta. We also provide infinite families of values (r,Delta) with optimal such codes and study the case of small values of r.