OpenRaiser/Intern-Atlas huggingface dataset:
The cost of probabilistic gathering in oblivious robot networks
Venue: arXiv cs.DC 2008
Year: 2008

In this paper we address the complexity issues of two agreement problems in oblivious robot networks namely gathering and scattering. These abstractions are fundamental coordination problems in cooperative mobile robotics. Moreover, their oblivious characteristics makes them appealing for self-stabilization since they are self-stabilizing with no extra-cost. Given a set of robots with arbitrary initial location and no initial agreement on a global coordinate system, gathering requires that all robots reach the exact same but not predetermined location while scattering aims at scatter robots such that no two robots share the same location. Both deterministic gathering and scattering have been proved impossible under arbitrary schedulers therefore probabilistic solutions have been recently proposed. The contribution of this paper is twofold. First, we propose a detailed complexity analysis of the existent probabilistic gathering algorithms in both fault-free and fault-prone environments. We consider both crash and byzantine-prone environments. Moreover, using Markov chains tools and additional assumptions on the environment we prove that the gathering convergence time can be reduced from O(n^2) (the best known tight bound) to O(nln(n)). Additionally, we prove that in crash-prone environments gathering is achieved in O(nln(n)+2f). Second, using the same technique we prove that the best known scattering strategy converges in fault-free systems is O(n) (which is one to optimal) while in crash-prone environments it needs O(n-f). Finally, we conclude the paper with a discussion related to different strategies to gather oblivious robots.
Isometric Diamond Subgraphs
Venue: arXiv cs.CG 2008
Year: 2008

We describe polynomial time algorithms for determining whether an undirected graph may be embedded in a distance-preserving way into the hexagonal tiling of the plane, the diamond structure in three dimensions, or analogous structures in higher dimensions. The graphs that may be embedded in this way form an interesting subclass of the partial cubes.
Avatar Mobility in Networked Virtual Environments: Measurements, Analysis, and Implications
Venue: arXiv cs.NI 2008
Year: 2008

We collected mobility traces of 84,208 avatars spanning 22 regions over two months in Second Life, a popular networked virtual environment. We analyzed the traces to characterize the dynamics of the avatars mobility and behavior, both temporally and spatially. We discuss the implications of the our findings to the design of peer-to-peer networked virtual environments, interest management, mobility modeling of avatars, server load balancing and zone partitioning, client-side caching, and prefetching.
Analyse des suites aléatoires engendrées par des automates cellulaires et applications à la cryptographie
Venue: arXiv cs.CR 2008
Year: 2008

This paper considers interactions between cellular automata and cryptology. It is known that non-linear elementary rule which is correlation-immune don't exist. This results limits the use of cellular automata as pseudo-random generators suitable for cryptographic applications. In addition, for this kind of pseudo-random generators, a successful cryptanalysis was proposed by Meier and Staffelbach. However, other ways to design cellular automata capable to generate good pseudo-random sequences remain and will be discussed in the end of this article.
Eigenfactor : Does the Principle of Repeated Improvement Result in Better Journal Impact Estimates than Raw Citation Counts?
Venue: arXiv cs.DL 2008
Year: 2008

Eigenfactor.org, a journal evaluation tool which uses an iterative algorithm to weight citations (similar to the PageRank algorithm used for Google) has been proposed as a more valid method for calculating the impact of journals. The purpose of this brief communication is to investigate whether the principle of repeated improvement provides different rankings of journals than does a simple unweighted citation count (the method used by ISI).
Information Societies and Digital Divides
Venue: arXiv cs.CY 2008
Year: 2008

