OpenRaiser/Intern-Atlas huggingface dataset:
Spiral Walk on Triangular Meshes : Adaptive Replication in Data P2P Networks
Venue: arXiv cs.NI 2008
Year: 2008

We introduce a decentralized replication strategy for peer-to-peer file exchange based on exhaustive exploration of the neighborhood of any node in the network. The replication scheme lets the replicas evenly populate the network mesh, while regulating the total number of replicas at the same time. This is achieved by self adaptation to entering or leaving of nodes. Exhaustive exploration is achieved by a spiral walk algorithm that generates a number of messages linearly proportional to the number of visited nodes. It requires a dedicated topology (a triangular mesh on a closed surface). We introduce protocols for node connection and departure that maintain the triangular mesh at low computational and bandwidth cost. Search efficiency is increased using a mechanism based on dynamically allocated super peers. We conclude with a discussion on experimental validation results.
Balanced Families of Perfect Hash Functions and Their Applications
Venue: arXiv cs.DS 2008
Year: 2008

The construction of perfect hash functions is a well-studied topic. In this paper, this concept is generalized with the following definition. We say that a family of functions from $[n]$ to $[k]$ is a $δ$-balanced $(n,k)$-family of perfect hash functions if for every $S \subseteq [n]$, $|S|=k$, the number of functions that are 1-1 on $S$ is between $T/δ$ and $δT$ for some constant $T>0$. The standard definition of a family of perfect hash functions requires that there will be at least one function that is 1-1 on $S$, for each $S$ of size $k$. In the new notion of balanced families, we require the number of 1-1 functions to be almost the same (taking $δ$ to be close to 1) for every such $S$. Our main result is that for any constant $δ> 1$, a $δ$-balanced $(n,k)$-family of perfect hash functions of size $2^{O(k \log \log k)} \log n$ can be constructed in time $2^{O(k \log \log k)} n \log n$. Using the technique of color-coding we can apply our explicit constructions to devise approximation algorithms for various counting problems in graphs. In particular, we exhibit a deterministic polynomial time algorithm for approximating both the number of simple paths of length $k$ and the number of simple cycles of size $k$ for any $k \leq O(\frac{\log n}{\log \log \log n})$ in a graph with $n$ vertices. The approximation is up to any fixed desirable relative error.
Low-Complexity Structured Precoding for Spatially Correlated MIMO Channels
Venue: arXiv cs.IT 2008
Year: 2008

The focus of this paper is on spatial precoding in correlated multi-antenna channels, where the number of independent data-streams is adapted to trade-off the data-rate with the transmitter complexity. Towards the goal of a low-complexity implementation, a structured precoder is proposed, where the precoder matrix evolves fairly slowly at a rate comparable with the statistical evolution of the channel. Here, the eigenvectors of the precoder matrix correspond to the dominant eigenvectors of the transmit covariance matrix, whereas the power allocation across the modes is fixed, known at both the ends, and is of low-complexity. A particular case of the proposed scheme (semiunitary precoding), where the spatial modes are excited with equal power, is shown to be near-optimal in matched channels. A matched channel is one where the dominant eigenvalues of the transmit covariance matrix are well-conditioned and their number equals the number of independent data-streams, and the receive covariance matrix is also well-conditioned. In mismatched channels, where the above conditions are not met, it is shown that the loss in performance with semiunitary precoding when compared with a perfect channel information benchmark is substantial. This loss needs to be mitigated via limited feedback techniques that provide partial channel information to the transmitter. More importantly, we develop matching metrics that capture the degree of matching of a channel to the precoder structure continuously, and allow ordering two matrix channels in terms of their mutual information or error probability performance.
Golden Space-Time Block Coded Modulation
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we present a block coded modulation scheme for a 2 x 2 MIMO system over slow fading channels, where the inner code is the Golden Code. The scheme is based on a set partitioning of the Golden Code using two-sided ideals whose norm is a power of two. In this case, a lower bound for the minimum determinant is given by the minimum Hamming distance. The description of the ring structure of the quotients suggests further optimization in order to improve the overall distribution of determinants. Performance simulations show that the GC-RS schemes achieve a significant gain over the uncoded Golden Code.
Telex: Principled System Support for Write-Sharing in Collaborative Applications
Venue: arXiv cs.OS 2008
Year: 2008

