OpenRaiser/Intern-Atlas huggingface dataset:
On the Sum-of-Squares Algorithm for Bin Packing
Venue: arXiv cs.DS 2002
Year: 2002

In this paper we present a theoretical analysis of the deterministic on-line {\em Sum of Squares} algorithm ($SS$) for bin packing introduced and studied experimentally in \cite{CJK99}, along with several new variants. $SS$ is applicable to any instance of bin packing in which the bin capacity $B$ and item sizes $s(a)$ are integral (or can be scaled to be so), and runs in time $O(nB)$. It performs remarkably well from an average case point of view: For any discrete distribution in which the optimal expected waste is sublinear, $SS$ also has sublinear expected waste. For any discrete distribution where the optimal expected waste is bounded, $SS$ has expected waste at most $O(\log n)$. In addition, we discuss several interesting variants on $SS$, including a randomized $O(nB\log B)$-time on-line algorithm $SS^*$, based on $SS$, whose expected behavior is essentially optimal for all discrete distributions. Algorithm $SS^*$ also depends on a new linear-programming-based pseudopolynomial-time algorithm for solving the NP-hard problem of determining, given a discrete distribution $F$, just what is the growth rate for the optimal expected waste. This article is a greatly expanded version of the conference paper \cite{sumsq2000}.
A Historic Name-Trail Service
Venue: arXiv cs.NI 2002
Year: 2002

People change the identifiers through which they are reachable online as they change jobs or residences or Internet service providers. This kind of personal mobility makes reaching people online error-prone. As people move, they do not always know who or what has cached their now obsolete identifiers so as to inform them of the move. Use of these old identifiers can cause delivery failure of important messages, or worse, may cause delivery of messages to unintended recipients. For example, a sensitive email message sent to my now obsolete work address at a former place of employment may reach my unfriendly former boss instead of me. In this paper we describe HINTS, a historic name-trail service. This service provides a persistent way to name willing participants online using today's transient online identifiers. HINTS accomplishes this by connecting together the names a person uses along with the times during which those names were valid for the person, thus giving people control over the historic use of their names. A correspondent who wishes to reach a mobile person can use an obsolete online name for that person, qualified with a time at which the online name was successfully used; HINTS resolves this historic name to a current valid online identifier for the intended recipient, if that recipient has chosen to leave a name trail in HINTS.
Geometric Aspects of Multiagent Systems
Venue: arXiv cs.MA 2002
Year: 2002

Recent advances in Multiagent Systems (MAS) and Epistemic Logic within Distributed Systems Theory, have used various combinatorial structures that model both the geometry of the systems and the Kripke model structure of models for the logic. Examining one of the simpler versions of these models, interpreted systems, and the related Kripke semantics of the logic $S5_n$ (an epistemic logic with $n$-agents), the similarities with the geometric / homotopy theoretic structure of groupoid atlases is striking. These latter objects arise in problems within algebraic K-theory, an area of algebra linked to the study of decomposition and normal form theorems in linear algebra. They have a natural well structured notion of path and constructions of path objects, etc., that yield a rich homotopy theory.
Narses: A Scalable Flow-Based Network Simulator
Venue: arXiv cs.PF 2002
Year: 2002

Most popular, modern network simulators, such as ns, are targeted towards simulating low-level protocol details. These existing simulators are not intended for simulating large distributed applications with many hosts and many concurrent connections over long periods of simulated time. We introduce a new simulator, Narses, targeted towards large distributed applications. The goal of Narses is to simulate and validate large applications efficiently using network models of varying levels of detail. We introduce several simplifying assumptions that allow our simulator to scale to the needs of large distributed applications while maintaining a reasonable degree of accuracy. Initial results show up to a 45 times speedup while consuming 28% of the memory used by ns. Narses maintains a reasonable degree of accuracy -- within 8% on average.
Adaptive Development of Koncepts in Virtual Animats: Insights into the Development of Knowledge
Venue: arXiv cs.AI 2002
Year: 2002

As a part of our effort for studying the evolution and development of cognition, we present results derived from synthetic experimentations in a virtual laboratory where animats develop koncepts adaptively and ground their meaning through action. We introduce the term "koncept" to avoid confusions and ambiguity derived from the wide use of the word "concept". We present the models which our animats use for abstracting koncepts from perceptions, plastically adapt koncepts, and associate koncepts with actions. On a more philosophical vein, we suggest that knowledge is a property of a cognitive system, not an element, and therefore observer-dependent.
Modelling intracellular signalling networks using behaviour-based systems and the blackboard architecture
Venue: arXiv cs.MA 2002
Year: 2002