The book argues ICT are part of the set of goods and services that determine quality of life, social inequality and the chances for economic development. Therefore understanding the digital divide demands a broader discussion of the place of ICT within each society and in the international system. The author argues against the perspectives that either isolates ICT from other basic social goods (in particular education and employment) as well as those that argue that new technologies are luxury of a consumer society. Though the author accepts that new technologies are not a panacea for the problems of inequality, access to them become a condition of full integration of social life. Using examples mainly from Latin America, the work presents some general policy proposals on the fight against the digital divide which take in consideration other dimensions of social inequality and access to public goods. Bernardo Sorj was born in Montevideo, Uruguay. He is a naturalized Brazilian, living in Brazil since 1976. He studied anthropology and philosophy in Uruguay, and holds a B.A. and an M.A. in History and Sociology from Haifa University, Israel. He received his Ph.D. in Sociology from the University of Manchester in England. Sorj was a professor at the Department of Political Science at the Federal University of Minas Gerais and at the Institute for International Relations, PUC/RJ. The author of 20 books and more than 100 articles, was visiting professor and chair at many European and North American universities...
Visual Grouping by Neural Oscillators
Venue: arXiv cs.CV 2008
Year: 2008

Distributed synchronization is known to occur at several scales in the brain, and has been suggested as playing a key functional role in perceptual grouping. State-of-the-art visual grouping algorithms, however, seem to give comparatively little attention to neural synchronization analogies. Based on the framework of concurrent synchronization of dynamic systems, simple networks of neural oscillators coupled with diffusive connections are proposed to solve visual grouping problems. Multi-layer algorithms and feedback mechanisms are also studied. The same algorithm is shown to achieve promising results on several classical visual grouping problems, including point clustering, contour integration and image segmentation.
On Probability Distributions for Trees: Representations, Inference and Learning
Venue: arXiv cs.LG 2008
Year: 2008

We study probability distributions over free algebras of trees. Probability distributions can be seen as particular (formal power) tree series [Berstel et al 82, Esik et al 03], i.e. mappings from trees to a semiring K . A widely studied class of tree series is the class of rational (or recognizable) tree series which can be defined either in an algebraic way or by means of multiplicity tree automata. We argue that the algebraic representation is very convenient to model probability distributions over a free algebra of trees. First, as in the string case, the algebraic representation allows to design learning algorithms for the whole class of probability distributions defined by rational tree series. Note that learning algorithms for rational tree series correspond to learning algorithms for weighted tree automata where both the structure and the weights are learned. Second, the algebraic representation can be easily extended to deal with unranked trees (like XML trees where a symbol may have an unbounded number of children). Both properties are particularly relevant for applications: nondeterministic automata are required for the inference problem to be relevant (recall that Hidden Markov Models are equivalent to nondeterministic string automata); nowadays applications for Web Information Extraction, Web Services and document processing consider unranked trees.
Universal Denoising of Discrete-time Continuous-Amplitude Signals
Venue: arXiv cs.IT 2008
Year: 2008

