OpenRaiser/Intern-Atlas huggingface dataset:
On the Capacity and Mutual Information of Memoryless Noncoherent Rayleigh-Fading Channels
Venue: arXiv cs.IT 2006
Year: 2006

The memoryless noncoherent single-input single-output (SISO) Rayleigh-fading channel is considered. Closed-form expressions for the mutual information between the output and the input of this channel when the input magnitude distribution is discrete and restricted to having two mass points are derived, and it is subsequently shown how these expressions can be used to obtain closed-form expressions for the capacity of this channel for signal to noise ratio (SNR) values of up to approximately 0 dB, and a tight capacity lower bound for SNR values between 0 dB and 10 dB. The expressions for the channel capacity and its lower bound are given as functions of a parameter which can be obtained via numerical root-finding algorithms.
The Capacity of the Single Source Multiple Relay Single Destination Mesh Network
Venue: arXiv cs.IT 2006
Year: 2006

In this paper, we derive the capacity of a special class of mesh networks. A mesh network is defined as a heterogeneous wireless network in which the transmission among power limited nodes is assisted by powerful relays, which use the same wireless medium. We find the capacity of the mesh network when there is one source, one destination, and multiple relays. We call this channel the single source multiple relay single destination (SSMRSD) mesh network. Our approach is as follows. We first look at an upper bound on the information theoretic capacity of these networks in the Gaussian setting. We then show that the bound is achievable asymptotically using the compress-forward strategy for the multiple relay channel. Theoretically, the results indicate the value of cooperation and the utility of carefully deployed relays in wireless ad-hoc and sensor networks. The capacity characterization quantifies how the relays can be used to either conserve node energy or to increase transmission rate.
Energy Efficiency in Multi-hop CDMA Networks: A Game Theoretic Analysis
Venue: arXiv cs.IT 2006
Year: 2006

A game-theoretic analysis is used to study the effects of receiver choice on the energy efficiency of multi-hop networks in which the nodes communicate using Direct-Sequence Code Division Multiple Access (DS-CDMA). A Nash equilibrium of the game in which the network nodes can choose their receivers as well as their transmit powers to maximize the total number of bits they transmit per unit of energy is derived. The energy efficiencies resulting from the use of different linear multiuser receivers in this context are compared, looking at both the non-cooperative game and the Pareto optimal solution. For analytical ease, particular attention is paid to asymptotically large networks. Significant gains in energy efficiency are observed when multiuser receivers, particularly the linear minimum mean-square error (MMSE) receiver, are used instead of conventional matched filter receivers.
Modeling the Dynamics of Social Networks
Venue: arXiv cs.CY 2006
Year: 2006

Modeling human dynamics responsible for the formation and evolution of the so-called social networks - structures comprised of individuals or organizations and indicating connectivities existing in a community - is a topic recently attracting a significant research interest. It has been claimed that these dynamics are scale-free in many practically important cases, such as impersonal and personal communication, auctioning in a market, accessing sites on the WWW, etc., and that human response times thus conform to the power law. While a certain amount of progress has recently been achieved in predicting the general response rate of a human population, existing formal theories of human behavior can hardly be found satisfactory to accommodate and comprehensively explain the scaling observed in social networks. In the presented study, a novel system-theoretic modeling approach is proposed and successfully applied to determine important characteristics of a communication network and to analyze consumer behavior on the WWW.
Stable partitions in coalitional games
Venue: arXiv cs.GT 2006
Year: 2006

We propose a notion of a stable partition in a coalitional game that is parametrized by the concept of a defection function. This function assigns to each partition of the grand coalition a set of different coalition arrangements for a group of defecting players. The alternatives are compared using their social welfare. We characterize the stability of a partition for a number of most natural defection functions and investigate whether and how so defined stable partitions can be reached from any initial partition by means of simple transformations. The approach is illustrated by analyzing an example in which a set of stores seeks an optimal transportation arrangement.
Efficient Route Tracing from a Single Source
Venue: arXiv cs.NI 2006
Year: 2006

