OpenRaiser/Intern-Atlas huggingface dataset:
Performance Analysis of Algebraic Soft Decoding of Reed-Solomon Codes over Binary Symmetric and Erasure Channels
Venue: arXiv cs.IT 2005
Year: 2005

In this paper, we characterize the decoding region of algebraic soft decoding (ASD) of Reed-Solomon (RS) codes over erasure channels and binary symmetric channel (BSC). Optimal multiplicity assignment strategies (MAS) are investigated and tight bounds are derived to show the ASD can significantly outperform conventional Berlekamp Massey (BM) decoding over these channels for a wide code rate range. The analysis technique can also be extended to other channel models, e.g., RS coded modulation over erasure channels.
On the NP-Completeness of Some Graph Cluster Measures
Venue: arXiv cs.CC 2005
Year: 2005

Graph clustering is the problem of identifying sparsely connected dense subgraphs (clusters) in a given graph. Proposed clustering algorithms usually optimize various fitness functions that measure the quality of a cluster within the graph. Examples of such cluster measures include the conductance, the local and relative densities, and single cluster editing. We prove that the decision problems associated with the optimization tasks of finding the clusters that are optimal with respect to these fitness measures are NP-complete.
The Three Node Wireless Network: Achievable Rates and Cooperation Strategies
Venue: arXiv cs.IT 2005
Year: 2005

We consider a wireless network composed of three nodes and limited by the half-duplex and total power constraints. This formulation encompasses many of the special cases studied in the literature and allows for capturing the common features shared by them. Here, we focus on three special cases, namely 1) Relay Channel, 2) Multicast Channel, and 3) Conference Channel. These special cases are judicially chosen to reflect varying degrees of complexity while highlighting the common ground shared by the different variants of the three node wireless network. For the relay channel, we propose a new cooperation scheme that exploits the wireless feedback gain. This scheme combines the benefits of decode-and-forward and compress-and-forward strategies and avoids the idealistic feedback assumption adopted in earlier works. Our analysis of the achievable rate of this scheme reveals the diminishing feedback gain at both the low and high signal-to-noise ratio regimes. Inspired by the proposed feedback strategy, we identify a greedy cooperation framework applicable to both the multicast and conference channels. Our performance analysis reveals several nice properties of the proposed greedy approach and the central role of cooperative source-channel coding in exploiting the receiver side information in the wireless network setting. Our proofs for the cooperative multicast with side-information rely on novel nested and independent binning encoders along with a list decoder.
Minimizing makespan in flowshop with time lags
Venue: arXiv cs.DM 2005
Year: 2005

We consider the problem of minimizing the makespan in a flowshop involving maximal and minimal time lags. Time lag constraints generalize the classical precedence constraints between operations. We assume that such constraints are only defined between operations of the same job. We propose a solution method and present several extensions.
Optimal and Suboptimal Detection of Gaussian Signals in Noise: Asymptotic Relative Efficiency
Venue: arXiv cs.IT 2005
Year: 2005

The performance of Bayesian detection of Gaussian signals using noisy observations is investigated via the error exponent for the average error probability. Under unknown signal correlation structure or limited processing capability it is reasonable to use the simple quadratic detector that is optimal in the case of an independent and identically distributed (i.i.d.) signal. Using the large deviations principle, the performance of this detector (which is suboptimal for non-i.i.d. signals) is compared with that of the optimal detector for correlated signals via the asymptotic relative efficiency defined as the ratio between sample sizes of two detectors required for the same performance in the large-sample-size regime. The effects of SNR on the ARE are investigated. It is shown that the asymptotic efficiency of the simple quadratic detector relative to the optimal detector converges to one as the SNR increases without bound for any bounded spectrum, and that the simple quadratic detector performs as well as the optimal detector for a wide range of the correlation values at high SNR.
On Hilberg's Law and Its Links with Guiraud's Law
Venue: arXiv cs.CL 2005
Year: 2005

