OpenRaiser/Intern-Atlas huggingface dataset:
Transmission capacity of wireless networks
Venue: arXiv cs.IT 2012
Year: 2012

Transmission capacity (TC) is a performance metric for wireless networks that measures the spatial intensity of successful transmissions per unit area, subject to a constraint on the permissible outage probability (where outage occurs when the SINR at a receiver is below a threshold). This volume gives a unified treatment of the TC framework that has been developed by the authors and their collaborators over the past decade. The mathematical framework underlying the analysis (reviewed in Ch. 2) is stochastic geometry: Poisson point processes model the locations of interferers, and (stable) shot noise processes represent the aggregate interference seen at a receiver. Ch. 3 presents TC results (exact, asymptotic, and bounds) on a simple model in order to illustrate a key strength of the framework: analytical tractability yields explicit performance dependence upon key model parameters. Ch. 4 presents enhancements to this basic model --- channel fading, variable link distances, and multi-hop. Ch. 5 presents four network design case studies well-suited to TC: i) spectrum management, ii) interference cancellation, iii) signal threshold transmission scheduling, and iv) power control. Ch. 6 studies the TC when nodes have multiple antennas, which provides a contrast vs. classical results that ignore interference.
Tree-Structure Expectation Propagation for LDPC Decoding over the BEC
Venue: arXiv cs.IT 2012
Year: 2012

We present the tree-structure expectation propagation (Tree-EP) algorithm to decode low-density parity-check (LDPC) codes over discrete memoryless channels (DMCs). EP generalizes belief propagation (BP) in two ways. First, it can be used with any exponential family distribution over the cliques in the graph. Second, it can impose additional constraints on the marginal distributions. We use this second property to impose pair-wise marginal constraints over pairs of variables connected to a check node of the LDPC code's Tanner graph. Thanks to these additional constraints, the Tree-EP marginal estimates for each variable in the graph are more accurate than those provided by BP. We also reformulate the Tree-EP algorithm for the binary erasure channel (BEC) as a peeling-type algorithm (TEP) and we show that the algorithm has the same computational complexity as BP and it decodes a higher fraction of errors. We describe the TEP decoding process by a set of differential equations that represents the expected residual graph evolution as a function of the code parameters. The solution of these equations is used to predict the TEP decoder performance in both the asymptotic regime and the finite-length regime over the BEC. While the asymptotic threshold of the TEP decoder is the same as the BP decoder for regular and optimized codes, we propose a scaling law (SL) for finite-length LDPC codes, which accurately approximates the TEP improved performance and facilitates its optimization.
Spectrum Sensing in the Presence of Multiple Primary Users
Venue: arXiv cs.IT 2012
Year: 2012

We consider multi-antenna cooperative spectrum sensing in cognitive radio networks, when there may be multiple primary users. A detector based on the spherical test is analyzed in such a scenario. Based on the moments of the distributions involved, simple and accurate analytical formulae for the key performance metrics of the detector are derived. The false alarm and the detection probabilities, as well as the detection threshold and Receiver Operation Characteristics are available in closed form. Simulations are provided to verify the accuracy of the derived results, and to compare with other detectors in realistic sensing scenarios.
Rapid Application Development Using Software Factories
Venue: arXiv cs.SE 2012
Year: 2012

Software development is still based on manufactory production, and most of the programming code is still hand-crafted. Software development is very far away from the ultimate goal of industrialization in software production, something which has been achieved long time ago in the other industries. The lack of software industrialization creates an inability to cope with fast and frequent changes in user requirements, and causes cost and time inefficiencies during their implementation. Analogous to what other industries had done long time ago, industrialization of software development has been proposed using the concept of software factories. We have accepted this vision about software factories, and developed our own software factory which produces three-layered ASP.NET web applications. In this paper we report about our experience with using this approach in the process of software development, and present comparative results on performances and deliverables in both traditional development and development using software factories.
Towards Self-Service Governance by Means of Information Technology
Venue: arXiv cs.CY 2012
Year: 2012

In this paper we present a novel model for governing societies based on modern information technology, which neither relies on manual bureaucratic labor, nor depends on process-based e-government services for governance. We expose the flaws of the later and argue that it is not feasible for sustainable governance due to permanently changing laws and instead propose a model in which people can govern themselves in a self-service manner by relying on constellations of data stored in a network of governmental databases to which citizen and officials have read- and write access under rules defined by temporary valid law.
Non-crossing Connectors in the Plane
Venue: arXiv cs.CG 2012
Year: 2012

