OpenRaiser/Intern-Atlas huggingface dataset:
On the Stretch Factor of Convex Delaunay Graphs
Venue: arXiv cs.CG 2008
Year: 2008

Let C be a compact and convex set in the plane that contains the origin in its interior, and let S be a finite set of points in the plane. The Delaunay graph DG_C(S) of S is defined to be the dual of the Voronoi diagram of S with respect to the convex distance function defined by C. We prove that DG_C(S) is a t-spanner for S, for some constant t that depends only on the shape of the set C. Thus, for any two points p and q in S, the graph DG_C(S) contains a path between p and q whose Euclidean length is at most t times the Euclidean distance between p and q.
A Dynamical Boolean Network
Venue: arXiv cs.DM 2008
Year: 2008

We propose a Dynamical Boolean Network (DBN), which is a Virtual Boolean Network (VBN) whose set of states is fixed but whose transition matrix can change from one discrete time step to another. The transition matrix $T_{k}$ of our DBN for time step $k$ is of the form $Q^{-1}TQ$, where $T$ is a transition matrix (of a VBN) defined at time step $k$ in the course of the construction of our DBN and $Q$ is the matrix representation of some randomly chosen permutation $P$ of the states of our DBN. For each of several classes of such permutations, we carried out a number of simulations of a DBN with two nodes; each of our simulations consisted of 1,000 trials of 10,000 time steps each. In one of our simulations, only six of the 16 possible single-node transition rules for a VBN with two nodes were visited a total of 300,000 times (over all 1,000 trials). In that simulation, linearity appears to play a significant role in that three of those six single-node transition rules are transition rules of a Linear Virtual Boolean Network (LVBN); the other three are the negations of the first three. We also discuss the notions of a Probabilistic Boolean Network and a Hidden Markov Model--in both cases, in the context of using an arbitrary (though not necessarily one-to-one) function to label the states of a VBN.
Cryptanalysis of Yang-Wang-Chang's Password Authentication Scheme with Smart Cards
Venue: arXiv cs.CR 2008
Year: 2008

In 2005, Yang, Wang, and Chang proposed an improved timestamp-based password authentication scheme in an attempt to overcome the flaws of Yang-Shieh_s legendary timestamp-based remote authentication scheme using smart cards. After analyzing the improved scheme proposed by Yang-Wang-Chang, we have found that their scheme is still insecure and vulnerable to four types of forgery attacks. Hence, in this paper, we prove that, their claim that their scheme is intractable is incorrect. Also, we show that even an attack based on Sun et al._s attack could be launched against their scheme which they claimed to resolve with their proposal.
A $O(\log m)$, deterministic, polynomial-time computable approximation of Lewis Carroll's scoring rule
Venue: arXiv cs.GT 2008
Year: 2008

We provide deterministic, polynomial-time computable voting rules that approximate Dodgson's and (the ``minimization version'' of) Young's scoring rules to within a logarithmic factor. Our approximation of Dodgson's rule is tight up to a constant factor, as Dodgson's rule is $\NP$-hard to approximate to within some logarithmic factor. The ``maximization version'' of Young's rule is known to be $\NP$-hard to approximate by any constant factor. Both approximations are simple, and natural as rules in their own right: Given a candidate we wish to score, we can regard either its Dodgson or Young score as the edit distance between a given set of voter preferences and one in which the candidate to be scored is the Condorcet winner. (The difference between the two scoring rules is the type of edits allowed.) We regard the marginal cost of a sequence of edits to be the number of edits divided by the number of reductions (in the candidate's deficit against any of its opponents in the pairwise race against that opponent) that the edits yield. Over a series of rounds, our scoring rules greedily choose a sequence of edits that modify exactly one voter's preferences and whose marginal cost is no greater than any other such single-vote-modifying sequence.
Distributed and Recursive Parameter Estimation in Parametrized Linear State-Space Models
Venue: arXiv cs.DC 2008
Year: 2008

