OpenRaiser/Intern-Atlas huggingface dataset:
Error Exponents of Optimum Decoding for the Interference Channel
Venue: arXiv cs.IT 2008
Year: 2008

Exponential error bounds for the finite-alphabet interference channel (IFC) with two transmitter-receiver pairs, are investigated under the random coding regime. Our focus is on optimum decoding, as opposed to heuristic decoding rules that have been used in previous works, like joint typicality decoding, decoding based on interference cancellation, and decoding that considers the interference as additional noise. Indeed, the fact that the actual interfering signal is a codeword and not an i.i.d. noise process complicates the application of conventional techniques to the performance analysis of the optimum decoder. Using analytical tools rooted in statistical physics, we derive a single letter expression for error exponents achievable under optimum decoding and demonstrate strict improvement over error exponents obtainable using suboptimal decoding rules, but which are amenable to more conventional analysis.
A global physician-oriented medical information system
Venue: arXiv cs.CY 2008
Year: 2008

We propose to improve medical decision making and reduce global health care costs by employing a free Internet-based medical information system with two main target groups: practicing physicians and medical researchers. After acquiring patients' consent, physicians enter medical histories, physiological data and symptoms or disorders into the system; an integrated expert system can then assist in diagnosis and statistical software provides a list of the most promising treatment options and medications, tailored to the patient. Physicians later enter information about the outcomes of the chosen treatments, data the system uses to optimize future treatment recommendations. Medical researchers can analyze the aggregate data to compare various drugs or treatments in defined patient populations on a large scale.
Joint source-channel coding via statistical mechanics: thermal equilibrium between the source and the channel
Venue: arXiv cs.IT 2008
Year: 2008

We examine the classical joint source--channel coding problem from the viewpoint of statistical physics and demonstrate that in the random coding regime, the posterior probability distribution of the source given the channel output is dominated by source sequences, which exhibit a behavior that is highly parallel to that of thermal equilibrium between two systems of particles that exchange energy, where one system corresponds to the source and the other corresponds to the channel. The thermodynamical entopies of the dual physical problem are analogous to conditional and unconditional Shannon entropies of the source, and so, their balance in thermal equilibrium yields a simple formula for the mutual information between the source and the channel output, that is induced by the typical code in an ensemble of joint source--channel codes under certain conditions. We also demonstrate how our results can be used in applications, like the wiretap channel, and how can it be extended to multiuser scenarios, like that of the multiple access channel.
A simple local 3-approximation algorithm for vertex cover
Venue: arXiv cs.DC 2008
Year: 2008

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required.
On the Throughput Maximization in Dencentralized Wireless Networks
Venue: arXiv cs.IT 2008
Year: 2008

A distributed single-hop wireless network with $K$ links is considered, where the links are partitioned into a fixed number ($M$) of clusters each operating in a subchannel with bandwidth $\frac{W}{M}$. The subchannels are assumed to be orthogonal to each other. A general shadow-fading model, described by parameters $(α,\varpi)$, is considered where $α$ denotes the probability of shadowing and $\varpi$ ($\varpi \leq 1$) represents the average cross-link gains. The main goal of this paper is to find the maximum network throughput in the asymptotic regime of $K \to \infty$, which is achieved by: i) proposing a distributed and non-iterative power allocation strategy, where the objective of each user is to maximize its best estimate (based on its local information, i.e., direct channel gain) of the average network throughput, and ii) choosing the optimum value for $M$. In the first part of the paper, the network hroughput is defined as the \textit{average sum-rate} of the network, which is shown to scale as $Θ(\log K)$. Moreover, it is proved that in the strong interference scenario, the optimum power allocation strategy for each user is a threshold-based on-off scheme. In the second part, the network throughput is defined as the \textit{guaranteed sum-rate}, when the outage probability approaches zero. In this scenario, it is demonstrated that the on-off power allocation scheme maximizes the throughput, which scales as $\frac{W}{α\varpi} \log K$. Moreover, the optimum spectrum sharing for maximizing the average sum-rate and the guaranteed sum-rate is achieved at M=1.
Path Planner for Objects, Robots and Mannequins by Multi-Agents Systems or Motion Captures
Venue: arXiv cs.RO 2008
Year: 2008