We consider the non-crossing connectors problem, which is stated as follows: Given n simply connected regions R_1,...,R_n in the plane and finite point sets P_i subset of R_i for i=1,...,n, are there non-crossing connectors y_i for (R_i,P_i), i.e., arc-connected sets y_i with P_i subset of y_i subset of R_i for every i=1,...,n, such that y_i and y_j are disjoint for all i different from j? We prove that non-crossing connectors do always exist if the regions form a collection of pseudo-disks, i.e., the boundaries of every pair of regions intersect at most twice. We provide a simple polynomial-time algorithm if the regions are axis-aligned rectangles. Finally we prove that the general problem is NP-complete, even if the regions are convex, the boundaries of every pair of regions intersect at most four times and P_i consists of only two points on the boundary of R_i for i=1,...,n.
Competitive Comparison of Optimal Designs of Experiments for Sampling-based Sensitivity Analysis
Venue: arXiv cs.CE 2012
Year: 2012

Nowadays, the numerical models of real-world structures are more precise, more complex and, of course, more time-consuming. Despite the growth of a computational effort, the exploration of model behaviour remains a complex task. The sensitivity analysis is a basic tool for investigating the sensitivity of the model to its inputs. One widely used strategy to assess the sensitivity is based on a finite set of simulations for a given sets of input parameters, i.e. points in the design space. An estimate of the sensitivity can be then obtained by computing correlations between the input parameters and the chosen response of the model. The accuracy of the sensitivity prediction depends on the choice of design points called the design of experiments. The aim of the presented paper is to review and compare available criteria determining the quality of the design of experiments suitable for sampling-based sensitivity analysis.
UMTS-WiMAX Vertical Handover in Next Generation Wireless Networks
Venue: arXiv cs.NI 2012
Year: 2012

The vision of next generation wireless network (NGWN) is to integrate different wireless access technologies, each with its own characteristics, into a common IP-based core network to provide mobile user with service continuity and seamless roaming. One of the major issues for the converged heterogeneous networks is providing a seamless vertical handover (VHO) with QoS support. In this paper we have reviewed the various interworking architectures and handover scenarios between UMTS and WiMAX. Also, we have compared the proposed solutions based on different criteria and revealed the pros and cons of each scheme. The comparison aids to adopt a better interworking and handover mechanism in NGWN.
Provably Total Functions of Arithmetic with Basic Terms
Venue: arXiv cs.LO 2012
Year: 2012

A new characterization of provably recursive functions of first-order arithmetic is described. Its main feature is using only terms consisting of 0, the successor S and variables in the quantifier rules, namely, universal elimination and existential introduction.
Information Distance: New Developments
Venue: arXiv cs.CV 2012
Year: 2012

In pattern recognition, learning, and data mining one obtains information from information-carrying objects. This involves an objective definition of the information in a single object, the information to go from one object to another object in a pair of objects, the information to go from one object to any other object in a multiple of objects, and the shared information between objects. This is called "information distance." We survey a selection of new developments in information distance.
A Representation of Binary Matrices
Venue: arXiv cs.MS 2012
Year: 2012

In this article we discuss the presentation of a random binary matrix using sequence of whole nonnegative numbers. We examine some advantages and disadvantages of this presentation as an alternative of the standard presentation using two-dimensional array. It is shown that the presentation of binary matrices using ordered n-tuples of natural numbers makes the algorithms faster and saves a lot of memory. In this work we use object-oriented programming using the syntax and the semantic of C++ programming language.
Identifying Clusters of Concepts in a Low Cohesive Class for Extract Class Refactoring Using Metrics Supplemented Agglomerative Clustering Technique
Venue: arXiv cs.SE 2012
Year: 2012

Object oriented software with low cohesive classes can increase maintenance cost. Low cohesive classes are likely to be introduced into the software during initial design due to deviation from design principles and during evolution due to software deterioration. Low cohesive class performs operations that should be done by two or more classes. The low cohesive classes need to be identified and refactored using extract class refactoring to improve the cohesion. In this regard, two aspects are involved; the first one is to identify the low cohesive classes and the second one is to identify the clusters of concepts in the low cohesive classes for extract class refactoring. In this paper, we propose metrics supplemented agglomerative clustering technique for covering the above two aspects. The proposed metrics are validated using Weyuker's properties. The approach is applied successfully on two examples and on a case study.
A direct product theorem for bounded-round public-coin randomized communication complexity
Venue: arXiv cs.CC 2012
Year: 2012