This paper proposes to model the intracellular signalling networks using a fusion of behaviour-based systems and the blackboard architecture. In virtue of this fusion, the model developed by us, which has been named Cellulat, allows to take account two essential aspects of the intracellular signalling networks: (1) the cognitive capabilities of certain types of networks' components and (2) the high level of spatial organization of these networks. A simple example of modelling of Ca2+ signalling pathways using Cellulat is presented here. An intracellular signalling virtual laboratory is being developed from Cellulat.
Monadic Style Control Constructs for Inference Systems
Venue: arXiv cs.AI 2002
Year: 2002

Recent advances in programming languages study and design have established a standard way of grounding computational systems representation in category theory. These formal results led to a better understanding of issues of control and side-effects in functional and imperative languages. Another benefit is a better way of modelling computational effects in logical frameworks. With this analogy in mind, we embark on an investigation of inference systems based on considering inference behaviour as a form of computation. We delineate a categorical formalisation of control constructs in inference systems. This representation emphasises the parallel between the modular articulation of the categorical building blocks (triples) used to account for the inference architecture and the modular composition of cognitive processes.
An Approach to Automatic Indexing of Scientific Publications in High Energy Physics for Database SPIRES HEP
Venue: arXiv cs.IR 2002
Year: 2002

We introduce an approach to automatic indexing of e-prints based on a pattern-matching technique making extensive use of an Associative Patterns Dictionary (APD), developed by us. Entries in the APD consist of natural language phrases with the same semantic interpretation as a set of keywords from a controlled vocabulary. The method also allows to recognize within e-prints formulae written in TeX notations that might also appear as keywords. We present an automatic indexing system, AUTEX, which we have applied to keyword index e-prints in selected areas in high energy physics (HEP) making use of the DESY-HEPI thesaurus as a controlled vocabulary.
Traveling Salesmen in the Presence of Competition
Venue: arXiv cs.CC 2002
Year: 2002

We propose the ``Competing Salesmen Problem'' (CSP), a 2-player competitive version of the classical Traveling Salesman Problem. This problem arises when considering two competing salesmen instead of just one. The concern for a shortest tour is replaced by the necessity to reach any of the customers before the opponent does. In particular, we consider the situation where players take turns, moving along one edge at a time within a graph G=(V,E). The set of customers is given by a subset V_C V of the vertices. At any given time, both players know of their opponent's position. A player wins if he is able to reach a majority of the vertices in V_C before the opponent does. We prove that the CSP is PSPACE-complete, even if the graph is bipartite, and both players start at distance 2 from each other. We show that the starting player may lose the game, even if both players start from the same vertex. For bipartite graphs, we show that the starting player always can avoid a loss. We also show that the second player can avoid to lose by more than one customer, when play takes place on a graph that is a tree T, and V_C consists of leaves of T. For the case where T is a star and V_C consists of n leaves of T, we give a simple and fast strategy which is optimal for both players. If V_C consists not only of leaves, the situation is more involved.
Ownership Confinement Ensures Representation Independence for Object-Oriented Programs
Venue: arXiv cs.PL 2002
Year: 2002

Dedicated to the memory of Edsger W.Dijkstra. Representation independence or relational parametricity formally characterizes the encapsulation provided by language constructs for data abstraction and justifies reasoning by simulation. Representation independence has been shown for a variety of languages and constructs but not for shared references to mutable state; indeed it fails in general for such languages. This paper formulates representation independence for classes, in an imperative, object-oriented language with pointers, subclassing and dynamic dispatch, class oriented visibility control, recursive types and methods, and a simple form of module. An instance of a class is considered to implement an abstraction using private fields and so-called representation objects. Encapsulation of representation objects is expressed by a restriction, called confinement, on aliasing. Representation independence is proved for programs satisfying the confinement condition. A static analysis is given for confinement that accepts common designs such as the observer and factory patterns. The formalization takes into account not only the usual interface between a client and a class that provides an abstraction but also the interface (often called ``protected'') between the class and its subclasses.
JohnnyVon: Self-Replicating Automata in Continuous Two-Dimensional Space
Venue: arXiv cs.NE 2002
Year: 2002

JohnnyVon is an implementation of self-replicating automata 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.
A Simple Model of Unbounded Evolutionary Versatility as a Largest-Scale Trend in Organismal Evolution
Venue: arXiv cs.NE 2002
Year: 2002