In order to optimise the costs and time of design of the new products while improving their quality, concurrent engineering is based on the digital model of these products. However, in order to be able to avoid definitively physical model without loss of information, new tools must be available. Especially, a tool making it possible to check simply and quickly the maintainability of complex mechanical sets using the numerical model is necessary. Since one decade, the MCM team of IRCCyN works on the creation of tools for the generation and the analysis of trajectories of virtual mannequins. The simulation of human tasks can be carried out either by robot-like simulation or by simulation by motion capture. This paper presents some results on the both two methods. The first method is based on a multi-agent system and on a digital mock-up technology, to assess an efficient path planner for a manikin or a robot for access and visibility task taking into account ergonomic constraints or joint limits. The human operator is integrated in the process optimisation to contribute to a global perception of the environment. This operator cooperates, in real-time, with several automatic local elementary agents. In the second method, we worked with the CEA and EADS/CCR to solve the constraints related to the evolution of human virtual in its environment on the basis of data resulting from motion capture system. An approach using of the virtual guides was developed to allow to the user the realization of precise trajectory in absence of force feedback.
On the cubicity of bipartite graphs
Venue: arXiv cs.DM 2008
Year: 2008

{\it A unit cube in $k$-dimension (or a $k$-cube) is defined as the cartesian product $R_1 \times R_2 \times ... \times R_k$, where each $R_i$ is a closed interval on the real line of the form $[a_i, a_i+1]$. The {\it cubicity} of $G$, denoted as $cub(G)$, is the minimum $k$ such that $G$ is the intersection graph of a collection of $k$-cubes. Many NP-complete graph problems can be solved efficiently or have good approximation ratios in graphs of low cubicity. In most of these cases the first step is to get a low dimensional cube representation of the given graph. It is known that for a graph $G$, $cub(G) \leq \lfloor\frac{2n}{3}\rfloor$. Recently it has been shown that for a graph $G$, $cub(G) \leq 4(Δ+ 1)\ln n$, where $n$ and $Δ$ are the number of vertices and maximum degree of $G$, respectively. In this paper, we show that for a bipartite graph $G = (A \cup B, E)$ with $|A| = n_1$, $|B| = n_2$, $n_1 \leq n_2$, and $Δ' = \min\{Δ_A, Δ_B\}$, where $Δ_A = {max}_{a \in A}d(a)$ and $Δ_B = {max}_{b \in B}d(b)$, $d(a)$ and $d(b)$ being the degree of $a$ and $b$ in $G$ respectively, $cub(G) \leq 2(Δ'+2) \lceil \ln n_2 \rceil$. We also give an efficient randomized algorithm to construct the cube representation of $G$ in $3(Δ'+2)\lceil \ln n_2 \rceil$ dimensions. The reader may note that in general $Δ'$ can be much smaller than $Δ$.}
Welfare Undominated Groves Mechanisms
Venue: arXiv cs.GT 2008
Year: 2008

A common objective in mechanism design is to choose the outcome (for example, allocation of resources) that maximizes the sum of the agents' valuations, without introducing incentives for agents to misreport their preferences. The class of Groves mechanisms achieves this; however, these mechanisms require the agents to make payments, thereby reducing the agents' total welfare. In this paper we introduce a measure for comparing two mechanisms with respect to the final welfare they generate. This measure induces a partial order on mechanisms and we study the question of finding minimal elements with respect to this partial order. In particular, we say a non-deficit Groves mechanism is welfare undominated if there exists no other non-deficit Groves mechanism that always has a smaller or equal sum of payments. We focus on two domains: (i) auctions with multiple identical units and unit-demand bidders, and (ii) mechanisms for public project problems. In the first domain we analytically characterize all welfare undominated Groves mechanisms that are anonymous and have linear payment functions, by showing that the family of optimal-in-expectation linear redistribution mechanisms, which were introduced in [6] and include the Bailey-Cavallo mechanism [1,2], coincides with the family of welfare undominated Groves mechanisms that are anonymous and linear in the setting we study. In the second domain we show that the classic VCG (Clarke) mechanism is welfare undominated for the class of public project problems with equal participation costs, but is not undominated for a more general class.
Taming Modal Impredicativity: Superlazy Reduction
Venue: arXiv cs.LO 2008
Year: 2008

