OpenRaiser/Intern-Atlas huggingface dataset:
Representation Dependence in Probabilistic Inference
Venue: arXiv cs.AI 2003
Year: 2003

Non-deductive reasoning systems are often {\em representation dependent}: representing the same situation in two different ways may cause such a system to return two different answers. Some have viewed this as a significant problem. For example, the principle of maximum entropy has been subjected to much criticism due to its representation dependence. There has, however, been almost no work investigating representation dependence. In this paper, we formalize this notion and show that it is not a problem specific to maximum entropy. In fact, we show that any representation-independent probabilistic inference procedure that ignores irrelevant information is essentially entailment, in a precise sense. Moreover, we show that representation independence is incompatible with even a weak default assumption of independence. We then show that invariance under a restricted class of representation changes can form a reasonable compromise between representation independence and other desiderata, and provide a construction of a family of inference procedures that provides such restricted representation independence, using relative entropy.
The similarity metric
Venue: arXiv cs.CC 2004
Year: 2004

A new class of distances appropriate for measuring similarity relations between sequences, say one type of similarity per distance, is studied. We propose a new ``normalized information distance'', based on the noncomputable notion of Kolmogorov complexity, and show that it is in this class and it minorizes every computable distance in the class (that is, it is universal in that it discovers all computable similarities). We demonstrate that it is a metric and call it the {\em similarity metric}. This theory forms the foundation for a new practical tool. To evidence generality and robustness we give two distinctive applications in widely divergent areas using standard compression programs like gzip and GenCompress. First, we compare whole mitochondrial genomes and infer their evolutionary history. This results in a first completely automatic computed whole mitochondrial phylogeny tree. Secondly, we fully automatically compute the language tree of 52 different languages.
Fast optical layer mesh protection using pre-cross-connected trails
Venue: arXiv cs.NI 2004
Year: 2004

Conventional optical networks are based on SONET rings, but since rings are known to use bandwidth inefficiently, there has been much research into shared mesh protection, which promises significant bandwidth savings. Unfortunately, most shared mesh protection schemes cannot guarantee that failed traffic will be restored within the 50 ms timeframe that SONET standards specify. A notable exception is the p-cycle scheme of Grover and Stamatelakis. We argue, however, that p-cycles have certain limitations, e.g., there is no easy way to adapt p-cycles to a path-based protection scheme, and p-cycles seem more suited to static traffic than to dynamic traffic. In this paper we show that the key to fast restoration times is not a ring-like topology per se, but rather the ability to pre-cross-connect protection paths. This leads to the concept of a pre-cross-connected trail or PXT, which is a structure that is more flexible than rings and that adapts readily to both path-based and link-based schemes and to both static and dynamic traffic. The PXT protection scheme achieves fast restoration speeds, and our simulations, which have been carefully chosen using ideas from experimental design theory, show that the bandwidth efficiency of the PXT protection scheme is comparable to that of conventional shared mesh protection schemes.
Universal Sequential Decisions in Unknown Environments
Venue: arXiv cs.AI 2004
Year: 2004

We give a brief introduction to the AIXI model, which unifies and overcomes the limitations of sequential decision theory and universal Solomonoff induction. While the former theory is suited for active agents in known environments, the latter is suited for passive prediction of unknown environments.
A Comparison of Secret Sharing Schemes Based on Latin Squares and RSA
Venue: arXiv cs.CR 2004
Year: 2004

In recent years there has been a great deal of work done on secret sharing scehemes. Secret Sharing Schemes allow for the division of keys so that an authorised set of users may access information. In this paper we wish to present a critical comparison of two of these schemes based on Latin Squares, [Cooper et., al.] and RSA [Shoup]. These two protocols will be examined in terms of their positive and negative aspects of their secuirty.
A Comparison of Cryptography Courses
Venue: arXiv cs.CR 2004
Year: 2004

