OpenRaiser/Intern-Atlas huggingface dataset:
Bethe Free Energy Approach to LDPC Decoding on Memory Channels
Venue: arXiv cs.IT 2009
Year: 2009

We address the problem of the joint sequence detection in partial-response (PR) channels and decoding of low-density parity-check (LDPC) codes. We model the PR channel and the LDPC code as a combined inference problem. We present for the first time the derivation of the belief propagation (BP) equations that allow the simultaneous detection and decoding of a LDPC codeword in a PR channel. To accomplish this we follow an approach from statistical mechanics, in which the Bethe free energy is minimized with respect to the beliefs on the nodes of the PR-LDPC graph. The equations obtained are explicit and are optimal for decoding LDPC codes on PR channels with polynomial $h(D) = 1 - a D^n$ (a real, n positive integer) in the sense that they provide the exact inference of the marginal probabilities on the nodes in a graph free of loops. A simple algorithmic solution to the set of BP equations is proposed and evaluated using numerical simulations, yielding bit-error rate performances that surpass those of turbo equalization.
Distributed Source Coding of Correlated Gaussian Remote Sources
Venue: arXiv cs.IT 2009
Year: 2009

We consider the distributed source coding system for $L$ correlated Gaussian observations $Y_i, i=1,2, ..., L$. Let $X_i,i=1,2, ..., L$ be $L$ correlated Gaussian random variables and $N_i,$ $i=1,2,... L$ be independent additive Gaussian noises also independent of $X_i, i=1,2,..., L$. We consider the case where for each $i=1,2,..., L$, $Y_i$ is a noisy observation of $X_i$, that is, $Y_i=X_i+N_i$. On this coding system the determination problem of the rate distortion region remains open. In this paper, we derive explicit outer and inner bounds of the rate distortion region. We further find an explicit sufficient condition for those two to match. We also study the sum rate part of the rate distortion region when the correlation has some symmetrical property and derive a new lower bound of the sum rate part. We derive a sufficient condition for this lower bound to be tight. The derived sufficient condition depends only on the correlation property of the sources and their observations.
Projective Space Codes for the Injection Metric
Venue: arXiv cs.IT 2009
Year: 2009

In the context of error control in random linear network coding, it is useful to construct codes that comprise well-separated collections of subspaces of a vector space over a finite field. In this paper, the metric used is the so-called "injection distance", introduced by Silva and Kschischang. A Gilbert-Varshamov bound for such codes is derived. Using the code-construction framework of Etzion and Silberstein, new non-constant-dimension codes are constructed; these codes contain more codewords than comparable codes designed for the subspace metric.
On approximating Gaussian relay networks by deterministic networks
Venue: arXiv cs.IT 2009
Year: 2009

We examine the extent to which Gaussian relay networks can be approximated by deterministic networks, and present two results, one negative and one positive. The gap between the capacities of a Gaussian relay network and a corresponding linear deterministic network can be unbounded. The key reasons are that the linear deterministic model fails to capture the phase of received signals, and there is a loss in signal strength in the reduction to a linear deterministic network. On the positive side, Gaussian relay networks are indeed well approximated by certain discrete superposition networks, where the inputs and outputs to the channels are discrete, and channel gains are signed integers. As a corollary, MIMO channels cannot be approximated by the linear deterministic model but can be by the discrete superposition model.
Color Dipole Moments for Edge Detection
Venue: arXiv cs.CV 2009
Year: 2009

Dipole and higher moments are physical quantities used to describe a charge distribution. In analogy with electromagnetism, it is possible to define the dipole moments for a gray-scale image, according to the single aspect of a gray-tone map. In this paper we define the color dipole moments for color images. For color maps in fact, we have three aspects, the three primary colors, to consider. Associating three color charges to each pixel, color dipole moments can be easily defined and used for edge detection.
5-axis High Speed Milling Optimisation
Venue: arXiv cs.OH 2009
Year: 2009

