OpenRaiser/Intern-Atlas huggingface dataset:
Comments on "Nonextensive Entropies derived from Form Invariance of Pseudoadditivity"
Venue: arXiv cs.IT 2012
Year: 2012

Recently, Suyari has defined nonextensive information content measure with unique class of functions which satisfies certain set of axioms. Nonextensive entropy is then defined as the appropriate expectation value of nonextensive information content [H. Suyari, Phys. Rev E 65 066118 (2002)]. In this comment we show that the class of functions determined by Suyari's axioms is actually wider than the one given by Suyari and we determine the class. Particularly, an information content corresponding to Havrda-Charvat entropy satisfies Suyari's axioms and does not belong to the class given by Suyari but belongs to our class. Moreover, some of the conditions from Suyari's set of axioms are redundant, and some of them can be replaced with more intuitive weaker ones. We give a modification of Suyari's axiomatic system with these weaker assumptions and define the corresponding information content measure.
Non-commutative Digital Signatures
Venue: arXiv cs.CR 2012
Year: 2012

The objective of this work is to survey several digital signatures proposed in the last decade using non-commutative groups and rings and propose a digital signature using non-commutative groups and analyze its security.
Convolutional Compressed Sensing Using Deterministic Sequences
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, a new class of circulant matrices built from deterministic sequences is proposed for convolution-based compressed sensing (CS). In contrast to random convolution, the coefficients of the underlying filter are given by the discrete Fourier transform of a deterministic sequence with good autocorrelation. Both uniform recovery and non-uniform recovery of sparse signals are investigated, based on the coherence parameter of the proposed sensing matrices. Many examples of the sequences are investigated, particularly the Frank-Zadoff-Chu (FZC) sequence, the \textit{m}-sequence and the Golay sequence. A salient feature of the proposed sensing matrices is that they can not only handle sparse signals in the time domain, but also those in the frequency and/or or discrete-cosine transform (DCT) domain.
HEP Analysis Facility An Approach to Grid Computing
Venue: arXiv cs.DC 2012
Year: 2012

HEP Analysis Facility is a cluster designed and implemented in Scientific Linux Cern 5.5 to grant High Energy Physics researchers one place where they can go to undertake a particular task or to provide a parallel processing architecture in which CPU resources are shared across a network and all machines function as one large supercomputer.
Hep Cluster First Step Towards Grid Computing
Venue: arXiv cs.DC 2012
Year: 2012

HEP Cluster is designed and implemented in Scientific Linux Cern 5.5 to grant High Energy Physics researchers one place where they can go to undertake a particular task or to provide a parallel processing architecture in which CPU resources are shared across a network and all machines function as one large supercomputer. It gives physicists a facility to access computers and data, transparently, without having to consider location, operating system, account administration, and other details. By using this facility researchers can process their jobs much faster than the stand alone desktop systems. Keywords: Cluster, Network, Storage, Parallel Computing & Gris.
A Dichotomy Theorem for Homomorphism Polynomials
Venue: arXiv cs.CC 2012
Year: 2012

