OpenRaiser/Intern-Atlas huggingface dataset:
An $O({\log n\over \log\log n})$ Upper Bound on the Price of Stability for Undirected Shapley Network Design Games
Venue: arXiv cs.GT 2008
Year: 2008

In this paper, we consider the Shapley network design game on undirected networks. In this game, we have an edge weighted undirected network $G(V,E)$ and $n$ selfish players where player $i$ wants to choose a path from source vertex $s_i$ to destination vertex $t_i$. The cost of each edge is equally split among players who pass it. The price of stability is defined as the ratio of the cost of the best Nash equilibrium to that of the optimal solution. We present an $O(\log n/\log\log n)$ upper bound on price of stability for the single sink case, i.e, $t_i=t$ for all $i$.
The statistical restricted isometry property and the Wigner semicircle distribution of incoherent dictionaries
Venue: arXiv cs.IT 2008
Year: 2008

In this article we present a statistical version of the Candes-Tao restricted isometry property (SRIP for short) which holds in general for any incoherent dictionary which is a disjoint union of orthonormal bases. In addition, we show that, under appropriate normalization, the eigenvalues of the associated Gram matrix fluctuate around 1 according to the Wigner semicircle distribution. The result is then applied to various dictionaries that arise naturally in the setting of finite harmonic analysis, giving, in particular, a better understanding on a remark of Applebaum-Howard-Searle-Calderbank concerning RIP for the Heisenberg dictionary of chirp like functions.
A Data Model for Integrating Heterogeneous Medical Data in the Health-e-Child Project
Venue: arXiv cs.DB 2008
Year: 2008

There has been much research activity in recent times about providing the data infrastructures needed for the provision of personalised healthcare. In particular the requirement of integrating multiple, potentially distributed, heterogeneous data sources in the medical domain for the use of clinicians has set challenging goals for the healthgrid community. The approach advocated in this paper surrounds the provision of an Integrated Data Model plus links to/from ontologies to homogenize biomedical (from genomic, through cellular, disease, patient and population-related) data in the context of the EC Framework 6 Health-e-Child project. Clinical requirements are identified, the design approach in constructing the model is detailed and the integrated model described in the context of examples taken from that project. Pointers are given to future work relating the model to medical ontologies and challenges to the use of fully integrated models and ontologies are identified.
On the Value of a Social Network
Venue: arXiv cs.NI 2008
Year: 2008

In this paper we investigate the value of a social network with respect to the probability mechanism underlying its structure. Specifically, we compute the value for small world and scale free networks. We provide evidence in support of the value to be given by Zipfs law.
Binary Classification Based on Potentials
Venue: arXiv cs.LG 2008
Year: 2008

We introduce a simple and computationally trivial method for binary classification based on the evaluation of potential functions. We demonstrate that despite the conceptual and computational simplicity of the method its performance can match or exceed that of standard Support Vector Machine methods.
Chain-Based Representations for Solid and Physical Modeling
Venue: arXiv cs.CG 2008
Year: 2008

In this paper we show that the (co)chain complex associated with a decomposition of the computational domain, commonly called a mesh in computational science and engineering, can be represented by a block-bidiagonal matrix that we call the Hasse matrix. Moreover, we show that topology-preserving mesh refinements, produced by the action of (the simplest) Euler operators, can be reduced to multilinear transformations of the Hasse matrix representing the complex. Our main result is a new representation of the (co)chain complex underlying field computations, a representation that provides new insights into the transformations induced by local mesh refinements. Our approach is based on first principles and is general in that it applies to most representational domains that can be characterized as cell complexes, without any restrictions on their type, dimension, codimension, orientability, manifoldness, connectedness.
XML Static Analyzer User Manual
Venue: arXiv cs.PL 2008
Year: 2008