Manufacturing of free form parts relies on the calculation of a tool path based on a CAD model, on a machining strategy and on a given numerically controlled machine tool. In order to reach the best possible performances, it is necessary to take into account a maximum of constraints during tool path calculation. For this purpose, we have developed a surface representation of the tool paths to manage 5-axis High Speed Milling, which is the most complicated case. This model allows integrating early in the step of tool path computation the machine tool geometrical constraints (axis ranges, part holder orientation), kinematical constraints (speed and acceleration on the axes, singularities) as well as gouging issues between the tool and the part. The aim of the paper is to optimize the step of 5-axis HSM tool path calculation with a bi-parameter surface representation of the tool path. We propose an example of integration of the digital process for tool path computation, ensuring the required quality and maximum productivity
On formal verification of arithmetic-based cryptographic primitives
Venue: arXiv cs.CR 2009
Year: 2009

Cryptographic primitives are fundamental for information security: they are used as basic components for cryptographic protocols or public-key cryptosystems. In many cases, their security proofs consist in showing that they are reducible to computationally hard problems. Those reductions can be subtle and tedious, and thus not easily checkable. On top of the proof assistant Coq, we had implemented in previous work a toolbox for writing and checking game-based security proofs of cryptographic primitives. In this paper we describe its extension with number-theoretic capabilities so that it is now possible to write and check arithmetic-based cryptographic primitives in our toolbox. We illustrate our work by machine checking the game-based proofs of unpredictability of the pseudo-random bit generator of Blum, Blum and Shub, and semantic security of the public-key cryptographic scheme of Goldwasser and Micali.
On the perfect matching index of bridgeless cubic graphs
Venue: arXiv cs.DM 2009
Year: 2009

If $G$ is a bridgeless cubic graph, Fulkerson conjectured that we can find 6 perfect matchings $M_1,...,M_6$ of $G$ with the property that every edge of $G$ is contained in exactly two of them and Berge conjectured that its edge set can be covered by 5 perfect matchings. We define $τ(G)$ as the least number of perfect matchings allowing to cover the edge set of a bridgeless cubic graph and we study this parameter. The set of graphs with perfect matching index 4 seems interesting and we give some informations on this class.
Estimating nonlinearities in twophase flow in porous media
Venue: arXiv cs.NA 2009
Year: 2009

In order to analyze numerically inverse problems several techniques based on linear and nonlinear stability analysis are presented. These techniques are illustrated on the problem of estimating mobilities and capillary pressure in one-dimensional two-phase displacements in porous media that are performed in laboratories. This is an example of the problem of estimating nonlinear coefficients in a system of nonlinear partial differential equations.
Online prediction of ovarian cancer
Venue: arXiv cs.AI 2009
Year: 2009

In this paper we apply computer learning methods to diagnosing ovarian cancer using the level of the standard biomarker CA125 in conjunction with information provided by mass-spectrometry. We are working with a new data set collected over a period of 7 years. Using the level of CA125 and mass-spectrometry peaks, our algorithm gives probability predictions for the disease. To estimate classification accuracy we convert probability predictions into strict predictions. Our algorithm makes fewer errors than almost any linear combination of the CA125 level and one peak's intensity (taken on the log scale). To check the power of our algorithm we use it to test the hypothesis that CA125 and the peaks do not contain useful information for the prediction of the disease at a particular time before the diagnosis. Our algorithm produces $p$-values that are better than those produced by the algorithm that has been previously applied to this data set. Our conclusion is that the proposed algorithm is more reliable for prediction on new data.
On the closed-form solution of the rotation matrix arising in computer vision problems
Venue: arXiv cs.CV 2009
Year: 2009