Traceroute is a networking tool that allows one to discover the path that packets take from a source machine, through the network, to a destination machine. It is widely used as an engineering tool, and also as a scientific tool, such as for discovery of the network topology at the IP level. In prior work, authors on this technical report have shown how to improve the efficiency of route tracing from multiple cooperating monitors. However, it is not unusual for a route tracing monitor to operate in isolation. Somewhat different strategies are required for this case, and this report is the first systematic study of those requirements. Standard traceroute is inefficient when used repeatedly towards multiple destinations, as it repeatedly probes the same interfaces close to the source. Others have recognized this inefficiency and have proposed tracing backwards from the destinations and stopping probing upon encounter with a previously-seen interface. One of this technical report's contributions is to quantify for the first time the efficiency of this approach. Another contribution is to describe the effect of non-responding destinations on this efficiency. Since a large portion of destination machines do not reply to probe packets, backwards probing from the destination is often infeasible. We propose an algorithm to tackle non-responding destinations, and we find that our algorithm can strongly decrease probing redundancy at the cost of a small reduction in node and link discovery.
Synthèse Comportementale Sous Contraintes de Communication et de Placement Mémoire pour les composants du TDSI
Venue: arXiv cs.AR 2006
Year: 2006

The design of complex Digital Signal Processing systems implies to minimize architectural cost and to maximize timing performances while taking into account communication and memory accesses constraints for the integration of dedicated hardware accelerator. Unfortunately, the traditional Matlab/ Simulink design flows gather not very flexible hardware blocs. In this paper, we present a methodology and a tool that permit the High-Level Synthesis of DSP applications, under both I/O timing and memory constraints. Based on formal models and a generic architecture, our tool GAUT helps the designer in finding a reasonable trade-off between the circuit's performance and its architectural complexity. The efficiency of our approach is demonstrated on the case study of a FFT algorithm.
Utilisation de la linguistique en reconnaissance de la parole : un état de l'art
Venue: arXiv cs.HC 2006
Year: 2006

To transcribe speech, automatic speech recognition systems use statistical methods, particularly hidden Markov model and N-gram models. Although these techniques perform well and lead to efficient systems, they approach their maximum possibilities. It seems thus necessary, in order to outperform current results, to use additional information, especially bound to language. However, introducing such knowledge must be realized taking into account specificities of spoken language (hesitations for example) and being robust to possible misrecognized words. This document presents a state of the art of these researches, evaluating the impact of the insertion of linguistic information on the quality of the transcription.
Explicit Randomness is not Necessary when Modeling Probabilistic Encryption
Venue: arXiv cs.CR 2006
Year: 2006

Although good encryption functions are probabilistic, most symbolic models do not capture this aspect explicitly. A typical solution, recently used to prove the soundness of such models with respect to computational ones, is to explicitly represent the dependency of ciphertexts on random coins as labels. In order to make these label-based models useful, it seems natural to try to extend the underlying decision procedures and the implementation of existing tools. In this paper we put forth a more practical alternative based on the following soundness theorem. We prove that for a large class of security properties (that includes rather standard formulations for secrecy and authenticity properties), security of protocols in the simpler model implies security in the label-based model. Combined with the soundness result of (\textbf{?}) our theorem enables the translation of security results in unlabeled symbolic models to computational security.
Minimum Pseudo-Weight and Minimum Pseudo-Codewords of LDPC Codes
Venue: arXiv cs.IT 2006
Year: 2006