Hilberg (1990) supposed that finite-order excess entropy of a random human text is proportional to the square root of the text length. Assuming that Hilberg's hypothesis is true, we derive Guiraud's law, which states that the number of word types in a text is greater than proportional to the square root of the text length. Our derivation is based on some mathematical conjecture in coding theory and on several experiments suggesting that words can be defined approximately as the nonterminals of the shortest context-free grammar for the text. Such operational definition of words can be applied even to texts deprived of spaces, which do not allow for Mandelbrot's ``intermittent silence'' explanation of Zipf's and Guiraud's laws. In contrast to Mandelbrot's, our model assumes some probabilistic long-memory effects in human narration and might be capable of explaining Menzerath's law.
Introduction to Quantum Message Space
Venue: arXiv cs.IT 2005
Year: 2005

This paper develops the quantum analog of the message ensemble of classical information theory as developed by Shannon and Khinchin. The principal mathematical tool is harmonic analysis on the free group with two generators.
Papillon: Greedy Routing in Rings
Venue: arXiv cs.DC 2005
Year: 2005

We study {\sc greedy} routing over $n$ nodes placed in a ring, with the \emph{distance} between two nodes defined to be the clockwise or the absolute distance between them along the ring. Such graphs arise in the context of modeling social networks and in routing networks for peer-to-peer systems. We construct the first network over $n$ nodes in which {\sc greedy} routing takes $O(\log n / \log d)$ hops in the worst-case, with $d$ out-going links per node. Our result has the first asymptotically optimal greedy routing complexity. Previous constructions required $O(\frac{\log^2 n}{d})$ hops.
Improved Inference for Checking Annotations
Venue: arXiv cs.PL 2005
Year: 2005

We consider type inference in the Hindley/Milner system extended with type annotations and constraints with a particular focus on Haskell-style type classes. We observe that standard inference algorithms are incomplete in the presence of nested type annotations. To improve the situation we introduce a novel inference scheme for checking type annotations. Our inference scheme is also incomplete in general but improves over existing implementations as found e.g. in the Glasgow Haskell Compiler (GHC). For certain cases (e.g. Haskell 98) our inference scheme is complete. Our approach has been fully implemented as part of the Chameleon system (experimental version of Haskell).
Revisiting Internet AS-level Topology Discovery
Venue: arXiv cs.NI 2005
Year: 2005

The development of veracious models of the Internet topology has received a lot of attention in the last few years. Many proposed models are based on topologies derived from RouteViews BGP table dumps (BTDs). However, BTDs do not capture all AS-links of the Internet topology and most importantly the number of the hidden AS-links is unknown, resulting in AS-graphs of questionable quality. As a first step to address this problem, we introduce a new AS-topology discovery methodology that results in more complete and accurate graphs. Moreover, we use data available from existing measurement facilities, circumventing the burden of additional measurement infrastructure. We deploy our methodology and construct an AS-topology that has at least 61.5% more AS-links than BTD-derived AS-topologies we examined. Finally, we analyze the temporal and topological properties of the augmented graph and pinpoint the differences from BTD-derived AS-topologies.
Redundancy in Logic III: Non-Mononotonic Reasoning
Venue: arXiv cs.LO 2005
Year: 2005

Results about the redundancy of circumscriptive and default theories are presented. In particular, the complexity of establishing whether a given theory is redundant is establihsed.
Explorations in engagement for humans and robots
Venue: arXiv cs.AI 2005
Year: 2005

This paper explores the concept of engagement, the process by which individuals in an interaction start, maintain and end their perceived connection to one another. The paper reports on one aspect of engagement among human interactors--the effect of tracking faces during an interaction. It also describes the architecture of a robot that can participate in conversational, collaborative interactions with engagement gestures. Finally, the paper reports on findings of experiments with human participants who interacted with a robot when it either performed or did not perform engagement gestures. Results of the human-robot studies indicate that people become engaged with robots: they direct their attention to the robot more often in interactions where engagement gestures are present, and they find interactions more appropriate when engagement gestures are present than when they are not.
The Entropy of a Binary Hidden Markov Process
Venue: arXiv cs.IT 2005
Year: 2005