We show the closed-form solution to the maximization of trace(A'R), where A is given and R is unknown rotation matrix. This problem occurs in many computer vision tasks involving optimal rotation matrix estimation. The solution has been continuously reinvented in different fields as part of specific problems. We summarize the historical evolution of the problem and present the general proof of the solution. We contribute to the proof by considering the degenerate cases of A and discuss the uniqueness of R.
Fuzzy inference based mentality estimation for eye robot agent
Venue: arXiv cs.RO 2009
Year: 2009

Household robots need to communicate with human beings in a friendly fashion. To achieve better understanding of displayed information, an importance and a certainty of the information should be communicated together with the main information. The proposed intent expression system aims to convey this additional information using an eye robot. The eye motions are represented as states in a pleasure-arousal space model. Change of the model state is calculated by fuzzy inference according to the importance and certainty of the displayed information. This change influences the arousal-sleep coordinate in the space which corresponds to activeness in communication. The eye robot provides a basic interface for the mascot robot system which is an easy to understand information terminal for home environments in a humatronics society.
The Star Height Hierarchy Vs. The Variable Hierarchy
Venue: arXiv cs.LO 2009
Year: 2009

The star height hierarchy (resp. the variable hierarchy) results in classifying $μ$-terms into classes according to the nested depth of fixed point operators (resp. to the number of bound variables). We prove, under some assumptions, that the variable hierarchy is a proper refinement of the star height hierarchy. We mean that the non collapse of the variable hierarchy implies the non collapse of the star height hierarchy. The proof relies on the combinatorial characterization of the two hierarchies.
Closure Under Minors of Undirected Entanglement
Venue: arXiv cs.DM 2009
Year: 2009

Entanglement is a digraph complexity measure that origins in fixed-point theory. Its purpose is to count the nested depth of cycles in digraphs. In this paper we prove that the class of undirected graphs of entanglement at most $k$, for arbitrary fixed $k \in \mathbb{N}$, is closed under taking minors. Our proof relies on the game theoretic characterization of entanglement in terms of Robber and Cops games.
Lattice Strategies for the Dirty Multiple Access Channel
Venue: arXiv cs.IT 2009
Year: 2009

A generalization of the Gaussian dirty-paper problem to a multiple access setup is considered. There are two additive interference signals, one known to each transmitter but none to the receiver. The rates achievable using Costa's strategies (i.e. by a random binning scheme induced by Costa's auxiliary random variables) vanish in the limit when the interference signals are strong. In contrast, it is shown that lattice strategies ("lattice precoding") can achieve positive rates independent of the interferences, and in fact in some cases - which depend on the noise variance and power constraints - they are optimal. In particular, lattice strategies are optimal in the limit of high SNR. It is also shown that the gap between the achievable rate region and the capacity region is at most 0.167 bit. Thus, the dirty MAC is another instance of a network setup, like the Korner-Marton modulo-two sum problem, where linear coding is potentially better than random binning. Lattice transmission schemes and conditions for optimality for the asymmetric case, where there is only one interference which is known to one of the users (who serves as a "helper" to the other user), and for the "common interference" case are also derived. In the former case the gap between the helper achievable rate and its capacity is at most 0.085 bit.
Ergodic Layered Erasure One-Sided Interference Channels
Venue: arXiv cs.IT 2009
Year: 2009

The sum capacity of a class of layered erasure one-sided interference channels is developed under the assumption of no channel state information at the transmitters. Outer bounds are presented for this model and are shown to be tight for the following sub-classes: i) weak, ii) strong (mix of strong but not very strong (SnVS) and very strong (VS)), iii) ergodic very strong (mix of strong and weak), and (iv) a sub-class of mixed interference (mix of SnVS and weak). Each sub-class is uniquely defined by the fading statistics.
Stochastic Service Guarantee Analysis Based on Time-Domain Models
Venue: arXiv cs.NI 2009
Year: 2009

Stochastic network calculus is a theory for stochastic service guarantee analysis of computer communication networks. In the current stochastic network calculus literature, its traffic and server models are typically based on the cumulative amount of traffic and cumulative amount of service respectively. However, there are network scenarios where the applicability of such models is limited, and hence new ways of modeling traffic and service are needed to address this limitation. This paper presents time-domain models and results for stochastic network calculus. Particularly, we define traffic models, which are based on probabilistic lower-bounds on cumulative packet inter-arrival time, and server models, which are based on probabilistic upper-bounds on cumulative packet service time. In addition, examples demonstrating the use of the proposed time-domain models are provided. On the basis of the proposed models, the five basic properties of stochastic network calculus are also proved, which implies broad applicability of the proposed time-domain approach.
Joint-sparse recovery from multiple measurements
Venue: arXiv cs.IT 2009
Year: 2009