In the present paper we show a dichotomy theorem for the complexity of polynomial evaluation. We associate to each graph H a polynomial that encodes all graphs of a fixed size homomorphic to H. We show that this family is computable by arithmetic circuits in constant depth if H has a loop or no edge and that it is hard otherwise (i.e., complete for VNP, the arithmetic class related to #P). We also demonstrate the hardness over the rational field of cut eliminator, a polynomial defined by Bürgisser which is known to be neither VP nor VNP-complete in the field of two elements, if VP is not equal to VNP (VP is the class of polynomials computable by arithmetic circuit of polynomial size).
Computing Nature: A Network of Networks of Concurrent Information Processes
Venue: arXiv cs.GL 2012
Year: 2012

This text presents the research field of natural/unconventional computing as it appears in the book COMPUTING NATURE. The articles discussed consist a selection of works from the Symposium on Natural Computing at AISB-IACAP (British Society for the Study of Artificial Intelligence and the Simulation of Behaviour and The International Association for Computing and Philosophy) World Congress 2012, held at the University of Birmingham, celebrating Turing centenary. The COMPUTING NATURE is about nature considered as the totality of physical existence, the universe. By physical we mean all phenomena, objects and processes, that are possible to detect either directly by our senses or via instruments. Historically, there have been many ways of describing the universe (cosmic egg, cosmic tree, theistic universe, mechanistic universe) while a particularly prominent contemporary approach is computational universe, as discussed in this article.
Stochastic Games on a Multiple Access Channel
Venue: arXiv cs.SY 2012
Year: 2012

We consider a scenario where N users try to access a common base station. Associated with each user is its channel state and a finite queue which varies with time. Each user chooses his power and the admission control variable in a dynamic manner so as to maximize his expected throughput. The throughput of each user is a function of the actions and states of all users. The scenario considers the situation where each user knows his channel and buffer state but is unaware of the states and actions taken by the other users. We consider the scenario when each user is saturated (i.e., always has a packet to transmit) as well as the case when each user is unsaturated. We formulate the problem as a Markov game and show connections with strategic form games. We then consider various throughput functions associated with the multiple user channel and provide algorithms for finding these equilibria.
Energy Efficient Algorithms and Power Consumption Techniques in High Performance Computing
Venue: arXiv cs.DC 2012
Year: 2012

High Performance Computing is an internet based computing which makes computer infrastructure and services available to the user for research purpose. However, an important issue which needs to be resolved before High Performance Computing Cluster with large pool of servers gain widespread acceptance is the design of data centers with less energy consumption. It is only possible when servers produce less heat and consume less power. Systems reliability decreases with increase in temperature due to heat generation caused by large power consumption as computing in high temperature is more error-prone. Here in this paper our approach is to design and implement a high performance cluster for high-end research in the High Energy Physics stream. This involves the usage of fine grained power gating technique in microprocessors and energy efficient algorithms that reduce the overall running cost of the data center.
Transmission of information via the non-linear Scroedinger equation: The random Gaussian input case
Venue: arXiv cs.IT 2012
Year: 2012

The explosion of demand for ultra-high information transmission rates over the last decade has necessitated the usage of increasingly high light intensities for fiber optical transmissions. As a result, the fiber non-linearities need to be treated non-perturbatively. Similar analyses in the past have focused on the effects of non-linearities on existing transmission technologies, e.g. WDM. In this paper we take advantage of the fact that, under certain assumptions, light transmission through optical fibers can be described using the non-linear Schroedinger equation, which is exactly integrable. As a particular example, we show that in the low Gaussian noise limit, the Gaussian input distribution has a higher mutual information than the transmission using WDM over the same available bandwidth.
An Atypical Survey of Typical-Case Heuristic Algorithms
Venue: arXiv cs.CC 2012
Year: 2012

Heuristic approaches often do so well that they seem to pretty much always give the right answer. How close can heuristic algorithms get to always giving the right answer, without inducing seismic complexity-theoretic consequences? This article first discusses how a series of results by Berman, Buhrman, Hartmanis, Homer, Longpré, Ogiwara, Schöening, and Watanabe, from the early 1970s through the early 1990s, explicitly or implicitly limited how well heuristic algorithms can do on NP-hard problems. In particular, many desirable levels of heuristic success cannot be obtained unless severe, highly unlikely complexity class collapses occur. Second, we survey work initiated by Goldreich and Wigderson, who showed how under plausible assumptions deterministic heuristics for randomized computation can achieve a very high frequency of correctness. Finally, we consider formal ways in which theory can help explain the effectiveness of heuristics that solve NP-hard problems in practice.
Limited-Capacity Many-To-Many Point Matching in One Dimension
Venue: arXiv cs.CG 2012
Year: 2012

Given two point sets S and T, in a many-to-many matching between S and T each point in S is assigned to one or more points in T and vice versa. A generalization of the many-to-many matching problem is the limited capacity many-to-many matching problem, where the number of points that can be matched to each point, that is the capacity of each point, is limited. In this paper, we provide an O(n^2) time algorithm for the one dimensional minimum-cost limited capacity many-to-many matching problem, where |S| + |T| = n. Our algorithm improves the best previous time complexity of O(k(n^2)), that in which k is the largest capacity of the points in the union of S and T. In this problem, both S and T lie on the real line and the cost of matching s in S to t in T is equal to the distance between s and t.
On the Relation Between the Common Labelling and the Median Graph
Venue: arXiv cs.CV 2012
Year: 2012

In structural pattern recognition, given a set of graphs, the computation of a Generalized Median Graph is a well known problem. Some methods approach the problem by assuming a relation between the Generalized Median Graph and the Common Labelling problem. However, this relation has still not been formally proved. In this paper, we analyse such relation between both problems. The main result proves that the cost of the common labelling upper-bounds the cost of the median with respect to the given set. In addition, we show that the two problems are equivalent in some cases.
Grammar-Based Construction of Indexes for Binary Jumbled Pattern Matching
Venue: arXiv cs.DS 2012
Year: 2012

We show how, given a straight-line program with $g$ rules for a binary string $B$ of length $n$, in $O(g^{2 / 3} n^{4 / 3})$ time we can build a linear-space index such that, given $m$ and $c$, in O(1) time we can determine whether there is a substring of $B$ with length $m$ containing exactly $c$ copies of 1. If we use $O(n \log n)$ space for the index, then we can list all such substrings using $O(m)$ time per substring.
Distributed Quantization Networks
Venue: arXiv cs.IT 2012
Year: 2012

Several key results in distributed source coding offer the intuition that little improvement in compression can be gained from intersensor communication when the information is coded in long blocks. However, when sensors are restricted to code their observations in small blocks (e.g., 1), intelligent collaboration between sensors can greatly reduce distortion. For networks where sensors are allowed to "chat" using a side channel that is unobservable at the fusion center, we provide asymptotically-exact characterization of distortion performance and optimal quantizer design in the high-resolution (low-distortion) regime using a framework called distributed functional scalar quantization (DFSQ). The key result is that chatting can dramatically improve performance even when intersensor communication is at very low rate, especially if the fusion center desires fidelity of a nonlinear computation applied to source realizations rather than fidelity in representing the sources themselves. We also solve the rate allocation problem when communication links have heterogeneous costs and provide a detailed example to demonstrate the theoretical and practical gains from chatting. This example for maximum computation gives insight on the gap between chatting and distributed networks, and how to optimize the intersensor communication.
Improving the Numerical Robustness of Sphere Swept Collision Detection
Venue: arXiv cs.CG 2012
Year: 2012

This paper discusses improvements to the numerical robustness of the algorithm described in Kasper Fauerby's "Improved Collision Detection and Response." The algorithm addresses a common collision detection query: a moving sphere or ellipsoid vs. a set of motionless triangles. In its current form, the algorithm allows the sphere to penetrate the triangles. The sphere also displays "jittering" behavior when colliding with certain geometry. Most of these problems are the product of insufficient attention to numerical robustness, the focus of this paper. Motivated by the importance of numerical robustness in collision detection code, this paper addresses these problems in detail and proposes efficient solutions to them.
Sampling and Reconstruction of Spatial Fields using Mobile Sensors
Venue: arXiv cs.MM 2012
Year: 2012

Spatial sampling is traditionally studied in a static setting where static sensors scattered around space take measurements of the spatial field at their locations. In this paper we study the emerging paradigm of sampling and reconstructing spatial fields using sensors that move through space. We show that mobile sensing offers some unique advantages over static sensing in sensing time-invariant bandlimited spatial fields. Since a moving sensor encounters such a spatial field along its path as a time-domain signal, a time-domain anti-aliasing filter can be employed prior to sampling the signal received at the sensor. Such a filtering procedure, when used by a configuration of sensors moving at constant speeds along equispaced parallel lines, leads to a complete suppression of spatial aliasing in the direction of motion of the sensors. We analytically quantify the advantage of using such a sampling scheme over a static sampling scheme by computing the reduction in sampling noise due to the filter. We also analyze the effects of non-uniform sensor speeds on the reconstruction accuracy. Using simulation examples we demonstrate the advantages of mobile sampling over static sampling in practical problems. We extend our analysis to sampling and reconstruction schemes for monitoring time-varying bandlimited fields using mobile sensors. We demonstrate that in some situations we require a lower density of sensors when using a mobile sensing scheme instead of the conventional static sensing scheme. The exact advantage is quantified for a problem of sampling and reconstructing an audio field.
Harmonious Hilbert curves and other extradimensional space-filling curves
Venue: arXiv cs.CG 2012
Year: 2012

This paper introduces a new way of generalizing Hilbert's two-dimensional space-filling curve to arbitrary dimensions. The new curves, called harmonious Hilbert curves, have the unique property that for any d' < d, the d-dimensional curve is compatible with the d'-dimensional curve with respect to the order in which the curves visit the points of any d'-dimensional axis-parallel space that contains the origin. Similar generalizations to arbitrary dimensions are described for several variants of Peano's curve (the original Peano curve, the coil curve, the half-coil curve, and the Meurthe curve). The d-dimensional harmonious Hilbert curves and the Meurthe curves have neutral orientation: as compared to the curve as a whole, arbitrary pieces of the curve have each of d! possible rotations with equal probability. Thus one could say these curves are `statistically invariant' under rotation---unlike the Peano curves, the coil curves, the half-coil curves, and the familiar generalization of Hilbert curves by Butz and Moore. In addition, prompted by an application in the construction of R-trees, this paper shows how to construct a 2d-dimensional generalized Hilbert or Peano curve that traverses the points of a certain d-dimensional diagonally placed subspace in the order of a given d-dimensional generalized Hilbert or Peano curve. Pseudocode is provided for comparison operators based on the curves presented in this paper.
Improved Time Complexity of Bandwidth Approximation in Dense Graphs
Venue: arXiv cs.DS 2012
Year: 2012

Given a graph $G=(V, E)$ and and a proper labeling $f$ from $V$ to $\{1, ..., n\}$, we define $B(f)$ as the maximum absolute difference between $f(u)$ and $f(v)$ where $(u,v)\in E$. The bandwidth of $G$ is the minimum $B(f)$ for all $f$. Say $G$ is $δ$-dense if its minimum degree is $δn$. In this paper, we investigate the trade-off between the approximation ratio and the time complexity of the classical approach of Karpinski {et al}.\cite{Karpin97}, and present a faster randomized algorithm for approximating the bandwidth of $δ$-dense graphs. In particular, by removing the polylog factor of the time complexity required to enumerate all possible placements for balls to bins, we reduce the time complexity from $O(n^6\cdot (\log n)^{O(1)})$ to $O(n^{4+o(1)})$. In advance, we reformulate the perfect matching phase of the algorithm with a maximum flow problem of smaller size and reduce the time complexity to $O(n^2\log\log n)$. We also extend the graph classes could be applied by the original approach: we show that the algorithm remains polynomial time as long as $δ$ is $O({(\log\log n)}^2 / {\log n})$.
Performance Evaluation of Random Set Based Pedestrian Tracking Algorithms
Venue: arXiv cs.CV 2012
Year: 2012

The paper evaluates the error performance of three random finite set based multi-object trackers in the context of pedestrian video tracking. The evaluation is carried out using a publicly available video dataset of 4500 frames (town centre street) for which the ground truth is available. The input to all pedestrian tracking algorithms is an identical set of head and body detections, obtained using the Histogram of Oriented Gradients (HOG) detector. The tracking error is measured using the recently proposed OSPA metric for tracks, adopted as the only known mathematically rigorous metric for measuring the distance between two sets of tracks. A comparative analysis is presented under various conditions.
Sketched SVD: Recovering Spectral Features from Compressive Measurements
Venue: arXiv cs.IT 2012
Year: 2012

We consider a streaming data model in which n sensors observe individual streams of data, presented in a turnstile model. Our goal is to analyze the singular value decomposition (SVD) of the matrix of data defined implicitly by the stream of updates. Each column i of the data matrix is given by the stream of updates seen at sensor i. Our approach is to sketch each column of the matrix, forming a "sketch matrix" Y, and then to compute the SVD of the sketch matrix. We show that the singular values and right singular vectors of Y are close to those of X, with small relative error. We also believe that this bound is of independent interest in non-streaming and non-distributed data collection settings. Assuming that the data matrix X is of size Nxn, then with m linear measurements of each column of X, we obtain a smaller matrix Y with dimensions mxn. If m = O(k ε^{-2} (log(1/ε) + log(1/δ)), where k denotes the rank of X, then with probability at least 1-δ, the singular values σ'_j of Y satisfy the following relative error result (1-ε)^(1/2)<= σ'_j/σ_j <= (1 + ε)^(1/2) as compared to the singular values σ_j of the original matrix X. Furthermore, the right singular vectors v'_j of Y satisfy ||v_j-v_j'||_2 <= min(sqrt{2}, (ε\sqrt{1+ε})/(\sqrt{1-ε}) max_{i\neq j} (\sqrt{2}σ_iσ_j)/(min_{c\in[-1,1]}(|σ^2_i-σ^2_j(1+cε)|))) as compared to the right singular vectors v_j of X. We apply this result to obtain a streaming graph algorithm to approximate the eigenvalues and eigenvectors of the graph Laplacian in the case where the graph has low rank (many connected components).
The use of percentiles and percentile rank classes in the analysis of bibliometric data: Opportunities and limits
Venue: arXiv cs.DL 2012
Year: 2012

Percentiles have been established in bibliometrics as an important alternative to mean-based indicators for obtaining a normalized citation impact of publications. Percentiles have a number of advantages over standard bibliometric indicators used frequently: for example, their calculation is not based on the arithmetic mean which should not be used for skewed bibliometric data. This study describes the opportunities and limits and the advantages and disadvantages of using percentiles in bibliometrics. We also address problems in the calculation of percentiles and percentile rank classes for which there is not (yet) a satisfactory solution. It will be hard to compare the results of different percentile-based studies with each other unless it is clear that the studies were done with the same choices for percentile calculation and rank assignment.
Verbalizing Ontologies in Controlled Baltic Languages
Venue: arXiv cs.CL 2012
Year: 2012

Controlled natural languages (mostly English-based) recently have emerged as seemingly informal supplementary means for OWL ontology authoring, if compared to the formal notations that are used by professional knowledge engineers. In this paper we present by examples controlled Latvian language that has been designed to be compliant with the state of the art Attempto Controlled English. We also discuss relation with controlled Lithuanian language that is being designed in parallel.
Ordinal Rating of Network Performance and Inference by Matrix Completion
Venue: arXiv cs.NI 2012
Year: 2012

This paper addresses the large-scale acquisition of end-to-end network performance. We made two distinct contributions: ordinal rating of network performance and inference by matrix completion. The former reduces measurement costs and unifies various metrics which eases their processing in applications. The latter enables scalable and accurate inference with no requirement of structural information of the network nor geometric constraints. By combining both, the acquisition problem bears strong similarities to recommender systems. This paper investigates the applicability of various matrix factorization models used in recommender systems. We found that the simple regularized matrix factorization is not only practical but also produces accurate results that are beneficial for peer selection.
Local Improvement Gives Better Expanders
Venue: arXiv cs.DM 2012
Year: 2012

It has long been known that random regular graphs are with high probability good expanders. This was first established in the 1980s by Bollobás by directly calculating the probability that a set of vertices has small expansion and then applying the union bound. In this paper we improve on this analysis by relying on a simple high-level observation: if a graph contains a set of vertices with small expansion then it must also contain such a set of vertices that is locally optimal, that is, a set whose expansion cannot be made smaller by exchanging a vertex from the set with one from the set's complement. We show that the probability that a set of vertices satisfies this additional property is significantly smaller. Thus, after again applying the union bound, we obtain improved lower bounds on the expansion of random $Δ$-regular graphs for $Δ\ge 4$. In fact, the gains from this analysis increase as $Δ$ grows, a fact we explain by extending our technique to general $Δ$. Thus, in the end we obtain an improvement not only for some small special cases but on the general asymptotic bound on the expansion of $Δ$-regular graphs given by Bollobás.