The entropy of a binary symmetric Hidden Markov Process is calculated as an expansion in the noise parameter epsilon. We map the problem onto a one-dimensional Ising model in a large field of random signs and calculate the expansion coefficients up to second order in epsilon. Using a conjecture we extend the calculation to 11th order and discuss the convergence of the resulting series.
Software Architecture Overview
Venue: arXiv cs.SE 2005
Year: 2005

What is Software Architecture? The rules, paradigmen, pattern that help to construct, build and test a serious piece of software. It is the practical experience boiled down to abstract level. Software Architecture builds on System Engineering and the scientific method as established by Galileo Galilei: Measure what you can and make measureable what you can not. The experiment (test) is more important then the deduction. Pieces of information about software architecture are all over the internet. This paper uses citation as much as possible. The aim is to bring together an overview, not to rephrase the wording.
n-Channel Asymmetric Multiple-Description Lattice Vector Quantization
Venue: arXiv cs.IT 2005
Year: 2005

We present analytical expressions for optimal entropy-constrained multiple-description lattice vector quantizers which, under high-resolutions assumptions, minimize the expected distortion for given packet-loss probabilities. We consider the asymmetric case where packet-loss probabilities and side entropies are allowed to be unequal and find optimal quantizers for any number of descriptions in any dimension. We show that the normalized second moments of the side-quantizers are given by that of an $L$-dimensional sphere independent of the choice of lattices. Furthermore, we show that the optimal bit-distribution among the descriptions is not unique. In fact, within certain limits, bits can be arbitrarily distributed.
The Benefit of Thresholding in LP Decoding of LDPC Codes
Venue: arXiv cs.IT 2005
Year: 2005

Consider data transmission over a binary-input additive white Gaussian noise channel using a binary low-density parity-check code. We ask the following question: Given a decoder that takes log-likelihood ratios as input, does it help to modify the log-likelihood ratios before decoding? If we use an optimal decoder then it is clear that modifying the log-likelihoods cannot possibly help the decoder's performance, and so the answer is "no." However, for a suboptimal decoder like the linear programming decoder, the answer might be "yes": In this paper we prove that for certain interesting classes of low-density parity-check codes and large enough SNRs, it is advantageous to truncate the log-likelihood ratios before passing them to the linear programming decoder.
Chosen-ciphertext attack on noncommutative Polly Cracker
Venue: arXiv cs.IT 2005
Year: 2005

We propose a chosen-ciphertext attack on recently presented noncommutative variant of the well-known Polly Cracker cryptosystem. We show that if one chooses parameters for this noncommutative Polly Cracker as initially proposed, than the system should be claimed as insecure.
Enhancing Content-And-Structure Information Retrieval using a Native XML Database
Venue: arXiv cs.IR 2005
Year: 2005

Three approaches to content-and-structure XML retrieval are analysed in this paper: first by using Zettair, a full-text information retrieval system; second by using eXist, a native XML database, and third by using a hybrid XML retrieval system that uses eXist to produce the final answers from likely relevant articles retrieved by Zettair. INEX 2003 content-and-structure topics can be classified in two categories: the first retrieving full articles as final answers, and the second retrieving more specific elements within articles as final answers. We show that for both topic categories our initial hybrid system improves the retrieval effectiveness of a native XML database. For ranking the final answer elements, we propose and evaluate a novel retrieval model that utilises the structural relationships between the answer elements of a native XML database and retrieves Coherent Retrieval Elements. The final results of our experiments show that when the XML retrieval task focusses on highly relevant elements our hybrid XML retrieval system with the Coherent Retrieval Elements module is 1.8 times more effective than Zettair and 3 times more effective than eXist, and yields an effective content-and-structure XML retrieval.
Capacity Theorems for Quantum Multiple Access Channels
Venue: arXiv cs.IT 2005
Year: 2005