We consider a network of sensors deployed to sense a spatio-temporal field and estimate a parameter of interest. We are interested in the case where the temporal process sensed by each sensor can be modeled as a state-space process that is perturbed by random noise and parametrized by an unknown parameter. To estimate the unknown parameter from the measurements that the sensors sequentially collect, we propose a distributed and recursive estimation algorithm, which we refer to as the incremental recursive prediction error algorithm. This algorithm has the distributed property of incremental gradient algorithms and the on-line property of recursive prediction error algorithms. We study the convergence behavior of the algorithm and provide sufficient conditions for its convergence. Our convergence result is rather general and contains as special cases the known convergence results for the incremental versions of the least-mean square algorithm. Finally, we use the algorithm developed in this paper to identify the source of a gas-leak (diffusing source) in a closed warehouse and also report numerical simulations to verify convergence.
On decomposition of tame polynomials and rational functions
Venue: arXiv cs.SC 2008
Year: 2008

In this paper we present algorithmic considerations and theoretical results about the relation between the orders of certain groups associated to the components of a polynomial and the order of the group that corresponds to the polynomial, proving it for arbitrary tame polynomials, and considering the case of rational functions.
Lower Bounds on the Rate-Distortion Function of Individual LDGM Codes
Venue: arXiv cs.IT 2008
Year: 2008

We consider lossy compression of a binary symmetric source by means of a low-density generator-matrix code. We derive two lower bounds on the rate distortion function which are valid for any low-density generator-matrix code with a given node degree distribution L(x) on the set of generators and for any encoding algorithm. These bounds show that, due to the sparseness of the code, the performance is strictly bounded away from the Shannon rate-distortion function. In this sense, our bounds represent a natural generalization of Gallager's bound on the maximum rate at which low-density parity-check codes can be used for reliable transmission. Our bounds are similar in spirit to the technique recently developed by Dimakis, Wainwright, and Ramchandran, but they apply to individual codes.
On affine usages in signal-based communication
Venue: arXiv cs.LO 2008
Year: 2008

We describe a type system for a synchronous pi-calculus formalising the notion of affine usage in signal-based communication. In particular, we identify a limited number of usages that preserve affinity and that can be composed. As a main application of the resulting system, we show that typable programs are deterministic.
The Symmetric Sugeno Integral
Venue: arXiv cs.DM 2008
Year: 2008

We propose an extension of the Sugeno integral for negative numbers, in the spirit of the symmetric extension of Choquet integral, also called \Sipos\ integral. Our framework is purely ordinal, since the Sugeno integral has its interest when the underlying structure is ordinal. We begin by defining negative numbers on a linearly ordered set, and we endow this new structure with a suitable algebra, very close to the ring of real numbers. In a second step, we introduce the Möbius transform on this new structure. Lastly, we define the symmetric Sugeno integral, and show its similarity with the symmetric Choquet integral.
Linear Time Recognition Algorithms for Topological Invariants in 3D
Venue: arXiv cs.CV 2008
Year: 2008

In this paper, we design linear time algorithms to recognize and determine topological invariants such as the genus and homology groups in 3D. These properties can be used to identify patterns in 3D image recognition. This has tremendous amount of applications in 3D medical image analysis. Our method is based on cubical images with direct adjacency, also called (6,26)-connectivity images in discrete geometry. According to the fact that there are only six types of local surface points in 3D and a discrete version of the well-known Gauss-Bonnett Theorem in differential geometry, we first determine the genus of a closed 2D-connected component (a closed digital surface). Then, we use Alexander duality to obtain the homology groups of a 3D object in 3D space.
Tight Bounds and Faster Algorithms for Directed Max-Leaf Problems
Venue: arXiv cs.DS 2008
Year: 2008