In this correspondence, we study the minimum pseudo-weight and minimum pseudo-codewords of low-density parity-check (LDPC) codes under linear programming (LP) decoding. First, we show that the lower bound of Kelly, Sridhara, Xu and Rosenthal on the pseudo-weight of a pseudo-codeword of an LDPC code with girth greater than 4 is tight if and only if this pseudo-codeword is a real multiple of a codeword. Then, we show that the lower bound of Kashyap and Vardy on the stopping distance of an LDPC code is also a lower bound on the pseudo-weight of a pseudo-codeword of this LDPC code with girth 4, and this lower bound is tight if and only if this pseudo-codeword is a real multiple of a codeword. Using these results we further show that for some LDPC codes, there are no other minimum pseudo-codewords except the real multiples of minimum codewords. This means that the LP decoding for these LDPC codes is asymptotically optimal in the sense that the ratio of the probabilities of decoding errors of LP decoding and maximum-likelihood decoding approaches to 1 as the signal-to-noise ratio leads to infinity. Finally, some LDPC codes are listed to illustrate these results.
Topology for Distributed Inference on Graphs
Venue: arXiv cs.IT 2006
Year: 2006

Let $N$ local decision makers in a sensor network communicate with their neighbors to reach a decision \emph{consensus}. Communication is local, among neighboring sensors only, through noiseless or noisy links. We study the design of the network topology that optimizes the rate of convergence of the iterative decision consensus algorithm. We reformulate the topology design problem as a spectral graph design problem, namely, maximizing the eigenratio~$γ$ of two eigenvalues of the graph Laplacian~$L$, a matrix that is naturally associated with the interconnectivity pattern of the network. This reformulation avoids costly Monte Carlo simulations and leads to the class of non-bipartite Ramanujan graphs for which we find a lower bound on~$γ$. For Ramanujan topologies and noiseless links, the local probability of error converges much faster to the overall global probability of error than for structured graphs, random graphs, or graphs exhibiting small-world characteristics. With noisy links, we determine the optimal number of iterations before calling a decision. Finally, we introduce a new class of random graphs that are easy to construct, can be designed with arbitrary number of sensors, and whose spectral and convergence properties make them practically equivalent to Ramanujan topologies.
Simple Methods For Drawing Rational Surfaces as Four or Six Bezier Patches
Venue: arXiv cs.CG 2006
Year: 2006

In this paper, we give several simple methods for drawing a whole rational surface (without base points) as several Bezier patches. The first two methods apply to surfaces specified by triangular control nets and partition the real projective plane RP2 into four and six triangles respectively. The third method applies to surfaces specified by rectangular control nets and partitions the torus RP1 X RP1 into four rectangular regions. In all cases, the new control nets are obtained by sign flipping and permutation of indices from the original control net. The proofs that these formulae are correct involve very little computations and instead exploit the geometry of the parameter space (RP2 or RP1 X RP1). We illustrate our method on some classical examples. We also propose a new method for resolving base points using a simple ``blowing up'' technique involving the computation of ``resolved'' control nets.
Inference and Evaluation of the Multinomial Mixture Model for Text Clustering
Venue: arXiv cs.IR 2006
Year: 2006

In this article, we investigate the use of a probabilistic model for unsupervised clustering in text collections. Unsupervised clustering has become a basic module for many intelligent text processing applications, such as information retrieval, text classification or information extraction. The model considered in this contribution consists of a mixture of multinomial distributions over the word counts, each component corresponding to a different theme. We present and contrast various estimation procedures, which apply both in supervised and unsupervised contexts. In supervised learning, this work suggests a criterion for evaluating the posterior odds of new documents which is more statistically sound than the "naive Bayes" approach. In an unsupervised context, we propose measures to set up a systematic evaluation framework and start with examining the Expectation-Maximization (EM) algorithm as the basic tool for inference. We discuss the importance of initialization and the influence of other features such as the smoothing strategy or the size of the vocabulary, thereby illustrating the difficulties incurred by the high dimensionality of the parameter space. We also propose a heuristic algorithm based on iterative EM with vocabulary reduction to solve this problem. Using the fact that the latent variables can be analytically integrated out, we finally show that Gibbs sampling algorithm is tractable and compares favorably to the basic expectation maximization approach.
Comparison of the estimation of the degree of polarization from four or two intensity images degraded by speckle noise
Venue: arXiv cs.IR 2006
Year: 2006