The joint-sparse recovery problem aims to recover, from sets of compressed measurements, unknown sparse matrices with nonzero entries restricted to a subset of rows. This is an extension of the single-measurement-vector (SMV) problem widely studied in compressed sensing. We analyze the recovery properties for two types of recovery algorithms. First, we show that recovery using sum-of-norm minimization cannot exceed the uniform recovery rate of sequential SMV using $\ell_1$ minimization, and that there are problems that can be solved with one approach but not with the other. Second, we analyze the performance of the ReMBo algorithm [M. Mishali and Y. Eldar, IEEE Trans. Sig. Proc., 56 (2008)] in combination with $\ell_1$ minimization, and show how recovery improves as more measurements are taken. From this analysis it follows that having more measurements than number of nonzero rows does not improve the potential theoretical recovery rate.
The Power of Depth 2 Circuits over Algebras
Venue: arXiv cs.CC 2009
Year: 2009

We study the problem of polynomial identity testing (PIT) for depth 2 arithmetic circuits over matrix algebra. We show that identity testing of depth 3 (Sigma-Pi-Sigma) arithmetic circuits over a field F is polynomial time equivalent to identity testing of depth 2 (Pi-Sigma) arithmetic circuits over U_2(F), the algebra of upper-triangular 2 x 2 matrices with entries from F. Such a connection is a bit surprising since we also show that, as computational models, Pi-Sigma circuits over U_2(F) are strictly `weaker' than Sigma-Pi-Sigma circuits over F. The equivalence further shows that PIT of depth 3 arithmetic circuits reduces to PIT of width-2 planar commutative Algebraic Branching Programs (ABP). Thus, identity testing for commutative ABPs is interesting even in the case of width-2. Further, we give a deterministic polynomial time identity testing algorithm for a Pi-Sigma circuit over any constant dimensional commutative algebra over F. While over commutative algebras of polynomial dimension, identity testing is at least as hard as that of Sigma-Pi-Sigma circuits over F.
On the Cooperation of the Constraint Domains H, R and FD in CFLP
Venue: arXiv cs.PL 2009
Year: 2009

This paper presents a computational model for the cooperation of constraint domains and an implementation for a particular case of practical importance. The computational model supports declarative programming with lazy and possibly higher-order functions, predicates, and the cooperation of different constraint domains equipped with their respective solvers, relying on a so-called Constraint Functional Logic Programming (CFLP) scheme. The implementation has been developed on top of the CFLP system TOY, supporting the cooperation of the three domains H, R and FD, which supply equality and disequality constraints over symbolic terms, arithmetic constraints over the real numbers, and finite domain constraints over the integers, respectively. The computational model has been proved sound and complete w.r.t. the declarative semantics provided by the $CFLP$ scheme, while the implemented system has been tested with a set of benchmarks and shown to behave quite efficiently in comparison to the closest related approach we are aware of. To appear in Theory and Practice of Logic Programming (TPLP)
On Binary Cyclic Codes with Five Nonzero Weights
Venue: arXiv cs.IT 2009
Year: 2009

Let $q=2^n$, $0\leq k\leq n-1$, $n/\gcd(n,k)$ be odd and $k\neq n/3, 2n/3$. In this paper the value distribution of following exponential sums \[\sum\limits_{x\in \bF_q}(-1)^{\mathrm{Tr}_1^n(αx^{2^{2k}+1}+βx^{2^k+1}+\ga x)}\quad(α,β,\ga\in \bF_{q})\] is determined. As an application, the weight distribution of the binary cyclic code $\cC$, with parity-check polynomial $h_1(x)h_2(x)h_3(x)$ where $h_1(x)$, $h_2(x)$ and $h_3(x)$ are the minimal polynomials of $π^{-1}$, $π^{-(2^k+1)}$ and $π^{-(2^{2k}+1)}$ respectively for a primitive element $π$ of $\bF_q$, is also determined.
Geodesic Paths On 3D Surfaces: Survey and Open Problems
Venue: arXiv cs.CG 2009
Year: 2009

This survey gives a brief overview of theoretically and practically relevant algorithms to compute geodesic paths and distances on three-dimensional surfaces. The survey focuses on polyhedral three-dimensional surfaces.
On Counteracting Byzantine Attacks in Network Coded Peer-to-Peer Networks
Venue: arXiv cs.NI 2009
Year: 2009

Random linear network coding can be used in peer-to-peer networks to increase the efficiency of content distribution and distributed storage. However, these systems are particularly susceptible to Byzantine attacks. We quantify the impact of Byzantine attacks on the coded system by evaluating the probability that a receiver node fails to correctly recover a file. We show that even for a small probability of attack, the system fails with overwhelming probability. We then propose a novel signature scheme that allows packet-level Byzantine detection. This scheme allows one-hop containment of the contamination, and saves bandwidth by allowing nodes to detect and drop the contaminated packets. We compare the net cost of our signature scheme with various other Byzantine schemes, and show that when the probability of Byzantine attacks is high, our scheme is the most bandwidth efficient.
A Non-Holonomic Systems Approach to Special Function Identities
Venue: arXiv cs.SC 2009
Year: 2009

We extend Zeilberger's approach to special function identities to cases that are not holonomic. The method of creative telescoping is thus applied to definite sums or integrals involving Stirling or Bernoulli numbers, incomplete Gamma function or polylogarithms, which are not covered by the holonomic framework. The basic idea is to take into account the dimension of appropriate ideals in Ore algebras. This unifies several earlier extensions and provides algorithms for summation and integration in classes that had not been accessible to computer algebra before.
On FO2 quantifier alternation over words
Venue: arXiv cs.LO 2009
Year: 2009

We show that each level of the quantifier alternation hierarchy within FO^2[<] -- the 2-variable fragment of the first order logic of order on words -- is a variety of languages. We then use the notion of condensed rankers, a refinement of the rankers defined by Weis and Immerman, to produce a decidable hierarchy of varieties which is interwoven with the quantifier alternation hierarchy -- and conjecturally equal to it. It follows that the latter hierarchy is decidable within one unit: given a formula alpha in FO^2[<], one can effectively compute an integer m such that alpha is equivalent to a formula with at most m+1 alternating blocks of quantifiers, but not to a formula with only m-1 blocks. This is a much more precise result than what is known about the quantifier alternation hierarchy within FO[<], where no decidability result is known beyond the very first levels.
Using Dissortative Mating Genetic Algorithms to Track the Extrema of Dynamic Deceptive Functions
Venue: arXiv cs.NE 2009
Year: 2009

Traditional Genetic Algorithms (GAs) mating schemes select individuals for crossover independently of their genotypic or phenotypic similarities. In Nature, this behaviour is known as random mating. However, non-random schemes - in which individuals mate according to their kinship or likeness - are more common in natural systems. Previous studies indicate that, when applied to GAs, negative assortative mating (a specific type of non-random mating, also known as dissortative mating) may improve their performance (on both speed and reliability) in a wide range of problems. Dissortative mating maintains the genetic diversity at a higher level during the run, and that fact is frequently observed as an explanation for dissortative GAs ability to escape local optima traps. Dynamic problems, due to their specificities, demand special care when tuning a GA, because diversity plays an even more crucial role than it does when tackling static ones. This paper investigates the behaviour of dissortative mating GAs, namely the recently proposed Adaptive Dissortative Mating GA (ADMGA), on dynamic trap functions. ADMGA selects parents according to their Hamming distance, via a self-adjustable threshold value. The method, by keeping population diversity during the run, provides an effective means to deal with dynamic problems. Tests conducted with deceptive and nearly deceptive trap functions indicate that ADMGA is able to outperform other GAs, some specifically designed for tracking moving extrema, on a wide range of tests, being particularly effective when speed of change is not very fast. When comparing the algorithm to a previously proposed dissortative GA, results show that performance is equivalent on the majority of the experiments, but ADMGA performs better when solving the hardest instances of the test set.