title:
Reconstructing Polyatomic Structures from Discrete X-Rays:
  NP-Completeness Proof for Three Atoms

abstract:
  We address a discrete tomography problem that arises in the study of the
atomic structure of crystal lattices. A polyatomic structure T can be defined
as an integer lattice in dimension D>=2, whose points may be occupied by $c$
distinct types of atoms. To ``analyze'' T, we conduct ell measurements that we
call_discrete X-rays_. A discrete X-ray in direction xi determines the number
of atoms of each type on each line parallel to xi. Given ell such non-parallel
X-rays, we wish to reconstruct T.
  The complexity of the problem for c=1 (one atom type) has been completely
determined by Gardner, Gritzmann and Prangenberg, who proved that the problem
is NP-complete for any dimension D>=2 and ell>=3 non-parallel X-rays, and that
it can be solved in polynomial time otherwise.
  The NP-completeness result above clearly extends to any c>=2, and therefore
when studying the polyatomic case we can assume that ell=2. As shown in another
article by the same authors, this problem is also NP-complete for c>=6 atoms,
even for dimension D=2 and axis-parallel X-rays. They conjecture that the
problem remains NP-complete for c=3,4,5, although, as they point out, the proof
idea does not seem to extend to c<=5.
  We resolve the conjecture by proving that the problem is indeed NP-complete
for c>=3 in 2D, even for axis-parallel X-rays. Our construction relies heavily
on some structure results for the realizations of 0-1 matrices with given row
and column sums.


title:
Resolving Part-of-Speech Ambiguity in the Greek Language Using Learning
  Techniques

abstract:
  This article investigates the use of Transformation-Based Error-Driven
learning for resolving part-of-speech ambiguity in the Greek language. The aim
is not only to study the performance, but also to examine its dependence on
different thematic domains. Results are presented here for two different test
cases: a corpus on "management succession events" and a general-theme corpus.
The two experiments show that the performance of this method does not depend on
the thematic domain of the corpus, and its accuracy for the Greek language is
around 95%.


title: Temporal Meaning Representations in a Natural Language Front-End

abstract:
  Previous work in the context of natural language querying of temporal
databases has established a method to map automatically from a large subset of
English time-related questions to suitable expressions of a temporal logic-like
language, called TOP. An algorithm to translate from TOP to the TSQL2 temporal
database language has also been defined. This paper shows how TOP expressions
could be translated into a simpler logic-like language, called BOT. BOT is very
close to traditional first-order predicate logic (FOPL), and hence existing
methods to manipulate FOPL expressions can be exploited to interface to
time-sensitive applications other than TSQL2 databases, maintaining the
existing English-to-TOP mapping.


title: Reconstructing hv-Convex Polyominoes from Orthogonal Projections

abstract:
  Tomography is the area of reconstructing objects from projections. Here we
wish to reconstruct a set of cells in a two dimensional grid, given the number
of cells in every row and column. The set is required to be an hv-convex
polyomino, that is all its cells must be connected and the cells in every row
and column must be consecutive. A simple, polynomial algorithm for
reconstructing hv-convex polyominoes is provided, which is several orders of
magnitudes faster than the best previously known algorithm from Barcucci et al.
In addition, the problem of reconstructing a special class of centered
hv-convex polyominoes is addressed. (An object is centered if it contains a row
whose length equals the total width of the object). It is shown that in this
case the reconstruction problem can be solved in linear time.


title: Zero-Parity Stabbing Information

abstract:
  Everett et al. introduced several varieties of stabbing information for the
lines determined by pairs of vertices of a simple polygon P, and established
their relationships to vertex visibility and other combinatorial data. In the
same spirit, we define the ``zero-parity (ZP) stabbing information'' to be a
natural weakening of their ``weak stabbing information,'' retaining only the
distinction among {zero, odd, even>0} in the number of polygon edges stabbed.
Whereas the weak stabbing information's relation to visibility remains an open
problem, we completely settle the analogous questions for zero-parity
information, with three results: (1) ZP information is insufficient to
distinguish internal from external visibility graph edges; (2) but it does
suffice for all polygons that avoid a certain complex substructure; and (3) the
natural generalization of ZP information to the continuous case of smooth
curves does distinguish internal from external visibility.


title: Computational Geometry Column 35

abstract:
  The subquadratic algorithm of Kapoor for finding shortest paths on a
polyhedron is described.


title: A decision procedure for well-formed linear quantum cellular automata

abstract:
  In this paper we introduce a new quantum computation model, the linear
quantum cellular automaton. Well-formedness is an essential property for any
quantum computing device since it enables us to define the probability of a
configuration in an observation as the squared magnitude of its amplitude. We
give an efficient algorithm which decides if a linear quantum cellular
automaton is well-formed. The complexity of the algorithm is $O(n^2)$ in the
algebraic model of computation if the input automaton has continuous
neighborhood.


title: Mapping Multilingual Hierarchies Using Relaxation Labeling

abstract:
  This paper explores the automatic construction of a multilingual Lexical
Knowledge Base from pre-existing lexical resources. We present a new and robust
approach for linking already existing lexical/semantic hierarchies. We used a
constraint satisfaction algorithm (relaxation labeling) to select --among all
the candidate translations proposed by a bilingual dictionary-- the right
English WordNet synset for each sense in a taxonomy automatically derived from
a Spanish monolingual dictionary. Although on average, there are 15 possible
WordNet connections for each sense in the taxonomy, the method achieves an
accuracy over 80%. Finally, we also propose several ways in which this
technique could be applied to enrich and improve existing lexical databases.


title: Robust Grammatical Analysis for Spoken Dialogue Systems

abstract:
  We argue that grammatical analysis is a viable alternative to concept
spotting for processing spoken input in a practical spoken dialogue system. We
discuss the structure of the grammar, and a model for robust parsing which
combines linguistic sources of information and statistical sources of
information. We discuss test results suggesting that grammatical processing
allows fast and accurate processing of spoken input.


title: Human-Computer Conversation

abstract:
  The article surveys a little of the history of the technology, sets out the
main current theoretical approaches in brief, and discusses the on-going
opposition between theoretical and empirical approaches. It illustrates the
situation with some discussion of CONVERSE, a system that won the Loebner prize
in 1997 and which displays features of both approaches.


title: On the Power of Positive Turing Reductions

abstract:
  In the early 1980s, Selman's seminal work on positive Turing reductions
showed that positive Turing reduction to NP yields no greater computational
power than NP itself. Thus, positive Turing and Turing reducibility to NP
differ sharply unless the polynomial hierarchy collapses.
  We show that the situation is quite different for DP, the next level of the
boolean hierarchy. In particular, positive Turing reduction to DP already
yields all (and only) sets Turing reducibility to NP. Thus, positive Turing and
Turing reducibility to DP yield the same class. Additionally, we show that an
even weaker class, P(NP[1]), can be substituted for DP in this context.


title: Events in Property Patterns

abstract:
  A pattern-based approach to the presentation, codification and reuse of
property specifications for finite-state verification was proposed by Dwyer and
his collegues. The patterns enable non-experts to read and write formal
specifications for realistic systems and facilitate easy conversion of
specifications between formalisms, such as LTL, CTL, QRE. In this paper, we
extend the pattern system with events - changes of values of variables in the
context of LTL.


title: SCR3: towards usability of formal methods

abstract:
  This paper gives an overview of SCR3 -- a toolset designed to increase the
usability of formal methods for software development. Formal requirements are
specified in SCR3 in an easy to use and review format, and then used in
checking requirements for correctness and in verifying consistency between
annotated code and requirements.
  In this paper we discuss motivations behind this work, describe several tools
which are part of SCR3, and illustrate their operation on an example of a
Cruise Control system.


title: Events in Linear-Time Properties

abstract:
  For over a decade, researchers in formal methods tried to create formalisms
that permit natural specification of systems and allow mathematical reasoning
about their correctness. The availability of fully-automated reasoning tools
enables more non-specialists to use formal methods effectively --- their
responsibility reduces to just specifying the model and expressing the desired
properties. Thus, it is essential that these properties be represented in a
language that is easy to use and sufficiently expressive.
  Linear-time temporal logic is a formalism that has been extensively used by
researchers for specifying properties of systems. When such properties are
closed under stuttering, i.e. their interpretation is not modified by
transitions that leave the system in the same state, verification tools can
utilize a partial-order reduction technique to reduce the size of the model and
thus analyze larger systems. If LTL formulas do not contain the ``next''
operator, the formulas are closed under stuttering, but the resulting language
is not expressive enough to capture many important properties, e.g., properties
involving events. Determining if an arbitrary LTL formula is closed under
stuttering is hard --- it has been proven to be PSPACE-complete.
  In this paper we relax the restriction on LTL that guarantees closure under
stuttering, introduce the notion of edges in the context of LTL, and provide
theorems that enable syntactic reasoning about closure under stuttering of LTL
formulas.


title: Formal Modeling in a Commercial Setting: A Case Study

abstract:
  This paper describes a case study conducted in collaboration with Nortel to
demonstrate the feasibility of applying formal modeling techniques to
telecommunication systems. A formal description language, SDL, was chosen by
our qualitative CASE tool evaluation to model a multimedia-messaging system
described by an 80-page natural language specification. Our model was used to
identify errors in the software requirements document and to derive test
suites, shadowing the existing development process and keeping track of a
variety of productivity data.


title: Robust Reductions

abstract:
  We continue the study of robust reductions initiated by Gavalda and Balcazar.
In particular, a 1991 paper of Gavalda and Balcazar claimed an optimal
separation between the power of robust and nondeterministic strong reductions.
Unfortunately, their proof is invalid. We re-establish their theorem.
  Generalizing robust reductions, we note that robustly strong reductions are
built from two restrictions, robust underproductivity and robust
overproductivity, both of which have been separately studied before in other
contexts. By systematically analyzing the power of these reductions, we explore
the extent to which each restriction weakens the power of reductions. We show
that one of these reductions yields a new, strong form of the Karp-Lipton
Theorem.