Active polarimetric imagery is a powerful tool for accessing the information present in a scene. Indeed, the polarimetric images obtained can reveal polarizing properties of the objects that are not avalaible using conventional imaging systems. However, when coherent light is used to illuminate the scene, the images are degraded by speckle noise. The polarization properties of a scene are characterized by the degree of polarization. In standard polarimetric imagery system, four intensity images are needed to estimate this degree . If we assume the uncorrelation of the measurements, this number can be decreased to two images using the Orthogonal State Contrast Image (OSCI). However, this approach appears too restrictive in some cases. We thus propose in this paper a new statistical parametric method to estimate the degree of polarization assuming correlated measurements with only two intensity images. The estimators obtained from four images, from the OSCI and from the proposed method, are compared using simulated polarimetric data degraded by speckle noise.
New Millennium AI and the Convergence of History
Venue: arXiv cs.AI 2006
Year: 2006

Artificial Intelligence (AI) has recently become a real formal science: the new millennium brought the first mathematically sound, asymptotically optimal, universal problem solvers, providing a new, rigorous foundation for the previously largely heuristic field of General AI and embedded agents. At the same time there has been rapid progress in practical methods for learning true sequence-processing programs, as opposed to traditional methods limited to stationary pattern association. Here we will briefly review some of the new results, and speculate about future developments, pointing out that the time intervals between the most notable events in over 40,000 years or 2^9 lifetimes of human history have sped up exponentially, apparently converging to zero within the next few decades. Or is this impression just a by-product of the way humans allocate memory space to past events?
Outlier Robust ICP for Minimizing Fractional RMSD
Venue: arXiv cs.GR 2006
Year: 2006

We describe a variation of the iterative closest point (ICP) algorithm for aligning two point sets under a set of transformations. Our algorithm is superior to previous algorithms because (1) in determining the optimal alignment, it identifies and discards likely outliers in a statistically robust manner, and (2) it is guaranteed to converge to a locally optimal solution. To this end, we formalize a new distance measure, fractional root mean squared distance (frmsd), which incorporates the fraction of inliers into the distance function. We lay out a specific implementation, but our framework can easily incorporate most techniques and heuristics from modern registration algorithms. We experimentally validate our algorithm against previous techniques on 2 and 3 dimensional data exposed to a variety of outlier types.
Performance comparison of multi-user detectors for the downlink of a broadband MC-CDMA system
Venue: arXiv cs.IT 2006
Year: 2006

In this paper multi-user detection techniques, such as Parallel and Serial Interference Cancellations (PIC & SIC), General Minimum Mean Square Error (GMMSE) and polynomial MMSE, for the downlink of a broadband Multi-Carrier Code Division Multiple Access (MCCDMA) system are investigated. The Bit Error Rate (BER) and Frame Error Rate (FER) results are evaluated, and compared with single-user detection (MMSEC, EGC) approaches, as well. The performance evaluation takes into account the system load, channel coding and modulation schemes.
A Novel Application of Lifting Scheme for Multiresolution Correlation of Complex Radar Signals
Venue: arXiv cs.DC 2006
Year: 2006

The lifting scheme of discrete wavelet transform (DWT) is now quite well established as an efficient technique for image compression, and has been incorporated into the JPEG2000 standards. However, the potential of the lifting scheme has not been exploited in the context of correlationbased processing, such as encountered in radar applications. This paper presents a complete and consistent framework for the application of DWT for correlation of complex signals. In particular, lifting scheme factorization of biorthogonal filterbanks is carried out in dual analysis basis spaces for multiresolution correlation of complex radar signals in the DWT domain only. A causal formulation of lifting for orthogonal filterbank is also developed. The resulting parallel algorithms and consequent saving of computational effort are briefly dealt with.
Modelling the Probability Density of Markov Sources
Venue: arXiv cs.NE 2006
Year: 2006