An out-tree $T$ of a directed graph $D$ is a rooted tree subgraph with all arcs directed outwards from the root. An out-branching is a spanning out-tree. By $l(D)$ and $l_s(D)$ we denote the maximum number of leaves over all out-trees and out-branchings of $D$, respectively. We give fixed parameter tractable algorithms for deciding whether $l_s(D)\geq k$ and whether $l(D)\geq k$ for a digraph $D$ on $n$ vertices, both with time complexity $2^{O(k\log k)} \cdot n^{O(1)}$. This improves on previous algorithms with complexity $2^{O(k^3\log k)} \cdot n^{O(1)}$ and $2^{O(k\log^2 k)} \cdot n^{O(1)}$, respectively. To obtain the complexity bound in the case of out-branchings, we prove that when all arcs of $D$ are part of at least one out-branching, $l_s(D)\geq l(D)/3$. The second bound we prove in this paper states that for strongly connected digraphs $D$ with minimum in-degree 3, $l_s(D)\geq Θ(\sqrt{n})$, where previously $l_s(D)\geq Θ(\sqrt[3]{n})$ was the best known bound. This bound is tight, and also holds for the larger class of digraphs with minimum in-degree 3 in which every arc is part of at least one out-branching.
Impact of Spatial Correlation on the Finite-SNR Diversity-Multiplexing Tradeoff
Venue: arXiv cs.IT 2008
Year: 2008

The impact of spatial correlation on the performance limits of multielement antenna (MEA) channels is analyzed in terms of the diversity-multiplexing tradeoff (DMT) at finite signal-to-noise ratio (SNR) values. A lower bound on the outage probability is first derived. Using this bound accurate finite-SNR estimate of the DMT is then derived. This estimate allows to gain insight on the impact of spatial correlation on the DMT at finite SNR. As expected, the DMT is severely degraded as the spatial correlation increases. Moreover, using asymptotic analysis, we show that our framework encompasses well-known results concerning the asymptotic behavior of the DMT.
Random sampling of colourings of sparse random graphs with a constant number of colours
Venue: arXiv cs.DM 2008
Year: 2008

In this work we present a simple and efficient algorithm which, with high probability, provides an almost uniform sample from the set of proper k-colourings on an instance of a sparse random graph G(n,d/n), where k=k(d) is a sufficiently large constant. Our algorithm is not based on the Markov Chain Monte Carlo method (M.C.M.C.). Instead, we provide a novel proof of correctness of our Algorithm that is based on interesting "spatial mixing" properties of colourings of G(n,d/n). Our result improves upon previous results (based on M.C.M.C.) that required a number of colours growing unboundedly with n.
Causal models have no complete axiomatic characterization
Venue: arXiv cs.AI 2008
Year: 2008

Markov networks and Bayesian networks are effective graphic representations of the dependencies embedded in probabilistic models. It is well known that independencies captured by Markov networks (called graph-isomorphs) have a finite axiomatic characterization. This paper, however, shows that independencies captured by Bayesian networks (called causal models) have no axiomatization by using even countably many Horn or disjunctive clauses. This is because a sub-independency model of a causal model may be not causal, while graph-isomorphs are closed under sub-models.
The ergodic decomposition of asymptotically mean stationary random sources
Venue: arXiv cs.IT 2008
Year: 2008

It is demonstrated how to represent asymptotically mean stationary (AMS) random sources with values in standard spaces as mixtures of ergodic AMS sources. This an extension of the well known decomposition of stationary sources which has facilitated the generalization of prominent source coding theorems to arbitrary, not necessarily ergodic, stationary sources. Asymptotic mean stationarity generalizes the definition of stationarity and covers a much larger variety of real-world examples of random sources of practical interest. It is sketched how to obtain source coding and related theorems for arbitrary, not necessarily ergodic, AMS sources, based on the presented ergodic decomposition.
Augmenting Actual Life Through MUVEs
Venue: arXiv cs.HC 2008
Year: 2008