This document describes how to use the XML static analyzer in practice. It provides informal documentation for using the XML reasoning solver implementation. The solver allows automated verification of properties that are expressed as logical formulas over trees. A logical formula may for instance express structural constraints or navigation properties (like e.g. path existence and node selection) in finite trees. Logical formulas can be expressed using the syntax of XPath expressions, DTD, XML Schemas, and Relax NG definitions.
MIMO Two-way Relay Channel: Diversity-Multiplexing Tradeoff Analysis
Venue: arXiv cs.IT 2008
Year: 2008

A multi-hop two-way relay channel is considered in which all the terminals are equipped with multiple antennas. Assuming independent quasi-static Rayleigh fading channels and channel state information available at the receivers, we characterize the optimal diversity-multiplexing gain tradeoff (DMT) curve for a full-duplex relay terminal. It is shown that the optimal DMT can be achieved by a compress-and-forward type relaying strategy in which the relay quantizes its received signal and transmits the corresponding channel codeword. It is noteworthy that, with this transmission protocol, the two transmissions in opposite directions can achieve their respective single user optimal DMT performances simultaneously, despite the interference they cause to each other. Motivated by the optimality of this scheme in the case of the two-way relay channel, a novel dynamic compress-and-forward (DCF) protocol is proposed for the one-way multi-hop MIMO relay channel for a half-duplex relay terminal, and this scheme is shown to achieve the optimal DMT performance.
Algorithmic and Statistical Challenges in Modern Large-Scale Data Analysis are the Focus of MMDS 2008
Venue: arXiv cs.DS 2008
Year: 2008

The 2008 Workshop on Algorithms for Modern Massive Data Sets (MMDS 2008), sponsored by the NSF, DARPA, LinkedIn, and Yahoo!, was held at Stanford University, June 25--28. The goals of MMDS 2008 were (1) to explore novel techniques for modeling and analyzing massive, high-dimensional, and nonlinearly-structured scientific and internet data sets; and (2) to bring together computer scientists, statisticians, mathematicians, and data analysis practitioners to promote cross-fertilization of ideas.
Comparing RNA structures using a full set of biologically relevant edit operations is intractable
Venue: arXiv cs.DS 2008
Year: 2008

Arc-annotated sequences are useful for representing structural information of RNAs and have been extensively used for comparing RNA structures in both terms of sequence and structural similarities. Among the many paradigms referring to arc-annotated sequences and RNA structures comparison (see \cite{IGMA_BliDenDul08} for more details), the most important one is the general edit distance. The problem of computing an edit distance between two non-crossing arc-annotated sequences was introduced in \cite{Evans99}. The introduced model uses edit operations that involve either single letters or pairs of letters (never considered separately) and is solvable in polynomial-time \cite{ZhangShasha:1989}. To account for other possible RNA structural evolutionary events, new edit operations, allowing to consider either silmutaneously or separately letters of a pair were introduced in \cite{jiangli}; unfortunately at the cost of computational tractability. It has been proved that comparing two RNA secondary structures using a full set of biologically relevant edit operations is {\sf\bf NP}-complete. Nevertheless, in \cite{DBLP:conf/spire/GuignonCH05}, the authors have used a strong combinatorial restriction in order to compare two RNA stem-loops with a full set of biologically relevant edit operations; which have allowed them to design a polynomial-time and space algorithm for comparing general secondary RNA structures. In this paper we will prove theoretically that comparing two RNA structures using a full set of biologically relevant edit operations cannot be done without strong combinatorial restrictions.
Multi-level algorithms for modularity clustering
Venue: arXiv cs.DS 2008
Year: 2008

