OpenRaiser/Intern-Atlas huggingface dataset:
Overview of MC CDMA PAPR Reduction Techniques
Venue: arXiv cs.NI 2012
Year: 2012

High Peak to Average Power Ratio (PAPR) of the transmitted signal is a critical problem in multicarrier modulation systems (MCM) such as Orthogonal Frequency Division Multiplexing (OFDM), and Multi-Carrier Code Division Multiple Access (MC CDMA) systems, due to large number of subcarriers. High PAPR leads to reduced resolution, and battery life. It also deteriorates system performance. This paper focuses on review of different PAPR reduction techniques with attendant technical issues as well as criteria for selection of PAPR reduction technique. To reduce PAPR the constraints are low power consumption, and low Bit Error Rate (BER). Spectral bandwidth is improved by better spectral characteristics, and low complexity/cost.
Asynchrony and Collusion in the N-party BAR Transfer Problem
Venue: arXiv cs.DC 2012
Year: 2012

The problem of reliably transferring data from a set of $N_P$ producers to a set of $N_C$ consumers in the BAR model, named N-party BAR Transfer (NBART), is an important building block for volunteer computing systems. An algorithm to solve this problem in synchronous systems, which provides a Nash equilibrium, has been presented in previous work. In this paper, we propose an NBART algorithm for asynchronous systems. Furthermore, we also address the possibility of collusion among the Rational processes. Our game theoretic analysis shows that the proposed algorithm tolerates certain degree of arbitrary collusion, while still fulfilling the NBART properties.
Modulation Diversity for Spatial Modulation Using Complex Interleaved Orthogonal Design
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we propose modulation diversity techniques for Spatial Modulation (SM) system using Complex Interleaved Orthogonal Design (CIOD) meant for two transmit antennas. Specifically, we show that by using the CIOD for two transmit antenna system, the standard SM scheme, where only one transmit antenna is activated in any symbol duration, can achieve a transmit diversity order of two. We show with our simulation results that the proposed schemes offer transmit diversity order of two, and hence, give a better Symbol Error Rate performance than the SM scheme with transmit diversity order of one.
Resource Buying Games
Venue: arXiv cs.GT 2012
Year: 2012

In resource buying games a set of players jointly buys a subset of a finite resource set E (e.g., machines, edges, or nodes in a digraph). The cost of a resource e depends on the number (or load) of players using e, and has to be paid completely by the players before it becomes available. Each player i needs at least one set of a predefined family S_i in 2^E to be available. Thus, resource buying games can be seen as a variant of congestion games in which the load-dependent costs of the resources can be shared arbitrarily among the players. A strategy of player i in resource buying games is a tuple consisting of one of i's desired configurations S_i together with a payment vector p_i in R^E_+ indicating how much i is willing to contribute towards the purchase of the chosen resources. In this paper, we study the existence and computational complexity of pure Nash equilibria (PNE, for short) of resource buying games. In contrast to classical congestion games for which equilibria are guaranteed to exist, the existence of equilibria in resource buying games strongly depends on the underlying structure of the S_i's and the behavior of the cost functions. We show that for marginally non-increasing cost functions, matroids are exactly the right structure to consider, and that resource buying games with marginally non-decreasing cost functions always admit a PNE.
Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding
Venue: arXiv cs.IT 2012
Year: 2012