Pure, or type-free, Linear Logic proof nets are Turing complete once cut-elimination is considered as computation. We introduce modal impredicativity as a new form of impredicativity causing the complexity of cut-elimination to be problematic from a complexity point of view. Modal impredicativity occurs when, during reduction, the conclusion of a residual of a box b interacts with a node that belongs to the proof net inside another residual of b. Technically speaking, superlazy reduction is a new notion of reduction that allows to control modal impredicativity. More specifically, superlazy reduction replicates a box only when all its copies are opened. This makes the overall cost of reducing a proof net finite and predictable. Specifically, superlazy reduction applied to any pure proof nets takes primitive recursive time. Moreover, any primitive recursive function can be computed by a pure proof net via superlazy reduction.
Clone Theory: Its Syntax and Semantics, Applications to Universal Algebra, Lambda Calculus and Algebraic Logic
Venue: arXiv cs.LO 2008
Year: 2008

The primary goal of this paper is to present a unified way to transform the syntax of a logic system into certain initial algebraic structure so that it can be studied algebraically. The algebraic structures which one may choose for this purpose are various clones over a full subcategory of a category. We show that the syntax of equational logic, lambda calculus and first order logic can be represented as clones or right algebras of clones over the set of positive integers. The semantics is then represented by structures derived from left algebras of these clones.
Dynamic Approaches to In-Network Aggregation
Venue: arXiv cs.DC 2008
Year: 2008

Collaboration between small-scale wireless devices hinges on their ability to infer properties shared across multiple nearby nodes. Wireless-enabled mobile devices in particular create a highly dynamic environment not conducive to distributed reasoning about such global properties. This paper addresses a specific instance of this problem: distributed aggregation. We present extensions to existing unstructured aggregation protocols that enable estimation of count, sum, and average aggregates in highly dynamic environments. With the modified protocols, devices with only limited connectivity can maintain estimates of the aggregate, despite \textit{unexpected} peer departures and arrivals. Our analysis of these aggregate maintenance extensions demonstrates their effectiveness in unstructured environments despite high levels of node mobility.
A sound spatio-temporal Hoare logic for the verification of structured interactive programs with registers and voices
Venue: arXiv cs.PL 2008
Year: 2008

Interactive systems with registers and voices (shortly, "rv-systems") are a model for interactive computing obtained closing register machines with respect to a space-time duality transformation ("voices" are the time-dual counterparts of "registers"). In the same vain, AGAPIA v0.1, a structured programming language for rv-systems, is the space-time dual closure of classical while programs (over a specific type of data). Typical AGAPIA programs describe open processes located at various sites and having their temporal windows of adequate reaction to the environment. The language naturally supports process migration, structured interaction, and deployment of components on heterogeneous machines. In this paper a sound Hoare-like spatio-temporal logic for the verification of AGAPIA v0.1 programs is introduced. As a case study, a formal verification proof of a popular distributed termination detection protocol is presented.
Enhancements to A Lightweight RFID Authentication Protocol
Venue: arXiv cs.CR 2008
Year: 2008

Vajda and Buttyan (VB) proposed a set of five lightweight RFID authentication protocols. Defend, Fu, and Juels (DFJ) did cryptanalysis on two of them - XOR and SUBSET. To the XOR protocol, DFJ proposed repeated keys attack and nibble attack. In this paper, we identify the vulnerability existed in the original VB's successive session key permutation algorithm. We propose three enhancements to prevent DFJ's attacks and make XOR protocol stronger without introducing extra resource cost.
Coding Theorems for Repeat Multiple Accumulate Codes
Venue: arXiv cs.IT 2008
Year: 2008

