OpenRaiser/Intern-Atlas huggingface dataset:
Emergent Statistical Wealth Distributions in Simple Monetary Exchange Models: A Critical Review
Venue: arXiv cs.MA 2005
Year: 2005

This paper reviews recent attempts at modelling inequality of wealth as an emergent phenomenon of interacting-agent processes. We point out that recent models of wealth condensation which draw their inspiration from molecular dynamics have, in fact, reinvented a process introduced quite some time ago by Angle (1986) in the sociological literature. We emphasize some problematic aspects of simple wealth exchange models and contrast them with a monetary model based on economic principles of market mediated exchange. The paper also reports new results on the influence of market power on the wealth distribution in statistical equilibrium. As it turns out, inequality increases but market power alone is not sufficient for changing the exponential tails of simple exchange models into Pareto tails.
The role of Quantum Interference in Quantum Computing
Venue: arXiv cs.CC 2005
Year: 2005

Quantum interference is proposed as a tool to augment Quantum Computation.
Strong normalisation for applied lambda calculi
Venue: arXiv cs.GT 2005
Year: 2005

We consider the untyped lambda calculus with constructors and recursively defined constants. We construct a domain-theoretic model such that any term not denoting bottom is strongly normalising provided all its `stratified approximations' are. From this we derive a general normalisation theorem for applied typed lambda-calculi: If all constants have a total value, then all typeable terms are strongly normalising. We apply this result to extensions of Gödel's system T and system F extended by various forms of bar recursion for which strong normalisation was hitherto unknown.
Isomorphism of graphs-a polynomial test
Venue: arXiv cs.DS 2005
Year: 2005

An explicit algorithm is presented for testing whether two non-directed graphs are isomorphic or not. It is shown that for a graph of n vertices, the number of n independent operations needed for the test is polynomial in n. A proof that the algorithm actually performs the test is presented.
Minimum Cost and List Homomorphisms to Semicomplete Digraphs
Venue: arXiv cs.DM 2005
Year: 2005

The following optimization problem was introduced in \cite{gutinDAM}, where it was motivated by a real-world problem in defence logistics. Suppose we are given a pair of digraphs $D,H$ and a positive cost $c_i(u)$ for each $u\in V(D)$ and $i\in V(H)$. The cost of a homomorphism $f$ of $D$ to $H$ is $\sum_{u\in V(D)}c_{f(u)}(u)$. For a fixed digraph $H$, the minimum cost homomorphism problem for $H$, MinHOMP($H$), is stated as follows: For an input digraph $D$ and costs $c_i(u)$ for each $u\in V(D)$ and $i\in V(H)$, verify whether there is a homomorphism of $D$ to $H$ and, if it exists, find such a homomorphism of minimum cost. We obtain dichotomy classifications of the computational complexity of the list homomorphism problem and MinHOMP($H$), when $H$ is a semicomplete digraph (a digraph in which every two vertices have at least one arc between them). Our dichotomy for the list homomorphism problem coincides with the one obtained by Bang-Jensen, Hell and MacGillivray in 1988 for the homomorphism problem when $H$ is a semicomplete digraph: both problems are polynomial solvable if $H$ has at most one cycle; otherwise, both problems are NP-complete. The dichotomy for \MiP is different: the problem is polynomial time solvable if $H$ is acyclic or $H$ is a cycle of length 2 or 3; otherwise, the problem is NP-hard.
Making Space for Stories: Ambiguity in the Design of Personal Communication Systems
Venue: arXiv cs.HC 2005
Year: 2005

Pervasive personal communication technologies offer the potential for important social benefits for individual users, but also the potential for significant social difficulties and costs. In research on face-to-face social interaction, ambiguity is often identified as an important resource for resolving social difficulties. In this paper, we discuss two design cases of personal communication systems, one based on fieldwork of a commercial system and another based on an unrealized design concept. The cases illustrate how user behavior concerning a particular social difficulty, unexplained unresponsiveness, can be influenced by technological issues that result in interactional ambiguity. The cases also highlight the need to balance the utility of ambiguity against the utility of usability and communicative clarity.
Experiments in Clustering Homogeneous XML Documents to Validate an Existing Typology
Venue: arXiv cs.IR 2005
Year: 2005

This paper presents some experiments in clustering homogeneous XMLdocuments to validate an existing classification or more generally anorganisational structure. Our approach integrates techniques for extracting knowledge from documents with unsupervised classification (clustering) of documents. We focus on the feature selection used for representing documents and its impact on the emerging classification. We mix the selection of structured features with fine textual selection based on syntactic characteristics.We illustrate and evaluate this approach with a collection of Inria activity reports for the year 2003. The objective is to cluster projects into larger groups (Themes), based on the keywords or different chapters of these activity reports. We then compare the results of clustering using different feature selections, with the official theme structure used by Inria.
Hard Problems of Algebraic Geometry Codes
Venue: arXiv cs.IT 2005
Year: 2005

The minimum distance is one of the most important combinatorial characterizations of a code. The maximum likelihood decoding problem is one of the most important algorithmic problems of a code. While these problems are known to be hard for general linear codes, the techniques used to prove their hardness often rely on the construction of artificial codes. In general, much less is known about the hardness of the specific classes of natural linear codes. In this paper, we show that both problems are NP-hard for algebraic geometry codes. We achieve this by reducing a well-known NP-complete problem to these problems using a randomized algorithm. The family of codes in the reductions are based on elliptic curves. They have positive rates, but the alphabet sizes are exponential in the block lengths.
Pattern Recognition for Conditionally Independent Data
Venue: arXiv cs.LG 2005
Year: 2005

In this work we consider the task of relaxing the i.i.d assumption in pattern recognition (or classification), aiming to make existing learning algorithms applicable to a wider range of tasks. Pattern recognition is guessing a discrete label of some object based on a set of given examples (pairs of objects and labels). We consider the case of deterministically defined labels. Traditionally, this task is studied under the assumption that examples are independent and identically distributed. However, it turns out that many results of pattern recognition theory carry over a weaker assumption. Namely, under the assumption of conditional independence and identical distribution of objects, while the only assumption on the distribution of labels is that the rate of occurrence of each label should be above some positive threshold. We find a broad class of learning algorithms for which estimations of the probability of a classification error achieved under the classical i.i.d. assumption can be generalised to the similar estimates for the case of conditionally i.i.d. examples.
The MammoGrid Virtual Organisation - Federating Distributed Mammograms
Venue: arXiv cs.DC 2005
Year: 2005

The MammoGrid project aims to deliver a prototype which enables the effective collaboration between radiologists using grid, service-orientation and database solutions. The grid technologies and service-based database management solution provide the platform for integrating diverse and distributed resources, creating what is called a virtual organisation. The MammoGrid Virtual Organisation facilitates the sharing and coordinated access to mammography data, medical imaging software and computing resources of participating hospitals. Hospitals manage their local database of mammograms, but in addition, radiologists who are part of this organisation can share mammograms, reports, results and image analysis software. The MammoGrid Virtual Organisation is a federation of autonomous multi-centres sites which transcends national boundaries. This paper outlines the service-based approach in the creation and management of the federated distributed mammography database and discusses the role of virtual organisations in distributed image analysis.
Confluent Layered Drawings
Venue: arXiv cs.CG 2005
Year: 2005

We combine the idea of confluent drawings with Sugiyama style drawings, in order to reduce the edge crossings in the resultant drawings. Furthermore, it is easier to understand the structures of graphs from the mixed style drawings. The basic idea is to cover a layered graph by complete bipartite subgraphs (bicliques), then replace bicliques with tree-like structures. The biclique cover problem is reduced to a special edge coloring problem and solved by heuristic coloring algorithms. Our method can be extended to obtain multi-depth confluent layered drawings.
Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku
Venue: arXiv cs.DS 2005
Year: 2005

We provide a simple linear time transformation from a directed or undirected graph with labeled edges to an unlabeled digraph, such that paths in the input graph in which no two consecutive edges have the same label correspond to paths in the transformed graph and vice versa. Using this transformation, we provide efficient algorithms for finding paths and cycles with no two consecutive equal labels. We also consider related problems where the paths and cycles are required to be simple; we find efficient algorithms for the undirected case of these problems but show the directed case to be NP-complete. We apply our path and cycle finding algorithms in a program for generating and solving Sudoku puzzles, and show experimentally that they lead to effective puzzle-solving rules that may also be of interest to human Sudoku puzzle solvers.
Logic Column 13: Reasoning Formally about Quantum Systems: An Overview
Venue: arXiv cs.LO 2005
Year: 2005

This article is intended as an introduction to the subject of quantum logic, and as a brief survey of the relevant literature. Also discussed here are logics for specification and analysis of quantum information systems, in particular, recent work by P. Mateus and A. Sernadas, and also by R. van der Meyden and M. Patra. Overall, our objective is to provide a high-level presentation of the logical aspects of quantum theory. Mateus' and Sernadas' EQPL logic is illustrated with a small example, namely the state of an entangled pair of qubits. The "KT" logic of van der Meyden and Patra is demonstrated briefly in the context of the B92 protocol for quantum key distribution.
Relations between the Local Weight Distributions of a Linear Block Code, Its Extended Code, and Its Even Weight Subcode
Venue: arXiv cs.IT 2005
Year: 2005

Relations between the local weight distributions of a binary linear code, its extended code, and its even weight subcode are presented. In particular, for a code of which the extended code is transitive invariant and contains only codewords with weight multiples of four, the local weight distribution can be obtained from that of the extended code. Using the relations, the local weight distributions of the $(127,k)$ primitive BCH codes for $k\leq50$, the $(127,64)$ punctured third-order Reed-Muller, and their even weight subcodes are obtained from the local weight distribution of the $(128,k)$ extended primitive BCH codes for $k\leq50$ and the $(128,64)$ third-order Reed-Muller code. We also show an approach to improve an algorithm for computing the local weight distribution proposed before.
Matrix Construction Using Cyclic Shifts of a Column
Venue: arXiv cs.DM 2005
Year: 2005

This paper describes the synthesis of matrices with good correlation, from cyclic shifts of pseudonoise columns. Optimum matrices result whenever the shift sequence satisfies the constant difference property. Known shift sequences with the constant (or almost constant) difference property are: Quadratic (Polynomial) and Reciprocal Shift modulo prime, Exponential Shift, Legendre Shift, Zech Logarithm Shift, and the shift sequences of some m-arrays. We use these shift sequences to produce arrays for watermarking of digital images. Matrices can also be unfolded into long sequences by diagonal unfolding (with no deterioration in correlation) or row-by-row unfolding, with some degradation in correlation.
Software Libraries and Their Reuse: Entropy, Kolmogorov Complexity, and Zipf's Law
Venue: arXiv cs.SE 2005
Year: 2005

We analyze software reuse from the perspective of information theory and Kolmogorov complexity, assessing our ability to ``compress'' programs by expressing them in terms of software components reused from libraries. A common theme in the software reuse literature is that if we can only get the right environment in place-- the right tools, the right generalizations, economic incentives, a ``culture of reuse'' -- then reuse of software will soar, with consequent improvements in productivity and software quality. The analysis developed in this paper paints a different picture: the extent to which software reuse can occur is an intrinsic property of a problem domain, and better tools and culture can have only marginal impact on reuse rates if the domain is inherently resistant to reuse. We define an entropy parameter $H \in [0,1]$ of problem domains that measures program diversity, and deduce from this upper bounds on code reuse and the scale of components with which we may work. For ``low entropy'' domains with $H$ near 0, programs are highly similar to one another and the domain is amenable to the Component-Based Software Engineering (CBSE) dream of programming by composing large-scale components. For problem domains with $H$ near 1, programs require substantial quantities of new code, with only a modest proportion of an application comprised of reused, small-scale components. Preliminary empirical results from Unix platforms support some of the predictions of our model.
Quantum Algorithm Processor For Finding Exact Divisors
Venue: arXiv cs.AR 2005
Year: 2005

Wiring diagrams are given for a quantum algorithm processor in CMOS to compute, in parallel, all divisors of an n-bit integer. Lines required in a wiring diagram are proportional to n. Execution time is proportional to the square of n.
Sequential Predictions based on Algorithmic Complexity
Venue: arXiv cs.IT 2005
Year: 2005

This paper studies sequence prediction based on the monotone Kolmogorov complexity Km=-log m, i.e. based on universal deterministic/one-part MDL. m is extremely close to Solomonoff's universal prior M, the latter being an excellent predictor in deterministic as well as probabilistic environments, where performance is measured in terms of convergence of posteriors or losses. Despite this closeness to M, it is difficult to assess the prediction quality of m, since little is known about the closeness of their posteriors, which are the important quantities for prediction. We show that for deterministic computable environments, the "posterior" and losses of m converge, but rapid convergence could only be shown on-sequence; the off-sequence convergence can be slow. In probabilistic environments, neither the posterior nor the losses converge, in general.
Multicommodity Flow Algorithms for Buffered Global Routing
Venue: arXiv cs.DS 2005
Year: 2005

In this paper we describe a new algorithm for buffered global routing according to a prescribed buffer site map. Specifically, we describe a provably good multi-commodity flow based algorithm that finds a global routing minimizing buffer and wire congestion subject to given constraints on routing area (wirelength and number of buffers) and sink delays. Our algorithm allows computing the tradeoff curve between routing area and wire/buffer congestion under any combination of delay and capacity constraints, and simultaneously performs buffer/wire sizing, as well as layer and pin assignment. Experimental results show that near-optimal results are obtained with a practical runtime.
Relaxation Bounds on the Minimum Pseudo-Weight of Linear Block Codes
Venue: arXiv cs.IT 2005
Year: 2005

Just as the Hamming weight spectrum of a linear block code sheds light on the performance of a maximum likelihood decoder, the pseudo-weight spectrum provides insight into the performance of a linear programming decoder. Using properties of polyhedral cones, we find the pseudo-weight spectrum of some short codes. We also present two general lower bounds on the minimum pseudo-weight. The first bound is based on the column weight of the parity-check matrix. The second bound is computed by solving an optimization problem. In some cases, this bound is more tractable to compute than previously known bounds and thus can be applied to longer codes.
Further Results on Coding for Reliable Communication over Packet Networks
Venue: arXiv cs.IT 2005
Year: 2005

In "On Coding for Reliable Communication over Packet Networks" (Lun, Medard, and Effros, Proc. 42nd Annu. Allerton Conf. Communication, Control, and Computing, 2004), a capacity-achieving coding scheme for unicast or multicast over lossy wireline or wireless packet networks is presented. We extend that paper's results in two ways: First, we extend the network model to allow packets received on a link to arrive according to any process with an average rate, as opposed to the assumption of Poisson traffic with i.i.d. losses that was previously made. Second, in the case of Poisson traffic with i.i.d. losses, we derive error exponents that quantify the rate at which the probability of error decays with coding delay.
Disks, Partitions, Volumes and RAID Performance with the Linux Operating System
Venue: arXiv cs.PF 2005
Year: 2005

Block devices in computer operating systems typically correspond to disks or disk partitions, and are used to store files in a filesystem. Disks are not the only real or virtual device which adhere to the block accessible stream of bytes block device model. Files, remote devices, or even RAM may be used as a virtual disks. This article examines several common combinations of block device layers used as virtual disks in the Linux operating system: disk partitions, loopback files, software RAID, Logical Volume Manager, and Network Block Devices. It measures their relative performance using different filesystems: Ext2, Ext3, ReiserFS, JFS, XFS,NFS.
Complexity of Networks
Venue: arXiv cs.IT 2005
Year: 2005

Network or graph structures are ubiquitous in the study of complex systems. Often, we are interested in complexity trends of these system as it evolves under some dynamic. An example might be looking at the complexity of a food web as species enter an ecosystem via migration or speciation, and leave via extinction. In this paper, a complexity measure of networks is proposed based on the {\em complexity is information content} paradigm. To apply this paradigm to any object, one must fix two things: a representation language, in which strings of symbols from some alphabet describe, or stand for the objects being considered; and a means of determining when two such descriptions refer to the same object. With these two things set, the information content of an object can be computed in principle from the number of equivalent descriptions describing a particular object. I propose a simple representation language for undirected graphs that can be encoded as a bitstring, and equivalence is a topological equivalence. I also present an algorithm for computing the complexity of an arbitrary undirected network.
A 3D RGB Axis-based Color-oriented Cryptography
Venue: arXiv cs.CR 2005
Year: 2005

In this document, a formal approach to encrypt, decrypt, transmit and receive information using colors is explored. A piece of information consists of set of symbols with a definite property imposed on the generating set. The symbols are usually encoded using ascii scheme. A linear to 3d transformation is presented. The change of axis from traditional xyz to rgb is highlighted and its effect are studied. A point in this new axis is then represented as a unique color and a vector or matrix is associated with it, making it amenable to standard vector or matrix operations. A formal notion on hybrid cryptography is introduced as the algorithm lies on the boundary of symmetric and asymmetric cryptography. No discussion is complete, without mentioning reference to communication aspects of secure information in a channel. Transmission scheme pertaining to light as carrier is introduced and studied. Key-exchanges do not come under the scope of current frame of document.
A General Framework for Codes Involving Redundancy Minimization
Venue: arXiv cs.IT 2005
Year: 2005

A framework with two scalar parameters is introduced for various problems of finding a prefix code minimizing a coding penalty function. The framework encompasses problems previously proposed by Huffman, Campbell, Nath, and Drmota and Szpankowski, shedding light on the relationships among these problems. In particular, Nath's range of problems can be seen as bridging the minimum average redundancy problem of Huffman with the minimum maximum pointwise redundancy problem of Drmota and Szpankowski. Using this framework, two linear-time Huffman-like algorithms are devised for the minimum maximum pointwise redundancy problem, the only one in the framework not previously solved with a Huffman-like algorithm. Both algorithms provide solutions common to this problem and a subrange of Nath's problems, the second algorithm being distinguished by its ability to find the minimum variance solution among all solutions common to the minimum maximum pointwise redundancy and Nath problems. Simple redundancy bounds are also presented.
Special Cases of Encodings by Generalized Adaptive Codes
Venue: arXiv cs.IT 2005
Year: 2005

Adaptive (variable-length) 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 presented in [Dragos Trinca, cs.DS/0505007] as a new class of non-standard variable-length codes. Generalized adaptive codes (GA codes, for short) have been also presented in [Dragos Trinca, cs.DS/0505007] not only as a new class of non-standard variable-length codes, but also as a natural generalization of adaptive codes of any order. This paper is intended to continue developing the theory of variable-length codes by establishing several interesting connections between adaptive codes and other classes of codes. The connections are discussed not only from a theoretical point of view (by proving new results), but also from an applicative one (by proposing several applications). First, we prove that adaptive Huffman encodings and Lempel-Ziv encodings are particular cases of encodings by GA codes. Second, we show that any (n,1,m) convolutional code satisfying certain conditions can be modelled as an adaptive code of order m. Third, we describe a cryptographic scheme based on the connection between adaptive codes and convolutional codes, and present an insightful analysis of this scheme. Finally, we conclude by generalizing adaptive codes to (p,q)-adaptive codes, and discussing connections between adaptive codes and time-varying codes.