We give a new construction of algebraic codes which are efficiently list decodable from a fraction $1-R-\eps$ of adversarial errors where $R$ is the rate of the code, for any desired positive constant $\eps$. The worst-case list size output by the algorithm is $O(1/\eps)$, matching the existential bound for random codes up to constant factors. Further, the alphabet size of the codes is a constant depending only on $\eps$ - it can be made $\exp(\tilde{O}(1/\eps^2))$ which is not much worse than the lower bound of $\exp(Ω(1/\eps))$. The parameters we achieve are thus quite close to the existential bounds in all three aspects - error-correction radius, alphabet size, and list-size - simultaneously. Our code construction is Monte Carlo and has the claimed list decoding property with high probability. Once the code is (efficiently) sampled, the encoding/decoding algorithms are deterministic with a running time $O_\eps(N^c)$ for an absolute constant $c$, where $N$ is the code's block length. Our construction is based on a linear-algebraic approach to list decoding folded codes from towers of function fields, and combining it with a special form of subspace-evasive sets. Instantiating this with the explicit "asymptotically good" Garcia-Stichtenoth tower of function fields yields the above parameters. To illustrate the method in a simpler setting, we also present a construction based on Hermitian function fields, which offers similar guarantees with a list and alphabet size polylogarithmic in the block length $N$. Along the way, we shed light on how to use automorphisms of certain function fields to enable list decoding of the folded version of the associated algebraic-geometric codes.
Higher Order City Voronoi Diagrams
Venue: arXiv cs.CG 2012
Year: 2012

We investigate higher-order Voronoi diagrams in the city metric. This metric is induced by quickest paths in the L1 metric in the presence of an accelerating transportation network of axis-parallel line segments. For the structural complexity of kth-order city Voronoi diagrams of n point sites, we show an upper bound of O(k(n - k) + kc) and a lower bound of Ω(n + kc), where c is the complexity of the transportation network. This is quite different from the bound O(k(n - k)) in the Euclidean metric. For the special case where k = n - 1 the complexity in the Euclidean metric is O(n), while that in the city metric is Θ(nc). Furthermore, we develop an O(k^2(n + c) log n)-time iterative algorithm to compute the kth-order city Voronoi diagram and an O(nc log^2(n + c) log n)-time divide-and-conquer algorithm to compute the farthest-site city Voronoi diagram.
Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash
Venue: arXiv cs.DS 2012
Year: 2012

It is shown that for cuckoo hashing with a stash as proposed by Kirsch, Mitzenmacher, and Wieder (2008) families of very simple hash functions can be used, maintaining the favorable performance guarantees: with stash size $s$ the probability of a rehash is $O(1/n^{s+1})$, and the evaluation time is $O(s)$. Instead of the full randomness needed for the analysis of Kirsch et al. and of Kutzelnigg (2010) (resp. $Θ(\log n)$-wise independence for standard cuckoo hashing) the new approach even works with 2-wise independent hash families as building blocks. Both construction and analysis build upon the work of Dietzfelbinger and Woelfel (2003). The analysis, which can also be applied to the fully random case, utilizes a graph counting argument and is much simpler than previous proofs. As a byproduct, an algorithm for simulating uniform hashing is obtained. While it requires about twice as much space as the most space efficient solutions, it is attractive because of its simple and direct structure.
A Privacy-Aware Bayesian Approach for Combining Classifier and Cluster Ensembles
Venue: arXiv cs.LG 2012
Year: 2012

This paper introduces a privacy-aware Bayesian approach that combines ensembles of classifiers and clusterers to perform semi-supervised and transductive learning. We consider scenarios where instances and their classification/clustering results are distributed across different data sites and have sharing restrictions. As a special case, the privacy aware computation of the model when instances of the target data are distributed across different data sites, is also discussed. Experimental results show that the proposed approach can provide good classification accuracies while adhering to the data/model sharing constraints.
Performance Evaluation of QoS Parameters in Dynamic Spectrum Sharing for Heterogeneous Wireless Communication Networks
Venue: arXiv cs.NI 2012
Year: 2012

Cognitive radio nodes have been proposed as means to improve the spectrum utilization. It reuses the spectrum of a primary service provider under the condition that the primary service provider services are not harmfully interrupted. A cognitive radio can sense its operating environment's conditions and it is able to reconfigure itself and to communicate with other counterparts based on the status of the environment and also the requirements of the user to meet the optimal communication conditions and to keep quality of service (QoS) as high as possible. The efficiency of spectrum sharing can be improved by minimizing the interference. The Utility function that captures the cooperative behavior to minimize the interference and the satisfaction to improve the throughput is investigated. The dynamic spectrum sharing algorithm can maintain the quality of service (QoS) of each network while the effective spectrum utilisation is improved under a fluctuation traffic environment when the available spectrum is limited.
On the Minimum Degree up to Local Complementation: Bounds and Complexity
Venue: arXiv cs.CC 2012
Year: 2012