We consider quantum channels with two senders and one receiver. For an arbitrary such channel, we give multi-letter characterizations of two different two-dimensional capacity regions. The first region characterizes the rates at which it is possible for one sender to send classical information while the other sends quantum information. The second region gives the rates at which each sender can send quantum information. We give an example of a channel for which each region has a single-letter description, concluding with a characterization of the rates at which each user can simultaneously send classical and quantum information.
An Operational Foundation for Delimited Continuations in the CPS Hierarchy
Venue: arXiv cs.LO 2005
Year: 2005

We present an abstract machine and a reduction semantics for the lambda-calculus extended with control operators that give access to delimited continuations in the CPS hierarchy. The abstract machine is derived from an evaluator in continuation-passing style (CPS); the reduction semantics (i.e., a small-step operational semantics with an explicit representation of evaluation contexts) is constructed from the abstract machine; and the control operators are the shift and reset family. We also present new applications of delimited continuations in the CPS hierarchy: finding list prefixes and normalization by evaluation for a hierarchical language of units and products.
Duality between channel capacity and rate distortion with two-sided state information
Venue: arXiv cs.IT 2005
Year: 2005

We show that the duality between channel capacity and data compression is retained when state information is available to the sender, to the receiver, to both, or to neither. We present a unified theory for eight special cases of channel capacity and rate distortion with state information, which also extends existing results to arbitrary pairs of independent and identically distributed (i.i.d.) correlated state information available at the sender and at the receiver, respectively. In particular, the resulting general formula for channel capacity assumes the same form as the generalized Wyner Ziv rate distortion function.
DNA Codes that Avoid Secondary Structures
Venue: arXiv cs.DM 2005
Year: 2005

In this paper, we consider the problem of designing DNA sequences (codewords) for DNA storage systems and DNA computing that are unlikely to fold back onto themselves to form undesirable secondary structures. The paper addresses both the issue of enumerating the sequences with such properties and the problem of practical code construction.
Representing Digital Assets using MPEG-21 Digital Item Declaration
Venue: arXiv cs.DL 2005
Year: 2005

Various XML-based approaches aimed at representing compound digital assets have emerged over the last several years. Approaches that are of specific relevance to the digital library community include the Metadata Encoding and Transmission Standard (METS), the IMS Content Packaging XML Binding, and the XML Formatted Data Units (XFDU) developed by CCSDS Panel 2. The MPEG-21 Digital Item Declaration (MPEG-21 DID) is another standard specifying the representation of digital assets in XML that, so far, has received little attention in the digital library community. This article gives a brief insight into the MPEG-21 standardization effort, highlights the major characteristics of the MPEG-21 DID Abstract Model, and describes the MPEG-21 Digital Item Declaration Language (MPEG-21 DIDL), an XML syntax for the representation of digital assets based on the MPEG-21 DID Abstract Model. Also, it briefly demonstrates the potential relevance of MPEG-21 DID to the digital library community by describing its use in the aDORe repository environment at the Research Library of the Los Alamos National Laboratory (LANL) for the representation of digital assets.
Can Small Museums Develop Compelling, Educational and Accessible Web Resources? The Case of Accademia Carrara
Venue: arXiv cs.MM 2005
Year: 2005

Due to the lack of budget, competence, personnel and time, small museums are often unable to develop compelling, educational and accessible web resources for their permanent collections or temporary exhibitions. In an attempt to prove that investing in these types of resources can be very fruitful even for small institutions, we will illustrate the case of Accademia Carrara, a museum in Bergamo, northern Italy, which, for a current temporary exhibition on Cezanne and Renoir's masterpieces from the Paul Guillaume collection, developed a series of multimedia applications, including an accessible website, rich in content and educational material [www.cezannerenoir.it].
Myopic Coding in Multiple Relay Channels
Venue: arXiv cs.IT 2005
Year: 2005