We consider the problem of reconstructing a discrete-time signal (sequence) with continuous-valued components corrupted by a known memoryless channel. When performance is measured using a per-symbol loss function satisfying mild regularity conditions, we develop a sequence of denoisers that, although independent of the distribution of the underlying `clean' sequence, is universally optimal in the limit of large sequence length. This sequence of denoisers is universal in the sense of performing as well as any sliding window denoising scheme which may be optimized for the underlying clean signal. Our results are initially developed in a ``semi-stochastic'' setting, where the noiseless signal is an unknown individual sequence, and the only source of randomness is due to the channel noise. It is subsequently shown that in the fully stochastic setting, where the noiseless sequence is a stationary stochastic process, our schemes universally attain optimum performance. The proposed schemes draw from nonparametric density estimation techniques and are practically implementable. We demonstrate efficacy of the proposed schemes in denoising gray-scale images in the conventional additive white Gaussian noise setting, with additional promising results for less conventional noise distributions.
Implementing general belief function framework with a practical codification for low complexity
Venue: arXiv cs.AI 2008
Year: 2008

In this chapter, we propose a new practical codification of the elements of the Venn diagram in order to easily manipulate the focal elements. In order to reduce the complexity, the eventual constraints must be integrated in the codification at the beginning. Hence, we only consider a reduced hyper power set $D_r^Θ$ that can be $2^Θ$ or $D^Θ$. We describe all the steps of a general belief function framework. The step of decision is particularly studied, indeed, when we can decide on intersections of the singletons of the discernment space no actual decision functions are easily to use. Hence, two approaches are proposed, an extension of previous one and an approach based on the specificity of the elements on which to decide. The principal goal of this chapter is to provide practical codes of a general belief function framework for the researchers and users needing the belief function theory.
Error Correction Capability of Column-Weight-Three LDPC Codes: Part II
Venue: arXiv cs.IT 2008
Year: 2008

The relation between the girth and the error correction capability of column-weight-three LDPC codes is investigated. Specifically, it is shown that the Gallager A algorithm can correct $g/2-1$ errors in $g/2$ iterations on a Tanner graph of girth $g \geq 10$.
An outer bound for 2-receiver discrete memoryless broadcast channels
Venue: arXiv cs.IT 2008
Year: 2008

An outer bound to the two-receiver discrete memoryless broadcast channel is presented. We compare it to the known outer bounds and show that the outer bound presented is at least as tight as the existing bounds.
A new upper bound for 3-SAT
Venue: arXiv cs.DM 2008
Year: 2008

We show that a randomly chosen 3-CNF formula over n variables with clauses-to-variables ratio at least 4.4898 is, as n grows large, asymptotically almost surely unsatisfiable. The previous best such bound, due to Dubois in 1999, was 4.506. The first such bound, independently discovered by many groups of researchers since 1983, was 5.19. Several decreasing values between 5.19 and 4.506 were published in the years between. The probabilistic techniques we use for the proof are, we believe, of independent interest.
How to Compute Times of Random Walks based Distributed Algorithms
Venue: arXiv cs.DC 2008
Year: 2008

Random walk based distributed algorithms make use of a token that circulates in the system according to a random walk scheme to achieve their goal. To study their efficiency and compare it to one of the deterministic solutions, one is led to compute certain quantities, namely the hitting times and the cover time. Until now, only bounds on these quantities were defined. First, this paper presents two generalizations of the notions of hitting and cover times to weighted graphs. Indeed, the properties of random walks on symmetrically weighted graphs provide interesting results on random walk based distributed algorithms, such as local load balancing. Both of these generalization are proposed to precisely represent the behaviour of these algorithms, and to take into account what the weights represent. Then, we propose an algorithm to compute the n^2 hitting times on a weighted graph of n vertices, which we improve to obtain a O(n^3) complexity. This complexity is the lowest up to now. This algorithm computes both of the generalizations that we propose for the hitting times on a weighted graph. Finally, we provide the first algorithm to compute the cover time (in both senses) of a graph. We improve it to achieve a complexity of O(n^3 2^n). The algorithms that we present are all robust to a topological change in a limited number of edges. This property allows us to use them on dynamic graphs.
Quantifying Timing Leaks and Cost Optimisation
Venue: arXiv cs.CR 2008
Year: 2008

We develop a new notion of security against timing attacks where the attacker is able to simultaneously observe the execution time of a program and the probability of the values of low variables. We then show how to measure the security of a program with respect to this notion via a computable estimate of the timing leakage and use this estimate for cost optimisation.
Rational streams coalgebraically
Venue: arXiv cs.LO 2008
Year: 2008

We study rational streams (over a field) from a coalgebraic perspective. Exploiting the finality of the set of streams, we present an elementary and uniform proof of the equivalence of four notions of representability of rational streams: by finite dimensional linear systems; by finite stream circuits; by finite weighted stream automata; and by finite dimensional subsystems of the set of streams.
Array Based Java Source Code Obfuscation Using Classes with Restructured Arrays
Venue: arXiv cs.CR 2008
Year: 2008

Array restructuring operations obscure arrays. Our work aims on java source code obfuscation containing arrays. Our main proposal is Classes with restructured array members and obscured member methods for setting, getting array elements and to get the length of arrays. The class method definition codes are obscured through index transformation and constant hiding. The instantiated objects of these classes are used for source code writing. A tool named JDATATRANS is developed for generating classes and to the best of our knowledge this is the first tool available for array restructuring, on java source codes.
Improved Algorithms for Approximate String Matching (Extended Abstract)
Venue: arXiv cs.DS 2008
Year: 2008

The problem of approximate string matching is important in many different areas such as computational biology, text processing and pattern recognition. A great effort has been made to design efficient algorithms addressing several variants of the problem, including comparison of two strings, approximate pattern identification in a string or calculation of the longest common subsequence that two strings share. We designed an output sensitive algorithm solving the edit distance problem between two strings of lengths n and m respectively in time O((s-|n-m|)min(m,n,s)+m+n) and linear space, where s is the edit distance between the two strings. This worst-case time bound sets the quadratic factor of the algorithm independent of the longest string length and improves existing theoretical bounds for this problem. The implementation of our algorithm excels also in practice, especially in cases where the two strings compared differ significantly in length. Source code of our algorithm is available at http://www.cs.miami.edu/dimitris/edit_distance
AceWiki: Collaborative Ontology Management in Controlled Natural Language
Venue: arXiv cs.HC 2008
Year: 2008

AceWiki is a prototype that shows how a semantic wiki using controlled natural language - Attempto Controlled English (ACE) in our case - can make ontology management easy for everybody. Sentences in ACE can automatically be translated into first-order logic, OWL, or SWRL. AceWiki integrates the OWL reasoner Pellet and ensures that the ontology is always consistent. Previous results have shown that people with no background in logic are able to add formal knowledge to AceWiki without being instructed or trained in advance.
Approximate kernel clustering
Venue: arXiv cs.DS 2008
Year: 2008

In the kernel clustering problem we are given a large $n\times n$ positive semi-definite matrix $A=(a_{ij})$ with $\sum_{i,j=1}^na_{ij}=0$ and a small $k\times k$ positive semi-definite matrix $B=(b_{ij})$. The goal is to find a partition $S_1,...,S_k$ of $\{1,... n\}$ which maximizes the quantity $$ \sum_{i,j=1}^k (\sum_{(i,j)\in S_i\times S_j}a_{ij})b_{ij}. $$ We study the computational complexity of this generic clustering problem which originates in the theory of machine learning. We design a constant factor polynomial time approximation algorithm for this problem, answering a question posed by Song, Smola, Gretton and Borgwardt. In some cases we manage to compute the sharp approximation threshold for this problem assuming the Unique Games Conjecture (UGC). In particular, when $B$ is the $3\times 3$ identity matrix the UGC hardness threshold of this problem is exactly $\frac{16π}{27}$. We present and study a geometric conjecture of independent interest which we show would imply that the UGC threshold when $B$ is the $k\times k$ identity matrix is $\frac{8π}{9}(1-\frac{1}{k})$ for every $k\ge 3$.
Hacia una teoria de unificacion para los comportamientos cognitivos
Venue: arXiv cs.AI 2008
Year: 2008

Each cognitive science tries to understand a set of cognitive behaviors. The structuring of knowledge of this nature's aspect is far from what it can be expected about a science. Until now universal standard consistently describing the set of cognitive behaviors has not been found, and there are many questions about the cognitive behaviors for which only there are opinions of members of the scientific community. This article has three proposals. The first proposal is to raise to the scientific community the necessity of unified the cognitive behaviors. The second proposal is claim the application of the Newton's reasoning rules about nature of his book, Philosophiae Naturalis Principia Mathematica, to the cognitive behaviors. The third is to propose a scientific theory, currently developing, that follows the rules established by Newton to make sense of nature, and could be the theory to explain all the cognitive behaviors.
Ranking and Unranking of Hereditarily Finite Functions and Permutations
Venue: arXiv cs.LO 2008
Year: 2008

Prolog's ability to return multiple answers on backtracking provides an elegant mechanism to derive reversible encodings of combinatorial objects as Natural Numbers i.e. {\em ranking} and {\em unranking} functions. Starting from a generalization of Ackerman's encoding of Hereditarily Finite Sets with Urelements and a novel tupling/untupling operation, we derive encodings for Finite Functions and use them as building blocks for an executable theory of {\em Hereditarily Finite Functions}. The more difficult problem of {\em ranking} and {\em unranking} {\em Hereditarily Finite Permutations} is then tackled using Lehmer codes and factoradics. The paper is organized as a self-contained literate Prolog program available at \url{http://logic.csci.unt.edu/tarau/research/2008/pHFF.zip}
Logic Engines as Interactors
Venue: arXiv cs.PL 2008
Year: 2008

We introduce a new programming language construct, Interactors, supporting the agent-oriented view that programming is a dialog between simple, self-contained, autonomous building blocks. We define Interactors as an abstraction of answer generation and refinement in Logic Engines resulting in expressive language extension and metaprogramming patterns, including emulation of Prolog's dynamic database. A mapping between backtracking based answer generation in the callee and "forward" recursion in the caller enables interaction between different branches of the callee's search process and provides simplified design patterns for algorithms involving combinatorial generation and infinite answer streams. Interactors extend language constructs like Ruby, Python and C#'s multiple coroutining block returns through yield statements and they can emulate the action of monadic constructs and catamorphisms in functional languages. Keywords: generalized iterators, logic engines, agent oriented programming language constructs, interoperation with stateful objects, metaprogramming
On row-by-row coding for 2-D constraints
Venue: arXiv cs.IT 2008
Year: 2008

A constant-rate encoder--decoder pair is presented for a fairly large family of two-dimensional (2-D) constraints. Encoding and decoding is done in a row-by-row manner, and is sliding-block decodable. Essentially, the 2-D constraint is turned into a set of independent and relatively simple one-dimensional (1-D) constraints; this is done by dividing the array into fixed-width vertical strips. Each row in the strip is seen as a symbol, and a graph presentation of the respective 1-D constraint is constructed. The maxentropic stationary Markov chain on this graph is next considered: a perturbed version of the corresponding probability distribution on the edges of the graph is used in order to build an encoder which operates in parallel on the strips. This perturbation is found by means of a network flow, with upper and lower bounds on the flow through the edges. A key part of the encoder is an enumerative coder for constant-weight binary words. A fast realization of this coder is shown, using floating-point arithmetic.
A Functional Hitchhiker's Guide to Hereditarily Finite Sets, Ackermann Encodings and Pairing Functions
Venue: arXiv cs.MS 2008
Year: 2008

The paper is organized as a self-contained literate Haskell program that implements elements of an executable finite set theory with focus on combinatorial generation and arithmetic encodings. The code, tested under GHC 6.6.1, is available at http://logic.csci.unt.edu/tarau/research/2008/fSET.zip . We introduce ranking and unranking functions generalizing Ackermann's encoding to the universe of Hereditarily Finite Sets with Urelements. Then we build a lazy enumerator for Hereditarily Finite Sets with Urelements that matches the unranking function provided by the inverse of Ackermann's encoding and we describe functors between them resulting in arithmetic encodings for powersets, hypergraphs, ordinals and choice functions. After implementing a digraph representation of Hereditarily Finite Sets we define {\em decoration functions} that can recover well-founded sets from encodings of their associated acyclic digraphs. We conclude with an encoding of arbitrary digraphs and discuss a concept of duality induced by the set membership relation. Keywords: hereditarily finite sets, ranking and unranking functions, executable set theory, arithmetic encodings, Haskell data representations, functional programming and computational mathematics