The local minimum degree of a graph is the minimum degree reached by means of a series of local complementations. In this paper, we investigate on this quantity which plays an important role in quantum computation and quantum error correcting codes. First, we show that the local minimum degree of the Paley graph of order p is greater than sqrt{p} - 3/2, which is, up to our knowledge, the highest known bound on an explicit family of graphs. Probabilistic methods allows us to derive the existence of an infinite number of graphs whose local minimum degree is linear in their order with constant 0.189 for graphs in general and 0.110 for bipartite graphs. As regards the computational complexity of the decision problem associated with the local minimum degree, we show that it is NP-complete and that there exists no k-approximation algorithm for this problem for any constant k unless P = NP.
Logic Characterization of Floyd Languages
Venue: arXiv cs.FL 2012
Year: 2012

Floyd languages (FL), alias Operator Precedence Languages, have recently received renewed attention thanks to their closure properties and local parsability which allow one to apply automatic verification techniques (e.g. model checking) and parallel and incremental parsing. They properly include various other classes, noticeably Visual Pushdown languages. In this paper we provide a characterization of FL in terms a monadic second order logic (MSO), in the same style as Buchi's one for regular languages. We prove the equivalence between automata recognizing FL and the MSO formalization.
String Trees
Venue: arXiv cs.DS 2012
Year: 2012

A string-like compact data structure for unlabelled rooted trees is given using 2n bits.
EHRs Connect Research and Practice: Where Predictive Modeling, Artificial Intelligence, and Clinical Decision Support Intersect
Venue: arXiv cs.AI 2012
Year: 2012

Objectives: Electronic health records (EHRs) are only a first step in capturing and utilizing health-related data - the challenge is turning that data into useful information. Furthermore, EHRs are increasingly likely to include data relating to patient outcomes, functionality such as clinical decision support, and genetic information as well, and, as such, can be seen as repositories of increasingly valuable information about patients' health conditions and responses to treatment over time. Methods: We describe a case study of 423 patients treated by Centerstone within Tennessee and Indiana in which we utilized electronic health record data to generate predictive algorithms of individual patient treatment response. Multiple models were constructed using predictor variables derived from clinical, financial and geographic data. Results: For the 423 patients, 101 deteriorated, 223 improved and in 99 there was no change in clinical condition. Based on modeling of various clinical indicators at baseline, the highest accuracy in predicting individual patient response ranged from 70-72% within the models tested. In terms of individual predictors, the Centerstone Assessment of Recovery Level - Adult (CARLA) baseline score was most significant in predicting outcome over time (odds ratio 4.1 + 2.27). Other variables with consistently significant impact on outcome included payer, diagnostic category, location and provision of case management services. Conclusions: This approach represents a promising avenue toward reducing the current gap between research and practice across healthcare, developing data-driven clinical decision support based on real-world populations, and serving as a component of embedded clinical artificial intelligences that "learn" over time.
Enumerating regular expressions and their languages
Venue: arXiv cs.FL 2012
Year: 2012

In this chapter we discuss the problem of enumerating distinct regular expressions by size and the regular languages they represent. We discuss various notions of the size of a regular expression that appear in the literature and their advantages and disadvantages. We consider a formal definition of regular expressions using a context-free grammar. We then show how to enumerate strings generated by an unambiguous context-free grammar using the Chomsky-Schützenberger theorem. This theorem allows one to construct an algebraic equation whose power series expansion provides the enumeration. Classical tools from complex analysis, such as singularity analysis, can then be used to determine the asymptotic behavior of the enumeration. We use these algebraic and analytic methods to obtain asymptotic estimates on the number of regular expressions of size n. A single regular language can often be described by several regular expressions, and we estimate the number of distinct languages denoted by regular expressions of size n. We also give asymptotic estimates for these quantities. For the first few values, we provide exact enumeration results.
Comparison of Different Parallel Implementations of the 2+1-Dimensional KPZ Model and the 3-Dimensional KMC Model
Venue: arXiv cs.DC 2012
Year: 2012