The author taught two courses on cryptography, one at Duke University aimed at non-mathematics majors and one at Rose-Hulman Institute of Technology aimed at mathematics and computer science majors. Both tried to incorporate technical and societal aspects of cryptography, with varying emphases. This paper will discuss the strengths and weaknesses of both courses and compare the differences in the author's approach.
A system for reflection in C++
Venue: arXiv cs.PL 2004
Year: 2004

Object-oriented programming languages such as Java and Objective C have become popular for implementing agent-based and other object-based simulations since objects in those languages can {\em reflect} (i.e. make runtime queries of an object's structure). This allows, for example, a fairly trivial {\em serialisation} routine (conversion of an object into a binary representation that can be stored or passed over a network) to be written. However C++ does not offer this ability, as type information is thrown away at compile time. Yet C++ is often a preferred development environment, whether for performance reasons or for its expressive features such as operator overloading. In this paper, we present the {\em Classdesc} system which brings many of the benefits of object reflection to C++.
Dynamic Linking of Smart Digital Objects Based on User Navigation Patterns
Venue: arXiv cs.DL 2004
Year: 2004

We discuss a methodology to dynamically generate links among digital objects by means of an unsupervised learning mechanism which analyzes user link traversal patterns. We performed an experiment with a test bed of 150 complex data objects, referred to as buckets. Each bucket manages its own content, provides methods to interact with users and individually maintains a set of links to other buckets. We demonstrate that buckets were capable of dynamically adjusting their links to other buckets according to user link selections, thereby generating a meaningful network of bucket relations. Our results indicate such adaptive networks of linked buckets approximate the collective link preferences of a community of user
Baptista-type chaotic cryptosystems: Problems and countermeasures
Venue: arXiv cs.CR 2004
Year: 2004

In 1998, M. S. Baptista proposed a chaotic cryptosystem, which has attracted much attention from the chaotic cryptography community: some of its modifications and also attacks have been reported in recent years. In [Phys. Lett. A 307 (2003) 22], we suggested a method to enhance the security of Baptista-type cryptosystem, which can successfully resist all proposed attacks. However, the enhanced Baptista-type cryptosystem has a nontrivial defect, which produces errors in the decrypted data with a generally small but nonzero probability, and the consequent error propagation exists. In this Letter, we analyze this defect and discuss how to rectify it. In addition, we point out some newly-found problems existing in all Baptista-type cryptosystems and consequently propose corresponding countermeasures.
A Knowledge-Theoretic Analysis of Uniform Distributed Coordination and Failure Detectors
Venue: arXiv cs.DC 2004
Year: 2004

It is shown that, in a precise sense, if there is no bound on the number of faulty processes in a system with unreliable but fair communication, Uniform Distributed Coordination (UDC) can be attained if and only if a system has perfect failure detectors. This result is generalized to the case where there is a bound t on the number of faulty processes. It is shown that a certain type of generalized failure detector is necessary and sufficient for achieving UDC in a context with at most t faulty processes. Reasoning about processes' knowledge as to which other processes are faulty plays a key role in the analysis.
Automatically Generating Interfaces for Personalized Interaction with Digital Libraries
Venue: arXiv cs.DL 2004
Year: 2004

We present an approach to automatically generate interfaces supporting personalized interaction with digital libraries; these interfaces augment the user-DL dialog by empowering the user to (optionally) supply out-of-turn information during an interaction, flatten or restructure the dialog, and enquire about dialog options. Interfaces generated using this approach for CITIDEL are described.
Efficient and Scalable Barrier over Quadrics and Myrinet with a New NIC-Based Collective Message Passing Protocol
Venue: arXiv cs.DC 2004
Year: 2004

Modern interconnects often have programmable processors in the network interface that can be utilized to offload communication processing from host CPU. In this paper, we explore different schemes to support collective operations at the network interface and propose a new collective protocol. With barrier as an initial case study, we have demontrated that much of the communication processing can be greatly simplified with this collective protocol. Accordingly, %with our proposed collective processing scheme, we have designed and implemented efficient and scalable NIC-based barrier operations over two high performance interconnects, Quadrics and Myrinet. Our evaluation shows that, over a Quadrics cluster of 8 nodes with ELan3 Network, the NIC-based barrier operation achieves a barrier latency of only 5.60$μ$s. This result is a 2.48 factor of improvement over the Elanlib tree-based barrier operation. Over a Myrinet cluster of 8 nodes with LANai-XP NIC cards, a barrier latency of 14.20$μ$s over 8 nodes is achieved. This is a 2.64 factor of improvement over the host-based barrier algorithm. Furthermore, an analytical model developed for the proposed scheme indicates that a NIC-based barrier operation on a 1024-node cluster can be performed with only 22.13$μ$s latency over Quadrics and with 38.94$μ$s latency over Myrinet. These results indicate the potential for developing high performance communication subsystems for next generation clusters.
Parameter-less hierarchical BOA
Venue: arXiv cs.NE 2004
Year: 2004

The parameter-less hierarchical Bayesian optimization algorithm (hBOA) enables the use of hBOA without the need for tuning parameters for solving each problem instance. There are three crucial parameters in hBOA: (1) the selection pressure, (2) the window size for restricted tournaments, and (3) the population size. Although both the selection pressure and the window size influence hBOA performance, performance should remain low-order polynomial with standard choices of these two parameters. However, there is no standard population size that would work for all problems of interest and the population size must thus be eliminated in a different way. To eliminate the population size, the parameter-less hBOA adopts the population-sizing technique of the parameter-less genetic algorithm. Based on the existing theory, the parameter-less hBOA should be able to solve nearly decomposable and hierarchical problems in quadratic or subquadratic number of function evaluations without the need for setting any parameters whatsoever. A number of experiments are presented to verify scalability of the parameter-less hBOA.
Recycling Computed Answers in Rewrite Systems for Abduction
Venue: arXiv cs.AI 2004
Year: 2004

In rule-based systems, goal-oriented computations correspond naturally to the possible ways that an observation may be explained. In some applications, we need to compute explanations for a series of observations with the same domain. The question whether previously computed answers can be recycled arises. A yes answer could result in substantial savings of repeated computations. For systems based on classic logic, the answer is YES. For nonmonotonic systems however, one tends to believe that the answer should be NO, since recycling is a form of adding information. In this paper, we show that computed answers can always be recycled, in a nontrivial way, for the class of rewrite procedures that we proposed earlier for logic programs with negation. We present some experimental results on an encoding of the logistics domain.
Anonymity and Information Hiding in Multiagent Systems
Venue: arXiv cs.CR 2004
Year: 2004

We provide a framework for reasoning about information-hiding requirements in multiagent systems and for reasoning about anonymity in particular. Our framework employs the modal logic of knowledge within the context of the runs and systems framework, much in the spirit of our earlier work on secrecy [Halpern and O'Neill 2002]. We give several definitions of anonymity with respect to agents, actions, and observers in multiagent systems, and we relate our definitions of anonymity to other definitions of information hiding, such as secrecy. We also give probabilistic definitions of anonymity that are able to quantify an observer s uncertainty about the state of the system. Finally, we relate our definitions of anonymity to other formalizations of anonymity and information hiding, including definitions of anonymity in the process algebra CSP and definitions of information hiding using function views.
The Complexity of Modified Instances
Venue: arXiv cs.CC 2004
Year: 2004

In this paper we study the complexity of solving a problem when a solution of a similar instance is known. This problem is relevant whenever instances may change from time to time, and known solutions may not remain valid after the change. We consider two scenarios: in the first one, what is known is only a solution of the problem before the change; in the second case, we assume that some additional information, found during the search for this solution, is also known. In the first setting, the techniques from the theory of NP-completeness suffice to show complexity results. In the second case, negative results can only be proved using the techniques of compilability, and are often related to the size of considered changes.
A Tribute to Alain Colmerauer
Venue: arXiv cs.PL 2004
Year: 2004

The paper describes the contributions of Alain Colmerauer to the areas of logic programs (LP) and constraint logic programs (CLP).
Distributed Computing Economics
Venue: arXiv cs.NI 2004
Year: 2004

Computing economics are changing. Today there is rough price parity between (1) one database access, (2) ten bytes of network traffic, (3) 100,000 instructions, (4) 10 bytes of disk storage, and (5) a megabyte of disk bandwidth. This has implications for how one structures Internet-scale distributed computing: one puts computing as close to the data as possible in order to avoid expensive network traffic.
Schedulers and Redundancy for a Class of Constraint Propagation Rules
Venue: arXiv cs.DS 2004
Year: 2004

We study here schedulers for a class of rules that naturally arise in the context of rule-based constraint programming. We systematically derive a scheduler for them from a generic iteration algorithm of [Apt 2000]. We apply this study to so-called membership rules of [Apt and Monfroy 2001]. This leads to an implementation that yields a considerably better performance for these rules than their execution as standard CHR rules. Finally, we show how redundant rules can be identified and how appropriately reduced sets of rules can be computed.
Government mandated blocking of foreign Web content
Venue: arXiv cs.CY 2004
Year: 2004

Blocking of foreign Web content by Internet access providers has been a hot topic for the last 18 months in Germany. Since fall 2001 the state of North-Rhine-Westphalia very actively tries to mandate such blocking. This paper will take a technical view on the problems imposed by the blocking orders and blocking content at access or network provider level in general. It will also give some empirical data on the effects of the blocking orders to help in the legal assessment of the orders.
Toward the Implementation of Functions in the DLV System (Preliminary Technical Report)
Venue: arXiv cs.AI 2004
Year: 2004

This document describes the functions as they are treated in the DLV system. We give first the language, then specify the main implementation issues.
A Modular and Fault-Tolerant Data Transport Framework
Venue: arXiv cs.DC 2004
Year: 2004

The High Level Trigger (HLT) of the future ALICE heavy-ion experiment has to reduce its input data rate of up to 25 GB/s to at most 1.25 GB/s for output before the data is written to permanent storage. To cope with these data rates a large PC cluster system is being designed to scale to several 1000 nodes, connected by a fast network. For the software that will run on these nodes a flexible data transport and distribution software framework, described in this thesis, has been developed. The framework consists of a set of separate components, that can be connected via a common interface. This allows to construct different configurations for the HLT, that are even changeable at runtime. To ensure a fault-tolerant operation of the HLT, the framework includes a basic fail-over mechanism that allows to replace whole nodes after a failure. The mechanism will be further expanded in the future, utilizing the runtime reconnection feature of the framework's component interface. To connect cluster nodes a communication class library is used that abstracts from the actual network technology and protocol used to retain flexibility in the hardware choice. It contains already two working prototype versions for the TCP protocol as well as SCI network adapters. Extensions can be added to the library without modifications to other parts of the framework. Extensive tests and measurements have been performed with the framework. Their results as well as conclusions drawn from them are also presented in this thesis. Performance tests show very promising results for the system, indicating that it can fulfill ALICE's requirements concerning the data transport.
Exploring tradeoffs in pleiotropy and redundancy using evolutionary computing
Venue: arXiv cs.NE 2004
Year: 2004

Evolutionary computation algorithms are increasingly being used to solve optimization problems as they have many advantages over traditional optimization algorithms. In this paper we use evolutionary computation to study the trade-off between pleiotropy and redundancy in a client-server based network. Pleiotropy is a term used to describe components that perform multiple tasks, while redundancy refers to multiple components performing one same task. Pleiotropy reduces cost but lacks robustness, while redundancy increases network reliability but is more costly, as together, pleiotropy and redundancy build flexibility and robustness into systems. Therefore it is desirable to have a network that contains a balance between pleiotropy and redundancy. We explore how factors such as link failure probability, repair rates, and the size of the network influence the design choices that we explore using genetic algorithms.
Optimizing genetic algorithm strategies for evolving networks
Venue: arXiv cs.NE 2004
Year: 2004

This paper explores the use of genetic algorithms for the design of networks, where the demands on the network fluctuate in time. For varying network constraints, we find the best network using the standard genetic algorithm operators such as inversion, mutation and crossover. We also examine how the choice of genetic algorithm operators affects the quality of the best network found. Such networks typically contain redundancy in servers, where several servers perform the same task and pleiotropy, where servers perform multiple tasks. We explore this trade-off between pleiotropy versus redundancy on the cost versus reliability as a measure of the quality of the network.
DAB Content Annotation and Receiver Hardware Control with XML
Venue: arXiv cs.GL 2004
Year: 2004

The Eureka-147 Digital Audio Broadcasting (DAB) standard defines the 'dynamic labels' data field for holding information about the transmission content. However, this information does not follow a well-defined structure since it is designed to carry text for direct output to displays, for human interpretation. This poses a problem when machine interpretation of DAB content information is desired. Extensible Markup Language (XML) was developed to allow for the well-defined, structured machine-to-machine exchange of data over computer networks. This article proposes a novel technique of machine-interpretable DAB content annotation and receiver hardware control, involving the utilisation of XML as metadata in the transmitted DAB frames.
2-Sat Sub-Clauses and the Hypernodal Structure of the 3-Sat Problem
Venue: arXiv cs.CC 2004
Year: 2004

Like simpler graphs, nested (hypernodal) graphs consist of two components: a set of nodes and a set of edges, where each edge connects a pair of nodes. In the hypernodal graph model, however, a node may contain other graphs, so that a node may be contained in a graph that it contains. The inherently recursive structure of the hypernodal graph model aptly characterizes both the structure and dynamic of the 3-sat problem, a broadly applicable, though intractable, computer science problem. In this paper I first discuss the structure of the 3-sat problem, analyzing the relation of 3-sat to 2-sat, a related, though tractable problem. I then discuss sub-clauses and sub-clause thresholds and the transformation of sub-clauses into implication graphs, demonstrating how combinations of implication graphs are equivalent to hypernodal graphs. I conclude with a brief discussion of the use of hypernodal graphs to model the 3-sat problem, illustrating how hypernodal graphs model both the conditions for satisfiability and the process by which particular 3-sat assignments either succeed or fail.
Benchmarking Blunders and Things That Go Bump in the Night
Venue: arXiv cs.PF 2004
Year: 2004

Benchmarking; by which I mean any computer system that is driven by a controlled workload, is the ultimate in performance testing and simulation. Aside from being a form of institutionalized cheating, it also offer countless opportunities for systematic mistakes in the way the workloads are applied and the resulting measurements interpreted. Right test, wrong conclusion is a ubiquitous mistake that happens because test engineers tend to treat data as divine. Such reverence is not only misplaced, it's also a sure ticket to production hell when the application finally goes live. I demonstrate how such mistakes can be avoided by means of two war stories that are real WOPRs. (a) How to resolve benchmark flaws over the psychic hotline and (b) How benchmarks can go flat with too much Java juice. In each case I present simple performance models and show how they can be applied to correctly assess benchmark data.
Knowledge And The Action Description Language A
Venue: arXiv cs.AI 2004
Year: 2004

We introduce Ak, an extension of the action description language A (Gelfond and Lifschitz, 1993) to handle actions which affect knowledge. We use sensing actions to increase an agent's knowledge of the world and non-deterministic actions to remove knowledge. We include complex plans involving conditionals and loops in our query language for hypothetical reasoning. We also present a translation of Ak domain descriptions into epistemic logic programs.