The Telex system is designed for sharing mutable data in a distributed environment, particularly for collaborative applications. Users operate on their local, persistent replica of shared documents; they can work disconnected and suffer no network latency. The Telex approach to detect and correct conflicts is application independent, based on an action-constraint graph (ACG) that summarises the concurrency semantics of applications. The ACG is stored efficiently in a multilog structure that eliminates contention and is optimised for locality. Telex supports multiple applications and multi-document updates. The Telex system clearly separates system logic (which includes replication, views, undo, security, consistency, conflicts, and commitment) from application logic. An example application is a shared calendar for managing multi-user meetings; the system detects meeting conflicts and resolves them consistently.
Report on article The Travelling Salesman Problem: A Linear Programming Formulation
Venue: arXiv cs.CC 2008
Year: 2008

This article describes counter example prepared in order to prove that linear formulation of TSP problem proposed in [arXiv:0803.4354] is incorrect (it applies also to QAP problem formulation in [arXiv:0802.4307]). Article refers not only to model itself, but also to ability of extension of proposed model to be correct.
Managing conflicts between users in Wikipedia
Venue: arXiv cs.IR 2008
Year: 2008

Wikipedia is nowadays a widely used encyclopedia, and one of the most visible sites on the Internet. Its strong principle of collaborative work and free editing sometimes generates disputes due to disagreements between users. In this article we study how the wikipedian community resolves the conflicts and which roles do wikipedian choose in this process. We observed the users behavior both in the article talk pages, and in the Arbitration Committee pages specifically dedicated to serious disputes. We first set up a users typology according to their involvement in conflicts and their publishing and management activity in the encyclopedia. We then used those user types to describe users behavior in contributing to articles that are tagged by the wikipedian community as being in conflict with the official guidelines of Wikipedia, or conversely as being well featured.
Regularization of Invers Problem for M-Ary Channel
Venue: arXiv cs.IT 2008
Year: 2008

The problem of computation of parameters of m-ary channel is considered. It is demonstrated that although the problem is ill-posed, it is possible turning of the parameters of the system and transform the problem to well-posed one.
Local approximation algorithms for a class of 0/1 max-min linear programs
Venue: arXiv cs.DC 2008
Year: 2008

We study the applicability of distributed, local algorithms to 0/1 max-min LPs where the objective is to maximise ${\min_k \sum_v c_{kv} x_v}$ subject to ${\sum_v a_{iv} x_v \le 1}$ for each $i$ and ${x_v \ge 0}$ for each $v$. Here $c_{kv} \in \{0,1\}$, $a_{iv} \in \{0,1\}$, and the support sets ${V_i = \{v : a_{iv} > 0 \}}$ and ${V_k = \{v : c_{kv}>0 \}}$ have bounded size; in particular, we study the case $|V_k| \le 2$. Each agent $v$ is responsible for choosing the value of $x_v$ based on information within its constant-size neighbourhood; the communication network is the hypergraph where the sets $V_k$ and $V_i$ constitute the hyperedges. We present a local approximation algorithm which achieves an approximation ratio arbitrarily close to the theoretical lower bound presented in prior work.
Model of information diffusion
Venue: arXiv cs.IT 2008
Year: 2008

The system of cellular automata, which expresses the process of dissemination and publication of the news among separate information resources, has been described. A bell-shaped dependence of news diffusion on internet-sources (web-sites) coheres well with a real behavior of thematic data flows, and at local time spans - with noted models, e.g., exponential and logistic ones.
Kinematic Analysis of the vertebra of an eel like robot
Venue: arXiv cs.RO 2008
Year: 2008

The kinematic analysis of a spherical wrist with parallel architecture is the object of this article. This study is part of a larger French project, which aims to design and to build an eel like robot to imitate the eel swimming. To implement direct and inverse kinematics on the control law of the prototype, we need to evaluate the workspace without any collisions between the different bodies. The tilt and torsion parameters are used to represent the workspace.
Steganographic Routing in Multi Agent System Environment
Venue: arXiv cs.CR 2008
Year: 2008