In this paper, we show a direct product theorm in the model of two-party bounded-round public-coin randomized communication complexity. For a relation f subset of X times Y times Z (X,Y,Z are finite sets), let R^{(t), pub}_e (f) denote the two-party t-message public-coin communication complexity of f with worst case error e. We show that for any relation f and positive integer k: R^{(t), pub}_{1 - 2^{-Omega(k/t^2)}}(f^k) = Omega(k/t (R^{(t), pub}_{1/3}(f) - O(t^2))) . In particular, it implies a strong direct product theorem for the two-party constant-message public-coin randomized communication complexity of all relations f. Our result for example implies a strong direct product theorem for the pointer chasing problem. This problem has been well studied for understanding round v/s communication trade-offs in both classical and quantum communication protocols. We show our result using information theoretic arguments. Our arguments and techniques build on the ones used in [Jain 2011], where a strong direct product theorem for the two-party one-way public-coin communication complexity of all relations is shown (that is the special case of our result when t=1). One key tool used in our work and also in [Jain 2011] is a message compression technique due to [Braverman and Rao 2011], who used it to show a direct sum theorem for the two-party bounded-round public-coin randomized communication complexity of all relations. Another important tool that we use is a correlated sampling protocol, which for example, has been used in [Holenstein 2007] for proving a parallel repetition theorem for two-prover games.
A Survey on Dynamic Spectrum Access Techniques for Cognitive Radio
Venue: arXiv cs.NI 2012
Year: 2012

Cognitive radio (CR) is a new paradigm that utilizes the available spectrum band. The key characteristic of CR system is to sense the electromagnetic environment to adapt their operation and dynamically vary its radio operating parameters. The technique of dynamically accessing the unused spectrum band is known as Dynamic Spectrum Access (DSA). The dynamic spectrum access technology helps to minimize unused spectrum bands. In this paper, main functions of Cognitive Radio (CR) i.e. spectrum sensing, spectrum management, spectrum mobility and spectrum sharing are discussed. Then DSA models are discussed along with different methods of DSA such as Command and Control, Exclusive-Use, Shared Use of Primary Licensed User and Commons method. Game-theoretic approach using Bertrand game model, Markovian Queuing Model for spectrum allocation in centralized architecture and Fuzzy logic based method are also discussed and result are shown.
Information Hiding in CSS : A Secure Scheme Text-Steganography using Public Key Cryptosystem
Venue: arXiv cs.CR 2012
Year: 2012

In many recent years, the programming world has been introduced about a new programming language for designing websites, it is CSS that can be be used together with HTML to develop a web interface. And now, these two programming languages as if inseparably from each other. As a client-side scripting, CSS is visible by all users as the original script, but it can not be granted changed. Website is a tool of information disseminator throughout the world, this is certainly can be used to a secret communication by using CSS as a message hider. This paper proposed a new scheme using web tools like CSS for hiding informations. This is a secret communication mechanism using text steganography techniques that is embedded messages on CSS files and is further encrypted using RSA as a public key cryptographic algorithm.
Order-Degree Curves for Hypergeometric Creative Telescoping
Venue: arXiv cs.SC 2012
Year: 2012

Creative telescoping applied to a bivariate proper hypergeometric term produces linear recurrence operators with polynomial coefficients, called telescopers. We provide bounds for the degrees of the polynomials appearing in these operators. Our bounds are expressed as curves in the (r,d)-plane which assign to every order r a bound on the degree d of the telescopers. These curves are hyperbolas, which reflect the phenomenon that higher order telescopers tend to have lower degree, and vice versa.
Adaptive Context Tree Weighting
Venue: arXiv cs.IT 2012
Year: 2012

We describe an adaptive context tree weighting (ACTW) algorithm, as an extension to the standard context tree weighting (CTW) algorithm. Unlike the standard CTW algorithm, which weights all observations equally regardless of the depth, ACTW gives increasing weight to more recent observations, aiming to improve performance in cases where the input sequence is from a non-stationary distribution. Data compression results show ACTW variants improving over CTW on merged files from standard compression benchmark tests while never being significantly worse on any individual file.
Sentence based semantic similarity measure for blog-posts
Venue: arXiv cs.AI 2012
Year: 2012

Blogs-Online digital diary like application on web 2.0 has opened new and easy way to voice opinion, thoughts, and like-dislike of every Internet user to the World. Blogosphere has no doubt the largest user-generated content repository full of knowledge. The potential of this knowledge is still to be explored. Knowledge discovery from this new genre is quite difficult and challenging as it is totally different from other popular genre of web-applications like World Wide Web (WWW). Blog-posts unlike web documents are small in size, thus lack in context and contain relaxed grammatical structures. Hence, standard text similarity measure fails to provide good results. In this paper, specialized requirements for comparing a pair of blog-posts is thoroughly investigated. Based on this we proposed a novel algorithm for sentence oriented semantic similarity measure of a pair of blog-posts. We applied this algorithm on a subset of political blogosphere of Pakistan, to cluster the blogs on different issues of political realm and to identify the influential bloggers.
Cooperation and its evolution in growing systems with cultural reproduction
Venue: arXiv cs.GT 2012
Year: 2012