The necessity of supporting more and more social interaction (and not only the mere information sharing) in online environments is the disruptive force upon which phenomena ascribed to the Web2.0 paradigm continuously bud. People interacting in online socio-technical environments mould technology on their needs, seamlessly integrating it into their everyday life. MUVEs (Multi User Virtual Environments) are no exception and, in several cases, represent the new frontier in this field. In this work we analyze if and how MUVEs can be considered a mean for augmenting communities (and more in general people) life. We trace a framework of analysis based on four main observations, and through these lenses we look at Second Life and at several projects we are currently developing in that synthetic world.
Design and Implementation of a Master of Science in Information and Computer Sciences - An Inventory and retrospect for the last four years
Venue: arXiv cs.GL 2008
Year: 2008

This Master of Science in Computer and Information Sciences (MICS) is an international accredited master program that has been initiated in 2004 and started in September 2005. MICS is a research-oriented academic study of 4 semesters and a continuation of the Bachelor towards the PhD. It is completely taught in English, supported by lecturers coming from more than ten different countries. This report compass a description of its underlying architecture, describes some implementation details and gives a presentation of diverse experiences and results. As the program has been designed and implemented right after the creation of the University, the significance of the program is moreover a self-discovery of the computer science department, which has finally led to the creation of the today's research institutes and research axes.
Information Resources in High-Energy Physics: Surveying the Present Landscape and Charting the Future Course
Venue: arXiv cs.DL 2008
Year: 2008

Access to previous results is of paramount importance in the scientific process. Recent progress in information management focuses on building e-infrastructures for the optimization of the research workflow, through both policy-driven and user-pulled dynamics. For decades, High-Energy Physics (HEP) has pioneered innovative solutions in the field of information management and dissemination. In light of a transforming information environment, it is important to assess the current usage of information resources by researchers and HEP provides a unique test-bed for this assessment. A survey of about 10% of practitioners in the field reveals usage trends and information needs. Community-based services, such as the pioneering arXiv and SPIRES systems, largely answer the need of the scientists, with a limited but increasing fraction of younger users relying on Google. Commercial services offered by publishers or database vendors are essentially unused in the field. The survey offers an insight into the most important features that users require to optimize their research workflow. These results inform the future evolution of information management in HEP and, as these researchers are traditionally ``early adopters'' of innovation in scholarly communication, can inspire developments of disciplinary repositories serving other communities.
Generalized Modal Satisfiability
Venue: arXiv cs.CC 2008
Year: 2008

It is well known that modal satisfiability is PSPACE-complete (Ladner 1977). However, the complexity may decrease if we restrict the set of propositional operators used. Note that there exist an infinite number of propositional operators, since a propositional operator is simply a Boolean function. We completely classify the complexity of modal satisfiability for every finite set of propositional operators, i.e., in contrast to previous work, we classify an infinite number of problems. We show that, depending on the set of propositional operators, modal satisfiability is PSPACE-complete, coNP-complete, or in P. We obtain this trichotomy not only for modal formulas, but also for their more succinct representation using modal circuits. We consider both the uni-modal and the multi-modal case, and study the dual problem of validity as well.
An Adaptive-Parity Error-Resilient LZ'77 Compression Algorithm
Venue: arXiv cs.IT 2008
Year: 2008

The paper proposes an improved error-resilient Lempel-Ziv'77 (LZ'77) algorithm employing an adaptive amount of parity bits for error protection. It is a modified version of error resilient algorithm LZRS'77, proposed recently, which uses a constant amount of parity over all of the encoded blocks of data. The constant amount of parity is bounded by the lowest-redundancy part of the encoded string, whereas the adaptive parity more efficiently utilizes the available redundancy of the encoded string, and can be on average much higher. The proposed algorithm thus provides better error protection of encoded data. The performance of both algorithms was measured. The comparison showed a noticeable improvement by use of adaptive parity. The proposed algorithm is capable of correcting up to a few times as many errors as the original algorithm, while the compression performance remains practically unchanged.
Eigenvalue based Spectrum Sensing Algorithms for Cognitive Radio
Venue: arXiv cs.IT 2008
Year: 2008