In this paper we present an idea of trusted communication platform for Multi-Agent Systems (MAS) called TrustMAS. Based on analysis of routing protocols suitable for MAS we have designed a new proactive hidden routing. Proposed steg-agents discovery procedure, as well as further routes updates and hidden communication, are cryptographically independent. Steganographic exchange can cover heterogeneous and geographically outlying environments using available cross-layer covert channels. Finally we have specified rules that agents have to follow to benefit the TrustMAS distributed router platform.
Collaborative model of interaction and Unmanned Vehicle Systems' interface
Venue: arXiv cs.AI 2008
Year: 2008

The interface for the next generation of Unmanned Vehicle Systems should be an interface with multi-modal displays and input controls. Then, the role of the interface will not be restricted to be a support of the interactions between the ground operator and vehicles. Interface must take part in the interaction management too. In this paper, we show that recent works in pragmatics and philosophy provide a suitable theoretical framework for the next generation of UV System's interface. We concentrate on two main aspects of the collaborative model of interaction based on acceptance: multi-strategy approach for communicative act generation and interpretation and communicative alignment.
Upper and Lower Bounds on Black-Box Steganography
Venue: arXiv cs.CR 2008
Year: 2008

We study the limitations of steganography when the sender is not using any properties of the underlying channel beyond its entropy and the ability to sample from it. On the negative side, we show that the number of samples the sender must obtain from the channel is exponential in the rate of the stegosystem. On the positive side, we present the first secret-key stegosystem that essentially matches this lower bound regardless of the entropy of the underlying channel. Furthermore, for high-entropy channels, we present the first secret-key stegosystem that matches this lower bound statelessly (i.e., without requiring synchronized state between sender and receiver).
Extracting Programs from Constructive HOL Proofs via IZF Set-Theoretic<br> Semantics
Venue: arXiv cs.LO 2008
Year: 2008

Church's Higher Order Logic is a basis for influential proof assistants -- HOL and PVS. Church's logic has a simple set-theoretic semantics, making it trustworthy and extensible. We factor HOL into a constructive core plus axioms of excluded middle and choice. We similarly factor standard set theory, ZFC, into a constructive core, IZF, and axioms of excluded middle and choice. Then we provide the standard set-theoretic semantics in such a way that the constructive core of HOL is mapped into IZF. We use the disjunction, numerical existence and term existence properties of IZF to provide a program extraction capability from proofs in the constructive core. We can implement the disjunction and numerical existence properties in two different ways: one using Rathjen's realizability for IZF and the other using a new direct weak normalization result for IZF by Moczydlowski. The latter can also be used for the term existence property.
VPOET: Using a Distributed Collaborative Platform for Semantic Web Applications
Venue: arXiv cs.SE 2008
Year: 2008

This paper describes a distributed collaborative wiki-based platform that has been designed to facilitate the development of Semantic Web applications. The applications designed using this platform are able to build semantic data through the cooperation of different developers and to exploit that semantic data. The paper shows a practical case study on the application VPOET, and how an application based on Google Gadgets has been designed to test VPOET and let human users exploit the semantic data created. This practical example can be used to show how different Semantic Web technologies can be integrated into a particular Web application, and how the knowledge can be cooperatively improved.
On the Superdistribution of Digital Goods
Venue: arXiv cs.MM 2008
Year: 2008

Business models involving buyers of digital goods in the distribution process are called superdistribution schemes. We review the state-of-the art of research and application of superdistribution and propose systematic approach to market mechanisms using super-distribution and technical system architectures supporting it. The limiting conditions on such markets are of economic, legal, technical, and psychological nature.
The injectivity of the global function of a cellular automaton in the hyperbolic plane is undecidable
Venue: arXiv cs.CG 2008
Year: 2008

In this paper, we look at the following question. We consider cellular automata in the hyperbolic plane and we consider the global function defined on all possible configurations. Is the injectivity of this function undecidable? The problem was answered positively in the case of the Euclidean plane by Jarkko Kari, in 1994. In the present paper, we show that the answer is also positive for the hyperbolic plane: the problem is undecidable.
Toward a combination rule to deal with partial conflict and specificity in belief functions theory
Venue: arXiv cs.AI 2008
Year: 2008