We show that efficient simulations of the Kardar-Parisi-Zhang interface growth in 2 + 1 dimensions and of the 3-dimensional Kinetic Monte Carlo of thermally activated diffusion can be realized both on GPUs and modern CPUs. In this article we present results of different implementations on GPUs using CUDA and OpenCL and also on CPUs using OpenCL and MPI. We investigate the runtime and scaling behavior on different architectures to find optimal solutions for solving current simulation problems in the field of statistical physics and materials science.
Smart Sort: Design and Analysis of a Fast, Efficient and Robust Comparison Based Internal Sort Algorithm
Venue: arXiv cs.DS 2012
Year: 2012

Smart Sort algorithm is a "smart" fusion of heap construction procedures (of Heap sort algorithm) into the conventional "Partition" function (of Quick sort algorithm) resulting in a robust version of Quick sort algorithm. We have also performed empirical analysis of average case behavior of our proposed algorithm along with the necessary theoretical analysis for best and worst cases. Its performance was checked against some standard probability distributions, both uniform and non-uniform, like Binomial, Poisson, Discrete & Continuous Uniform, Exponential, and Standard Normal. The analysis exhibited the desired robustness coupled with excellent performance of our algorithm. Although this paper assumes the static partition ratios, its dynamic version is expected to yield still better results.
Reimplementing the Mathematical Subject Classification (MSC) as a Linked Open Dataset
Venue: arXiv cs.DL 2012
Year: 2012

The Mathematics Subject Classification (MSC) is a widely used scheme for classifying documents in mathematics by subject. Its traditional, idiosyncratic conceptualization and representation makes the scheme hard to maintain and requires custom implementations of search, query and annotation support. This limits uptake e.g. in semantic web technologies in general and the creation and exploration of connections between mathematics and related domains (e.g. science) in particular. This paper presents the new official implementation of the MSC2010 as a Linked Open Dataset, building on SKOS (Simple Knowledge Organization System). We provide a brief overview of the dataset's structure, its available implementations, and first applications.
Correction Trees as an Alternative to Turbo Codes and Low Density Parity Check Codes
Venue: arXiv cs.IT 2012
Year: 2012

The rapidly improving performance of modern hardware renders convolutional codes obsolete, and allows for the practical implementation of more sophisticated correction codes such as low density parity check (LDPC) and turbo codes (TC). Both are decoded by iterative algorithms, which require a disproportional computational effort for low channel noise. They are also unable to correct higher noise levels, still below the Shannon theoretical limit. In this paper, we discuss an enhanced version of a convolutional-like decoding paradigm which adopts very large spaces of possible system states, of the order of $2^{64}$. Under such conditions, the traditional convolution operation is rendered useless and needs to be replaced by a carefully designed state transition procedure. The size of the system state space completely changes the correction philosophy, as state collisions are virtually impossible and the decoding procedure becomes a correction tree. The proposed decoding algorithm is practically cost-free for low channel noise. As the channel noise approaches the Shannon limit, it is still possible to perform correction, although its cost increases to infinity. In many applications, the implemented decoder can essentially outperform both LDPC and TC. This paper describes the proposed correction paradigm and theoretically analyzes the asymptotic correction performance. The considered encoder and decoder were verified experimentally for the binary symmetric channel. The correction process remains practically cost-free for channel error rates below 0.05 and 0.13 for the 1/2 and 1/4 rate codes, respectively. For the considered resource limit, the output bit error rates reach the order of $10^{-3}$ for channel error rates 0.08 and 0.18. The proposed correction paradigm can be easily extended to other communication channels; the appropriate generalizations are also discussed in this study.
Computing the Discrete Fréchet Distance in Subquadratic Time
Venue: arXiv cs.CG 2012
Year: 2012

