OpenRaiser/Intern-Atlas huggingface dataset:
Solution of the Linear Ordering Problem (NP=P)
Venue: arXiv cs.CC 2003
Year: 2003

A polynomial algorithm is obtained for the NP-complete linear ordering problem.
Efficient linear feedback shift registers with maximal period
Venue: arXiv cs.CR 2003
Year: 2003

We introduce and analyze an efficient family of linear feedback shift registers (LFSR's) with maximal period. This family is word-oriented and is suitable for implementation in software, thus provides a solution to a recent challenge posed in FSE '94. The classical theory of LFSR's is extended to provide efficient algorithms for generation of irreducible and primitive LFSR's of this new type.
Individual Communication Complexity
Venue: arXiv cs.CC 2003
Year: 2003

We initiate the theory of communication complexity of individual inputs held by the agents, rather than worst-case or average-case. We consider total, partial, and partially correct protocols, one-way versus two-way, with and without help bits. The results are expressed in trems of Kolmogorov complexity.
Commitment Capacity of Discrete Memoryless Channels
Venue: arXiv cs.CR 2003
Year: 2003

In extension of the bit commitment task and following work initiated by Crepeau and Kilian, we introduce and solve the problem of characterising the optimal rate at which a discrete memoryless channel can be used for bit commitment. It turns out that the answer is very intuitive: it is the maximum equivocation of the channel (after removing trivial redundancy), even when unlimited noiseless bidirectional side communication is allowed. By a well-known reduction, this result provides a lower bound on the channel's capacity for implementing coin tossing, which we conjecture to be an equality. The method of proving this relates the problem to Wyner's wire--tap channel in an amusing way. We also discuss extensions to quantum channels.
A Performance Study of Monitoring and Information Services for Distributed Systems
Venue: arXiv cs.PF 2003
Year: 2003

Monitoring and information services form a key component of a distributed system, or Grid. A quantitative study of such services can aid in understanding the performance limitations, advise in the deployment of the systems, and help evaluate future development work. To this end, we study the performance of three monitoring and information services for distributed systems: the Globus Toolkit's Monitoring and Discovery Service (MDS), the European Data Grid Relational Grid Monitoring Architecture (R-GMA), and Hawkeye, part of the Condor project. We perform experiments to test their scalability with respect to number of users, number of resources, and amount of data collected. Our study shows that each approach has different behaviors, often due to their different design goals. In the four sets of experiments we conducted to evaluate the performance of the service components under different circumstances, we found a strong advantage to caching or prefetching the data, as well as the need to have primary components at well connected sites due to high load seen by all systems.
A direct sum theorem in communication complexity via message compression
Venue: arXiv cs.CC 2003
Year: 2003

We prove lower bounds for the direct sum problem for two-party bounded error randomised multiple-round communication protocols. Our proofs use the notion of information cost of a protocol, as defined by Chakrabarti, Shi, Wirth and Yao and refined further by Bar-Yossef, Jayram, Kumar and Sivakumar. Our main technical result is a `compression' theorem saying that, for any probability distribution $μ$ over the inputs, a $k$-round private coin bounded error protocol for a function $f$ with information cost $c$ can be converted into a $k$-round deterministic protocol for $f$ with bounded distributional error and communication cost $O(kc)$. We prove this result using a substate theorem about relative entropy and a rejection sampling argument. Our direct sum result follows from this `compression' result via elementary information theoretic arguments. We also consider the direct sum problem in quantum communication. Using a probabilistic argument, we show that messages cannot be compressed in this manner even if they carry small information. Hence, new techniques may be necessary to tackle the direct sum problem in quantum communication.
Self-Replicating Machines in Continuous Space with Virtual Physics
Venue: arXiv cs.NE 2003
Year: 2003

JohnnyVon is an implementation of self-replicating machines in continuous two-dimensional space. Two types of particles drift about in a virtual liquid. The particles are automata with discrete internal states but continuous external relationships. Their internal states are governed by finite state machines but their external relationships are governed by a simulated physics that includes Brownian motion, viscosity, and spring-like attractive and repulsive forces. The particles can be assembled into patterns that can encode arbitrary strings of bits. We demonstrate that, if an arbitrary "seed" pattern is put in a "soup" of separate individual particles, the pattern will replicate by assembling the individual particles into copies of itself. We also show that, given sufficient time, a soup of separate individual particles will eventually spontaneously form self-replicating patterns. We discuss the implications of JohnnyVon for research in nanotechnology, theoretical biology, and artificial life.
An XML based Document Suite
Venue: arXiv cs.CL 2003
Year: 2003

We report about the current state of development of a document suite and its applications. This collection of tools for the flexible and robust processing of documents in German is based on the use of XML as unifying formalism for encoding input and output data as well as process information. It is organized in modules with limited responsibilities that can easily be combined into pipelines to solve complex tasks. Strong emphasis is laid on a number of techniques to deal with lexical and conceptual gaps that are typical when starting a new application.
Approximation thresholds for combinatorial optimization problems
Venue: arXiv cs.CC 2003
Year: 2003

An NP-hard combinatorial optimization problem $Π$ is said to have an {\em approximation threshold} if there is some $t$ such that the optimal value of $Π$ can be approximated in polynomial time within a ratio of $t$, and it is NP-hard to approximate it within a ratio better than $t$. We survey some of the known approximation threshold results, and discuss the pattern that emerges from the known results.
Hybrid Rounding Techniques for Knapsack Problems
Venue: arXiv cs.CC 2003
Year: 2003

We address the classical knapsack problem and a variant in which an upper bound is imposed on the number of items that can be selected. We show that appropriate combinations of rounding techniques yield novel and powerful ways of rounding. As an application of these techniques, we present a linear-storage Polynomial Time Approximation Scheme (PTAS) and a Fully Polynomial Time Approximation Scheme (FPTAS) that compute an approximate solution, of any fixed accuracy, in linear time. This linear complexity bound gives a substantial improvement of the best previously known polynomial bounds.
A Representation of Changes of Images and its Application for Developmental Biolology
Venue: arXiv cs.CC 2003
Year: 2003

In this paper, we consider a series of events observed at spaced time intervals and present a method of representation of the series. To explain an idea, by dealing with a set of gene expression data, which could be obtained from developmental biology, the procedures are sketched with comments in some details. We mean representation by choosing a proper function, which fits well with observed data of a series, and turning its characteristics into numbers, which extract the intrinsic properties of fluctuating data. With help of a machine learning techniques, this method will give a classification of developmental biological data as well as any varying data during a certain period and the classification can be applied for diagnosis of a disease.
Dempster's Rule for Evidence Ordered in a Complete Directed Acyclic Graph
Venue: arXiv cs.AI 2003
Year: 2003

For the case of evidence ordered in a complete directed acyclic graph this paper presents a new algorithm with lower computational complexity for Dempster's rule than that of step-by-step application of Dempster's rule. In this problem, every original pair of evidences, has a corresponding evidence against the simultaneous belief in both propositions. In this case, it is uncertain whether the propositions of any two evidences are in logical conflict. The original evidences are associated with the vertices and the additional evidences are associated with the edges. The original evidences are ordered, i.e., for every pair of evidences it is determinable which of the two evidences is the earlier one. We are interested in finding the most probable completely specified path through the graph, where transitions are possible only from lower- to higher-ranked vertices. The path is here a representation for a sequence of states, for instance a sequence of snapshots of a physical object's track. A completely specified path means that the path includes no other vertices than those stated in the path representation, as opposed to an incompletely specified path that may also include other vertices than those stated. In a hierarchical network of all subsets of the frame, i.e., of all incompletely specified paths, the original and additional evidences support subsets that are not disjoint, thus it is not possible to prune the network to a tree. Instead of propagating belief, the new algorithm reasons about the logical conditions of a completely specified path through the graph. The new algorithm is O(|THETA| log |THETA|), compared to O(|THETA| ** log |THETA|) of the classic brute force algorithm.
Managing Inconsistent Intelligence
Venue: arXiv cs.AI 2003
Year: 2003

In this paper we demonstrate that it is possible to manage intelligence in constant time as a pre-process to information fusion through a series of processes dealing with issues such as clustering reports, ranking reports with respect to importance, extraction of prototypes from clusters and immediate classification of newly arriving intelligence reports. These methods are used when intelligence reports arrive which concerns different events which should be handled independently, when it is not known a priori to which event each intelligence report is related. We use clustering that runs as a back-end process to partition the intelligence into subsets representing the events, and in parallel, a fast classification that runs as a front-end process in order to put the newly arriving intelligence into its correct information fusion process.
Reliable Force Aggregation Using a Refined Evidence Specification from Dempster-Shafer Clustering
Venue: arXiv cs.AI 2003
Year: 2003

In this paper we develop methods for selection of templates and use these templates to recluster an already performed Dempster-Shafer clustering taking into account intelligence to template fit during the reclustering phase. By this process the risk of erroneous force aggregation based on some misplace pieces of evidence from the first clustering process is greatly reduced. Finally, a more reliable force aggregation is performed using the result of the second clustering. These steps are taken in order to maintain most of the excellent computational performance of Dempster-Shafer clustering, while at the same time improve on the clustering result by including some higher relations among intelligence reports described by the templates. The new improved algorithm has a computational complexity of O(n**3 log**2 n) compared to O(n**2 log**2 n) of standard Dempster-Shafer clustering using Potts spin mean field theory.
Clustering belief functions based on attracting and conflicting metalevel evidence
Venue: arXiv cs.AI 2003
Year: 2003

In this paper we develop a method for clustering belief functions based on attracting and conflicting metalevel evidence. Such clustering is done when the belief functions concern multiple events, and all belief functions are mixed up. The clustering process is used as the means for separating the belief functions into subsets that should be handled independently. While the conflicting metalevel evidence is generated internally from pairwise conflicts of all belief functions, the attracting metalevel evidence is assumed given by some external source.
Factorization of Language Models through Backing-Off Lattices
Venue: arXiv cs.CL 2003
Year: 2003

Factorization of statistical language models is the task that we resolve the most discriminative model into factored models and determine a new model by combining them so as to provide better estimate. Most of previous works mainly focus on factorizing models of sequential events, each of which allows only one factorization manner. To enable parallel factorization, which allows a model event to be resolved in more than one ways at the same time, we propose a general framework, where we adopt a backing-off lattice to reflect parallel factorizations and to define the paths along which a model is resolved into factored models, we use a mixture model to combine parallel paths in the lattice, and generalize Katz's backing-off method to integrate all the mixture models got by traversing the entire lattice. Based on this framework, we formulate two types of model factorizations that are used in natural language modeling.
On the Existence and Convergence Computable Universal Priors
Venue: arXiv cs.LG 2003
Year: 2003

Solomonoff unified Occam's razor and Epicurus' principle of multiple explanations to one elegant, formal, universal theory of inductive inference, which initiated the field of algorithmic information theory. His central result is that the posterior of his universal semimeasure M converges rapidly to the true sequence generating posterior mu, if the latter is computable. Hence, M is eligible as a universal predictor in case of unknown mu. We investigate the existence and convergence of computable universal (semi)measures for a hierarchy of computability classes: finitely computable, estimable, enumerable, and approximable. For instance, M is known to be enumerable, but not finitely computable, and to dominate all enumerable semimeasures. We define seven classes of (semi)measures based on these four computability concepts. Each class may or may not contain a (semi)measure which dominates all elements of another class. The analysis of these 49 cases can be reduced to four basic cases, two of them being new. The results hold for discrete and continuous semimeasures. We also investigate more closely the types of convergence, possibly implied by universality: in difference and in ratio, with probability 1, in mean sum, and for Martin-Loef random sequences. We introduce a generalized concept of randomness for individual sequences and use it to exhibit difficulties regarding these issues.
DIAMOnDS - DIstributed Agents for MObile & Dynamic Services
Venue: arXiv cs.DC 2003
Year: 2003

Distributed Services Architecture with support for mobile agents between services, offer significantly improved communication and computational flexibility. The uses of agents allow execution of complex operations that involve large amounts of data to be processed effectively using distributed resources. The prototype system Distributed Agents for Mobile and Dynamic Services (DIAMOnDS), allows a service to send agents on its behalf, to other services, to perform data manipulation and processing. Agents have been implemented as mobile services that are discovered using the Jini Lookup mechanism and used by other services for task management and communication. Agents provide proxies for interaction with other services as well as specific GUI to monitor and control the agent activity. Thus agents acting on behalf of one service cooperate with other services to carry out a job, providing inter-operation of loosely coupled services in a semi-autonomous way. Remote file system access functionality has been incorporated by the agent framework and allows services to dynamically share and browse the file system resources of hosts, running the services. Generic database access functionality has been implemented in the mobile agent framework that allows performing complex data mining and processing operations efficiently in distributed system. A basic data searching agent is also implemented that performs a query based search in a file system. The testing of the framework was carried out on WAN by moving Connectivity Test agents between AgentStations in CERN, Switzerland and NUST, Pakistan.
McRunjob: A High Energy Physics Workflow Planner for Grid Production Processing
Venue: arXiv cs.DC 2003
Year: 2003

McRunjob is a powerful grid workflow manager used to manage the generation of large numbers of production processing jobs in High Energy Physics. In use at both the DZero and CMS experiments, McRunjob has been used to manage large Monte Carlo production processing since 1999 and is being extended to uses in regular production processing for analysis and reconstruction. Described at CHEP 2001, McRunjob converts core metadata into jobs submittable in a variety of environments. The powerful core metadata description language includes methods for converting the metadata into persistent forms, job descriptions, multi-step workflows, and data provenance information. The language features allow for structure in the metadata by including full expressions, namespaces, functional dependencies, site specific parameters in a grid environment, and ontological definitions. It also has simple control structures for parallelization of large jobs. McRunjob features a modular design which allows for easy expansion to new job description languages or new application level tasks.
The Open Language Archives Community: An infrastructure for distributed archiving of language resources
Venue: arXiv cs.CL 2003
Year: 2003

New ways of documenting and describing language via electronic media coupled with new ways of distributing the results via the World-Wide Web offer a degree of access to language resources that is unparalleled in history. At the same time, the proliferation of approaches to using these new technologies is causing serious problems relating to resource discovery and resource creation. This article describes the infrastructure that the Open Language Archives Community (OLAC) has built in order to address these problems. Its technical and usage infrastructures address problems of resource discovery by constructing a single virtual library of distributed resources. Its governance infrastructure addresses problems of resource creation by providing a mechanism through which the language-resource community can express its consensus on recommended best practices.
The WorldGrid transatlantic testbed: a successful example of Grid interoperability across EU and U.S. domains
Venue: arXiv cs.DC 2003
Year: 2003

The European DataTAG project has taken a major step towards making the concept of a worldwide computing Grid a reality. In collaboration with the companion U.S. project iVDGL, DataTAG has realized an intercontinental testbed spanning Europe and the U.S. integrating architecturally different Grid implementations based on the Globus toolkit. The WorldGrid testbed has been successfully demonstrated at SuperComputing 2002 and IST2002 where real HEP application jobs were transparently submitted from U.S. and Europe using native mechanisms and run where resources were available, independently of their location. In this paper we describe the architecture of the WorldGrid testbed, the problems encountered and the solutions taken in realizing such a testbed. With our work we present an important step towards interoperability of Grid middleware developed and deployed in Europe and the U.S.. Some of the solutions developed in WorldGrid will be adopted by the LHC Computing Grid first service. To the best of our knowledge, this is the first large-scale testbed that combines middleware components and makes them work together.
Compact Approximation of Lattice Functions with Applications to Large-Alphabet Text Search
Venue: arXiv cs.DS 2003
Year: 2003

We propose a very simple randomised data structure that stores an approximation from above of a lattice-valued function. Computing the function value requires a constant number of steps, and the error probability can be balanced with space usage, much like in Bloom filters. The structure is particularly well suited for functions that are bottom on most of their domain. We then show how to use our methods to store in a compact way the bad-character shift function for variants of the Boyer-Moore text search algorithms. As a result, we obtain practical implementations of these algorithms that can be used with large alphabets, such as Unicode collation elements, with a small setup time. The ideas described in this paper have been implemented as free software under the GNU General Public License within the MG4J project (http://mg4j.dsi.unimi.it/).
Concrete uses of XML in software development and data analysis
Venue: arXiv cs.SE 2003
Year: 2003

XML is now becoming an industry standard for data description and exchange. Despite this there are still some questions about how or if this technology can be useful in High Energy Physics software development and data analysis. This paper aims to answer these questions by demonstrating how XML is used in the IceCube software development system, data handling and analysis. It does this by first surveying the concepts and tools that make up the XML technology. It then goes on to discuss concrete examples of how these concepts and tools are used to speed up software development in IceCube and what are the benefits of using XML in IceCube's data handling and analysis chain. The overall aim of this paper it to show that XML does have many benefits to bring High Energy Physics software development and data analysis.
Hyperdense Coding Modulo 6 with Filter-Machines
Venue: arXiv cs.CC 2003
Year: 2003

We show how one can encode $n$ bits with $n^{o(1)}$ ``wave-bits'' using still hypothetical filter-machines (here $o(1)$ denotes a positive quantity which goes to 0 as $n$ goes to infity). Our present result - in a completely different computational model - significantly improves on the quantum superdense-coding breakthrough of Bennet and Wiesner (1992) which encoded $n$ bits by $\lceil{n/2}\rceil$ quantum-bits. We also show that our earlier algorithm (Tech. Rep. TR03-001, ECCC, See ftp://ftp.eccc.uni-trier.de/pub/eccc/reports/2003/TR03-001/index.html) which used $n^{o(1)}$ muliplication for computing a representation of the dot-product of two $n$-bit sequences modulo 6, and, similarly, an algorithm for computing a representation of the multiplication of two $n\times n$ matrices with $n^{2+o(1)}$ multiplications can be turned to algorithms computing the exact dot-product or the exact matrix-product with the same number of multiplications with filter-machines. With classical computation, computing the dot-product needs $Ω(n)$ multiplications and the best known algorithm for matrix multiplication (D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput., 9(3):251--280, 1990) uses $n^{2.376}$ multiplications.