The idea that there are any large-scale trends in the evolution of biological organisms is highly controversial. It is commonly believed, for example, that there is a large-scale trend in evolution towards increasing complexity, but empirical and theoretical arguments undermine this belief. Natural selection results in organisms that are well adapted to their local environments, but it is not clear how local adaptation can produce a global trend. In this paper, I present a simple computational model, in which local adaptation to a randomly changing environment results in a global trend towards increasing evolutionary versatility. In this model, for evolutionary versatility to increase without bound, the environment must be highly dynamic. The model also shows that unbounded evolutionary versatility implies an accelerating evolutionary pace. I believe that unbounded increase in evolutionary versatility is a large-scale trend in evolution. I discuss some of the testable predictions about organismal evolution that are suggested by the model.
A Generalization of the Lifting Lemma for Logic Programming
Venue: arXiv cs.LO 2002
Year: 2002

Since the seminal work of J. A. Robinson on resolution, many lifting lemmas for simplifying proofs of completeness of resolution have been proposed in the literature. In the logic programming framework, they may also help to detect some infinite derivations while proving goals under the SLD-resolution. In this paper, we first generalize a version of the lifting lemma, by extending the relation "is more general than" so that it takes into account only some arguments of the atoms. The other arguments, which we call neutral arguments, are disregarded. Then we propose two syntactic conditions of increasing power for identifying neutral arguments from mere inspection of the text of a logic program.
Qualitative Study of a Robot Arm as a Hamiltonian System
Venue: arXiv cs.RO 2002
Year: 2002

A double pendulum subject to external torques is used as a model to study the stability of a planar manipulator with two links and two rotational driven joints. The hamiltonian equations of motion and the fixed points (stationary solutions) in phase space are determined. Under suitable conditions, the presence of constant torques does not change the number of fixed points, and preserves the topology of orbits in their linear neighborhoods; two equivalent invariant manifolds are observed, each corresponding to a saddle-center fixed point.
Mining the Web for Synonyms: PMI-IR versus LSA on TOEFL
Venue: arXiv cs.LG 2002
Year: 2002

This paper presents a simple unsupervised learning algorithm for recognizing synonyms, based on statistical data acquired by querying a Web search engine. The algorithm, called PMI-IR, uses Pointwise Mutual Information (PMI) and Information Retrieval (IR) to measure the similarity of pairs of words. PMI-IR is empirically evaluated using 80 synonym test questions from the Test of English as a Foreign Language (TOEFL) and 50 synonym test questions from a collection of tests for students of English as a Second Language (ESL). On both tests, the algorithm obtains a score of 74%. PMI-IR is contrasted with Latent Semantic Analysis (LSA), which achieves a score of 64% on the same 80 TOEFL questions. The paper discusses potential applications of the new unsupervised learning algorithm and some implications of the results for LSA and LSI (Latent Semantic Indexing).
Solving a "Hard" Problem to Approximate an "Easy" One: Heuristics for Maximum Matchings and Maximum Traveling Salesman Problems
Venue: arXiv cs.DS 2002
Year: 2002

We consider geometric instances of the Maximum Weighted Matching Problem (MWMP) and the Maximum Traveling Salesman Problem (MTSP) with up to 3,000,000 vertices. Making use of a geometric duality relationship between MWMP, MTSP, and the Fermat-Weber-Problem (FWP), we develop a heuristic approach that yields in near-linear time solutions as well as upper bounds. Using various computational tools, we get solutions within considerably less than 1% of the optimum. An interesting feature of our approach is that, even though an FWP is hard to compute in theory and Edmonds' algorithm for maximum weighted matching yields a polynomial solution for the MWMP, the practical behavior is just the opposite, and we can solve the FWP with high accuracy in order to find a good heuristic solution for the MWMP.
Confluent Drawings: Visualizing Non-planar Diagrams in a Planar Way
Venue: arXiv cs.CG 2002
Year: 2002

In this paper, we introduce a new approach for drawing diagrams that have applications in software visualization. Our approach is to use a technique we call confluent drawing for visualizing non-planar diagrams in a planar way. This approach allows us to draw, in a crossing-free manner, graphs--such as software interaction diagrams--that would normally have many crossings. The main idea of this approach is quite simple: we allow groups of edges to be merged together and drawn as "tracks" (similar to train tracks). Producing such confluent diagrams automatically from a graph with many crossings is quite challenging, however, so we offer two heuristic algorithms to test if a non-planar graph can be drawn efficiently in a confluent way. In addition, we identify several large classes of graphs that can be completely categorized as being either confluently drawable or confluently non-drawable.
On the Work of Madhu Sudan: the 2002 Nevalinna Prize Winner
Venue: arXiv cs.CC 2002
Year: 2002