In this paper the ensemble of codes formed by a serial concatenation of a repetition code with multiple accumulators connected through random interleavers is considered. Based on finite length weight enumerators for these codes, asymptotic expressions for the minimum distance and an arbitrary number of accumulators larger than one are derived using the uniform interleaver approach. In accordance with earlier results in the literature, it is first shown that the minimum distance of repeat-accumulate codes can grow, at best, sublinearly with block length. Then, for repeat-accumulate-accumulate codes and rates of 1/3 or less, it is proved that these codes exhibit asymptotically linear distance growth with block length, where the gap to the Gilbert-Varshamov bound can be made vanishingly small by increasing the number of accumulators beyond two. In order to address larger rates, random puncturing of a low-rate mother code is introduced. It is shown that in this case the resulting ensemble of repeat-accumulate-accumulate codes asymptotically achieves linear distance growth close to the Gilbert-Varshamov bound. This holds even for very high rate codes.
Hierarchical Bag of Paths for Kernel Based Shape Classification
Venue: arXiv cs.CV 2008
Year: 2008

Graph kernels methods are based on an implicit embedding of graphs within a vector space of large dimension. This implicit embedding allows to apply to graphs methods which where until recently solely reserved to numerical data. Within the shape classification framework, graphs are often produced by a skeletonization step which is sensitive to noise. We propose in this paper to integrate the robustness to structural noise by using a kernel based on a bag of path where each path is associated to a hierarchy encoding successive simplifications of the path. Several experiments prove the robustness and the flexibility of our approach compared to alternative shape classification methods.
Resource Allocation and Relay Selection for Collaborative Communications
Venue: arXiv cs.IT 2008
Year: 2008

We investigate the relay selection problem for a decode and forward collaborative network. Users are able to collaborate; decode messages of each other, re-encode and forward along with their own messages. We study the performance obtained from collaboration in terms of 1) increasing the achievable rate, 2) saving the transmit energy and 3) reducing the resource requirement (resource means time-bandwidth). To ensure fairness, we fix the transmit-energy-to-rate ratio among all users. We allocate resource optimally for the collaborative protocol (CP), and compare the result with the non-collaborative protocol (NCP) where users transmits their messages directly. The collaboration gain is a function of the channel gain and available energies and allows us 1) to decide to collaborate or not, 2) to select one relay among the possible relay users, and 3) to determine the involved gain and loss of possible collaboration. A considerable gain can be obtained if the direct source-destination channel gain is significantly smaller than those of alternative involved links. We demonstrate that a rate and energy improvement of up to $(1+\sqrt[η]{\frac{k}{k+1}})^η$ can be obtained, where $η$ is the environment path loss exponent and $k$ is the ratio of the rates of involved users. The gain is maximum for low transmit-energy-to-received-noise-ratio (TERN) and in a high TERN environment the NCP is preferred.
Message passing resource allocation for the uplink of multicarrier systems
Venue: arXiv cs.IT 2008
Year: 2008

We propose a novel distributed resource allocation scheme for the up-link of a cellular multi-carrier system based on the message passing (MP) algorithm. In the proposed approach each transmitter iteratively sends and receives information messages to/from the base station with the goal of achieving an optimal resource allocation strategy. The exchanged messages are the solution of small distributed allocation problems. To reduce the computational load, the MP problems at the terminals follow a dynamic programming formulation. The advantage of the proposed scheme is that it distributes the computational effort among all the transmitters in the cell and it does not require the presence of a central controller that takes all the decisions. Numerical results show that the proposed approach is an excellent solution to the resource allocation problem for cellular multi-carrier systems.
Indexability of Restless Bandit Problems and Optimality of Whittle's Index for Dynamic Multichannel Access
Venue: arXiv cs.IT 2008
Year: 2008