title: A Unified Example-Based and Lexicalist Approach to Machine Translation

abstract:
  We present an approach to Machine Translation that combines the ideas and
methodologies of the Example-Based and Lexicalist theoretical frameworks. The
approach has been implemented in a multilingual Machine Translation system.


title: Setting Parameters by Example

abstract:
  We introduce a class of "inverse parametric optimization" problems, in which
one is given both a parametric optimization problem and a desired optimal
solution; the task is to determine parameter values that lead to the given
solution. We describe algorithms for solving such problems for minimum spanning
trees, shortest paths, and other "optimal subgraph" problems, and discuss
applications in multicast routing, vehicle path planning, resource allocation,
and board game programming.


title:
The Distribution of Cycle Lengths in Graphical Models for Iterative
  Decoding

abstract:
  This paper analyzes the distribution of cycle lengths in turbo decoding and
low-density parity check (LDPC) graphs. The properties of such cycles are of
significant interest in the context of iterative decoding algorithms which are
based on belief propagation or message passing. We estimate the probability
that there exist no simple cycles of length less than or equal to k at a
randomly chosen node in a turbo decoding graph using a combination of counting
arguments and independence assumptions. For large block lengths n, this
probability is approximately e^{-{2^{k-1}-4}/n}, k>=4. Simulation results
validate the accuracy of the various approximations. For example, for turbo
codes with a block length of 64000, a randomly chosen node has a less than 1%
chance of being on a cycle of length less than or equal to 10, but has a
greater than 99.9% chance of being on a cycle of length less than or equal to
20. The effect of the "S-random" permutation is also analyzed and it is shown
that while it eliminates short cycles of length k<8, it does not significantly
affect the overall distribution of cycle lengths. Similar analyses and
simulations are also presented for graphs for LDPC codes. The paper concludes
by commenting briefly on how these results may provide insight into the
practical success of iterative decoding methods.


title:
Annotation graphs as a framework for multidimensional linguistic data
  analysis

abstract:
  In recent work we have presented a formal framework for linguistic annotation