We present and discuss a mixed conjunctive and disjunctive rule, a generalization of conflict repartition rules, and a combination of these two rules. In the belief functions theory one of the major problem is the conflict repartition enlightened by the famous Zadeh's example. To date, many combination rules have been proposed in order to solve a solution to this problem. Moreover, it can be important to consider the specificity of the responses of the experts. Since few year some unification rules are proposed. We have shown in our previous works the interest of the proportional conflict redistribution rule. We propose here a mixed combination rule following the proportional conflict redistribution rule modified by a discounting procedure. This rule generalizes many combination rules.
Self-overlapping Curves Revisited
Venue: arXiv cs.CG 2008
Year: 2008

A surface embedded in space, in such a way that each point has a neighborhood within which the surface is a terrain, projects to an immersed surface in the plane, the boundary of which is a self-intersecting curve. Under what circumstances can we reverse these mappings algorithmically? Shor and van Wyk considered one such problem, determining whether a curve is the boundary of an immersed disk; they showed that the self-overlapping curves defined in this way can be recognized in polynomial time. We show that several related problems are more difficult: it is NP-complete to determine whether an immersed disk is the projection of a surface embedded in space, or whether a curve is the boundary of an immersed surface in the plane that is not constrained to be a disk. However, when a casing is supplied with a self-intersecting curve, describing which component of the curve lies above and which below at each crossing, we may determine in time linear in the number of crossings whether the cased curve forms the projected boundary of a surface in space. As a related result, we show that an immersed surface with a single boundary curve that crosses itself n times has at most 2^{n/2} combinatorially distinct spatial embeddings, and we discuss the existence of fixed-parameter tractable algorithms for related problems.
Detrended fluctuation analysis of traffic data
Venue: arXiv cs.NI 2008
Year: 2008

Different routing strategies may result in different behaviors of traffic on internet. We analyze the correlation of traffic data for three typical routing strategies by the detrended fluctuation analysis (DFA) and find that the degree of correlation of the data can be divided into three regions, i.e., weak, medium, and strong correlation. The DFA scalings are constants in both the regions of weak and strong correlation but monotonously increase in the region of medium correlation. We suggest that it is better to consider the traffic on complex network as three phases, i.e., the free, buffer, and congestion phase, than just as two phases believed before, i.e., the free and congestion phase.
Non-linear index coding outperforming the linear optimum
Venue: arXiv cs.IT 2008
Year: 2008

The following source coding problem was introduced by Birk and Kol: a sender holds a word $x\in\{0,1\}^n$, and wishes to broadcast a codeword to $n$ receivers, $R_1,...,R_n$. The receiver $R_i$ is interested in $x_i$, and has prior \emph{side information} comprising some subset of the $n$ bits. This corresponds to a directed graph $G$ on $n$ vertices, where $i j$ is an edge iff $R_i$ knows the bit $x_j$. An \emph{index code} for $G$ is an encoding scheme which enables each $R_i$ to always reconstruct $x_i$, given his side information. The minimal word length of an index code was studied by Bar-Yossef, Birk, Jayram and Kol (FOCS 2006). They introduced a graph parameter, $\minrk_2(G)$, which completely characterizes the length of an optimal \emph{linear} index code for $G$. The authors of BBJK showed that in various cases linear codes attain the optimal word length, and conjectured that linear index coding is in fact \emph{always} optimal. In this work, we disprove the main conjecture of BBJK in the following strong sense: for any $ε> 0$ and sufficiently large $n$, there is an $n$-vertex graph $G$ so that every linear index code for $G$ requires codewords of length at least $n^{1-ε}$, and yet a non-linear index code for $G$ has a word length of $n^ε$. This is achieved by an explicit construction, which extends Alon's variant of the celebrated Ramsey construction of Frankl and Wilson. In addition, we study optimal index codes in various, less restricted, natural models, and prove several related properties of the graph parameter $\minrk(G)$.
Max Cut and the Smallest Eigenvalue
Venue: arXiv cs.DS 2008
Year: 2008