Spectrum sensing is a fundamental component is a cognitive radio. In this paper, we propose new sensing methods based on the eigenvalues of the covariance matrix of signals received at the secondary users. In particular, two sensing algorithms are suggested, one is based on the ratio of the maximum eigenvalue to minimum eigenvalue; the other is based on the ratio of the average eigenvalue to minimum eigenvalue. Using some latest random matrix theories (RMT), we quantify the distributions of these ratios and derive the probabilities of false alarm and probabilities of detection for the proposed algorithms. We also find the thresholds of the methods for a given probability of false alarm. The proposed methods overcome the noise uncertainty problem, and can even perform better than the ideal energy detection when the signals to be detected are highly correlated. The methods can be used for various signal detection applications without requiring the knowledge of signal, channel and noise power. Simulations based on randomly generated signals, wireless microphone signals and captured ATSC DTV signals are presented to verify the effectiveness of the proposed methods.
OFDM based Distributed Space Time Coding for Asynchronous Relay Networks
Venue: arXiv cs.IT 2008
Year: 2008

Recently Li and Xia have proposed a transmission scheme for wireless relay networks based on the Alamouti space time code and orthogonal frequency division multiplexing to combat the effect of timing errors at the relay nodes. This transmission scheme is amazingly simple and achieves a diversity order of two for any number of relays. Motivated by its simplicity, this scheme is extended to a more general transmission scheme that can achieve full cooperative diversity for any number of relays. The conditions on the distributed space time block code (DSTBC) structure that admit its application in the proposed transmission scheme are identified and it is pointed out that the recently proposed full diversity four group decodable DSTBCs from precoded co-ordinate interleaved orthogonal designs and extended Clifford algebras satisfy these conditions. It is then shown how differential encoding at the source can be combined with the proposed transmission scheme to arrive at a new transmission scheme that can achieve full cooperative diversity in asynchronous wireless relay networks with no channel information and also no timing error knowledge at the destination node. Finally, four group decodable distributed differential space time block codes applicable in this new transmission scheme for power of two number of relays are also provided.
On the performance of approximate equilibria in congestion games
Venue: arXiv cs.GT 2008
Year: 2008

We study the performance of approximate Nash equilibria for linear congestion games. We consider how much the price of anarchy worsens and how much the price of stability improves as a function of the approximation factor $ε$. We give (almost) tight upper and lower bounds for both the price of anarchy and the price of stability for atomic and non-atomic congestion games. Our results not only encompass and generalize the existing results of exact equilibria to $ε$-Nash equilibria, but they also provide a unified approach which reveals the common threads of the atomic and non-atomic price of anarchy results. By expanding the spectrum, we also cast the existing results in a new light. For example, the Pigou network, which gives tight results for exact Nash equilibria of selfish routing, remains tight for the price of stability of $ε$-Nash equilibria but not for the price of anarchy.
Reconstruction of Multidimensional Signals from Irregular Noisy Samples
Venue: arXiv cs.IT 2008
Year: 2008

We focus on a multidimensional field with uncorrelated spectrum, and study the quality of the reconstructed signal when the field samples are irregularly spaced and affected by independent and identically distributed noise. More specifically, we apply linear reconstruction techniques and take the mean square error (MSE) of the field estimate as a metric to evaluate the signal reconstruction quality. We find that the MSE analysis could be carried out by using the closed-form expression of the eigenvalue distribution of the matrix representing the sampling system. Unfortunately, such distribution is still unknown. Thus, we first derive a closed-form expression of the distribution moments, and we find that the eigenvalue distribution tends to the Marcenko-Pastur distribution as the field dimension goes to infinity. Finally, by using our approach, we derive a tight approximation to the MSE of the reconstructed field.