based on labeled acyclic digraphs. These `annotation graphs' offer a simple yet
powerful method for representing complex annotation structures incorporating
hierarchy and overlap. Here, we motivate and illustrate our approach using
discourse-level annotations of text and speech data drawn from the CALLHOME,
COCONUT, MUC-7, DAMSL and TRAINS annotation schemes. With the help of domain
specialists, we have constructed a hybrid multi-level annotation for a fragment
of the Boston University Radio Speech Corpus which includes the following
levels: segment, word, breath, ToBI, Tilt, Treebank, coreference and named
entity. We show how annotation graphs can represent hybrid multi-level
structures which derive from a diverse set of file formats. We also show how
the approach facilitates substantive comparison of multiple annotations of a
single signal based on different theoretical models. The discussion shows how
annotation graphs open the door to wide-ranging integration of tools, formats
and corpora.


title:
MAP Lexicon is useful for segmentation and word discovery in
  child-directed speech

abstract:
  Because of rather fundamental changes to the underlying model proposed in the
paper, it has been withdrawn from the archive.


title:
Alternative Local Discriminant Bases Using Empirical Expectation and
  Variance Estimation

abstract:
  We propose alternative discriminant measures for selecting the best basis
among a large collection of orthonormal bases for classification purposes. A
generalization of the Local Discriminant Basis Algorithm of Saito and Coifman
is constructed. The success of these new methods is evaluated and compared to
earlier methods in experiments.


title: Representing Text Chunks

abstract:
  Dividing sentences in chunks of words is a useful preprocessing step for
parsing, information extraction and information retrieval. (Ramshaw and Marcus,
1995) have introduced a "convenient" data representation for chunking by
converting it to a tagging task. In this paper we will examine seven different
data representations for the problem of recognizing noun phrase chunks. We will
show that the the data representation choice has a minor influence on chunking
performance. However, equipped with the most suitable data representation, our
memory-based learning chunker was able to improve the best published chunking
results for a standard data set.


title: Cross-Language Information Retrieval for Technical Documents

abstract:
  This paper proposes a Japanese/English cross-language information retrieval
(CLIR) system targeting technical documents. Our system first translates a
given query containing technical terms into the target language, and then
retrieves documents relevant to the translated query. The translation of
technical terms is still problematic in that technical terms are often compound
words, and thus new terms can be progressively created simply by combining
existing base words. In addition, Japanese often represents loanwords based on
its phonogram. Consequently, existing dictionaries find it difficult to achieve
sufficient coverage. To counter the first problem, we use a compound word
translation method, which uses a bilingual dictionary for base words and
collocational statistics to resolve translation ambiguity. For the second
problem, we propose a transliteration method, which identifies phonetic
equivalents in the target language. We also show the effectiveness of our
system using a test collection for CLIR.


title: Explanation-based Learning for Machine Translation

abstract:
  In this paper we present an application of explanation-based learning (EBL)
in the parsing module of a real-time English-Spanish machine translation system
designed to translate closed captions. We discuss the efficiency/coverage
trade-offs available in EBL and introduce the techniques we use to increase
coverage while maintaining a high level of space and time efficiency. Our
performance results indicate that this approach is effective.


title:
Designing and Mining Multi-Terabyte Astronomy Archives: The Sloan
  Digital Sky Survey

abstract:
  The next-generation astronomy digital archives will cover most of the
universe at fine resolution in many wave-lengths, from X-rays to ultraviolet,
optical, and infrared. The archives will be stored at diverse geographical
locations. One of the first of these projects, the Sloan Digital Sky Survey
(SDSS) will create a 5-wavelength catalog over 10,000 square degrees of the sky
(see http://www.sdss.org/). The 200 million objects in the multi-terabyte
database will have mostly numerical attributes, defining a space of 100+
dimensions. Points in this space have highly correlated distributions.
  The archive will enable astronomers to explore the data interactively. Data
access will be aided by a multidimensional spatial index and other indices. The
data will be partitioned in many ways. Small tag objects consisting of the most
popular attributes speed up frequent searches. Splitting the data among
multiple servers enables parallel, scalable I/O and applies parallel processing
to the data. Hashing techniques allow efficient clustering and pair-wise
comparison algorithms that parallelize nicely. Randomly sampled subsets allow
debugging otherwise large queries at the desktop. Central servers will operate
a data pump that supports sweeping searches that touch most of the data. The
anticipated queries require special operators related to angular distances and
complex similarity tests of object properties, like shapes, colors, velocity
vectors, or temporal behaviors. These issues pose interesting data management
challenges.


title: Language Identification With Confidence Limits

abstract:
  A statistical classification algorithm and its application to language
identification from noisy input are described. The main innovation is to
compute confidence limits on the classification, so that the algorithm
terminates when enough evidence to make a clear decision has been made, and so
avoiding problems with categories that have similar characteristics. A second
application, to genre identification, is briefly examined. The results show
that some of the problems of other language identification techniques can be
avoided, and illustrate a more important point: that a statistical language
process can be used to provide feedback about its own success rate.


title: Reducing Randomness via Irrational Numbers

abstract:
  We propose a general methodology for testing whether a given polynomial with
integer coefficients is identically zero. The methodology evaluates the
polynomial at efficiently computable approximations of suitable irrational
points. In contrast to the classical technique of DeMillo, Lipton, Schwartz,
and Zippel, this methodology can decrease the error probability by increasing
the precision of the approximations instead of using more random bits.
Consequently, randomized algorithms that use the classical technique can
generally be improved using the new methodology. To demonstrate the
methodology, we discuss two nontrivial applications. The first is to decide
whether a graph has a perfect matching in parallel. Our new NC algorithm uses
fewer random bits while doing less work than the previously best NC algorithm
by Chari, Rohatgi, and Srinivasan. The second application is to test the
equality of two multisets of integers. Our new algorithm improves upon the
previously best algorithms by Blum and Kannan and can speed up their checking
algorithm for sorting programs on a large range of inputs.


title: Selective Magic HPSG Parsing

abstract:
  We propose a parser for constraint-logic grammars implementing HPSG that
combines the advantages of dynamic bottom-up and advanced top-down control. The
parser allows the user to apply magic compilation to specific constraints in a
grammar which as a result can be processed dynamically in a bottom-up and
goal-directed fashion. State of the art top-down processing techniques are used
to deal with the remaining constraints. We discuss various aspects concerning
the implementation of the parser as part of a grammar development system.


title: Corpus Annotation for Parser Evaluation

abstract:
  We describe a recently developed corpus annotation scheme for evaluating
parsers that avoids shortcomings of current methods. The scheme encodes
grammatical relations between heads and dependents, and has been used to mark
up a new public-domain corpus of naturally occurring English text. We show how
the corpus can be used to evaluate the accuracy of a robust parser, and relate
the corpus to extant resources.


title:
No information can be conveyed by certain events: The case of the clever
  widows of Fornicalia and the Stobon Oracle

abstract:
  In this short article, we look at an old logical puzzle, its solution and
proof and discuss some interesting aspects concerning its representation in a
logic programming language like Prolog. We also discuss an intriguing
information theoretic aspect of the puzzle.


title:
Linear-Time Approximation Algorithms for Computing Numerical Summation
  with Provably Small Errors

abstract:
  Given a multiset $X=\{x_1,..., x_n\}$ of real numbers, the {\it
floating-point set summation} problem asks for $S_n=x_1+...+x_n$. Let $E^*_n$
denote the minimum worst-case error over all possible orderings of evaluating
$S_n$. We prove that if $X$ has both positive and negative numbers, it is
NP-hard to compute $S_n$ with the worst-case error equal to $E^*_n$. We then
give the first known polynomial-time approximation algorithm that has a
provably small error for arbitrary $X$. Our algorithm incurs a worst-case error
at most $2(\mix)E^*_n$.\footnote{All logarithms $\log$ in this paper are base
2.} After $X$ is sorted, it runs in O(n) time. For the case where $X$ is either
all positive or all negative, we give another approximation algorithm with a
worst-case error at most $\lceil\log\log n\rceil E^*_n$. Even for unsorted $X$,
this algorithm runs in O(n) time. Previously, the best linear-time
approximation algorithm had a worst-case error at most $\lceil\log n\rceil
E^*_n$, while $E^*_n$ was known to be attainable in $O(n \log n)$ time using
Huffman coding.


title: Microsoft TerraServer: A Spatial Data Warehouse

abstract:
  The TerraServer stores aerial, satellite, and topographic images of the earth
in a SQL database available via the Internet. It is the world's largest online
atlas, combining five terabytes of image data from the United States Geological
Survey (USGS) and SPIN-2. This report describes the system-redesign based on
our experience over the last year. It also reports usage and operations results
over the last year -- over 2 billion web hits and over 20 Terabytes of imagry
served over the Internet. Internet browsers provide intuitive spatial and text
interfaces to the data. Users need no special hardware, software, or knowledge
to locate and browse imagery. This paper describes how terabytes of "Internet
unfriendly" geo-spatial images were scrubbed and edited into hundreds of
millions of "Internet friendly" image tiles and loaded into a SQL data
warehouse. Microsoft TerraServer demonstrates that general-purpose relational
database technology can manage large scale image repositories, and shows that
web browsers can be a good geospatial image presentation system.


title: A Bootstrap Approach to Automatically Generating Lexical Transfer Rules

abstract:
  We describe a method for automatically generating Lexical Transfer Rules
(LTRs) from word equivalences using transfer rule templates. Templates are
skeletal LTRs, unspecified for words. New LTRs are created by instantiating a
template with words, provided that the words belong to the appropriate lexical
categories required by the template. We define two methods for creating an
inventory of templates and using them to generate new LTRs. A simpler method
consists of extracting a finite set of templates from a sample of hand coded
LTRs and directly using them in the generation process. A further method
consists of abstracting over the initial finite set of templates to define
higher level templates, where bilingual equivalences are defined in terms of
correspondences involving phrasal categories. Phrasal templates are then mapped
onto sets of lexical templates with the aid of grammars. In this way an
infinite set of lexical templates is recursively defined. New LTRs are created
by parsing input words, matching a template at the phrasal level and using the
corresponding lexical categories to instantiate the lexical template. The
definition of an infinite set of templates enables the automatic creation of
LTRs for multi-word, non-compositional word equivalences of any cardinality.


title: Hinged Dissection of Polyominoes and Polyforms

abstract:
  A hinged dissection of a set of polygons S is a collection of polygonal
pieces hinged together at vertices that can be folded into any member of S. We
present a hinged dissection of all edge-to-edge gluings of n congruent copies
of a polygon P that join corresponding edges of P. This construction uses kn
pieces, where k is the number of vertices of P. When P is a regular polygon, we
show how to reduce the number of pieces to ceiling(k/2)*(n-1). In particular,
we consider polyominoes (made up of unit squares), polyiamonds (made up of
equilateral triangles), and polyhexes (made up of regular hexagons). We also
give a hinged dissection of all polyabolos (made up of right isosceles
triangles), which do not fall under the general result mentioned above.
Finally, we show that if P can be hinged into Q, then any edge-to-edge gluing
of n congruent copies of P can be hinged into any edge-to-edge gluing of n
congruent copies of Q.


title: A Reasonable C++ Wrappered Java Native Interface

abstract:
  A reasonable C++ Java Native Interface (JNI) technique termed C++ Wrappered
JNI (C++WJ) is presented. The technique simplifies current error-prone JNI
development by wrappering JNI calls. Provided development is done with the aid
of a C++ compiler, C++WJ offers type checking and behind the scenes caching. A
tool (jH) patterned on javah automates the creation of C++WJ classes.
  The paper presents the rationale behind the choices that led to C++WJ.
Handling of Java class and interface hierarchy including Java type downcasts is
discussed. Efficiency considerations in the C++WJ lead to two flavors of C++
classes: jtypes and Jtypes. A jtype is a lightweight less than full wrapper of
a JNI object reference. A Jtype is a heavyweight full wrapper of a JNI object
reference.


title: Generalized linearization in nonlinear modeling of data

abstract:
  The principal innovative idea in this paper is to transform the original
complex nonlinear modeling problem into a combination of linear problem and
very simple nonlinear problems. The key step is the generalized linearization
of nonlinear terms. This paper only presents the introductory strategy of this
methodology. The practical numerical experiments will be provided subsequently.


title:
Architectural Considerations for Conversational Systems -- The
  Verbmobil/INTARC Experience

abstract:
  The paper describes the speech to speech translation system INTARC, developed
during the first phase of the Verbmobil project. The general design goals of
the INTARC system architecture were time synchronous processing as well as
incrementality and interactivity as a means to achieve a higher degree of
robustness and scalability. Interactivity means that in addition to the
bottom-up (in terms of processing levels) data flow the ability to process
top-down restrictions considering the same signal segment for all processing
levels. The construction of INTARC 2.0, which has been operational since fall
1996, followed an engineering approach focussing on the integration of symbolic
(linguistic) and stochastic (recognition) techniques which led to a
generalization of the concept of a ``one pass'' beam search.


title: Weak length induction and slow growing depth boolean circuits

abstract:
  We define a hierarchy of circuit complexity classes LD^i, whose depth are the
inverse of a function in Ackermann hierarchy. Then we introduce extremely weak
versions of length induction and construct a bounded arithmetic theory L^i_2
whose provably total functions exactly correspond to functions computable by
LD^i circuits. Finally, we prove a non-conservation result between L^i_2 and a
weaker theory AC^0CA which corresponds to the class AC^0. Our proof utilizes
KPT witnessing theorem.


title: On Deletion in Delaunay Triangulation

abstract:
  This paper presents how the space of spheres and shelling may be used to
delete a point from a $d$-dimensional triangulation efficiently. In dimension
two, if k is the degree of the deleted vertex, the complexity is O(k log k),
but we notice that this number only applies to low cost operations, while time
consuming computations are only done a linear number of times.
  This algorithm may be viewed as a variation of Heller's algorithm, which is
popular in the geographic information system community. Unfortunately, Heller
algorithm is false, as explained in this paper.


title: Improved Incremental Randomized Delaunay Triangulation

abstract:
  We propose a new data structure to compute the Delaunay triangulation of a
set of points in the plane. It combines good worst case complexity, fast
behavior on real data, and small memory occupation.
  The location structure is organized into several levels. The lowest level
just consists of the triangulation, then each level contains the triangulation
of a small sample of the levels below. Point location is done by marching in a
triangulation to determine the nearest neighbor of the query at that level,
then the march restarts from that neighbor at the level below. Using a small
sample (3%) allows a small memory occupation; the march and the use of the
nearest neighbor to change levels quickly locate the query.


title:
The union of unit balls has quadratic complexity, even if they all
  contain the origin

abstract:
  We provide a lower bound construction showing that the union of unit balls in
three-dimensional space has quadratic complexity, even if they all contain the
origin. This settles a conjecture of Sharir.


title:
Mixing representation levels: The hybrid approach to automatic text
  generation

abstract:
  Natural language generation systems (NLG) map non-linguistic representations
into strings of words through a number of steps using intermediate
representations of various levels of abstraction. Template based systems, by
contrast, tend to use only one representation level, i.e. fixed strings, which
are combined, possibly in a sophisticated way, to generate the final text.
  In some circumstances, it may be profitable to combine NLG and template based
techniques. The issue of combining generation techniques can be seen in more
abstract terms as the issue of mixing levels of representation of different
degrees of linguistic abstraction. This paper aims at defining a reference
architecture for systems using mixed representations. We argue that mixed
representations can be used without abandoning a linguistically grounded
approach to language generation.


title:
The Alma Project, or How First-Order Logic Can Help Us in Imperative
  Programming

abstract:
  The aim of the Alma project is the design of a strongly typed constraint
programming language that combines the advantages of logic and imperative
programming. The first stage of the project was the design and implementation
of Alma-0, a small programming language that provides a support for declarative
programming within the imperative programming framework. It is obtained by
extending a subset of Modula-2 by a small number of features inspired by the
logic programming paradigm. In this paper we discuss the rationale for the
design of Alma-0, the benefits of the resulting hybrid programming framework,
and the current work on adding constraint processing capabilities to the
language. In particular, we discuss the role of the logical and customary
variables, the interaction between the constraint store and the program, and
the need for lists.


title: Further Results on Arithmetic Filters for Geometric Predicates

abstract:
  An efficient technique to solve precision problems consists in using exact
computations. For geometric predicates, using systematically expensive exact
computations can be avoided by the use of filters. The predicate is first
evaluated using rounding computations, and an error estimation gives a
certificate of the validity of the result. In this note, we studies the
statistical efficiency of filters for cosphericity predicate with an assumption
of regular distribution of the points. We prove that the expected value of the
polynomial corresponding to the in sphere test is greater than epsilon with
probability O(epsilon log 1/epsilon) improving the results of a previous paper
by the same authors.


title: A Probabilistic Analysis of the Power of Arithmetic Filters

abstract:
  The assumption of real-number arithmetic, which is at the basis of
conventional geometric algorithms, has been seriously challenged in recent
years, since digital computers do not exhibit such capability.
  A geometric predicate usually consists of evaluating the sign of some
algebraic expression. In most cases, rounded computations yield a reliable
result, but sometimes rounded arithmetic introduces errors which may invalidate
the algorithms. The rounded arithmetic may produce an incorrect result only if
the exact absolute value of the algebraic expression is smaller than some
(small) varepsilon, which represents the largest error that may arise in the
evaluation of the expression. The threshold varepsilon depends on the structure
of the expression and on the adopted computer arithmetic, assuming that the
input operands are error-free.
  A pair (arithmetic engine,threshold) is an "arithmetic filter". In this paper
we develop a general technique for assessing the efficacy of an arithmetic
filter. The analysis consists of evaluating both the threshold and the
probability of failure of the filter.
  To exemplify the approach, under the assumption that the input points be
chosen randomly in a unit ball or unit cube with uniform density, we analyze
the two important predicates "which-side" and "insphere". We show that the
probability that the absolute values of the corresponding determinants be no
larger than some positive value V, with emphasis on small V, is Theta(V) for
the which-side predicate, while for the insphere predicate it is Theta(V^(2/3))
in dimension 1, O(sqrt(V)) in dimension 2, and O(sqrt(V) ln(1/V)) in higher
dimensions. Constants are small, and are given in the paper.


title: Algorithms for Coloring Quadtrees

abstract:
  We describe simple linear time algorithms for coloring the squares of
balanced and unbalanced quadtrees so that no two adjacent squares are given the
same color. If squares sharing sides are defined as adjacent, we color balanced
quadtrees with three colors, and unbalanced quadtrees with four colors; these
results are both tight, as some quadtrees require this many colors. If squares
sharing corners are defined as adjacent, we color balanced or unbalanced
quadtrees with six colors; for some quadtrees, at least five colors are
required.


title: Beta-Skeletons have Unbounded Dilation

abstract:
  A fractal construction shows that, for any beta>0, the beta-skeleton of a
point set can have arbitrarily large dilation. In particular this applies to
the Gabriel graph.


title: Clausal Temporal Resolution

abstract:
  In this article, we examine how clausal resolution can be applied to a
specific, but widely used, non-classical logic, namely discrete linear temporal
logic. Thus, we first define a normal form for temporal formulae and show how
arbitrary temporal formulae can be translated into the normal form, while
preserving satisfiability. We then introduce novel resolution rules that can be
applied to formulae in this normal form, provide a range of examples and
examine the correctness and complexity of this approach is examined and. This
clausal resolution approach. Finally, we describe related work and future
developments concerning this work.


title:
Unambiguous Computation: Boolean Hierarchies and Sparse Turing-Complete
  Sets

abstract:
  It is known that for any class C closed under union and intersection, the
Boolean closure of C, the Boolean hierarchy over C, and the symmetric
difference hierarchy over C all are equal. We prove that these equalities hold
for any complexity class closed under intersection; in particular, they thus
hold for unambiguous polynomial time (UP). In contrast to the NP case, we prove
that the Hausdorff hierarchy and the nested difference hierarchy over UP both
fail to capture the Boolean closure of UP in some relativized worlds.
  Karp and Lipton proved that if nondeterministic polynomial time has sparse
Turing-complete sets, then the polynomial hierarchy collapses. We establish the
first consequences from the assumption that unambiguous polynomial time has
sparse Turing-complete sets: (a) UP is in Low_2, where Low_2 is the second
level of the low hierarchy, and (b) each level of the unambiguous polynomial
hierarchy is contained one level lower in the promise unambiguous polynomial
hierarchy than is otherwise known to be the case.


title: Polynomial-Time Multi-Selectivity

abstract:
  We introduce a generalization of Selman's P-selectivity that yields a more
flexible notion of selectivity, called (polynomial-time) multi-selectivity, in
which the selector is allowed to operate on multiple input strings. Since our
introduction of this class, it has been used to prove the first known (and
optimal) lower bounds for generalized selectivity-like classes in terms of
EL_2, the second level of the extended low hierarchy. We study the resulting
selectivity hierarchy, denoted by SH, which we prove does not collapse. In
particular, we study the internal structure and the properties of SH and
completely establish, in terms of incomparability and strict inclusion, the
relations between our generalized selectivity classes and Ogihara's P-mc
(polynomial-time membership-comparable) classes. Although SH is a strictly
increasing infinite hierarchy, we show that the core results that hold for the
P-selective sets and that prove them structurally simple also hold for SH. In
particular, all sets in SH have small circuits; the NP sets in SH are in Low_2,
the second level of the low hierarchy within NP; and SAT cannot be in SH unless
P = NP. Finally, it is known that P-Sel, the class of P-selective sets, is not
closed under union or intersection. We provide an extended selectivity
hierarchy that is based on SH and that is large enough to capture those
closures of the P-selective sets, and yet, in contrast with the P-mc classes,
is refined enough to distinguish them.


title: Easy Sets and Hard Certificate Schemes

abstract:
  Can easy sets only have easy certificate schemes? In this paper, we study the
class of sets that, for all NP certificate schemes (i.e., NP machines), always
have easy acceptance certificates (i.e., accepting paths) that can be computed
in polynomial time. We also study the class of sets that, for all NP
certificate schemes, infinitely often have easy acceptance certificates.
  In particular, we provide equivalent characterizations of these classes in
terms of relative generalized Kolmogorov complexity, showing that they are
robust. We also provide structural conditions---regarding immunity and class
collapses---that put upper and lower bounds on the sizes of these two classes.
Finally, we provide negative results showing that some of our positive claims
are optimal with regard to being relativizable. Our negative results are proven
using a novel observation: we show that the classical ``wide spacing'' oracle
construction technique yields instant non-bi-immunity results. Furthermore, we
establish a result that improves upon Baker, Gill, and Solovay's classical
result that NP \neq P = NP \cap coNP holds in some relativized world.


title:
Exact Analysis of Dodgson Elections: Lewis Carroll's 1876 Voting System
  is Complete for Parallel Access to NP

abstract:
  In 1876, Lewis Carroll proposed a voting system in which the winner is the
candidate who with the fewest changes in voters' preferences becomes a
Condorcet winner---a candidate who beats all other candidates in pairwise
majority-rule elections. Bartholdi, Tovey, and Trick provided a lower
bound---NP-hardness---on the computational complexity of determining the
election winner in Carroll's system. We provide a stronger lower bound and an
upper bound that matches our lower bound. In particular, determining the winner
in Carroll's system is complete for parallel access to NP, i.e., it is complete
for $\thetatwo$, for which it becomes the most natural complete problem known.
It follows that determining the winner in Carroll's elections is not
NP-complete unless the polynomial hierarchy collapses.


title: Boolean Operations, Joins, and the Extended Low Hierarchy

abstract:
  We prove that the join of two sets may actually fall into a lower level of
the extended low hierarchy than either of the sets. In particular, there exist
sets that are not in the second level of the extended low hierarchy, EL_2, yet
their join is in EL_2. That is, in terms of extended lowness, the join operator
can lower complexity. Since in a strong intuitive sense the join does not lower
complexity, our result suggests that the extended low hierarchy is unnatural as
a complexity measure. We also study the closure properties of EL_ and prove
that EL_2 is not closed under certain Boolean operations. To this end, we
establish the first known (and optimal) EL_2 lower bounds for certain notions
generalizing Selman's P-selectivity, which may be regarded as an interesting
result in its own right.


title: A Second Step Towards Complexity-Theoretic Analogs of Rice's Theorem

abstract:
  Rice's Theorem states that every nontrivial language property of the
recursively enumerable sets is undecidable. Borchert and Stephan initiated the
search for complexity-theoretic analogs of Rice's Theorem. In particular, they
proved that every nontrivial counting property of circuits is UP-hard, and that
a number of closely related problems are SPP-hard.
  The present paper studies whether their UP-hardness result itself can be
improved to SPP-hardness. We show that their UP-hardness result cannot be
strengthened to SPP-hardness unless unlikely complexity class containments
hold. Nonetheless, we prove that every P-constructibly bi-infinite counting
property of circuits is SPP-hard. We also raise their general lower bound from
unambiguous nondeterminism to constant-ambiguity nondeterminism.


title: Raising NP Lower Bounds to Parallel NP Lower Bounds

abstract:
  A decade ago, a beautiful paper by Wagner developed a ``toolkit'' that in
certain cases allows one to prove problems hard for parallel access to NP.
However, the problems his toolkit applies to most directly are not overly
natural. During the past year, problems that previously were known only to be
NP-hard or coNP-hard have been shown to be hard even for the class of sets
solvable via parallel access to NP. Many of these problems are longstanding and
extremely natural, such as the Minimum Equivalent Expression problem (which was
the original motivation for creating the polynomial hierarchy), the problem of
determining the winner in the election system introduced by Lewis Carroll in
1876, and the problem of determining on which inputs heuristic algorithms
perform well. In the present article, we survey this recent progress in raising
lower bounds.


title:
Characterizations of the Existence of Partial and Total One-Way
  Permutations

abstract:
  In this note, we study the easy certificate classes introduced by
Hemaspaandra, Rothe, and Wechsung, with regard to the question of whether or
not surjective one-way functions exist. This is an important open question in
cryptology. We show that the existence of partial one-way permutations can be
characterized by separating P from the class of UP sets that, for all
unambiguous polynomial-time Turing machines accepting them, always have easy
(i.e., polynomial-time computable) certificates. This extends results of
Grollmann and Selman. By Gr\"adel's recent results about one-way functions,
this also links statements about easy certificates of NP sets with statements
in finite model theory. Similarly, there exist surjective poly-one one-way
functions if and only if there is a set L in P such that not all FewP machines
accepting L always have easy certificates. We also establish a condition
necessary and sufficient for the existence of (total) one-way permutations.


title: Restrictive Acceptance Suffices for Equivalence Problems

abstract:
  One way of suggesting that an NP problem may not be NP-complete is to show
that it is in the class UP. We suggest an analogous new approach---weaker in
strength of evidence but more broadly applicable---to suggesting that
concrete~NP problems are not NP-complete. In particular we introduce the class
EP, the subclass of NP consisting of those languages accepted by NP machines
that when they accept always have a number of accepting paths that is a power
of two. Since if any NP-complete set is in EP then all NP sets are in EP, it
follows---with whatever degree of strength one believes that EP differs from
NP---that membership in EP can be viewed as evidence that a problem is not
NP-complete.
  We show that the negation equivalence problem for OBDDs (ordered binary
decision diagrams) and the interchange equivalence problem for 2-dags are in
EP. We also show that for boolean negation the equivalence problem is in
EP^{NP}, thus tightening the existing NP^{NP} upper bound. We show that FewP,
bounded ambiguity polynomial time, is contained in EP, a result that is not
known to follow from the previous SPP upper bound. For the three problems and
classes just mentioned with regard to EP, no proof of membership/containment in
UP is known, and for the problem just mentioned with regard to EP^{NP}, no
proof of membership in UP^{NP} is known. Thus, EP is indeed a tool that gives
evidence against NP-completeness in natural cases where UP cannot currently be
applied.


title:
Raising Reliability of Web Search Tool Research through Replication and
  Chaos Theory

abstract:
  Because the World Wide Web is a dynamic collection of information, the Web
search tools (or "search engines") that index the Web are dynamic. Traditional
information retrieval evaluation techniques may not provide reliable results
when applied to the Web search tools. This study is the result of ten
replications of the classic 1996 Ding and Marchionini Web search tool research.
It explores the effects that replication can have on transforming unreliable
results from one iteration into replicable and therefore reliable results after
multiple iterations.


title:
A simple C++ library for manipulating scientific data sets as structured
  data

abstract:
  Representing scientific data sets efficiently on external storage usually
involves converting them to a byte string representation using specialized
reader/writer routines. The resulting storage files are frequently difficult to
interpret without these specialized routines as they do not contain information
about the logical structure of the data. Avoiding such problems usually
involves heavy-weight data format libraries or data base systems. We present a
simple C++ library that allows to create and access data files that store
structured data. The structure of the data is described by a data type that can
be built from elementary data types (integer and floating-point numbers, byte
strings) and composite data types (arrays, structures, unions). An abstract
data access class presents the data to the application. Different actual data
file structures can be implemented under this layer. This method is
particularly suited to applications that require complex data structures, e.g.
molecular dynamics simulations. Extensions such as late type binding and object
persistence are discussed.


title: Detecting Sub-Topic Correspondence through Bipartite Term Clustering

abstract:
  This paper addresses a novel task of detecting sub-topic correspondence in a
pair of text fragments, enhancing common notions of text similarity. This task
is addressed by coupling corresponding term subsets through bipartite
clustering. The paper presents a cost-based clustering scheme and compares it
with a bipartite version of the single-link method, providing illustrating
results.


title:
After Compilers and Operating Systems : The Third Advance in Application
  Support

abstract:
  After compilers and operating systems, TSIAs are the third advance in
application support. A compiler supports a high level application definition in
a programming language. An operating system supports a high level interface to
the resources used by an application execution. A Task System and Item
Architecture (TSIA) provides an application with a transparent reliable,
distributed, heterogeneous, adaptive, dynamic, real-time, interactive,
parallel, secure or other execution. In addition to supporting the application
execution, a TSIA also supports the application definition. This run-time
support for the definition is complementary to the compile-time support of a
compiler. For example, this allows a language similar to Fortran or C to
deliver features promised by functional computing. While many TSIAs exist, they
previously have not been recognized as such and have served only a particular
type of application. Existing TSIAs and other projects demonstrate that TSIAs
are feasible for most applications. As the next paradigm for application
support, the TSIA simplifies and unifies existing computing practice and
research. By solving many outstanding problems, the TSIA opens many, many new
opportunities for computing.


title: Ununfoldable Polyhedra with Convex Faces

abstract:
  Unfolding a convex polyhedron into a simple planar polygon is a well-studied
problem. In this paper, we study the limits of unfoldability by studying
nonconvex polyhedra with the same combinatorial structure as convex polyhedra.
In particular, we give two examples of polyhedra, one with 24 convex faces and
one with 36 triangular faces, that cannot be unfolded by cutting along edges.
We further show that such a polyhedron can indeed be unfolded if cuts are
allowed to cross faces. Finally, we prove that ``open'' polyhedra with
triangular faces may not be unfoldable no matter how they are cut.


title: Extending the Stable Model Semantics with More Expressive Rules

abstract:
  The rules associated with propositional logic programs and the stable model
semantics are not expressive enough to let one write concise programs. This
problem is alleviated by introducing some new types of propositional rules.
Together with a decision procedure that has been used as a base for an
efficient implementation, the new rules supplant the standard ones in practical
applications of the stable model semantics.


title: Polygonal Chains Cannot Lock in 4D

abstract:
  We prove that, in all dimensions d>=4, every simple open polygonal chain and
every tree may be straightened, and every simple closed polygonal chain may be
convexified. These reconfigurations can be achieved by algorithms that use
polynomial time in the number of vertices, and result in a polynomial number of
``moves.'' These results contrast to those known for d=2, where trees can
``lock,'' and for d=3, where open and closed chains can lock.


title: Computational Geometry Column 36

abstract: Two results in "computational origami" are illustrated.


title: Computational Geometry Column 37

abstract: Open problems from the 15th Annual ACM Symposium on Computational Geometry.


title: Secure Multicast in a WAN

abstract:
  A secure reliable multicast protocol enables a process to send a message to a
group of recipients such that all correct destinations receive the same
message, despite the malicious efforts of fewer than a third of the total
number of processes, including the sender. This has been sh own to be a useful
tool in building secure distributed services, albeit with a cost that typically
grows linearly with the size of the system. For very large networks, for which
this is prohibitive, we present two approaches for reducing the cost: First, we
show a protocol whose cost is on the order of the number of tolerated failures.
Secondly, we show how relaxing the consistency requirement to a probabilistic
guarantee can reduce the associated cost, effectively to a constant.


title: Secure Execution of Java Applets using a Remote Playground

abstract:
  Mobile code presents a number of threats to machines that execute it. We
introduce an approach for protecting machines and the resources they hold from
mobile code, and describe a system based on our approach for protecting host
machines from Java 1.1 applets. In our approach, each Java applet downloaded to
the protected domain is rerouted to a dedicated machine (or set of machines),
the {\em playground}, at which it is executed. Prior to execution the applet is
transformed to use the downloading user's web browser as a graphics terminal
for its input and output, and so the user has the illusion that the applet is
running on her own machine. In reality, however, mobile code runs only in the
sanitized environment of the playground, where user files cannot be mounted and
from which only limited network connections are accepted by machines in the
protected domain. Our playground thus provides a second level of defense
against mobile code that circumvents language-based defenses. The paper
presents the design and implementation of a playground for Java 1.1 applets,
and discusses extensions of it for other forms of mobile code including Java
1.2.


title: On Propagating Updates in a Byzantine Environment

abstract:
  We study how to efficiently diffuse updates to a large distributed system of
data replicas, some of which may exhibit arbitrary (Byzantine) failures. We
assume that strictly fewer than $t$ replicas fail, and that each update is
initially received by at least $t$ correct replicas. The goal is to diffuse
each update to all correct replicas while ensuring that correct replicas accept
no updates generated spuriously by faulty replicas. To achieve reliable
diffusion, each correct replica accepts an update only after receiving it from
at least $t$ others. We provide the first analysis of epidemic-style protocols
for such environments. This analysis is fundamentally different from known
analyses for the benign case due to our treatment of fully Byzantine
failures---which, among other things, precludes the use of digital signatures
for authenticating forwarded updates. We propose two epidemic-style diffusion
algorithms and two measures that characterize the efficiency of diffusion
algorithms in general. We characterize both of our algorithms according to
these measures, and also prove lower bounds with regards to these measures that
show that our algorithms are close to optimal.


title: The Load and Availability of Byzantine Quorum Systems

abstract:
  Replicated services accessed via {\em quorums} enable each access to be
performed at only a subset (quorum) of the servers, and achieve consistency
across accesses by requiring any two quorums to intersect. Recently,
$b$-masking quorum systems, whose intersections contain at least $2b+1$
servers, have been proposed to construct replicated services tolerant of $b$
arbitrary (Byzantine) server failures. In this paper we consider a hybrid fault
model allowing benign failures in addition to the Byzantine ones. We present
four novel constructions for $b$-masking quorum systems in this model, each of
which has optimal {\em load} (the probability of access of the busiest server)
or optimal availability (probability of some quorum surviving failures). To
show optimality we also prove lower bounds on the load and availability of any
$b$-masking quorum system in this model.


title: Safe Deals Between Strangers

abstract:
  E-business, information serving, and ubiquitous computing will create heavy
request traffic from strangers or even incognitos. Such requests must be
managed automatically. Two ways of doing this are well known: giving every
incognito consumer the same treatment, and rendering service in return for
money. However, different behavior will be often wanted, e.g., for a university
library with different access policies for undergraduates, graduate students,
faculty, alumni, citizens of the same state, and everyone else.
  For a data or process server contacted by client machines on behalf of users
not previously known, we show how to provide reliable automatic access
administration conforming to service agreements. Implementations scale well
from very small collections of consumers and producers to immense client/server
networks. Servers can deliver information, effect state changes, and control
external equipment.
  Consumer privacy is easily addressed by the same protocol. We support
consumer privacy, but allow servers to deny their resources to incognitos. A
protocol variant even protects against statistical attacks by consortia of
service organizations.
  One e-commerce application would put the consumer's tokens on a smart card
whose readers are in vending kiosks. In e-business we can simplify supply chain
administration. Our method can also be used in sensitive networks without
introducing new security loopholes.


title: Collective Intelligence for Control of Distributed Dynamical Systems

abstract:
  We consider the El Farol bar problem, also known as the minority game (W. B.
Arthur, ``The American Economic Review'', 84(2): 406--411 (1994), D. Challet
and Y.C. Zhang, ``Physica A'', 256:514 (1998)). We view it as an instance of
the general problem of how to configure the nodal elements of a distributed
dynamical system so that they do not ``work at cross purposes'', in that their
collective dynamics avoids frustration and thereby achieves a provided global
goal. We summarize a mathematical theory for such configuration applicable when
(as in the bar problem) the global goal can be expressed as minimizing a global
energy function and the nodes can be expressed as minimizers of local free
energy functions. We show that a system designed with that theory performs
nearly optimally for the bar problem.

categories: cs.LG adap-org cond-mat cs.AI cs.DC cs.MA nlin.AO


title: An Introduction to Collective Intelligence

abstract:
  This paper surveys the emerging science of how to design a ``COllective
INtelligence'' (COIN). A COIN is a large multi-agent system where:
  (i) There is little to no centralized communication or control; and
  (ii) There is a provided world utility function that rates the possible
histories of the full system.
  In particular, we are interested in COINs in which each agent runs a
reinforcement learning (RL) algorithm. Rather than use a conventional modeling
approach (e.g., model the system dynamics, and hand-tune agents to cooperate),
we aim to solve the COIN design problem implicitly, via the ``adaptive''
character of the RL algorithms of each of the agents. This approach introduces
an entirely new, profound design problem: Assuming the RL algorithms are able
to achieve high rewards, what reward functions for the individual agents will,
when pursued by those agents, result in high world utility? In other words,
what reward functions will best ensure that we do not have phenomena like the
tragedy of the commons, Braess's paradox, or the liquidity trap?
  Although still very young, research specifically concentrating on the COIN
design problem has already resulted in successes in artificial domains, in
particular in packet-routing, the leader-follower problem, and in variants of
Arthur's El Farol bar problem. It is expected that as it matures and draws upon
other disciplines related to COINs, this research will greatly expand the range
of tasks addressable by human engineers. Moreover, in addition to drawing on
them, such a fully developed scie nce of COIN design may provide much insight
into other already established scientific fields, such as economics, game
theory, and population biology.

categories: cs.LG adap-org cond-mat cs.DC cs.MA nlin.AO


title:
Representing Scholarly Claims in Internet Digital Libraries: A Knowledge
  Modelling Approach

abstract:
  This paper is concerned with tracking and interpreting scholarly documents in
distributed research communities. We argue that current approaches to document
description, and current technological infrastructures particularly over the
World Wide Web, provide poor support for these tasks. We describe the design of
a digital library server which will enable authors to submit a summary of the
contributions they claim their documents makes, and its relations to the
literature. We describe a knowledge-based Web environment to support the
emergence of such a community-constructed semantic hypertext, and the services
it could provide to assist the interpretation of an idea or document in the
context of its literature. The discussion considers in detail how the approach
addresses usability issues associated with knowledge structuring environments.


title: Quadrilateral Meshing by Circle Packing

abstract:
  We use circle-packing methods to generate quadrilateral meshes for polygonal
domains, with guaranteed bounds both on the quality and the number of elements.
We show that these methods can generate meshes of several types: (1) the
elements form the cells of a Voronoi diagram, (2) all elements have two
opposite right angles, (3) all elements are kites, or (4) all angles are at
most 120 degrees. In each case the total number of elements is O(n), where n is
the number of input vertices.


title: A Differential Invariant for Zooming

abstract:
  This paper presents an invariant under scaling and linear brightness change.
The invariant is based on differentials and therefore is a local feature.
Rotationally invariant 2-d differential Gaussian operators up to third order
are proposed for the implementation of the invariant. The performance is
analyzed by simulating a camera zoom-out.


title: Construction of regular languages and recognizability of polynomials

abstract:
  A generalization of numeration system in which the set N of the natural
numbers is recognizable by finite automata can be obtained by describing a
lexicographically ordered infinite regular language. Here we show that if P
belonging to Q[x] is a polynomial such that P(N) is a subset of N then we can
construct a numeration system in which the set of representations of P(N) is
regular. The main issue in this construction is to setup a regular language
with a density function equals to P(n+1)-P(n) for n large enough.


title: Emerging Challenges in Computational Topology

abstract:
  Here we present the results of the NSF-funded Workshop on Computational
Topology, which met on June 11 and 12 in Miami Beach, Florida. This report
identifies important problems involving both computation and topology.


title:
Semantic robust parsing for noun extraction from natural language
  queries

abstract:
  This paper describes how robust parsing techniques can be fruitful applied
for building a query generation module which is part of a pipelined NLP
architecture aimed at process natural language queries in a restricted domain.
We want to show that semantic robustness represents a key issue in those NLP
systems where it is more likely to have partial and ill-formed utterances due
to various factors (e.g. noisy environments, low quality of speech recognition
modules, etc...) and where it is necessary to succeed, even if partially, in
extracting some meaningful information.


title: Iterative Deepening Branch and Bound

abstract:
  In tree search problem the best-first search algorithm needs too much of
space . To remove such drawbacks of these algorithms the IDA* was developed
which is both space and time cost efficient. But again IDA* can give an optimal
solution for real valued problems like Flow shop scheduling, Travelling
Salesman and 0/1 Knapsack due to their real valued cost estimates. Thus further
modifications are done on it and the Iterative Deepening Branch and Bound
Search Algorithms is developed which meets the requirements. We have tried
using this algorithm for the Flow Shop Scheduling Problem and have found that
it is quite effective.


title: Convex Tours of Bounded Curvature

abstract:
  We consider the motion planning problem for a point constrained to move along
a smooth closed convex path of bounded curvature. The workspace of the moving
point is bounded by a convex polygon with m vertices, containing an obstacle in
a form of a simple polygon with $n$ vertices. We present an O(m+n) time
algorithm finding the path, going around the obstacle, whose curvature is the
smallest possible.


title: Computing largest circles separating two sets of segments

abstract:
  A circle $C$ separates two planar sets if it encloses one of the sets and its
open interior disk does not meet the other set. A separating circle is a
largest one if it cannot be locally increased while still separating the two
given sets. An Theta(n log n) optimal algorithm is proposed to find all largest
circles separating two given sets of line segments when line segments are
allowed to meet only at their endpoints. In the general case, when line
segments may intersect $\Omega(n^2)$ times, our algorithm can be adapted to
work in O(n alpha(n) log n) time and O(n \alpha(n)) space, where alpha(n)
represents the extremely slowly growing inverse of the Ackermann function.


title: Motion Planning of Legged Robots

abstract:
  We study the problem of computing the free space F of a simple legged robot
called the spider robot. The body of this robot is a single point and the legs
are attached to the body. The robot is subject to two constraints: each leg has
a maximal extension R (accessibility constraint) and the body of the robot must
lie above the convex hull of its feet (stability constraint). Moreover, the
robot can only put its feet on some regions, called the foothold regions. The
free space F is the set of positions of the body of the robot such that there
exists a set of accessible footholds for which the robot is stable. We present
an efficient algorithm that computes F in O(n2 log n) time using O(n2 alpha(n))
space for n discrete point footholds where alpha(n) is an extremely slowly
growing function (alpha(n) <= 3 for any practical value of n). We also present
an algorithm for computing F when the foothold regions are pairwise disjoint
polygons with n edges in total. This algorithm computes F in O(n2 alpha8(n) log
n) time using O(n2 alpha8(n)) space (alpha8(n) is also an extremely slowly
growing function). These results are close to optimal since Omega(n2) is a
lower bound for the size of F.


title: Circular Separability of Polygons

abstract:
  Two planar sets are circularly separable if there exists a circle enclosing
one of the sets and whose open interior disk does not intersect the other set.
  This paper studies two problems related to circular separability. A
linear-time algorithm is proposed to decide if two polygons are circularly
separable. The algorithm outputs the smallest separating circle. The second
problem asks for the largest circle included in a preprocessed, convex polygon,
under some point and/or line constraints. The resulting circle must contain the
query points and it must lie in the halfplanes delimited by the query lines.


title:
Not Just a Matter of Time: Field Differences and the Shaping of
  Electronic Media in Supporting Scientific Communication

abstract:
  The shift towards the use of electronic media in scholarly communication
appears to be an inescapable imperative. However, these shifts are uneven, both
with respect to field and with respect to the form of communication. Different
scientific fields have developed and use distinctly different communicative
forums, both in the paper and electronic arenas, and these forums play
different communicative roles within the field. One common claim is that we are
in the early stages of an electronic revolution, that it is only a matter of
time before other fields catch up with the early adopters, and that all fields
converge on a stable set of electronic forums. A social shaping of technology
(SST) perspective helps us to identify important social forces centered around
disciplinary constructions of trust and of legitimate communication that pull
against convergence. This analysis concludes that communicative plurality and
communicative heterogeneity are durable features of the scholarly landscape,
and that we are likely to see field differences in the use of and meaning
ascribed to communications forums persist, even as overall use of electronic
communications technologies both in science and in society as a whole
increases.


title: The Rough Guide to Constraint Propagation

abstract:
  We provide here a simple, yet very general framework that allows us to
explain several constraint propagation algorithms in a systematic way. In
particular, using the notions commutativity and semi-commutativity, we show how
the well-known AC-3, PC-2, DAC and DPC algorithms are instances of a single
generic algorithm. The work reported here extends and simplifies that of Apt,
cs.AI/9811024.


title:
Automatic Generation of Constraint Propagation Algorithms for Small
  Finite Domains

abstract:
  We study here constraint satisfaction problems that are based on predefined,
explicitly given finite constraints. To solve them we propose a notion of rule
consistency that can be expressed in terms of rules derived from the explicit
representation of the initial constraints.
  This notion of local consistency is weaker than arc consistency for
constraints of arbitrary arity but coincides with it when all domains are unary
or binary. For Boolean constraints rule consistency coincides with the closure
under the well-known propagation rules for Boolean constraints.
  By generalizing the format of the rules we obtain a characterization of arc
consistency in terms of so-called inclusion rules. The advantage of rule
consistency and this rule based characterization of the arc consistency is that
the algorithms that enforce both notions can be automatically generated, as CHR
rules. So these algorithms could be integrated into constraint logic
programming systems such as Eclipse.
  We illustrate the usefulness of this approach to constraint propagation by
discussing the implementations of both algorithms and their use on various
examples, including Boolean constraints, three valued logic of Kleene,
constraints dealing with Waltz's language for describing polyhedreal scenes,
and Allen's qualitative approach to temporal logic.


title: Distributed Algorithms in Multihop Broadcast Networks

abstract:
  Broadcast networks are often used in modern communication systems. A common
broadcast network is a single hop shared media system, where a transmitted
message is heard by all neighbors, such as some LAN networks. In this work we
consider a more complex environment, in which a transmitted message is heard
only by a group of neighbors, such as Ad-Hoc networks, satellite and radio
networks, as well as wireless multistation backbone system for mobile
communication. It is important to design efficient algorithms for such
environments. Our main result is a new Leader Election algorithm, with O(n)
time complexity and O(n*lg(n)) message transmission complexity. Our distributed
solution uses a propagation of information with feedback (PIF) building block
tuned to the broadcast media, and a special counting and joining approach for
the election procedure phase. The latter is required for achieving the linear
time. It is demonstrated that the broadcast model requires solutions which are
different from the known point-to-point model.


title: Certificate Revocation Paradigms

abstract:
  Research in the field of electronic signature confirmation has been active
for some 20 years now. Unfortunately present certificate-based solutions also
come from that age when no-one knew about online data transmission. The
official standardized X.509 framework also depends heavily on offline
operations, one of the most complicated ones being certificate revocation
handling. This is done via huge Certificate Revocation Lists which are both
inconvenient and expencive. Several improvements to these lists are proposed
and in this report we try to analyze them briefly. We conclude that although it
is possible to do better than in the original X.509 setting, none of the
solutions presented this far is good enough.


title: Self-stabilizing mutual exclusion on a ring, even if K=N

abstract:
  We show that, contrary to common belief, Dijkstra's self-stabilizing mutual
exclusion algorithm on a ring [Dij74,Dij82] also stabilizes when the number of
states per node is one less than the number of nodes on the ring.


title: Reasoning About Common Knowledge with Infinitely Many Agents

abstract:
  Complete axiomatizations and exponential-time decision procedures are
provided for reasoning about knowledge and common knowledge when there are
infinitely many agents. The results show that reasoning about knowledge and
common knowledge with infinitely many agents is no harder than when there are
finitely many agents, provided that we can check the cardinality of certain set
differences G - G', where G and G' are sets of agents. Since our complexity
results are independent of the cardinality of the sets G involved, they
represent improvements over the previous results even with the sets of agents
involved are finite. Moreover, our results make clear the extent to which
issues of complexity and completeness depend on how the sets of agents involved
are represented.


title: A decision-theoretic approach to reliable message delivery

abstract:
  We argue that the tools of decision theory need to be taken more seriously in
the specification and analysis of systems. We illustrate this by considering a
simple problem involving reliable communication, showing how considerations of
utility and probability can be used to decide when it is worth sending
heartbeat messages and, if they are sent, how often they should be sent.


title: Least expected cost query optimization: an exercise in utility

abstract:
  We identify two unreasonable, though standard, assumptions made by database
query optimizers that can adversely affect the quality of the chosen evaluation
plans. One assumption is that it is enough to optimize for the expected
case---that is, the case where various parameters (like available memory) take
on their expected value. The other assumption is that the parameters are
constant throughout the execution of the query. We present an algorithm based
on the ``System R''-style query optimization algorithm that does not rely on
these assumptions. The algorithm we present chooses the plan of the least
expected cost instead of the plan of least cost given some fixed value of the
parameters. In execution environments that exhibit a high degree of
variability, our techniques should result in better performance.


title: Finding an ordinary conic and an ordinary hyperplane

abstract:
  Given a finite set of non-collinear points in the plane, there exists a line
that passes through exactly two points. Such a line is called an ordinary line.
An efficient algorithm for computing such a line was proposed by Mukhopadhyay
et al. In this note we extend this result in two directions. We first show how
to use this algorithm to compute an ordinary conic, that is, a conic passing
through exactly five points, assuming that all the points do not lie on the
same conic. Both our proofs of existence and the consequent algorithms are
simpler than previous ones. We next show how to compute an ordinary hyperplane
in three and higher dimensions.


title: Geometric compression for progressive transmission

abstract:
  The compression of geometric structures is a relatively new field of data
compression. Since about 1995, several articles have dealt with the coding of
meshes, using for most of them the following approach: the vertices of the mesh
are coded in an order such that it contains partially the topology of the mesh.
In the same time, some simple rules attempt to predict the position of the
current vertex from the positions of its neighbours that have been previously
coded. In this article, we describe a compression algorithm whose principle is
completely different: the order of the vertices is used to compress their
coordinates, and then the topology of the mesh is reconstructed from the
vertices. This algorithm, particularly suited for terrain models, achieves
compression factors that are slightly greater than those of the currently
available algorithms, and moreover, it allows progressive and interactive
transmission of the meshes.


title: Knowledge in Multi-Agent Systems: Initial Configurations and Broadcast

abstract:
  The semantic framework for the modal logic of knowledge due to Halpern and
Moses provides a way to ascribe knowledge to agents in distributed and
multi-agent systems. In this paper we study two special cases of this
framework: full systems and hypercubes. Both model static situations in which
no agent has any information about another agent's state. Full systems and
hypercubes are an appropriate model for the initial configurations of many
systems of interest. We establish a correspondence between full systems and
hypercube systems and certain classes of Kripke frames. We show that these
classes of systems correspond to the same logic. Moreover, this logic is also
the same as that generated by the larger class of weakly directed frames. We
provide a sound and complete axiomatization, S5WDn, of this logic. Finally, we
show that under certain natural assumptions, in a model where knowledge evolves
over time, S5WDn characterizes the properties of knowledge not just at the
initial configuration, but also at all later configurations. In particular,
this holds for homogeneous broadcast systems, which capture settings in which
agents are initially ignorant of each others local states, operate
synchronously, have perfect recall and can communicate only by broadcasting.


title: Query Order

abstract:
  We study the effect of query order on computational power, and show that
$\pjk$-the languages computable via a polynomial-time machine given one query
to the jth level of the boolean hierarchy followed by one query to the kth
level of the boolean hierarchy-equals $\redttnp{j+2k-1}$ if j is even and k is
odd, and equals $\redttnp{j+2k}$ otherwise. Thus, unless the polynomial
hierarchy collapses, it holds that for each $1\leq j \leq k$: $\pjk = \pkj \iff
(j=k) \lor (j{is even} \land k=j+1)$. We extend our analysis to apply to more
general query classes.


title: Fixed-parameter tractability, definability, and model checking

abstract:
  In this article, we study parameterized complexity theory from the
perspective of logic, or more specifically, descriptive complexity theory.
  We propose to consider parameterized model-checking problems for various
fragments of first-order logic as generic parameterized problems and show how
this approach can be useful in studying both fixed-parameter tractability and
intractability. For example, we establish the equivalence between the
model-checking for existential first-order logic, the homomorphism problem for
relational structures, and the substructure isomorphism problem. Our main
tractability result shows that model-checking for first-order formulas is
fixed-parameter tractable when restricted to a class of input structures with
an excluded minor. On the intractability side, for every t >= 0 we prove an
equivalence between model-checking for first-order formulas with t quantifier
alternations and the parameterized halting problem for alternating Turing
machines with t alternations. We discuss the close connection between this
alternation hierarchy and Downey and Fellows' W-hierarchy.
  On a more abstract level, we consider two forms of definability, called Fagin
definability and slicewise definability, that are appropriate for describing
parameterized problems. We give a characterization of the class FPT of all
fixed-parameter tractable problems in terms of slicewise definability in finite
variable least fixed-point logic, which is reminiscent of the Immerman-Vardi
Theorem characterizing the class PTIME in terms of definability in least
fixed-point logic.


title:
What's Up with Downward Collapse: Using the Easy-Hard Technique to Link
  Boolean and Polynomial Hierarchy Collapses

abstract:
  During the past decade, nine papers have obtained increasingly strong
consequences from the assumption that boolean or bounded-query hierarchies
collapse. The final four papers of this nine-paper progression actually achieve
downward collapse---that is, they show that high-level collapses induce
collapses at (what beforehand were thought to be) lower complexity levels. For
example, for each $k\geq 2$ it is now known that if $\psigkone=\psigktwo$ then
$\ph=\sigmak$. This article surveys the history, the results, and the
technique---the so-called easy-hard method---of these nine papers.


title: R_{1-tt}^{SN}(NP) Distinguishes Robust Many-One and Turing Completeness

abstract:
  Do complexity classes have many-one complete sets if and only if they have
Turing-complete sets? We prove that there is a relativized world in which a
relatively natural complexity class-namely a downward closure of NP, \rsnnp -
has Turing-complete sets but has no many-one complete sets. In fact, we show
that in the same relativized world this class has 2-truth-table complete sets
but lacks 1-truth-table complete sets. As part of the groundwork for our
result, we prove that \rsnnp has many equivalent forms having to do with
ordered and parallel access to $\np$ and $\npinterconp$.


title: An Introduction to Query Order

abstract:
  Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] raised the following
questions: If one is allowed one question to each of two different information
sources, does the order in which one asks the questions affect the class of
problems that one can solve with the given access? If so, which order yields
the greater computational power?
  The answers to these questions have been learned-inasfar as they can be
learned without resolving whether or not the polynomial hierarchy collapses-for
both the polynomial hierarchy and the boolean hierarchy. In the polynomial
hierarchy, query order never matters. In the boolean hierarchy, query order
sometimes does not matter and, unless the polynomial hierarchy collapses,
sometimes does matter. Furthermore, the study of query order has yielded
dividends in seemingly unrelated areas, such as bottleneck computations and
downward translation of equality.
  In this article, we present some of the central results on query order. The
article is written in such a way as to encourage the reader to try his or her
own hand at proving some of these results. We also give literature pointers to
the quickly growing set of related results and applications.


title: Query Order and the Polynomial Hierarchy

abstract:
  Hemaspaandra, Hempel, and Wechsung [cs.CC/9909020] initiated the field of
query order, which studies the ways in which computational power is affected by
the order in which information sources are accessed. The present paper studies,
for the first time, query order as it applies to the levels of the polynomial
hierarchy. We prove that the levels of the polynomial hierarchy are
order-oblivious. Yet, we also show that these ordered query classes form new
levels in the polynomial hierarchy unless the polynomial hierarchy collapses.
We prove that all leaf language classes - and thus essentially all standard
complexity classes - inherit all order-obliviousness results that hold for P.


title: Self-Specifying Machines

abstract:
  We study the computational power of machines that specify their own
acceptance types, and show that they accept exactly the languages that
$\manyonesharp$-reduce to NP sets. A natural variant accepts exactly the
languages that $\manyonesharp$-reduce to P sets. We show that these two classes
coincide if and only if $\psone = \psnnoplusbigohone$, where the latter class
denotes the sets acceptable via at most one question to $\sharpp$ followed by
at most a constant number of questions to $\np$.


title: A Downward Collapse within the Polynomial Hierarchy

abstract:
  Downward collapse (a.k.a. upward separation) refers to cases where the
equality of two larger classes implies the equality of two smaller classes. We
provide an unqualified downward collapse result completely within the
polynomial hierarchy. In particular, we prove that, for k > 2, if $\psigkone =
\psigktwo$ then $\sigmak = \pik = \ph$. We extend this to obtain a more general
downward collapse result.


title: Translating Equality Downwards

abstract:
  Downward translation of equality refers to cases where a collapse of some
pair of complexity classes would induce a collapse of some other pair of
complexity classes that (a priori) one expects are smaller. Recently, the first
downward translation of equality was obtained that applied to the polynomial
hierarchy-in particular, to bounded access to its levels [cs.CC/9910007]. In
this paper, we provide a much broader downward translation that extends not
only that downward translation but also that translation's elegant enhancement
by Buhrman and Fortnow. Our work also sheds light on previous research on the
structure of refined polynomial hierarchies, and strengthens the connection
between the collapse of bounded query hierarchies and the collapse of the
polynomial hierarchy.


title: Locked and Unlocked Polygonal Chains in 3D

abstract:
  In this paper, we study movements of simple polygonal chains in 3D. We say
that an open, simple polygonal chain can be straightened if it can be
continuously reconfigured to a straight sequence of segments in such a manner
that both the length of each link and the simplicity of the chain are
maintained throughout the movement. The analogous concept for closed chains is
convexification: reconfiguration to a planar convex polygon. Chains that cannot
be straightened or convexified are called locked. While there are open chains
in 3D that are locked, we show that if an open chain has a simple orthogonal
projection onto some plane, it can be straightened. For closed chains, we show
that there are unknotted but locked closed chains, and we provide an algorithm
for convexifying a planar simple polygon in 3D. All our algorithms require only
O(n) basic ``moves'' and run in linear time.


title: Communication Complexity Lower Bounds by Polynomials

abstract:
  The quantum version of communication complexity allows the two communicating
parties to exchange qubits and/or to make use of prior entanglement (shared
EPR-pairs). Some lower bound techniques are available for qubit communication
complexity, but except for the inner product function, no bounds are known for
the model with unlimited prior entanglement. We show that the log-rank lower
bound extends to the strongest model (qubit communication + unlimited prior
entanglement). By relating the rank of the communication matrix to properties
of polynomials, we are able to derive some strong bounds for exact protocols.
In particular, we prove both the "log-rank conjecture" and the polynomial
equivalence of quantum and classical communication complexity for various
classes of functions. We also derive some weaker bounds for bounded-error
quantum protocols.


title: A statistical model for word discovery in child directed speech

abstract:
  A statistical model for segmentation and word discovery in child directed
speech is presented. An incremental unsupervised learning algorithm to infer
word boundaries based on this model is described and results of empirical tests
showing that the algorithm is competitive with other models that have been used
for similar tasks are also presented.


title: The Complexity of Temporal Logic over the Reals

abstract:
  It is shown that the decision problem for the temporal logic with until and
since connectives over real-numbers time is PSPACE-complete.


title: Map Graphs

abstract:
  We consider a modified notion of planarity, in which two nations of a map are
considered adjacent when they share any point of their boundaries (not
necessarily an edge, as planarity requires). Such adjacencies define a map
graph. We give an NP characterization for such graphs, and a cubic time
recognition algorithm for a restricted version: given a graph, decide whether
it is realized by adjacencies in a map without holes, in which at most four
nations meet at any point.


title:
Processor Verification Using Efficient Reductions of the Logic of
  Uninterpreted Functions to Propositional Logic

abstract:
  The logic of equality with uninterpreted functions (EUF) provides a means of
abstracting the manipulation of data by a processor when verifying the
correctness of its control logic. By reducing formulas in this logic to
propositional formulas, we can apply Boolean methods such as Ordered Binary
Decision Diagrams (BDDs) and Boolean satisfiability checkers to perform the
verification.
  We can exploit characteristics of the formulas describing the verification
conditions to greatly simplify the propositional formulas generated. In
particular, we exploit the property that many equations appear only in positive
form. We can therefore reduce the set of interpretations of the function
symbols that must be considered to prove that a formula is universally valid to
those that are ``maximally diverse.''
  We present experimental results demonstrating the efficiency of this approach
when verifying pipelined processors using the method proposed by Burch and
Dill.


title: PIPE: Personalizing Recommendations via Partial Evaluation

abstract:
  It is shown that personalization of web content can be advantageously viewed
as a form of partial evaluation --- a technique well known in the programming
languages community. The basic idea is to model a recommendation space as a
program, then partially evaluate this program with respect to user preferences
(and features) to obtain specialized content. This technique supports both
content-based and collaborative approaches, and is applicable to a range of
applications that require automatic information integration from multiple web
sources. The effectiveness of this methodology is illustrated by two example
applications --- (i) personalizing content for visitors to the Blacksburg
Electronic Village (http://www.bev.net), and (ii) locating and selecting
scientific software on the Internet. The scalability of this technique is
demonstrated by its ability to interface with online web ontologies that index
thousands of web pages.


title: Probabilistic Agent Programs

abstract:
  Agents are small programs that autonomously take actions based on changes in
their environment or ``state.'' Over the last few years, there have been an
increasing number of efforts to build agents that can interact and/or
collaborate with other agents. In one of these efforts, Eiter, Subrahmanian amd
Pick (AIJ, 108(1-2), pages 179-255) have shown how agents may be built on top
of legacy code. However, their framework assumes that agent states are
completely determined, and there is no uncertainty in an agent's state. Thus,
their framework allows an agent developer to specify how his agents will react
when the agent is 100% sure about what is true/false in the world state. In
this paper, we propose the concept of a \emph{probabilistic agent program} and
show how, given an arbitrary program written in any imperative language, we may
build a declarative ``probabilistic'' agent program on top of it which supports
decision making in the presence of uncertainty. We provide two alternative
semantics for probabilistic agent programs. We show that the second semantics,
though more epistemically appealing, is more complex to compute. We provide
sound and complete algorithms to compute the semantics of \emph{positive} agent
programs.


title: Finite-resolution hidden surface removal

abstract:
  We propose a hybrid image-space/object-space solution to the classical hidden
surface removal problem: Given n disjoint triangles in Real^3 and p sample
points (``pixels'') in the xy-plane, determine the first triangle directly
behind each pixel. Our algorithm constructs the sampled visibility map of the
triangles with respect to the pixels, which is the subset of the trapezoids in
a trapezoidal decomposition of the analytic visibility map that contain at
least one pixel. The sampled visibility map adapts to local changes in image
complexity, and its complexity is bounded both by the number of pixels and by
the complexity of the analytic visibility map. Our algorithm runs in time
O(n^{1+e} + n^{2/3+e}t^{2/3} + p), where t is the output size and e is any
positive constant. This is nearly optimal in the worst case and compares
favorably with the best output-sensitive algorithms for both ray casting and
analytic hidden surface removal. In the special case where the pixels form a
regular grid, a sweepline variant of our algorithm runs in time O(n^{1+e} +
n^{2/3+e}t^{2/3} + t log p), which is usually sublinear in the number of
pixels.


title: Decoupling Control from Data for TCP Congestion Control

abstract:
  Many applications want to use TCP congestion control to regulate the
transmission rate of a data packet stream. A natural way to achieve this goal
is to transport the data packet stream on a TCP connection. However, because
TCP implements both congestion and error control, transporting a data packet
stream directly using a TCP connection forces the data packet stream to be
subject to TCP's other properties caused by TCP error control, which may be
inappropriate for these applications.
  The TCP decoupling approach proposed in this thesis is a novel way of
applying TCP congestion control to a data packet stream without actually
transporting the data packet stream on a TCP connection. Instead, a TCP
connection using the same network path as the data packet stream is set up
separately and the transmission rate of the data packet stream is then
associated with that of the TCP packets. Since the transmission rate of these
TCP packets is under TCP congestion control, so is that of the data packet
stream. Furthermore, since the data packet stream is not transported on a TCP
connection, the regulated data packet stream is not subject to TCP error
control.
  Because of this flexibility, the TCP decoupling approach opens up many new
opportunities, solves old problems, and improves the performance of some
existing applications. All of these advantages will be demonstrated in the
thesis.
  This thesis presents the design, implementation, and analysis of the TCP
decoupling approach, and its successful applications in TCP trunking, wireless
communication, and multimedia streaming.


title:
Consistent Checkpointing in Distributed Databases: Towards a Formal
  Approach

abstract:
  Whether it is for audit or for recovery purposes, data checkpointing is an
important problem of distributed database systems. Actually, transactions
establish dependence relations on data checkpoints taken by data object
managers. So, given an arbitrary set of data checkpoints (including at least a
single data checkpoint from a data manager, and at most a data checkpoint from
each data manager), an important question is the following one: ``Can these
data checkpoints be members of a same consistent global checkpoint?''. This
paper answers this question by providing a necessary and sufficient condition
suited for database systems. Moreover, to show the usefulness of this
condition, two {\em non-intrusive} data checkpointing protocols are derived
from this condition. It is also interesting to note that this paper, by
exhibiting ``correspondences'', establishes a bridge between the data
object/transaction model and the process/message-passing model.