We consider a class of restless multi-armed bandit problems (RMBP) that arises in dynamic multichannel access, user/server scheduling, and optimal activation in multi-agent systems. For this class of RMBP, we establish the indexability and obtain Whittle's index in closed-form for both discounted and average reward criteria. These results lead to a direct implementation of Whittle's index policy with remarkably low complexity. When these Markov chains are stochastically identical, we show that Whittle's index policy is optimal under certain conditions. Furthermore, it has a semi-universal structure that obviates the need to know the Markov transition probabilities. The optimality and the semi-universal structure result from the equivalency between Whittle's index policy and the myopic policy established in this work. For non-identical channels, we develop efficient algorithms for computing a performance upper bound given by Lagrangian relaxation. The tightness of the upper bound and the near-optimal performance of Whittle's index policy are illustrated with simulation examples.
A topological chaos framework for hash functions
Venue: arXiv cs.CR 2008
Year: 2008

This paper presents a new procedure of generating hash functions which can be evaluated using some mathematical tools. This procedure is based on discrete chaotic iterations. First, it is mathematically proven, that these discrete chaotic iterations can be considered as a \linebreak particular case of topological chaos. Then, the process of generating hash function based on the \linebreak topological chaos is detailed. Finally it is shown how some tools coming from the domain of \linebreak topological chaos can be used to measure quantitatively and qualitatively some desirable properties for hash functions. An illustration example is detailed in order to show how one can create hash functions using our theoretical study. Key-words : Discrete chaotic iterations. Topological chaos. Hash function
Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves
Venue: arXiv cs.DS 2008
Year: 2008

The {\sc $k$-Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) with at least $k$ leaves in a given digraph. The problem has recently received much attention from the viewpoint of parameterized algorithms {alonLNCS4596,AlonFGKS07fsttcs,BoDo2,KnLaRo}. In this paper we step aside and take a kernelization based approach to the {\sc $k$-Leaf-Out-Branching} problem. We give the first polynomial kernel for {\sc Rooted $k$-Leaf-Out-Branching}, a variant of {\sc $k$-Leaf-Out-Branching} where the root of the tree searched for is also a part of the input. Our kernel has cubic size and is obtained using extremal combinatorics. For the {\sc $k$-Leaf-Out-Branching} problem we show that no polynomial kernel is possible unless polynomial hierarchy collapses to third level %$PH=Σ_p^3$ by applying a recent breakthrough result by Bodlaender et al. {BDFH08} in a non-trivial fashion. However our positive results for {\sc Rooted $k$-Leaf-Out-Branching} immediately imply that the seemingly intractable the {\sc $k$-Leaf-Out-Branching} problem admits a data reduction to $n$ independent $O(k^3)$ kernels. These two results, tractability and intractability side by side, are the first separating {\it many-to-one kernelization} from {\it Turing kernelization}. This answers affirmatively an open problem regarding "cheat kernelization" raised in {IWPECOPEN08}.
An Activity-Based Model for Separation of Duty
Venue: arXiv cs.CR 2008
Year: 2008

This paper offers several contributions for separation of duty (SoD) administration in role-based access control (RBAC) systems. We first introduce a new formal framework, based on business perspective, where SoD constraints are analyzed introducing the activity concept. This notion helps organizations define SoD constraints in terms of business requirements and reduces management complexity in large-scale RBAC systems. The model enables the definition of a wide taxonomy of conflict types. In particular, object-based SoD is introduced using the SoD domain concept, namely the set of data in which transaction conflicts may occur. Together with the formalization of the above properties, in this paper we also show the effectiveness of our proposal: we have applied the model to a large, existing organization; results highlight the benefits of adopting the proposed model in terms of reduced administration cost.
A Combinatorial-Probabilistic Diagnostic Entropy and Information
Venue: arXiv cs.IT 2008
Year: 2008

A new combinatorial-probabilistic diagnostic entropy has been introduced. It describes the pair-wise sum of probabilities of system conditions that have to be distinguished during the diagnosing process. The proposed measure describes the uncertainty of the system conditions, and at the same time complexity of the diagnosis problem. Treating the assumed combinatorial-diagnostic entropy as a primary notion, the information delivered by the symptoms has been defined. The relationships have been derived to facilitate explicit, quantitative assessment of the information of a single symptom as well as that of a symptoms set. It has been proved that the combinatorial-probabilistic information shows the property of additivity. The presented measures are focused on diagnosis problem, but they can be easily applied to other disciplines such as decision theory and classification.