We describe a new approximation algorithm for Max Cut. Our algorithm runs in $\tilde O(n^2)$ time, where $n$ is the number of vertices, and achieves an approximation ratio of $.531$. On instances in which an optimal solution cuts a $1-ε$ fraction of edges, our algorithm finds a solution that cuts a $1-4\sqrtε + 8ε-o(1)$ fraction of edges. Our main result is a variant of spectral partitioning, which can be implemented in nearly linear time. Given a graph in which the Max Cut optimum is a $1-ε$ fraction of edges, our spectral partitioning algorithm finds a set $S$ of vertices and a bipartition $L,R=S-L$ of $S$ such that at least a $1-O(\sqrt ε)$ fraction of the edges incident on $S$ have one endpoint in $L$ and one endpoint in $R$. (This can be seen as an analog of Cheeger's inequality for the smallest eigenvalue of the adjacency matrix of a graph.) Iterating this procedure yields the approximation results stated above. A different, more complicated, variant of spectral partitioning leads to an $\tilde O(n^3)$ time algorithm that cuts $1/2 + e^{-Ω(1/\eps)}$ fraction of edges in graphs in which the optimum is $1/2 + ε$.
Beyond Nash Equilibrium: Solution Concepts for the 21st Century
Venue: arXiv cs.GT 2008
Year: 2008

Nash equilibrium is the most commonly-used notion of equilibrium in game theory. However, it suffers from numerous problems. Some are well known in the game theory community; for example, the Nash equilibrium of repeated prisoner's dilemma is neither normatively nor descriptively reasonable. However, new problems arise when considering Nash equilibrium from a computer science perspective: for example, Nash equilibrium is not robust (it does not tolerate ``faulty'' or ``unexpected'' behavior), it does not deal with coalitions, it does not take computation cost into account, and it does not deal with cases where players are not aware of all aspects of the game. Solution concepts that try to address these shortcomings of Nash equilibrium are discussed.
An Intelligent Multi-Agent Recommender System for Human Capacity Building
Venue: arXiv cs.AI 2008
Year: 2008

This paper presents a Multi-Agent approach to the problem of recommending training courses to engineering professionals. The recommendation system is built as a proof of concept and limited to the electrical and mechanical engineering disciplines. Through user modelling and data collection from a survey, collaborative filtering recommendation is implemented using intelligent agents. The agents work together in recommending meaningful training courses and updating the course information. The system uses a users profile and keywords from courses to rank courses. A ranking accuracy for courses of 90% is achieved while flexibility is achieved using an agent that retrieves information autonomously using data mining techniques from websites. This manner of recommendation is scalable and adaptable. Further improvements can be made using clustering and recording user feedback.
Ad-hoc Limited Scale-Free Models for Unstructured Peer-to-Peer Networks
Venue: arXiv cs.DC 2008
Year: 2008

Several protocol efficiency metrics (e.g., scalability, search success rate, routing reachability and stability) depend on the capability of preserving structure even over the churn caused by the ad-hoc nodes joining or leaving the network. Preserving the structure becomes more prohibitive due to the distributed and potentially uncooperative nature of such networks, as in the peer-to-peer (P2P) networks. Thus, most practical solutions involve unstructured approaches while attempting to maintain the structure at various levels of protocol stack. The primary focus of this paper is to investigate construction and maintenance of scale-free topologies in a distributed manner without requiring global topology information at the time when nodes join or leave. We consider the uncooperative behavior of peers by limiting the number of neighbors to a pre-defined hard cutoff value (i.e., no peer is a major hub), and the ad-hoc behavior of peers by rewiring the neighbors of nodes leaving the network. We also investigate the effect of these hard cutoffs and rewiring of ad-hoc nodes on the P2P search efficiency.
The computability path ordering: the end of a quest
Venue: arXiv cs.LO 2008
Year: 2008

In this paper, we first briefly survey automated termination proof methods for higher-order calculi. We then concentrate on the higher-order recursive path ordering, for which we provide an improved definition, the Computability Path Ordering. This new definition appears indeed to capture the essence of computability arguments à la Tait and Girard, therefore explaining the name of the improved ordering.