Modularity is one of the most widely used quality measures for graph clusterings. Maximizing modularity is NP-hard, and the runtime of exact algorithms is prohibitive for large graphs. A simple and effective class of heuristics coarsens the graph by iteratively merging clusters (starting from singletons), and optionally refines the resulting clustering by iteratively moving individual vertices between clusters. Several heuristics of this type have been proposed in the literature, but little is known about their relative performance. This paper experimentally compares existing and new coarsening- and refinement-based heuristics with respect to their effectiveness (achieved modularity) and efficiency (runtime). Concerning coarsening, it turns out that the most widely used criterion for merging clusters (modularity increase) is outperformed by other simple criteria, and that a recent algorithm by Schuetz and Caflisch is no improvement over simple greedy coarsening for these criteria. Concerning refinement, a new multi-level algorithm is shown to produce significantly better clusterings than conventional single-level algorithms. A comparison with published benchmark results and algorithm implementations shows that combinations of coarsening and multi-level refinement are competitive with the best algorithms in the literature.
How Many Attackers Can Selfish Defenders Catch?
Venue: arXiv cs.GT 2008
Year: 2008

In a distributed system with {\it attacks} and {\it defenses,} both {\it attackers} and {\it defenders} are self-interested entities. We assume a {\it reward-sharing} scheme among {\it interdependent} defenders; each defender wishes to (locally) maximize her own total {\it fair share} to the attackers extinguished due to her involvement (and possibly due to those of others). What is the {\em maximum} amount of protection achievable by a number of such defenders against a number of attackers while the system is in a {\it Nash equilibrium}? As a measure of system protection, we adopt the {\it Defense-Ratio} \cite{MPPS05a}, which provides the expected (inverse) proportion of attackers caught by the defenders. In a {\it Defense-Optimal} Nash equilibrium, the Defense-Ratio is optimized. We discover that the possibility of optimizing the Defense-Ratio (in a Nash equilibrium) depends in a subtle way on how the number of defenders compares to two natural graph-theoretic thresholds we identify. In this vein, we obtain, through a combinatorial analysis of Nash equilibria, a collection of trade-off results: - When the number of defenders is either sufficiently small or sufficiently large, there are cases where the Defense-Ratio can be optimized. The optimization problem is computationally tractable for a large number of defenders; the problem becomes ${\cal NP}$-complete for a small number of defenders and the intractability is inherited from a previously unconsidered combinatorial problem in {\em Fractional Graph Theory}. - Perhaps paradoxically, there is a middle range of values for the number of defenders where optimizing the Defense-Ratio is never possible.
Tsallis $q$-exponential describes the distribution of scientific citations - A new characterization of the impact
Venue: arXiv cs.DL 2008
Year: 2008