In this paper, we investigate achievable rates for data transmission from sources to sinks through multiple relay networks. We consider myopic coding, a constrained communication strategy in which each node has only a local view of the network, meaning that nodes can only transmit to and decode from neighboring nodes. We compare this with omniscient coding, in which every node has a global view of the network and all nodes can cooperate. Using Gaussian channels as examples, we find that when the nodes transmit at low power, the rates achievable with two-hop myopic coding are as large as that under omniscient coding in a five-node multiple relay channel and close to that under omniscient coding in a six-node multiple relay channel. These results suggest that we may do local coding and cooperation without compromising much on the transmission rate. Practically, myopic coding schemes are more robust to topology changes because encoding and decoding at a node are not affected when there are changes at remote nodes. Furthermore, myopic coding mitigates the high computational complexity and large buffer/memory requirements of omniscient coding.
Families of unitary matrices achieving full diversity
Venue: arXiv cs.IT 2005
Year: 2005

This paper presents an algebraic construction of families of unitary matrices that achieve full diversity. They are obtained as subsets of cyclic division algebras.
The Structure of Collaborative Tagging Systems
Venue: arXiv cs.DL 2005
Year: 2005

Collaborative tagging describes the process by which many users add metadata in the form of keywords to shared content. Recently, collaborative tagging has grown in popularity on the web, on sites that allow users to tag bookmarks, photographs and other content. In this paper we analyze the structure of collaborative tagging systems as well as their dynamical aspects. Specifically, we discovered regularities in user activity, tag frequencies, kinds of tags used, bursts of popularity in bookmarking and a remarkable stability in the relative proportions of tags within a given url. We also present a dynamical model of collaborative tagging that predicts these stable patterns and relates them to imitation and shared knowledge.
Modelling the EAH Data Compression Algorithm using Graph Theory
Venue: arXiv cs.DS 2005
Year: 2005

Adaptive codes associate variable-length codewords to symbols being encoded depending on the previous symbols in the input data string. This class of codes has been introduced in [Dragos Trinca, cs.DS/0505007] as a new class of non-standard variable-length codes. New algorithms for data compression, based on adaptive codes of order one, have been presented in [Dragos Trinca, ITCC-2004], where we have behaviorally shown that for a large class of input data strings, these algorithms substantially outperform the Lempel-Ziv universal data compression algorithm. EAH has been introduced in [Dragos Trinca, cs.DS/0505061], as an improved generalization of these algorithms. In this paper, we present a translation of the EAH algorithm into the graph theory.
Extending Prolog with Incomplete Fuzzy Information
Venue: arXiv cs.PL 2005
Year: 2005

Incomplete information is a problem in many aspects of actual environments. Furthermore, in many sceneries the knowledge is not represented in a crisp way. It is common to find fuzzy concepts or problems with some level of uncertainty. There are not many practical systems which handle fuzziness and uncertainty and the few examples that we can find are used by a minority. To extend a popular system (which many programmers are using) with the ability of combining crisp and fuzzy knowledge representations seems to be an interesting issue. Our first work (Fuzzy Prolog) was a language that models $\mathcal{B}([0,1])$-valued Fuzzy Logic. In the Borel algebra, $\mathcal{B}([0,1])$, truth value is represented using unions of intervals of real numbers. This work was more general in truth value representation and propagation than previous works. An interpreter for this language using Constraint Logic Programming over Real numbers (CLP(${\cal R}$)) was implemented and is available in the Ciao system. Now, we enhance our former approach by using default knowledge to represent incomplete information in Logic Programming. We also provide the implementation of this new framework. This new release of Fuzzy Prolog handles incomplete information, it has a complete semantics (the previous one was incomplete as Prolog) and moreover it is able to combine crisp and fuzzy logic in Prolog programs. Therefore, new Fuzzy Prolog is more expressive to represent real world. Fuzzy Prolog inherited from Prolog its incompleteness. The incorporation of default reasoning to Fuzzy Prolog removes this problem and requires a richer semantics which we discuss.