The Fréchet distance is a similarity measure between two curves $A$ and $B$: Informally, it is the minimum length of a leash required to connect a dog, constrained to be on $A$, and its owner, constrained to be on $B$, as they walk without backtracking along their respective curves from one endpoint to the other. The advantage of this measure on other measures such as the Hausdorff distance is that it takes into account the ordering of the points along the curves. The discrete Fréchet distance replaces the dog and its owner by a pair of frogs that can only reside on $n$ and $m$ specific pebbles on the curves $A$ and $B$, respectively. These frogs hop from a pebble to the next without backtracking. The discrete Fréchet distance can be computed by a rather straightforward quadratic dynamic programming algorithm. However, despite a considerable amount of work on this problem and its variations, there is no subquadratic algorithm known, even for approximation versions of the problem. In this paper we present a subquadratic algorithm for computing the discrete Fréchet distance between two sequences of points in the plane, of respective lengths $m\le n$. The algorithm runs in $O(\dfrac{mn\log\log n}{\log n})$ time and uses $O(n+m)$ storage. Our approach uses the geometry of the problem in a subtle way to encode legal positions of the frogs as states of a finite automata.
Approximate Counting of Matchings in Sparse Uniform Hypergraphs
Venue: arXiv cs.DS 2012
Year: 2012

In this paper we give a fully polynomial randomized approximation scheme (FPRAS) for the number of matchings in k-uniform hypergraphs whose intersection graphs contain few claws. Our method gives a generalization of the canonical path method of Jerrum and Sinclair to hypergraphs satisfying a local restriction. Our proof method depends on an application of the Euler tour technique for the canonical paths of the underlying Markov chains. On the other hand, we prove that it is NP-hard to approximate the number of matchings even for the class of k-uniform, 2-regular and linear hypergraphs, for all k >= 6, without the above restriction.
Reversible Programmable Logic Array (RPLA) using Feynman & MUX Gates for Low Power Industrial Applications
Venue: arXiv cs.AR 2012
Year: 2012

This paper present the research work directed towards the design of reversible programmable logic array using very high speed integrated circuit hardware description language (VHDL). Reversible logic circuits have significant importance in bioinformatics, optical information processing, CMOS design etc. In this paper the authors propose the design of new RPLA using Feynman & MUX gate.VHDL based codes of reversible gates with simulating results are shown .This proposed RPLA may be further used to design any reversible logic function or Boolean function (Adder, subtractor etc.) which dissipate very low or ideally no heat.
Understanding differential equations through diffusion point of view
Venue: arXiv cs.NA 2012
Year: 2012

In this paper, we propose a new adaptation of the D-iteration algorithm to numerically solve the differential equations. This problem can be reinterpreted in 2D or 3D (or higher dimensions) as a limit of a diffusion process where the boundary or initial conditions are replaced by fluid catalysts. Pre-computing the diffusion process for an elementary catalyst case as a fundamental block of a class of differential equations, we show that the computation efficiency can be greatly improved. The method can be applied on the class of problems that can be addressed by the Gauss-Seidel iteration, based on the linear approximation of the differential equations.
Robust Head Pose Estimation Using Contourlet Transform
Venue: arXiv cs.CV 2012
Year: 2012

Estimating pose of the head is an important preprocessing step in many pattern recognition and computer vision systems such as face recognition. Since the performance of the face recognition systems is greatly affected by the poses of the face, how to estimate the accurate pose of the face in human face image is still a challenging problem. In this paper, we represent a novel method for head pose estimation. To enhance the efficiency of the estimation we use contourlet transform for feature extraction. Contourlet transform is multi-resolution, multi-direction transform. In order to reduce the feature space dimension and obtain appropriate features we use LDA (Linear Discriminant Analysis) and PCA (Principal Component Analysis) to remove ineffcient features. Then, we apply different classifiers such as k-nearest neighborhood (knn) and minimum distance. We use the public available FERET database to evaluate the performance of proposed method. Simulation results indicate the superior robustness of the proposed method.