This paper introduces an objective function that seeks to minimise the average total number of bits required to encode the joint state of all of the layers of a Markov source. This type of encoder may be applied to the problem of optimising the bottom-up (recognition model) and top-down (generative model) connections in a multilayer neural network, and it unifies several previous results on the optimisation of multilayer neural networks.
Iterative Decoding Performance Bounds for LDPC Codes on Noisy Channels
Venue: arXiv cs.IT 2006
Year: 2006

The asymptotic iterative decoding performances of low-density parity-check (LDPC) codes using min-sum (MS) and sum-product (SP) decoding algorithms on memoryless binary-input output-symmetric (MBIOS) channels are analyzed in this paper. For MS decoding, the analysis is done by upper bounding the bit error probability of the root bit of a tree code by the sequence error probability of a subcode of the tree code assuming the transmission of the all-zero codeword. The result is a recursive upper bound on the bit error probability after each iteration. For SP decoding, we derive a recursively determined lower bound on the bit error probability after each iteration. This recursive lower bound recovers the density evolution equation of LDPC codes on the binary erasure channel (BEC) with inequalities satisfied with equalities. A significant implication of this result is that the performance of LDPC codes under SP decoding on the BEC is an upper bound of the performance on all MBIOS channels with the same uncoded bit error probability. All results hold for the more general multi-edge type LDPC codes.
A distributed approximation algorithm for the minimum degree minimum weight spanning trees
Venue: arXiv cs.DC 2006
Year: 2006

Fischer has shown how to compute a minimum weight spanning tree of degree at most $b Δ^* + \lceil \log\_b n\rceil$ in time $O(n^{4 + 1/\ln b})$ for any constant $b > 1$, where $Δ^*$ is the value of an optimal solution and $n$ is the number of nodes in the network. In this paper, we propose a distributed version of Fischer's algorithm that requires messages and time complexity $O(n^{2 + 1/\ln b})$, and O(n) space per node.
Asymptotic Analysis of a Leader Election Algorithm
Venue: arXiv cs.DC 2006
Year: 2006

Itai and Rodeh showed that, on the average, the communication of a leader election algorithm takes no more than $LN$ bits, where $L \simeq 2.441716$ and $N$ denotes the size of the ring. We give a precise asymptotic analysis of the average number of rounds M(n) required by the algorithm, proving for example that $\dis M(\infty) := \lim\_{n\to \infty} M(n) = 2.441715879...$, where $n$ is the number of starting candidates in the election. Accurate asymptotic expressions of the second moment $M^{(2)}(n)$ of the discrete random variable at hand, its probability distribution, and the generalization to all moments are given. Corresponding asymptotic expansions $(n\to \infty)$ are provided for sufficiently large $j$, where $j$ counts the number of rounds. Our numerical results show that all computations perfectly fit the observed values. Finally, we investigate the generalization to probability $t/n$, where $t$ is a non negative real parameter. The real function $\dis M(\infty,t) := \lim\_{n\to \infty} M(n,t)$ is shown to admit \textit{one unique minimum} $M(\infty,t^{*})$ on the real segment $(0,2)$. Furthermore, the variations of $M(\infty,t)$ on thewhole real line are also studied in detail.
Resettable Zero Knowledge in the Bare Public-Key Model under Standard Assumption
Venue: arXiv cs.CR 2006
Year: 2006

In this paper we resolve an open problem regarding resettable zero knowledge in the bare public-key (BPK for short) model: Does there exist constant round resettable zero knowledge argument with concurrent soundness for $\mathcal{NP}$ in BPK model without assuming \emph{sub-exponential hardness}? We give a positive answer to this question by presenting such a protocol for any language in $\mathcal{NP}$ in the bare public-key model assuming only collision-resistant hash functions against \emph{polynomial-time} adversaries.