Madhu Sudan's work spans many areas of computer science theory including computational complexity theory, the design of efficient algorithms, algorithmic coding theory, and the theory of program checking and correcting. Two results of Sudan stand out in the impact they have had on the mathematics of computation. The first work shows a probabilistic characterization of the class NP -- those sets for which short and easily checkable proofs of membership exist, and demonstrates consequences of this characterization to classifying the complexity of approximation problems. The second work shows a polynomial time algorithm for list decoding the Reed Solomon error correcting codes. This short note will be devoted to describing Sudan's work on probabilistically checkable proofs -- the so called {\it PCP theorem} and its implications.
When Can You Fold a Map?
Venue: arXiv cs.CG 2003
Year: 2003

We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds? There are several models of simple folds; the simplest one-layer simple fold rotates a portion of paper about a crease in the paper by +-180 degrees. We first consider the analogous questions in one dimension lower -- bending a segment into a flat object -- which lead to interesting problems on strings. We develop efficient algorithms for the recognition of simply foldable 1D crease patterns, and reconstruction of a sequence of simple folds. Indeed, we prove that a 1D crease pattern is flat-foldable by any means precisely if it is by a sequence of one-layer simple folds. Next we explore simple foldability in two dimensions, and find a surprising contrast: ``map'' folding and variants are polynomial, but slight generalizations are NP-complete. Specifically, we develop a linear-time algorithm for deciding foldability of an orthogonal crease pattern on a rectangular piece of paper, and prove that it is (weakly) NP-complete to decide foldability of (1) an orthogonal crease pattern on a orthogonal piece of paper, (2) a crease pattern of axis-parallel and diagonal (45-degree) creases on a square piece of paper, and (3) crease patterns without a mountain/valley assignment.
The Gibbs Representation of 3D Rotations
Venue: arXiv cs.DS 2003
Year: 2003

This paper revisits the little-known Gibbs-Rodrigues representation of rotations in a three-dimensional space and demonstrates a set of algorithms for handling it. In this representation the rotation is itself represented as a three-dimensional vector. The vector is parallel to the axis of rotation and its three components transform covariantly on change of coordinates. The mapping from rotations to vectors is 1:1 apart from computation error. The discontinuities of the representation require special handling but are not problematic. The rotation matrix can be generated efficiently from the vector without the use of transcendental functions, and vice-versa. The representation is more efficient than Euler angles, has affinities with Hassenpflug's Argyris angles and is very closely related to the quaternion representation. While the quaternion representation avoids the discontinuities inherent in any 3-component representation, this problem is readily overcome. The present paper gives efficient algorithms for computing the set of rotations which map a given vector to another of the same length and the rotation which maps a given pair of vectors to another pair of the same length and subtended angle.
Solving equations in the relational algebra
Venue: arXiv cs.LO 2003
Year: 2003

Enumerating all solutions of a relational algebra equation is a natural and powerful operation which, when added as a query language primitive to the nested relational algebra, yields a query language for nested relational databases, equivalent to the well-known powerset algebra. We study \emph{sparse} equations, which are equations with at most polynomially many solutions. We look at their complexity, and compare their expressive power with that of similar notions in the powerset algebra.
The Geometric Maximum Traveling Salesman Problem
Venue: arXiv cs.DS 2003
Year: 2003

We consider the traveling salesman problem when the cities are points in R^d for some fixed d and distances are computed according to geometric distances, determined by some norm. We show that for any polyhedral norm, the problem of finding a tour of maximum length can be solved in polynomial time. If arithmetic operations are assumed to take unit time, our algorithms run in time O(n^{f-2} log n), where f is the number of facets of the polyhedron determining the polyhedral norm. Thus for example we have O(n^2 log n) algorithms for the cases of points in the plane under the Rectilinear and Sup norms. This is in contrast to the fact that finding a minimum length tour in each case is NP-hard. Our approach can be extended to the more general case of quasi-norms with not necessarily symmetric unit ball, where we get a complexity of O(n^{2f-2} log n). For the special case of two-dimensional metrics with f=4 (which includes the Rectilinear and Sup norms), we present a simple algorithm with O(n) running time. The algorithm does not use any indirect addressing, so its running time remains valid even in comparison based models in which sorting requires Omega(n \log n) time. The basic mechanism of the algorithm provides some intuition on why polyhedral norms allow fast algorithms. Complementing the results on simplicity for polyhedral norms, we prove that for the case of Euclidean distances in R^d for d>2, the Maximum TSP is NP-hard. This sheds new light on the well-studied difficulties of Euclidean distances.