In this work we have studied the research activity for countries of Europe, Latin America and Africa for all sciences between 1945 and November 2008. All the data are captured from the Web of Science database during this period. The analysis of the experimental data shows that, within a nonextensive thermostatistical formalism, the Tsallis \emph{q}-exponential distribution $N(c)$ satisfactorily describes Institute of Scientific Information citations. The data which are examined in the present survey can be fitted successfully as a first approach by applying a {\it single} curve (namely, $N(c) \propto 1/[1+(q-1) c/T]^{\frac{1}{q-1}}$ with $q\simeq 4/3$ for {\it all} the available citations $c$, $T$ being an "effective temperature". The present analysis ultimately suggests that the phenomenon might essentially be {\it one and the same} along the {\it entire} range of the citation number. Finally, this manuscript provides a new ranking index, via the "effective temperature" $T$, for the impact level of the research activity in these countries, taking into account the number of the publications and their citations.
Some sufficient conditions on Hamiltonian digraph
Venue: arXiv cs.DM 2008
Year: 2008

Z-mapping graph is a balanced bipartite graph $G$ of a digraph $D$ by split each vertex of $D$ into a pair of vertices of $G$. Based on the property of the $G$, it is proved that if $D$ is strong connected and $G$ is Hamiltonian, then $D$ is Hamiltonian. It is also proved if $D$ is Hamiltonian, then $G$ contains at least a perfect matching. Thus some existence sufficient conditions for Hamiltonian digraph and Hamiltonian graph are proved to be equivalent, and two sufficient conditions of disjoint Hamiltonian digraph are given in this paper.
Statistical Physics of Signal Estimation in Gaussian Noise: Theory and Examples of Phase Transitions
Venue: arXiv cs.IT 2008
Year: 2008

We consider the problem of signal estimation (denoising) from a statistical mechanical perspective, using a relationship between the minimum mean square error (MMSE), of estimating a signal, and the mutual information between this signal and its noisy version. The paper consists of essentially two parts. In the first, we derive several statistical-mechanical relationships between a few important quantities in this problem area, such as the MMSE, the differential entropy, the Fisher information, the free energy, and a generalized notion of temperature. We also draw analogies and differences between certain relations pertaining to the estimation problem and the parallel relations in thermodynamics and statistical physics. In the second part of the paper, we provide several application examples, where we demonstrate how certain analysis tools that are customary in statistical physics, prove useful in the analysis of the MMSE. In most of these examples, the corresponding statistical-mechanical systems turn out to consist of strong interactions that cause phase transitions, which in turn are reflected as irregularities and discontinuities (similar to threshold effects) in the behavior of the MMSE.
Bootstrapping Key Pre-Distribution: Secure, Scalable and User-Friendly Initialization of Sensor Nodes
Venue: arXiv cs.CR 2008
Year: 2008

To establish secure (point-to-point and/or broadcast) communication channels among the nodes of a wireless sensor network is a fundamental task. To this end, a plethora of (socalled) key pre-distribution schemes have been proposed in the past. All these schemes, however, rely on shared secret(s), which are assumed to be somehow pre-loaded onto the sensor nodes. In this paper, we propose a novel method for secure initialization of sensor nodes based on a visual out-of-band channel. Using the proposed method, the administrator of a sensor network can distribute keys onto the sensor nodes, necessary to bootstrap key pre-distribution. Our secure initialization method requires only a little extra cost, is efficient and scalable with respect to the number of sensor nodes. Moreover, based on a usability study that we conducted, the method turns out to be quite user-friendly and easy to use by naive human users.
On Quantum and Classical Error Control Codes: Constructions and Applications
Venue: arXiv cs.IT 2008
Year: 2008

It is conjectured that quantum computers are able to solve certain problems more quickly than any deterministic or probabilistic computer. A quantum computer exploits the rules of quantum mechanics to speed up computations. However, it is a formidable task to build a quantum computer, since the quantum mechanical systems storing the information unavoidably interact with their environment. Therefore, one has to mitigate the resulting noise and decoherence effects to avoid computational errors. In this work, I study various aspects of quantum error control codes -- the key component of fault-tolerant quantum information processing. I present the fundamental theory and necessary background of quantum codes and construct many families of quantum block and convolutional codes over finite fields, in addition to families of subsystem codes over symmetric and asymmetric channels. Particularly, many families of quantum BCH, RS, duadic, and convolutional codes are constructed over finite fields. Families of subsystem codes and a class of optimal MDS subsystem codes are derived over asymmetric and symmetric quantum channels. In addition, propagation rules and tables of upper bounds on subsystem code parameters are established. Classes of quantum and classical LDPC codes based on finite geometries and Latin squares are constructed.
Symmetric and Asymmetric Asynchronous Interaction
Venue: arXiv cs.LO 2008
Year: 2008

We investigate classes of systems based on different interaction patterns with the aim of achieving distributability. As our system model we use Petri nets. In Petri nets, an inherent concept of simultaneity is built in, since when a transition has more than one preplace, it can be crucial that tokens are removed instantaneously. When modelling a system which is intended to be implemented in a distributed way by a Petri net, this built-in concept of synchronous interaction may be problematic. To investigate this we consider asynchronous implementations of nets, in which removing tokens from places can no longer be considered as instantaneous. We model this by inserting silent (unobservable) transitions between transitions and some of their preplaces. We investigate three such implementations, differing in the selection of preplaces of a transition from which the removal of a token is considered time consuming, and the possibility of collecting the tokens in a given order. We investigate the effect of these different transformations of instantaneous interaction into asynchronous interaction patterns by comparing the behaviours of nets before and after insertion of the silent transitions. We exhibit for which classes of Petri nets we obtain equivalent behaviour with respect to failures equivalence. It turns out that the resulting hierarchy of Petri net classes can be described by semi-structural properties. For two of the classes we obtain precise characterisations; for the remaining class we obtain lower and upper bounds. We briefly comment on possible applications of our results to Message Sequence Charts.
Using constraint programming to resolve the multi-source/multi-site data movement paradigm on the Grid
Venue: arXiv cs.PF 2008
Year: 2008

In order to achieve both fast and coordinated data transfer to collaborative sites as well as to create a distribution of data over multiple sites, efficient data movement is one of the most essential aspects in distributed environment. With such capabilities at hand, truly distributed task scheduling with minimal latencies would be reachable by internationally distributed collaborations (such as ones in HENP) seeking for scavenging or maximizing on geographically spread computational resources. But it is often not all clear (a) how to move data when available from multiple sources or (b) how to move data to multiple compute resources to achieve an optimal usage of available resources. We present a method of creating a Constraint Programming (CP) model consisting of sites, links and their attributes such as bandwidth for grid network data transfer also considering user tasks as part of the objective function for an optimal solution. We will explore and explain trade-off between schedule generation time and divergence from the optimal solution and show how to improve and render viable the solution's finding time by using search tree time limit, approximations, restrictions such as symmetry breaking or grouping similar tasks together, or generating sequence of optimal schedules by splitting the input problem. Results of data transfer simulation for each case will also include a well known Peer-2-Peer model, and time taken to generate a schedule as well as time needed for a schedule execution will be compared to a CP optimal solution. We will additionally present a possible implementation aimed to bring a distributed datasets (multiple sources) to a given site in a minimal time.
Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
Venue: arXiv cs.CC 2008
Year: 2008

Combinatorial games lead to several interesting, clean problems in algorithms and complexity theory, many of which remain open. The purpose of this paper is to provide an overview of the area to encourage further research. In particular, we begin with general background in Combinatorial Game Theory, which analyzes ideal play in perfect-information games, and Constraint Logic, which provides a framework for showing hardness. Then we survey results about the complexity of determining ideal play in these games, and the related problems of solving puzzles, in terms of both polynomial-time algorithms and computational intractability results. Our review of background and survey of algorithmic results are by no means complete, but should serve as a useful primer.
In the beginning was game semantics
Venue: arXiv cs.LO 2008
Year: 2008

This article presents an overview of computability logic -- the game-semantically constructed logic of interactive computational tasks and resources. There is only one non-overview, technical section in it, devoted to a proof of the soundness of affine logic with respect to the semantics of computability logic. A comprehensive online source on the subject can be found at http://www.cis.upenn.edu/~giorgi/cl.html
Deciding Quantifier-Free Presburger Formulas Using Parameterized Solution Bounds
Venue: arXiv cs.LO 2008
Year: 2008

Given a formula in quantifier-free Presburger arithmetic, if it has a satisfying solution, there is one whose size, measured in bits, is polynomially bounded in the size of the formula. In this paper, we consider a special class of quantifier-free Presburger formulas in which most linear constraints are difference (separation) constraints, and the non-difference constraints are sparse. This class has been observed to commonly occur in software verification. We derive a new solution bound in terms of parameters characterizing the sparseness of linear constraints and the number of non-difference constraints, in addition to traditional measures of formula size. In particular, we show that the number of bits needed per integer variable is linear in the number of non-difference constraints and logarithmic in the number and size of non-zero coefficients in them, but is otherwise independent of the total number of linear constraints in the formula. The derived bound can be used in a decision procedure based on instantiating integer variables over a finite domain and translating the input quantifier-free Presburger formula to an equi-satisfiable Boolean formula, which is then checked using a Boolean satisfiability solver. In addition to our main theoretical result, we discuss several optimizations for deriving tighter bounds in practice. Empirical evidence indicates that our decision procedure can greatly outperform other decision procedures.