We explore the evolution of cooperation in the framework of the evolutionary game theory using the prisoner's dilemma as metaphor of the problem. We present a minimal model taking into account the growing process of the systems and individuals with imitation capacity. We consider the topological structure and the evolution of strategies decoupled instead of a coevolutionary dynamic. We show conditions to build up a cooperative system with real topological structures for any natural selection intensity. When the system starts to grow, cooperation is unstable but becomes stable as soon as the system reaches a small core of cooperators whose size increase when the intensity of natural selection decreases. Thus, we reduce the emergence of cooperative systems with cultural reproduction to justify a small initial cooperative structure that we call cooperative seed. Otherwise, given that the system grows principally as cooperator whose cooperators inhabit the most linked parts of the system, the benefit-cost ratio required for cooperation evolve is drastically reduced compared to the found in static networks. In this way, we show that in systems whose individuals have imitation capacity the growing process is essential for the evolution of cooperation.
Memory-Assisted Universal Source Coding
Venue: arXiv cs.IT 2012
Year: 2012

The problem of the universal compression of a sequence from a library of several small to moderate length sequences from similar context arises in many practical scenarios, such as the compression of the storage data and the Internet traffic. In such scenarios, it is often required to compress and decompress every sequence individually. However, the universal compression of the individual sequences suffers from significant redundancy overhead. In this paper, we aim at answering whether or not having a memory unit in the middle can result in a fundamental gain in the universal compression. We present the problem setup in the most basic scenario consisting of a server node $S$, a relay node $R$ (i.e., the memory unit), and a client node $C$. We assume that server $S$ wishes to send the sequence $x^n$ to the client $C$ who has never had any prior communication with the server, and hence, is not capable of memorization of the source context. However, $R$ has previously communicated with $S$ to forward previous sequences from $S$ to the clients other than $C$, and thus, $R$ has memorized a context $y^m$ shared with $S$. Note that if the relay node was absent the source could possibly apply universal compression to $x^n$ and transmit to $C$ whereas the presence of memorized context at $R$ can possibly reduce the communication overhead in $S$-$R$ link. In this paper, we investigate the fundamental gain of the context memorization in the memory-assisted universal compression of the sequence $x^n$ over conventional universal source coding by providing a lower bound on the gain of memory-assisted source coding.
Reduced Functional Dependence Graph and Its Applications
Venue: arXiv cs.IT 2012
Year: 2012

Functional dependence graph (FDG) is an important class of directed graph that captures the dominance relationship among a set of variables. FDG is frequently used in calculating network coding capacity bounds. However, the order of FDG is usually much larger than the original network and the computational complexity of many bounds grows exponentially with the order of FDG. In this paper, we introduce the concept of reduced FDG, which is obtained from the original FDG by keeping only those "essential" edges. It is proved that the reduced FDG gives the same capacity region/bounds with the original FDG, but requiring much less computation. The applications of reduced FDG in the algebraic formulation of scalar linear network coding is also discussed.
A Well-typed Lightweight Situation Calculus
Venue: arXiv cs.PL 2012
Year: 2012

Situation calculus has been widely applied in Artificial Intelligence related fields. This formalism is considered as a dialect of logic programming language and mostly used in dynamic domain modeling. However, type systems are hardly deployed in situation calculus in the literature. To achieve a correct and sound typed program written in situation calculus, adding typing elements into the current situation calculus will be quite helpful. In this paper, we propose to add more typing mechanisms to the current version of situation calculus, especially for three basic elements in situation calculus: situations, actions and objects, and then perform rigid type checking for existing situation calculus programs to find out the well-typed and ill-typed ones. In this way, type correctness and soundness in situation calculus programs can be guaranteed by type checking based on our type system. This modified version of a lightweight situation calculus is proved to be a robust and well-typed system.
Nearly Optimal Sparse Fourier Transform
Venue: arXiv cs.DS 2012
Year: 2012

We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. We show: * An O(k log n)-time randomized algorithm for the case where the input signal has at most k non-zero Fourier coefficients, and * An O(k log n log(n/k))-time randomized algorithm for general input signals. Both algorithms achieve o(n log n) time, and thus improve over the Fast Fourier Transform, for any k = o(n). They are the first known algorithms that satisfy this property. Also, if one assumes that the Fast Fourier Transform is optimal, the algorithm for the exactly k-sparse case is optimal for any k = n^{Ω(1)}. We complement our algorithmic results by showing that any algorithm for computing the sparse Fourier transform of a general signal must use at least Ω(k log(n/k)/ log log n) signal samples, even if it is allowed to perform adaptive sampling.
On the security of an enhanced short signature scheme
Venue: arXiv cs.CR 2012
Year: 2012

Currently, short signature is receiving significant attention since it is particularly useful in low-bandwidth communication environments. However, most of the short signature schemes are only based on one intractable assumption. Recently, Su presented an identity-based short signature scheme based on knapsack and bilinear pairing. He claimed that the signature scheme is secure in the random oracle model. Unfortunately, in this paper, we show that his scheme is insecure. Concretely, an adversary can forge a valid signature on any message with respect to any identity in Su's scheme.