title: Co-Authorship Networks in the Digital Library Research Community

abstract:
  The field of digital libraries (DLs) coalesced in 1994: the first digital
library conferences were held that year, awareness of the World Wide Web was
accelerating, and the National Science Foundation awarded $24 Million (U.S.)
for the Digital Library Initiative (DLI). In this paper we examine the state of
the DL domain after a decade of activity by applying social network analysis to
the co-authorship network of the past ACM, IEEE, and joint ACM/IEEE digital
library conferences. We base our analysis on a common binary undirectional
network model to represent the co-authorship network, and from it we extract
several established network measures. We also introduce a weighted directional
network model to represent the co-authorship network, for which we define
$AuthorRank$ as an indicator of the impact of an individual author in the
network. The results are validated against conference program committee members
in the same period. The results show clear advantages of PageRank and
AuthorRank over degree, closeness and betweenness centrality metrics. We also
investigate the amount and nature of international participation in Joint
Conference on Digital Libraries (JCDL).


title:
Decomposable Problems, Niching, and Scalability of Multiobjective
  Estimation of Distribution Algorithms

abstract:
  The paper analyzes the scalability of multiobjective estimation of
distribution algorithms (MOEDAs) on a class of boundedly-difficult
additively-separable multiobjective optimization problems. The paper
illustrates that even if the linkage is correctly identified, massive
multimodality of the search problems can easily overwhelm the nicher and lead
to exponential scale-up. Facetwise models are subsequently used to propose a
growth rate of the number of differing substructures between the two objectives
to avoid the niching method from being overwhelmed and lead to polynomial
scalability of MOEDAs.


title: The Complexity of Computing the Size of an Interval

abstract:
  Given a p-order A over a universe of strings (i.e., a transitive, reflexive,
antisymmetric relation such that if (x, y) is an element of A then |x| is
polynomially bounded by |y|), an interval size function of A returns, for each
string x in the universe, the number of strings in the interval between strings
b(x) and t(x) (with respect to A), where b(x) and t(x) are functions that are
polynomial-time computable in the length of x.
  By choosing sets of interval size functions based on feasibility requirements
for their underlying p-orders, we obtain new characterizations of complexity
classes. We prove that the set of all interval size functions whose underlying
p-orders are polynomial-time decidable is exactly #P. We show that the interval
size functions for orders with polynomial-time adjacency checks are closely
related to the class FPSPACE(poly). Indeed, FPSPACE(poly) is exactly the class
of all nonnegative functions that are an interval size function minus a
polynomial-time computable function.
  We study two important functions in relation to interval size functions. The
function #DIV maps each natural number n to the number of nontrivial divisors
of n. We show that #DIV is an interval size function of a polynomial-time
decidable partial p-order with polynomial-time adjacency checks. The function
#MONSAT maps each monotone boolean formula F to the number of satisfying
assignments of F. We show that #MONSAT is an interval size function of a
polynomial-time decidable total p-order with polynomial-time adjacency checks.
  Finally, we explore the related notion of cluster computation.


title:
New approach for Finite Difference Method for Thermal Analysis of
  Passive Solar Systems

abstract:
  Mathematical treatment of massive wall systems is a useful tool for
investigation of these solar applications. The objectives of this work are to
develop (and validate) a numerical solution model for predication the thermal
behaviour of passive solar systems with massive wall, to improve knowledge of
using indirect passive solar systems and assess its energy efficiency according
to climatic conditions in Bulgaria. The problem of passive solar systems with
massive walls is modelled by thermal and mass transfer equations. As a boundary
conditions for the mathematical problem are used equations, which describe
influence of weather data and constructive parameters of building on the
thermal performance of the passive system. The mathematical model is solved by
means of finite differences method and improved solution procedure. In article
are presented results of theoretical and experimental study for developing and
validating a numerical solution model for predication the thermal behaviour of
passive solar systems with massive wall.


title: Perspectives for Strong Artificial Life

abstract:
  This text introduces the twin deadlocks of strong artificial life.
Conceptualization of life is a deadlock both because of the existence of a
continuum between the inert and the living, and because we only know one
instance of life. Computationalism is a second deadlock since it remains a
matter of faith. Nevertheless, artificial life realizations quickly progress
and recent constructions embed an always growing set of the intuitive
properties of life. This growing gap between theory and realizations should
sooner or later crystallize in some kind of paradigm shift and then give clues
to break the twin deadlocks.


title: A Geographic Directed Preferential Internet Topology Model

abstract:
  The goal of this work is to model the peering arrangements between Autonomous
Systems (ASes). Most existing models of the AS-graph assume an undirected
graph. However, peering arrangements are mostly asymmetric Customer-Provider
arrangements, which are better modeled as directed edges. Furthermore, it is
well known that the AS-graph, and in particular its clustering structure, is
influenced by geography.
  We introduce a new model that describes the AS-graph as a directed graph,
with an edge going from the customer to the provider, but also models symmetric
peer-to-peer arrangements, and takes geography into account. We are able to
mathematically analyze its power-law exponent and number of leaves. Beyond the
analysis we have implemented our model as a synthetic network generator we call
GdTang. Experimentation with GdTang shows that the networks it produces are
more realistic than those generated by other network generators, in terms of
its power-law exponent, fractions of customer-provider and symmetric peering
arrangements, and the size of its dense core. We believe that our model is the
first to manifest realistic regional dense cores that have a clear geographic
flavor. Our synthetic networks also exhibit path inflation effects that are
similar to those observed in the real AS graph.


title: Tree Parity Machine Rekeying Architectures

abstract:
  The necessity to secure the communication between hardware components in
embedded systems becomes increasingly important with regard to the secrecy of
data and particularly its commercial use. We suggest a low-cost (i.e. small
logic-area) solution for flexible security levels and short key lifetimes. The
basis is an approach for symmetric key exchange using the synchronisation of
Tree Parity Machines. Fast successive key generation enables a key exchange
within a few milliseconds, given realistic communication channels with a
limited bandwidth. For demonstration we evaluate characteristics of a
standard-cell ASIC design realisation as IP-core in 0.18-micrometer
CMOS-technology.


title:
Nonlinear MMSE Multiuser Detection Based on Multivariate Gaussian
  Approximation

abstract:
  In this paper, a class of nonlinear MMSE multiuser detectors are derived
based on a multivariate Gaussian approximation of the multiple access
interference. This approach leads to expressions identical to those describing
the probabilistic data association (PDA) detector, thus providing an
alternative analytical justification for this structure. A simplification to
the PDA detector based on approximating the covariance matrix of the
multivariate Gaussian distribution is suggested, resulting in a soft
interference cancellation scheme. Corresponding multiuser soft-input,
soft-output detectors delivering extrinsic log-likelihood ratios are derived
for application in iterative multiuser decoders. Finally, a large system
performance analysis is conducted for the simplified PDA, showing that the bit
error rate performance of this detector can be accurately predicted and related
to the replica method analysis for the optimal detector. Methods from
statistical neuro-dynamics are shown to provide a closely related alternative
large system prediction. Numerical results demonstrate that for large systems,
the bit error rate is accurately predicted by the analysis and found to be
close to optimal performance.


title: The Lattice of Machine Invariant Sets and Subword Complexity

abstract:
  We investigate the lattice of machine invariant classes. This is an infinite
completely distributive lattice but it is not a Boolean lattice. We show the
subword complexity and the growth function create machine invariant classes. So
the lattice would serve as a measure of words cryptographic quality if we like
to identify new stream ciphers suitable for widespread adoption.


title: Highly Scalable Algorithms for Robust String Barcoding

abstract:
  String barcoding is a recently introduced technique for genomic-based
identification of microorganisms. In this paper we describe the engineering of
highly scalable algorithms for robust string barcoding. Our methods enable
distinguisher selection based on whole genomic sequences of hundreds of
microorganisms of up to bacterial size on a well-equipped workstation, and can
be easily parallelized to further extend the applicability range to thousands
of bacterial size genomes. Experimental results on both randomly generated and
NCBI genomic data show that whole-genome based selection results in a number of
distinguishers nearly matching the information theoretic lower bounds for the
problem.


title: On the Complexity of Real Functions

abstract:
  We develop a notion of computability and complexity of functions over the
reals, which seems to be very natural when one tries to determine just how
"difficult" a certain function is. This notion can be viewed as an extension of
both BSS computability [Blum, Cucker, Shub, Smale 1998], and bit computability
in the tradition of computable analysis [Weihrauch 2000] as it relies on the
latter but allows some discontinuities and multiple values.


title:
Master Algorithms for Active Experts Problems based on Increasing Loss
  Values

abstract:
  We specify an experts algorithm with the following characteristics: (a) it
uses only feedback from the actions actually chosen (bandit setup), (b) it can
be applied with countably infinite expert classes, and (c) it copes with losses
that may grow in time appropriately slowly. We prove loss bounds against an
adaptive adversary. From this, we obtain master algorithms for "active experts
problems", which means that the master's actions may influence the behavior of
the adversary. Our algorithm can significantly outperform standard experts
algorithms on such problems. Finally, we combine it with a universal expert
class. This results in a (computationally infeasible) universal master
algorithm which performs - in a certain sense - almost as well as any
computable strategy, for any online problem.


title: Limits of Rush Hour Logic Complexity

abstract:
  Rush Hour Logic was introduced in [Flake&Baum99] as a model of computation
inspired by the ``Rush Hour'' toy puzzle, in which cars can move horizontally
or vertically within a parking lot. The authors show how the model supports
polynomial space computation, using certain car configurations as building
blocks to construct boolean circuits for a cpu and memory. They consider the
use of cars of length 3 crucial to their construction, and conjecture that cars
of size 2 only, which we'll call `Size 2 Rush Hour', do not support polynomial
space computation. We settle this conjecture by showing that the required
building blocks are constructible in Size 2 Rush Hour. Furthermore, we consider
Unit Rush Hour, which was hitherto believed to be trivial, show its relation to
maze puzzles, and provide empirical support for its hardness.


title:
Koordinatenfreies Lokationsbewusstsein (Localization without
  Coordinates)

abstract:
  Localization is one of the fundamental issues in sensor networks. It is
almost always assumed that it must be solved by assigning coordinates to the
nodes. This article discusses positioning algorithms from a theoretical,
practical and simulative point of view, and identifies difficulties and
limitations. Ideas for more abstract means of location awareness are presented
and the resulting possible improvements for applications are shown. Nodes with
certain topological or environmental properties are clustered, and the
neighborhood structure of the clusters is modeled as a graph. Eines der
fundamentalen Probleme in Sensornetzwerken besteht darin, ein Bewusstsein fuer
die Position eines Knotens im Netz zu entwickeln. Dabei wird fast immer davon
ausgegangen, dass dies durch die Zuweisung von Koordinaten zu erfolgen hat. In
diesem Artikel wird auf theoretischer, praktischer und simulativer Ebene ein
kritischer Blick auf entsprechende Verfahren geworfen, und es werden Grenzen
aufgezeigt. Es wird ein Ansatz vorgestellt, mit dem in der Zukunft eine
abstrakte Form von Lokationsbewusstsein etabliert werden kann, und es wird
gezeigt, wie Anwendungen dadurch verbessert werden koennen. Er basiert auf
einer graphenbasierten Modellierung des Netzes: Knoten mit bestimmten
topologischen oder Umwelteigenschaften werden zu Clustern zusammengefasst, und
Clusternachbarschaften dann als Graphen modelliert.


title: Bidimensionality, Map Graphs, and Grid Minors

abstract:
  In this paper we extend the theory of bidimensionality to two families of
graphs that do not exclude fixed minors: map graphs and power graphs. In both
cases we prove a polynomial relation between the treewidth of a graph in the
family and the size of the largest grid minor. These bounds improve the running
times of a broad class of fixed-parameter algorithms. Our novel technique of
using approximate max-min relations between treewidth and size of grid minors
is powerful, and we show how it can also be used, e.g., to prove a linear
relation between the treewidth of a bounded-genus graph and the treewidth of
its dual.


title:
Analysis of Second-order Statistics Based Semi-blind Channel Estimation
  in CDMA Channels

abstract:
  The performance of second order statistics (SOS) based semi-blind channel
estimation in long-code DS-CDMA systems is analyzed. The covariance matrix of
SOS estimates is obtained in the large system limit, and is used to analyze the
large-sample performance of two SOS based semi-blind channel estimation
algorithms. A notion of blind estimation efficiency is also defined and is
examined via simulation results.


title: Batch is back: CasJobs, serving multi-TB data on the Web

abstract:
  The Sloan Digital Sky Survey (SDSS) science database describes over 140
million objects and is over 1.5 TB in size. The SDSS Catalog Archive Server
(CAS) provides several levels of query interface to the SDSS data via the
SkyServer website. Most queries execute in seconds or minutes. However, some
queries can take hours or days, either because they require non-index scans of
the largest tables, or because they request very large result sets, or because
they represent very complex aggregations of the data. These "monster queries"
not only take a long time, they also affect response times for everyone else -
one or more of them can clog the entire system. To ameliorate this problem, we
developed a multi-server multi-queue batch job submission and tracking system
for the CAS called CasJobs. The transfer of very large result sets from queries
over the network is another serious problem. Statistics suggested that much of
this data transfer is unnecessary; users would prefer to store results locally
in order to allow further joins and filtering. To allow local analysis, a
system was developed that gives users their own personal databases (MyDB) at
the server side. Users may transfer data to their MyDB, and then perform
further analysis before extracting it to their own machine. MyDB tables also
provide a convenient way to share results of queries with collaborators without
downloading them. CasJobs is built using SOAP XML Web services and has been in
operation since May 2004.


title: A note on the Burrows-Wheeler transformation

abstract:
  We relate the Burrows-Wheeler transformation with a result in combinatorics
on words known as the Gessel-Reutenauer transformation.


title: On sample complexity for computational pattern recognition

abstract:
  In statistical setting of the pattern recognition problem the number of
examples required to approximate an unknown labelling function is linear in the
VC dimension of the target learning class. In this work we consider the
question whether such bounds exist if we restrict our attention to computable
pattern recognition methods, assuming that the unknown labelling function is
also computable. We find that in this case the number of examples required for
a computable method to approximate the labelling function not only is not
linear, but grows faster (in the VC dimension of the class) than any computable
function. No time or space constraints are put on the predictors or target
functions; the only resource we consider is the training examples.
  The task of pattern recognition is considered in conjunction with another
learning problem -- data compression. An impossibility result for the task of
data compression allows us to estimate the sample complexity for pattern
recognition.


title:
How far will you walk to find your shortcut: Space Efficient Synopsis
  Construction Algorithms

abstract:
  In this paper we consider the wavelet synopsis construction problem without
the restriction that we only choose a subset of coefficients of the original
data. We provide the first near optimal algorithm. We arrive at the above
algorithm by considering space efficient algorithms for the restricted version
of the problem. In this context we improve previous algorithms by almost a
linear factor and reduce the required space to almost linear. Our techniques
also extend to histogram construction, and improve the space-running time
tradeoffs for V-Opt and range query histograms. We believe the idea applies to
a broad range of dynamic programs and demonstrate it by showing improvements in
a knapsack-like setting seen in construction of Extended Wavelets.


title: Learning nonsingular phylogenies and hidden Markov models

abstract:
  In this paper we study the problem of learning phylogenies and hidden Markov
models. We call a Markov model nonsingular if all transition matrices have
determinants bounded away from 0 (and 1). We highlight the role of the
nonsingularity condition for the learning problem. Learning hidden Markov
models without the nonsingularity condition is at least as hard as learning
parity with noise, a well-known learning problem conjectured to be
computationally hard. On the other hand, we give a polynomial-time algorithm
for learning nonsingular phylogenies and hidden Markov models.

categories: cs.LG cs.CE math.PR math.ST q-bio.PE stat.TH


title:
On the Achievable Information Rates of Finite-State Input
  Two-Dimensional Channels with Memory

abstract:
  The achievable information rate of finite-state input two-dimensional (2-D)
channels with memory is an open problem, which is relevant, e.g., for
inter-symbol-interference (ISI) channels and cellular multiple-access channels.
We propose a method for simulation-based computation of such information rates.
We first draw a connection between the Shannon-theoretic information rate and
the statistical mechanics notion of free energy. Since the free energy of such
systems is intractable, we approximate it using the cluster variation method,
implemented via generalized belief propagation. The derived, fully tractable,
algorithm is shown to provide a practically accurate estimate of the
information rate. In our experimental study we calculate the information rates
of 2-D ISI channels and of hexagonal Wyner cellular networks with binary
inputs, for which formerly only bounds were known.


title:
Semantical Characterizations and Complexity of Equivalences in Answer
  Set Programming

abstract:
  In recent research on non-monotonic logic programming, repeatedly strong
equivalence of logic programs P and Q has been considered, which holds if the
programs P union R and Q union R have the same answer sets for any other
program R. This property strengthens equivalence of P and Q with respect to
answer sets (which is the particular case for R is the empty set), and has its
applications in program optimization, verification, and modular logic
programming. In this paper, we consider more liberal notions of strong
equivalence, in which the actual form of R may be syntactically restricted. On
the one hand, we consider uniform equivalence, where R is a set of facts rather
than a set of rules. This notion, which is well known in the area of deductive
databases, is particularly useful for assessing whether programs P and Q are
equivalent as components of a logic program which is modularly structured. On
the other hand, we consider relativized notions of equivalence, where R ranges
over rules over a fixed alphabet, and thus generalize our results to
relativized notions of strong and uniform equivalence. For all these notions,
we consider disjunctive logic programs in the propositional (ground) case, as
well as some restricted classes, provide semantical characterizations and
analyze the computational complexity. Our results, which naturally extend to
answer set semantics for programs with strong negation, complement the results
on strong equivalence of logic programs and pave the way for optimizations in
answer set solvers as a tool for input-based problem solving.


title: Multilevel expander codes

abstract:
  We define multilevel codes on bipartite graphs that have properties analogous
to multilevel serial concatenations. A decoding algorithm is described that
corrects a proportion of errors equal to half the Blokh-Zyablov bound on the
minimum distance. The error probability of this algorithm has exponent similar
to that of serially concatenated multilevel codes.


title:
Sensor Configuration and Activation for Field Detection in Large Sensor
  Arrays

abstract:
  The problems of sensor configuration and activation for the detection of
correlated random fields using large sensor arrays are considered. Using
results that characterize the large-array performance of sensor networks in
this application, the detection capabilities of different sensor configurations
are analyzed and compared. The dependence of the optimal choice of
configuration on parameters such as sensor signal-to-noise ratio (SNR), field
correlation, etc., is examined, yielding insights into the most effective
choices for sensor selection and activation in various operating regimes.


title: Tables, Memorized Semirings and Applications

abstract:
  We define and construct a new data structure, the tables, this structure
generalizes the (finite) $k$-sets sets of Eilenberg \cite{Ei}, it is versatile
(one can vary the letters, the words and the coefficients). We derive from this
structure a new semiring (with several semiring structures) which can be
applied to the needs of automatic processing multi-agents behaviour problems.
The purpose of this account/paper is to present also the basic elements of this
new structures from a combinatorial point of view. These structures present a
bunch of properties. They will be endowed with several laws namely : Sum,
Hadamard product, Cauchy product, Fuzzy operations (min, max, complemented
product) Two groups of applications are presented. The first group is linked to
the process of "forgetting" information in the tables. The second, linked to
multi-agent systems, is announced by showing a methodology to manage emergent
organization from individual behaviour models.


title: Graphs and colorings for answer set programming

abstract:
  We investigate the usage of rule dependency graphs and their colorings for
characterizing and computing answer sets of logic programs. This approach
provides us with insights into the interplay between rules when inducing answer
sets. We start with different characterizations of answer sets in terms of
totally colored dependency graphs that differ in graph-theoretical aspects. We
then develop a series of operational characterizations of answer sets in terms
of operators on partial colorings. In analogy to the notion of a derivation in
proof theory, our operational characterizations are expressed as
(non-deterministically formed) sequences of colorings, turning an uncolored
graph into a totally colored one. In this way, we obtain an operational
framework in which different combinations of operators result in different
formal properties. Among others, we identify the basic strategy employed by the
noMoRe system and justify its algorithmic approach. Furthermore, we distinguish
operations corresponding to Fitting's operator as well as to well-founded
semantics. (To appear in Theory and Practice of Logic Programming (TPLP))


title: Impulse Radio Systems with Multiple Types of Ultra-Wideband Pulses

abstract:
  Spectral properties and performance of multi-pulse impulse radio
ultra-wideband systems with pulse-based polarity randomization are analyzed.
Instead of a single type of pulse transmitted in each frame, multiple types of
pulses are considered, which is shown to reduce the effects of multiple-access
interference. First, the spectral properties of a multi-pulse impulse radio
system is investigated. It is shown that the power spectral density is the
average of spectral contents of different pulse shapes. Then, approximate
closed-form expressions for bit error probability of a multi-pulse impulse
radio system are derived for RAKE receivers in asynchronous multiuser
environments. The theoretical and simulation results indicate that impulse
radio systems that are more robust against multiple-access interference than a
"classical" impulse radio system can be designed with multiple types of
ultra-wideband pulses.


title: On the Typicality of the Linear Code Among the LDPC Coset Code Ensemble

abstract:
  Density evolution (DE) is one of the most powerful analytical tools for
low-density parity-check (LDPC) codes on memoryless
binary-input/symmetric-output channels. The case of non-symmetric channels is
tackled either by the LDPC coset code ensemble (a channel symmetrizing
argument) or by the generalized DE for linear codes on non-symmetric channels.
Existing simulations show that the bit error rate performances of these two
different approaches are nearly identical. This paper explains this phenomenon
by proving that as the minimum check node degree $d_c$ becomes sufficiently
large, the performance discrepancy of the linear and the coset LDPC codes is
theoretically indistinguishable. This typicality of linear codes among the LDPC
coset code ensemble provides insight into the concentration theorem of LDPC
coset codes.


title: Fast generation of random connected graphs with prescribed degrees

abstract:
  We address here the problem of generating random graphs uniformly from the
set of simple connected graphs having a prescribed degree sequence. Our goal is
to provide an algorithm designed for practical use both because of its ability
to generate very large graphs (efficiency) and because it is easy to implement
(simplicity). We focus on a family of heuristics for which we prove optimality
conditions, and show how this optimality can be reached in practice. We then
propose a different approach, specifically designed for typical real-world
degree distributions, which outperforms the first one. Assuming a conjecture
which we state and argue rigorously, we finally obtain an log-linear algorithm,
which, in spite of being very simple, improves the best known complexity.


title: The Self-Organization of Speech Sounds

abstract:
  The speech code is a vehicle of language: it defines a set of forms used by a
community to carry information. Such a code is necessary to support the
linguistic interactions that allow humans to communicate. How then may a speech
code be formed prior to the existence of linguistic interactions? Moreover, the
human speech code is discrete and compositional, shared by all the individuals
of a community but different across communities, and phoneme inventories are
characterized by statistical regularities. How can a speech code with these
properties form? We try to approach these questions in the paper, using the
"methodology of the artificial". We build a society of artificial agents, and
detail a mechanism that shows the formation of a discrete speech code without
pre-supposing the existence of linguistic capacities or of coordinated
interactions. The mechanism is based on a low-level model of sensory-motor
interactions. We show that the integration of certain very simple and non
language-specific neural devices leads to the formation of a speech code that
has properties similar to the human speech code. This result relies on the
self-organizing properties of a generic coupling between perception and
production within agents, and on the interactions between agents. The
artificial system helps us to develop better intuitions on how speech might
have appeared, by showing how self-organization might have helped natural
selection to find speech.


title: Self-Replicating Strands that Self-Assemble into User-Specified Meshes

abstract:
  It has been argued that a central objective of nanotechnology is to make
products inexpensively, and that self-replication is an effective approach to
very low-cost manufacturing. The research presented here is intended to be a
step towards this vision. In previous work (JohnnyVon 1.0), we simulated
machines that bonded together to form self-replicating strands. There were two
types of machines (called types 0 and 1), which enabled strands to encode
arbitrary bit strings. However, the information encoded in the strands had no
functional role in the simulation. The information was replicated without being
interpreted, which was a significant limitation for potential manufacturing
applications. In the current work (JohnnyVon 2.0), the information in a strand
is interpreted as instructions for assembling a polygonal mesh. There are now
four types of machines and the information encoded in a strand determines how
it folds. A strand may be in an unfolded state, in which the bonds are straight
(although they flex slightly due to virtual forces acting on the machines), or
in a folded state, in which the bond angles depend on the types of machines. By
choosing the sequence of machine types in a strand, the user can specify a
variety of polygonal shapes. A simulation typically begins with an initial
unfolded seed strand in a soup of unbonded machines. The seed strand replicates
by bonding with free machines in the soup. The child strands fold into the
encoded polygonal shape, and then the polygons drift together and bond to form
a mesh. We demonstrate that a variety of polygonal meshes can be manufactured
in the simulation, by simply changing the sequence of machine types in the
seed.


title: Towards a Systematic Account of Different Semantics for Logic Programs

abstract:
  In [Hitzler and Wendt 2002, 2005], a new methodology has been proposed which
allows to derive uniform characterizations of different declarative semantics
for logic programs with negation. One result from this work is that the
well-founded semantics can formally be understood as a stratified version of
the Fitting (or Kripke-Kleene) semantics. The constructions leading to this
result, however, show a certain asymmetry which is not readily understood. We
will study this situation here with the result that we will obtain a coherent
picture of relations between different semantics for normal logic programs.


title: The QuarkNet/Grid Collaborative Learning e-Lab

abstract:
  We describe a case study that uses grid computing techniques to support the
collaborative learning of high school students investigating cosmic rays.
Students gather and upload science data to our e-Lab portal. They explore those
data using techniques from the GriPhyN collaboration. These techniques include
virtual data transformations, workflows, metadata cataloging and indexing, data
product provenance and persistence, as well as job planners. Students use web
browsers and a custom interface that extends the GriPhyN Chiron portal to
perform all of these tasks. They share results in the form of online posters
and ask each other questions in this asynchronous environment. Students can
discover and extend the research of other students, modeling the processes of
modern large-scale scientific collaborations. Also, the e-Lab portal provides
tools for teachers to guide student work throughout an investigation.
http://quarknet.uchicago.edu/elab/cosmic


title: UNICORE - From Project Results to Production Grids

abstract:
  The UNICORE Grid-technology provides a seamless, secure and intuitive access
to distributed Grid resources. In this paper we present the recent evolution
from project results to production Grids. At the beginning UNICORE was
developed as a prototype software in two projects funded by the German research
ministry (BMBF). Over the following years, in various European-funded projects,
UNICORE evolved to a full-grown and well-tested Grid middleware system, which
today is used in daily production at many supercomputing centers worldwide.
Beyond this production usage, the UNICORE technology serves as a solid basis in
many European and International research projects, which use existing UNICORE
components to implement advanced features, high level services, and support for
applications from a growing range of domains. In order to foster these ongoing
developments, UNICORE is available as open source under BSD licence at
SourceForge, where new releases are published on a regular basis. This paper is
a review of the UNICORE achievements so far and gives a glimpse on the UNICORE
roadmap.


title: An Audit Logic for Accountability

abstract:
  We describe and implement a policy language. In our system, agents can
distribute data along with usage policies in a decentralized architecture. Our
language supports the specification of conditions and obligations, and also the
possibility to refine policies. In our framework, the compliance with usage
policies is not actively enforced. However, agents are accountable for their
actions, and may be audited by an authority requiring justifications.


title: Divergence-free Wavelets for Navier-Stokes

abstract:
  In this paper, we investigate the use of compactly supported divergence-free
wavelets for the representation of the Navier-Stokes solution. After reminding
the theoretical construction of divergence-free wavelet vectors, we present in
detail the bases and corresponding fast algorithms for 2D and 3D incompressible
flows. In order to compute the nonlinear term, we propose a new method which
provides in practice with the Hodge decomposition of any flow: this
decomposition enables us to separate the incompressible part of the flow from
its orthogonal complement, which corresponds to the gradient component of the
flow. Finally we show numerical tests to validate our approach.


title: Online Permutation Routing in Partitioned Optical Passive Star Networks

abstract:
  This paper establishes the state of the art in both deterministic and
randomized online permutation routing in the POPS network. Indeed, we show that
any permutation can be routed online on a POPS network either with
$O(\frac{d}{g}\log g)$ deterministic slots, or, with high probability, with
$5c\lceil d/g\rceil+o(d/g)+O(\log\log g)$ randomized slots, where constant
$c=\exp (1+e^{-1})\approx 3.927$. When $d=\Theta(g)$, that we claim to be the
"interesting" case, the randomized algorithm is exponentially faster than any
other algorithm in the literature, both deterministic and randomized ones. This
is true in practice as well. Indeed, experiments show that it outperforms its
rivals even starting from as small a network as a POPS(2,2), and the gap grows
exponentially with the size of the network. We can also show that, under proper
hypothesis, no deterministic algorithm can asymptotically match its
performance.


title:
Coalition Formation: Concessions, Task Relationships and Complexity
  Reduction

abstract:
  Solutions to the coalition formation problem commonly assume agent
rationality and, correspondingly, utility maximization. This in turn may
prevent agents from making compromises. As shown in recent studies, compromise
may facilitate coalition formation and increase agent utilities. In this study
we leverage on those new results. We devise a novel coalition formation
mechanism that enhances compromise. Our mechanism can utilize information on
task dependencies to reduce formation complexity. Further, it works well with
both cardinal and ordinal task values. Via experiments we show that the use of
the suggested compromise-based coalition formation mechanism provides
significant savings in the computation and communication complexity of
coalition formation. Our results also show that when information on task
dependencies is used, the complexity of coalition formation is further reduced.
We demonstrate successful use of the mechanism for collaborative information
filtering, where agents combine linguistic rules to analyze documents'
contents.


title: Gradient Vector Flow Models for Boundary Extraction in 2D Images

abstract:
  The Gradient Vector Flow (GVF) is a vector diffusion approach based on
Partial Differential Equations (PDEs). This method has been applied together
with snake models for boundary extraction medical images segmentation. The key
idea is to use a diffusion-reaction PDE to generate a new external force field
that makes snake models less sensitivity to initialization as well as improves
the snake's ability to move into boundary concavities. In this paper, we
firstly review basic results about convergence and numerical analysis of usual
GVF schemes. We point out that GVF presents numerical problems due to
discontinuities image intensity. This point is considered from a practical
viewpoint from which the GVF parameters must follow a relationship in order to
improve numerical convergence. Besides, we present an analytical analysis of
the GVF dependency from the parameters values. Also, we observe that the method
can be used for multiply connected domains by just imposing the suitable
boundary condition. In the experimental results we verify these theoretical
points and demonstrate the utility of GVF on a segmentation approach that we
have developed based on snakes.


title:
Property analysis of symmetric travelling salesman problem instances
  acquired through evolution

abstract:
  We show how an evolutionary algorithm can successfully be used to evolve a
set of difficult to solve symmetric travelling salesman problem instances for
two variants of the Lin-Kernighan algorithm. Then we analyse the instances in
those sets to guide us towards deferring general knowledge about the efficiency
of the two variants in relation to structural properties of the symmetric
travelling sale sman problem.


title:
Top-Down Unsupervised Image Segmentation (it sounds like oxymoron, but
  actually it is not)

abstract:
  Pattern recognition is generally assumed as an interaction of two inversely
directed image-processing streams: the bottom-up information details gathering
and localization (segmentation) stream, and the top-down information features
aggregation, association and interpretation (recognition) stream. Inspired by
recent evidence from biological vision research and by the insights of
Kolmogorov Complexity theory, we propose a new, just top-down evolving,
procedure of initial image segmentation. We claim that traditional top-down
cognitive reasoning, which is supposed to guide the segmentation process to its
final result, is not at all a part of the image information content evaluation.
And that initial image segmentation is certainly an unsupervised process. We
present some illustrative examples, which support our claims.


title:
Local and Global Analysis: Complementary Activities for Increasing the
  Effectiveness of Requirements Verification and Validation

abstract:
  This paper presents a unique approach to connecting requirements engineering
(RE) activities into a process framework that can be employed to obtain quality
requirements with reduced expenditures of effort and cost. We propose a
two-phase model that is novel in that it introduces the concept of verification
and validation (V&V) early in the requirements life cycle. In the first phase,
we perform V&V immediately following the elicitation of requirements for each
individually distinct system function. Because the first phase focuses on
capturing smaller sets of related requirements iteratively, each corresponding
V&V activity is better focused for detecting and correcting errors in each
requirement set. In the second phase, a complementary verification activity is
initiated; the corresponding focus is on the quality of linkages between
requirements sets rather than on the requirements within the sets.
Consequently, this approach reduces the effort in verification and enhances the
focus on the verification task. Our approach, unlike other models, has a
minimal time delay between the elicitation of requirements and the execution of
the V&V activities. Because of this short time gap, the stakeholders have a
clearer recollection of the requirements, their context and rationale; this
enhances the stakeholder feedback. Furthermore, our model includes activities
that closely align with the effective RE processes employed in the software
industry. Thus, our approach facilitates a better understanding of the flow of
requirements, and provides guidance for the implementation of the RE process.


title:
An Objectives-Driven Process for Selecting Methods to Support
  Requirements Engineering Activities

abstract:
  This paper presents a framework that guides the requirements engineer in the
implementation and execution of an effective requirements generation process.
We achieve this goal by providing a well-defined requirements engineering model
and a criteria based process for optimizing method selection for attendant
activities. Our model, unlike other models, addresses the complete requirements
generation process and consists of activities defined at more adequate levels
of abstraction. Additionally, activity objectives are identified and explicitly
stated - not implied as in the current models. Activity objectives are crucial
as they drive the selection of methods for each activity. Our model also
incorporates a unique approach to verification and validation that enhances
quality and reduces the cost of generating requirements. To assist in the
selection of methods, we have mapped commonly used methods to activities based
on their objectives. In addition, we have identified method selection criteria
and prescribed a reduced set of methods that optimize these criteria for each
activity defined by our requirements generation process. Thus, the defined
approach assists in the task of selecting methods by using selection criteria
to reduce a large collection of potential methods to a smaller, manageable set.
The model and the set of methods, taken together, provide the much needed
guidance for the effective implementation and execution of the requirements
generation process.


title:
Effective Requirements Generation: Synchronizing Early Verification &
  Validation, Methods and Method Selection Criteria

abstract:
  This paper presents an approach for the implementation and execution of an
effective requirements generation process. We achieve this goal by providing a
well-defined requirements engineering model that includes verification and
validation (V&V), and analysis. In addition, we identify focused activity
objectives and map popular methods to lower-level activities, and define a
criterion based process for optimizing method selection for attendant
activities. Our model, unlike other models, addresses the complete requirements
generation process and consists of activities defined at more adequate levels
of abstraction. Furthermore, our model also incorporates a unique approach to
V&V that enhances quality and reduces the cost of generating requirements.
Additionally, activity objectives are identified and explicitly stated - not
implied as in the current models. To assist in the selection of an appropriate
set of methods, we have mapped commonly used methods to activities based on
their objectives. Finally, we have identified method selection criteria and
prescribed a reduced set of methods that optimize these criteria for each
activity in our model. Thus, our approach assists in the task of selecting
methods by using selection criteria to reduce a large collection of potential
methods to a smaller, manageable set. The model, clear mapping of methods to
activity objectives, and the criteria based process, taken together, provide
the much needed guidance for the effective implementation and execution of the
requirements generation process.


title:
High efficiency and low absorption Fresnel compound zone plates for hard
  X-ray focusing

abstract:
  Circular and linear zone plates have been fabricated on the surface of
silicon crystals for the energy of 8 keV by electron beam lithography and deep
ion plasma etching methods. Various variants of compound zone plates with
first, second, third diffraction orders have been made. The zone relief height
is about 10 mkm, the outermost zone width of the zone plate is 0.4 mkm. The
experimental testing of the zone plates has been conducted on SPring-8 and ESRF
synchrotron radiation sources. A focused spot size and diffraction efficiency
measured by knife-edge scanning are accordingly 0.5 mkm and 39% for the first
order circular zone plate.


title:
A New Non-Iterative Decoding Algorithm for the Erasure Channel :
  Comparisons with Enhanced Iterative Methods

abstract:
  This paper investigates decoding of binary linear block codes over the binary
erasure channel (BEC). Of the current iterative decoding algorithms on this
channel, we review the Recovery Algorithm and the Guess Algorithm. We then
present a Multi-Guess Algorithm extended from the Guess Algorithm and a new
algorithm -- the In-place Algorithm. The Multi-Guess Algorithm can push the
limit to break the stopping sets. However, the performance of the Guess and the
Multi-Guess Algorithm depend on the parity-check matrix of the code.
Simulations show that we can decrease the frame error rate by several orders of
magnitude using the Guess and the Multi-Guess Algorithms when the parity-check
matrix of the code is sparse. The In-place Algorithm can obtain better
performance even if the parity check matrix is dense. We consider the
application of these algorithms in the implementation of multicast and
broadcast techniques on the Internet. Using these algorithms, a user does not
have to wait until the entire transmission has been received.


title:
Toward alternative metrics of journal impact: A comparison of download
  and citation data

abstract:
  We generated networks of journal relationships from citation and download
data, and determined journal impact rankings from these networks using a set of
social network centrality metrics. The resulting journal impact rankings were
compared to the ISI IF. Results indicate that, although social network metrics
and ISI IF rankings deviate moderately for citation-based journal networks,
they differ considerably for journal networks derived from download data. We
believe the results represent a unique aspect of general journal impact that is
not captured by the ISI IF. These results furthermore raise questions regarding
the validity of the ISI IF as the sole assessment of journal impact, and
suggest the possibility of devising impact metrics based on usage information
in general.


title:
Approximation of dynamical systems using S-systems theory : application
  to biological systems

abstract:
  In this paper we propose a new symbolic-numeric algorithm to find positive
equilibria of a n-dimensional dynamical system. This algorithm implies a
symbolic manipulation of ODE in order to give a local approximation of
differential equations with power-law dynamics (S-systems). A numerical
calculus is then needed to converge towards an equilibrium, giving at the same
time a S-system approximating the initial system around this equilibrium. This
algorithm is applied to a real biological example in 14 dimensions which is a
subsystem of a metabolic pathway in Arabidopsis Thaliana.


title: Minimal chordal sense of direction and circulant graphs

abstract:
  A sense of direction is an edge labeling on graphs that follows a globally
consistent scheme and is known to considerably reduce the complexity of several
distributed problems. In this paper, we study a particular instance of sense of
direction, called a chordal sense of direction (CSD). In special, we identify
the class of k-regular graphs that admit a CSD with exactly k labels (a minimal
CSD). We prove that connected graphs in this class are Hamiltonian and that the
class is equivalent to that of circulant graphs, presenting an efficient
(polynomial-time) way of recognizing it when the graphs' degree k is fixed.


title:
Optimized network structure and routing metric in wireless multihop ad
  hoc communication

abstract:
  Inspired by the Statistical Physics of complex networks, wireless multihop ad
hoc communication networks are considered in abstracted form. Since such
engineered networks are able to modify their structure via topology control, we
search for optimized network structures, which maximize the end-to-end
throughput performance. A modified version of betweenness centrality is
introduced and shown to be very relevant for the respective modeling. The
calculated optimized network structures lead to a significant increase of the
end-to-end throughput. The discussion of the resulting structural properties
reveals that it will be almost impossible to construct these optimized
topologies in a technologically efficient distributive manner. However, the
modified betweenness centrality also allows to propose a new routing metric for
the end-to-end communication traffic. This approach leads to an even larger
increase of throughput capacity and is easily implementable in a
technologically relevant manner.


title:
Shuffling a Stacked Deck: The Case for Partially Randomized Ranking of
  Search Engine Results

abstract:
  In-degree, PageRank, number of visits and other measures of Web page
popularity significantly influence the ranking of search results by modern
search engines. The assumption is that popularity is closely correlated with
quality, a more elusive concept that is difficult to measure directly.
Unfortunately, the correlation between popularity and quality is very weak for
newly-created pages that have yet to receive many visits and/or in-links.
Worse, since discovery of new content is largely done by querying search
engines, and because users usually focus their attention on the top few
results, newly-created but high-quality pages are effectively ``shut out,'' and
it can take a very long time before they become popular.
  We propose a simple and elegant solution to this problem: the introduction of
a controlled amount of randomness into search result ranking methods. Doing so
offers new pages a chance to prove their worth, although clearly using too much
randomness will degrade result quality and annul any benefits achieved. Hence
there is a tradeoff between exploration to estimate the quality of new pages
and exploitation of pages already known to be of high quality. We study this
tradeoff both analytically and via simulation, in the context of an economic
objective function based on aggregate result quality amortized over time. We
show that a modest amount of randomness leads to improved search results.


title:
First-order Complete and Computationally Complete Query Languages for
  Spatio-Temporal Databases

abstract:
  We address a fundamental question concerning spatio-temporal database
systems: ``What are exactly spatio-temporal queries?'' We define
spatio-temporal queries to be computable mappings that are also generic,
meaning that the result of a query may only depend to a limited extent on the
actual internal representation of the spatio-temporal data. Genericity is
defined as invariance under groups of geometric transformations that preserve
certain characteristics of spatio-temporal data (e.g., collinearity, distance,
velocity, acceleration, ...). These groups depend on the notions that are
relevant in particular spatio-temporal database applications.
  These transformations also have the distinctive property that they respect
the monotone and unidirectional nature of time.
  We investigate different genericity classes with respect to the constraint
database model for spatio-temporal databases and we identify sound and complete
languages for the first-order and the computable queries in these genericity
classes. We distinguish between genericity determined by time-invariant
transformations, genericity notions concerning physical quantities and
genericity determined by time-dependent transformations.


title: Pr\'{e}diction de Performances pour les Communications Collectives

abstract:
  Des travaux r\'{e}cents visent l'optimisation des op\'{e}rations de
communication collective dans les environnements de type grille de calcul. La
solution la plus r\'{e}pandue est la s\'{e}paration des communications internes
et externes \`{a} chaque grappe, mais cela n'exclut pas le d\'{e}coupage des
communications en plusieurs couches, pratique efficace d\'{e}montr\'{e}e par
Karonis et al. [10]. Dans les deux cas, la pr\'{e}diction des performances est
un facteur essentiel, soit pour le r\'{e}glage fin des param\`{e}tres de
communication, soit pour le calcul de la distribution et de la hi\'{e}rarchie
des communications. Pour cela, il est tr\`{e}s important d'avoir des
mod\`{e}les pr\'{e}cis des communications collectives, lesquels seront
utilis\'{e}s pour pr\'{e}dire ces performances. Cet article d\'{e}crit notre
exp\'{e}rience sur la mod\'{e}lisation des op\'{e}rations de communication
collective. Nous pr\'{e}sentons des mod\`{e}les de communication pour
diff\'{e}rents patrons de communication collective comme un vers plusieurs, un
vers plusieurs personnalis\'{e} et plusieurs vers plusieurs. Pour \'{e}valuer
la pr\'{e}cision des mod\`{e}les, nous comparons les pr\'{e}dictions obtenues
avec les r\'{e}sultats des exp\'{e}rimentations effectu\'{e}es sur deux
environnements r\'{e}seaux diff\'{e}rents, Fast Ethernet et Myrinet.


title:
ADF95: Tool for automatic differentiation of a FORTRAN code designed for
  large numbers of independent variables

abstract:
  ADF95 is a tool to automatically calculate numerical first derivatives for
any mathematical expression as a function of user defined independent
variables. Accuracy of derivatives is achieved within machine precision. ADF95
may be applied to any FORTRAN 77/90/95 conforming code and requires minimal
changes by the user. It provides a new derived data type that holds the value
and derivatives and applies forward differencing by overloading all FORTRAN
operators and intrinsic functions. An efficient indexing technique leads to a
reduced memory usage and a substantially increased performance gain over other
available tools with operator overloading. This gain is especially pronounced
for sparse systems with large number of independent variables. A wide class of
numerical simulations, e.g., those employing implicit solvers, can profit from
ADF95.


title:
A Systematic Aspect-Oriented Refactoring and Testing Strategy, and its
  Application to JHotDraw

abstract:
  Aspect oriented programming aims at achieving better modularization for a
system's crosscutting concerns in order to improve its key quality attributes,
such as evolvability and reusability. Consequently, the adoption of
aspect-oriented techniques in existing (legacy) software systems is of interest
to remediate software aging. The refactoring of existing systems to employ
aspect-orientation will be considerably eased by a systematic approach that
will ensure a safe and consistent migration.
  In this paper, we propose a refactoring and testing strategy that supports
such an approach and consider issues of behavior conservation and (incremental)
integration of the aspect-oriented solution with the original system. The
strategy is applied to the JHotDraw open source project and illustrated on a
group of selected concerns. Finally, we abstract from the case study and
present a number of generic refactorings which contribute to an incremental
aspect-oriented refactoring process and associate particular types of
crosscutting concerns to the model and features of the employed aspect
language. The contributions of this paper are both in the area of supporting
migration towards aspect-oriented solutions and supporting the development of
aspect languages that are better suited for such migrations.


title:
File-based storage of Digital Objects and constituent datastreams:
  XMLtapes and Internet Archive ARC files

abstract:
  This paper introduces the write-once/read-many XMLtape/ARC storage approach
for Digital Objects and their constituent datastreams. The approach combines
two interconnected file-based storage mechanisms that are made accessible in a
protocol-based manner. First, XML-based representations of multiple Digital
Objects are concatenated into a single file named an XMLtape. An XMLtape is a
valid XML file; its format definition is independent of the choice of the
XML-based complex object format by which Digital Objects are represented. The
creation of indexes for both the identifier and the creation datetime of the
XML-based representation of the Digital Objects facilitates OAI-PMH-based
access to Digital Objects stored in an XMLtape. Second, ARC files, as
introduced by the Internet Archive, are used to contain the constituent
datastreams of the Digital Objects in a concatenated manner. An index for the
identifier of the datastream facilitates OpenURL-based access to an ARC file.
The interconnection between XMLtapes and ARC files is provided by conveying the
identifiers of ARC files associated with an XMLtape as administrative
information in the XMLtape, and by including OpenURL references to constituent
datastreams of a Digital Object in the XML-based representation of that Digital
Object.


title: A Fast Combined Decimal Adder/Subtractor

abstract: This paper has been withdrawn.


title: Probabilistic Algorithmic Knowledge

abstract:
  The framework of algorithmic knowledge assumes that agents use deterministic
knowledge algorithms to compute the facts they explicitly know. We extend the
framework to allow for randomized knowledge algorithms. We then characterize
the information provided by a randomized knowledge algorithm when its answers
have some probability of being incorrect. We formalize this information in
terms of evidence; a randomized knowledge algorithm returning ``Yes'' to a
query about a fact \phi provides evidence for \phi being true. Finally, we
discuss the extent to which this evidence can be used as a basis for decisions.


title: Duality Bounds on the Cut-Off Rate with Applications to Ricean Fading

abstract:
  We propose a technique to derive upper bounds on Gallager's cost-constrained
random coding exponent function. Applying this technique to the non-coherent
peak-power or average-power limited discrete time memoryless Ricean fading
channel, we obtain the high signal-to-noise ratio (SNR) expansion of this
channel's cut-off rate. At high SNR the gap between channel capacity and the
cut-off rate approaches a finite limit. This limit is approximately 0.26 nats
per channel-use for zero specular component (Rayleigh) fading and approaches
0.39 nats per channel-use for very large specular components.
  We also compute the asymptotic cut-off rate of a Rayleigh fading channel when
the receiver has access to some partial side information concerning the fading.
It is demonstrated that the cut-off rate does not utilize the side information
as efficiently as capacity, and that the high SNR gap between the two increases
to infinity as the imperfect side information becomes more and more precise.


title: Earlier Web Usage Statistics as Predictors of Later Citation Impact

abstract:
  The use of citation counts to assess the impact of research articles is well
established. However, the citation impact of an article can only be measured
several years after it has been published. As research articles are
increasingly accessed through the Web, the number of times an article is
downloaded can be instantly recorded and counted. One would expect the number
of times an article is read to be related both to the number of times it is
cited and to how old the article is. This paper analyses how short-term Web
usage impact predicts medium-term citation impact. The physics e-print archive
(arXiv.org) is used to test this.


title:
Fast-Forward on the Green Road to Open Access: The Case Against Mixing
  Up Green and Gold

abstract:
  This article is a critique of: "The 'Green' and 'Gold' Roads to Open Access:
The Case for Mixing and Matching" by Jean-Claude Guedon (in Serials Review
30(4) 2004).
  Open Access (OA) means: free online access to all peer-reviewed journal
articles. Jean-Claude Guedon argues against the efficacy of author
self-archiving of peer-reviewed journal articles (the "Green" road to OA). He
suggests instead that we should convert to Open Access Publishing (the "Golden"
road to OA) by "mixing and matching" Green and Gold as follows: o First,
self-archive dissertations (not published, peer-reviewed journal articles). o
Second, identify and tag how those dissertations have been evaluated and
reviewed. o Third, self-archive unrefereed preprints (not published,
peer-reviewed journal articles). o Fourth, develop new mechanisms for
evaluating and reviewing those unrefereed preprints, at multiple levels. The
result will be OA Publishing (Gold). I argue that rather than yet another 10
years of speculation like this, what is actually needed (and imminent) is for
OA self-archiving to be mandated by research funders and institutions so that
the self-archiving of published, peer-reviewed journal articles (Green) can be
fast-forwarded to 100% OA.


title: Theory and Practice of Transactional Method Caching

abstract:
  Nowadays, tiered architectures are widely accepted for constructing large
scale information systems. In this context application servers often form the
bottleneck for a system's efficiency. An application server exposes an object
oriented interface consisting of set of methods which are accessed by
potentially remote clients. The idea of method caching is to store results of
read-only method invocations with respect to the application server's interface
on the client side. If the client invokes the same method with the same
arguments again, the corresponding result can be taken from the cache without
contacting the server. It has been shown that this approach can considerably
improve a real world system's efficiency.
  This paper extends the concept of method caching by addressing the case where
clients wrap related method invocations in ACID transactions. Demarcating
sequences of method calls in this way is supported by many important
application server standards. In this context the paper presents an
architecture, a theory and an efficient protocol for maintaining full
transactional consistency and in particular serializability when using a method
cache on the client side. In order to create a protocol for scheduling cached
method results, the paper extends a classical transaction formalism. Based on
this extension, a recovery protocol and an optimistic serializability protocol
are derived. The latter one differs from traditional transactional cache
protocols in many essential ways. An efficiency experiment validates the
approach: Using the cache a system's performance and scalability are
considerably improved.


title: The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems

abstract:
  We consider problems in which we are given a rooted tree as input, and must
find a subtree with the same root, optimizing some objective function of the
nodes in the subtree. When this function is the sum of constant node weights,
the problem is trivially solved in linear time. When the objective is the sum
of weights that are linear functions of a parameter, we show how to list all
optima for all possible parameter values in O(n log n) time; this parametric
optimization problem can be used to solve many bicriterion optimizations
problems, in which each node has two values xi and yi associated with it, and
the objective function is a bivariate function f(SUM(xi),SUM(yi)) of the sums
of these two values. A special case, when f is the ratio of the two sums, is
the Weighted Maximum-Mean Subtree Problem, or equivalently the Fractional
Prize-Collecting Steiner Tree Problem on Trees; for this special case, we
provide a linear time algorithm for this problem when all weights are positive,
improving a previous O(n log n) solution, and prove that the problem is
NP-complete when negative weights are allowed.


title:
Fine-Grained Word Sense Disambiguation Based on Parallel Corpora, Word
  Alignment, Word Clustering and Aligned Wordnets

abstract:
  The paper presents a method for word sense disambiguation based on parallel
corpora. The method exploits recent advances in word alignment and word
clustering based on automatic extraction of translation equivalents and being
supported by available aligned wordnets for the languages in the corpus. The
wordnets are aligned to the Princeton Wordnet, according to the principles
established by EuroWordNet. The evaluation of the WSD system, implementing the
method described herein showed very encouraging results. The same system used
in a validation mode, can be used to check and spot alignment errors in
multilingually aligned wordnets as BalkaNet and EuroWordNet.


title: A Taxonomy of Workflow Management Systems for Grid Computing

abstract:
  With the advent of Grid and application technologies, scientists and
engineers are building more and more complex applications to manage and process
large data sets, and execute scientific experiments on distributed resources.
Such application scenarios require means for composing and executing complex
workflows. Therefore, many efforts have been made towards the development of
workflow management systems for Grid computing. In this paper, we propose a
taxonomy that characterizes and classifies various approaches for building and
executing workflows on Grids. We also survey several representative Grid
workflow systems developed by various projects world-wide to demonstrate the
comprehensiveness of the taxonomy. The taxonomy not only highlights the design
and engineering similarities and differences of state-of-the-art in Grid
workflow systems, but also identifies the areas that need further research.


title: On Generalized Computable Universal Priors and their Convergence

abstract:
  Solomonoff unified Occam's razor and Epicurus' principle of multiple
explanations to one elegant, formal, universal theory of inductive inference,
which initiated the field of algorithmic information theory. His central result
is that the posterior of the universal semimeasure M converges rapidly to the
true sequence generating posterior mu, if the latter is computable. Hence, M is
eligible as a universal predictor in case of unknown mu. The first part of the
paper investigates the existence and convergence of computable universal
(semi)measures for a hierarchy of computability classes: recursive, estimable,
enumerable, and approximable. For instance, M is known to be enumerable, but
not estimable, and to dominate all enumerable semimeasures. We present proofs
for discrete and continuous semimeasures. The second part investigates more
closely the types of convergence, possibly implied by universality: in
difference and in ratio, with probability 1, in mean sum, and for Martin-Loef
random sequences. We introduce a generalized concept of randomness for
individual sequences and use it to exhibit difficulties regarding these issues.
In particular, we show that convergence fails (holds) on generalized-random
sequences in gappy (dense) Bernoulli classes.


title: Authentication with Distortion Criteria

abstract:
  In a variety of applications, there is a need to authenticate content that
has experienced legitimate editing in addition to potential tampering attacks.
We develop one formulation of this problem based on a strict notion of
security, and characterize and interpret the associated information-theoretic
performance limits. The results can be viewed as a natural generalization of
classical approaches to traditional authentication. Additional insights into
the structure of such systems and their behavior are obtained by further
specializing the results to Bernoulli and Gaussian cases. The associated
systems are shown to be substantially better in terms of performance and/or
security than commonly advocated approaches based on data hiding and digital
watermarking. Finally, the formulation is extended to obtain efficient layered
authentication system constructions.


title:
Stabilization of Cooperative Information Agents in Unpredictable
  Environment: A Logic Programming Approach

abstract:
  An information agent is viewed as a deductive database consisting of 3 parts:
an observation database containing the facts the agent has observed or sensed
from its surrounding environment, an input database containing the information
the agent has obtained from other agents, and an intensional database which is
a set of rules for computing derived information from the information stored in
the observation and input databases. Stabilization of a system of information
agents represents a capability of the agents to eventually get correct
information about their surrounding despite unpredictable environment changes
and the incapability of many agents to sense such changes causing them to have
temporary incorrect information. We argue that the stabilization of a system of
cooperative information agents could be understood as the convergence of the
behavior of the whole system toward the behavior of a "superagent", who has the
sensing and computing capabilities of all agents combined. We show that
unfortunately, stabilization is not guaranteed in general, even if the agents
are fully cooperative and do not hide any information from each other. We give
sufficient conditions for stabilization and discuss the consequences of our
results.


title: The Effect of Use and Access on Citations

abstract:
  It has been shown (S. Lawrence, 2001, Nature, 411, 521) that journal articles
which have been posted without charge on the internet are more heavily cited
than those which have not been. Using data from the NASA Astrophysics Data
System (ads.harvard.edu) and from the ArXiv e-print archive at Cornell
University (arXiv.org) we examine the causes of this effect.


title: A Suffix Tree Approach to Email Filtering

abstract:
  We present an approach to email filtering based on the suffix tree data
structure. A method for the scoring of emails using the suffix tree is
developed and a number of scoring and score normalisation functions are tested.
Our results show that the character level representation of emails and classes
facilitated by the suffix tree can significantly improve classification
accuracy when compared with the currently popular methods, such as naive Bayes.
We believe the method can be extended to the classification of documents in
other domains.


title:
On the Scalability of Cooperative Time Synchronization in
  Pulse-Connected Networks

abstract:
  The problem of time synchronization in dense wireless networks is considered.
Well established synchronization techniques suffer from an inherent scalability
problem in that synchronization errors grow with an increasing number of hops
across the network. In this work, a model for communication in wireless
networks is first developed, and then the model is used to define a new time
synchronization mechanism. A salient feature of the proposed method is that, in
the regime of asymptotically dense networks, it can average out all random
errors and maintain global synchronization in the sense that all nodes in the
multi-hop network can see identical timing signals. This is irrespective of the
distance separating any two nodes.


title:
Complexity and Approximation of Fixing Numerical Attributes in Databases
  Under Integrity Constraints

abstract:
  Consistent query answering is the problem of computing the answers from a
database that are consistent with respect to certain integrity constraints that
the database as a whole may fail to satisfy. Those answers are characterized as
those that are invariant under minimal forms of restoring the consistency of
the database. In this context, we study the problem of repairing databases by
fixing integer numerical values at the attribute level with respect to denial
and aggregation constraints. We introduce a quantitative definition of database
fix, and investigate the complexity of several decision and optimization
problems, including DFP, i.e. the existence of fixes within a given distance
from the original instance, and CQA, i.e. deciding consistency of answers to
aggregate conjunctive queries under different semantics. We provide sharp
complexity bounds, identify relevant tractable cases; and introduce
approximation algorithms for some of those that are intractable. More
specifically, we obtain results like undecidability of existence of fixes for
aggregation constraints; MAXSNP-hardness of DFP, but a good approximation
algorithm for a relevant special case; and intractability but good
approximation for CQA for aggregate queries for one database atom denials (plus
built-ins).


title:
An Introduction to the Summarization of Evolving Events: Linear and
  Non-linear Evolution

abstract:
  This paper examines the summarization of events that evolve through time. It
discusses different types of evolution taking into account the time in which
the incidents of an event are happening and the different sources reporting on
the specific event. It proposes an approach for multi-document summarization
which employs ``messages'' for representing the incidents of an event and
cross-document relations that hold between messages according to certain
conditions. The paper also outlines the current version of the summarization
system we are implementing to realize this approach.


title: Comment on "Some non-conventional ideas about algorithmic complexity"

abstract:
  We comment on a recent paper by D'Abramo [Chaos, Solitons & Fractals, 25
(2005) 29], focusing on the author's statement that an algorithm can produce a
list of strings containing at least one string whose algorithmic complexity is
greater than that of the entire list. We show that this statement, although
perplexing, is not as paradoxical as it seems when the definition of
algorithmic complexity is applied correctly.


title: The egalitarian sharing rule in provision of public projects

abstract:
  In this note we consider a society that partitions itself into disjoint
jurisdictions, each choosing a location of its public project and a taxation
scheme to finance it. The set of public project is multi-dimensional, and their
costs could vary from jurisdiction to jurisdiction. We impose two principles,
egalitarianism, that requires the equalization of the total cost for all agents
in the same jurisdiction, and efficiency, that implies the minimization of the
aggregate total cost within jurisdiction. We show that these two principles
always yield a core-stable partition but a Nash stable partition may fail to
exist.


title: Timed Analysis of Security Protocols

abstract:
  We propose a method for engineering security protocols that are aware of
timing aspects. We study a simplified version of the well-known Needham
Schroeder protocol and the complete Yahalom protocol, where timing information
allows the study of different attack scenarios. We model check the protocols
using UPPAAL. Further, a taxonomy is obtained by studying and categorising
protocols from the well known Clark Jacob library and the Security Protocol
Open Repository (SPORE) library. Finally, we present some new challenges and
threats that arise when considering time in the analysis, by providing a novel
protocol that uses time challenges and exposing a timing attack over an
implementation of an existing security protocol.


title: Mining Top-k Approximate Frequent Patterns

abstract:
  Frequent pattern (itemset) mining in transactional databases is one of the
most well-studied problems in data mining. One obstacle that limits the
practical usage of frequent pattern mining is the extremely large number of
patterns generated. Such a large size of the output collection makes it
difficult for users to understand and use in practice. Even restricting the
output to the border of the frequent itemset collection does not help much in
alleviating the problem. In this paper we address the issue of overwhelmingly
large output size by introducing and studying the following problem: mining
top-k approximate frequent patterns. The union of the power sets of these k
sets should satisfy the following conditions: (1) including itemsets with
larger support as many as possible and (2) including itemsets with smaller
support as less as possible. An integrated objective function is designed to
combine these two objectives. Consequently, we derive the upper bounds on
objective function and present an approximate branch-and-bound method for
finding the feasible solution. We give empirical evidence showing that our
formulation and approximation methods work well in practice.


title: On a Kronecker products sum distance bounds

abstract:
  A binary linear error correcting codes represented by two code families
Kronecker products sum are considered. The dimension and distance of new code
is investigated. Upper and lower bounds of distance are obtained. Some examples
are given. It is shown that some classic constructions are the private cases of
considered one. The subclass of codes with equal lower and upper distance
bounds is allocated.


title: Notes for Miscellaneous Lectures

abstract:
  Here I share a few notes I used in various course lectures, talks, etc. Some
may be just calculations that in the textbooks are more complicated, scattered,
or less specific; others may be simple observations I found useful or curious.


title:
Uplink Throughput in a Single-Macrocell/Single-Microcell CDMA System,
  with Application to Data Access Points

abstract:
  This paper studies a two-tier CDMA system in which the microcell base is
converted into a data access point (DAP), i.e., a limited-range base station
that provides high-speed access to one user at a time. The microcell (or DAP)
user operates on the same frequency as the macrocell users and has the same
chip rate. However, it adapts its spreading factor, and thus its data rate, in
accordance with interference conditions. By contrast, the macrocell serves
multiple simultaneous data users, each with the same fixed rate. The
achieveable throughput for individual microcell users is examined and a simple,
accurate approximation for its probability distribution is presented.
Computations for average throughputs, both per-user and total, are also
presented. The numerical results highlight the impact of a desensitivity
parameter used in the base-selection process.


title: Soft Handoff and Uplink Capacity in a Two-Tier CDMA System

abstract:
  This paper examines the effect of soft handoff on the uplink user capacity of
a CDMA system consisting of a single macrocell in which a single hotspot
microcell is embedded. The users of these two base stations operate over the
same frequency band. In the soft handoff scenario studied here, both macrocell
and microcell base stations serve each system user and the two received copies
of a desired user's signal are summed using maximal ratio combining. Exact and
approximate analytical methods are developed to compute uplink user capacity.
Simulation results demonstrate a 20% increase in user capacity compared to hard
handoff. In addition, simple, approximate methods are presented for estimating
soft handoff capacity and are shown to be quite accurate.


title:
Uplink User Capacity in a CDMA System with Hotspot Microcells: Effects
  of Finite Transmit Power and Dispersion

abstract:
  This paper examines the uplink user capacity in a two-tier code division
multiple access (CDMA) system with hotspot microcells when user terminal power
is limited and the wireless channel is finitely-dispersive. A
finitely-dispersive channel causes variable fading of the signal power at the
output of the RAKE receiver. First, a two-cell system composed of one macrocell
and one embedded microcell is studied and analytical methods are developed to
estimate the user capacity as a function of a dimensionless parameter that
depends on the transmit power constraint and cell radius. Next, novel
analytical methods are developed to study the effect of variable fading, both
with and without transmit power constraints. Finally, the analytical methods
are extended to estimate uplink user capacity for multicell CDMA systems,
composed of multiple macrocells and multiple embedded microcells. In all cases,
the analysis-based estimates are compared with and confirmed by simulation
results.


title:
Complexity Issues in Finding Succinct Solutions of PSPACE-Complete
  Problems

abstract:
  We study the problem of deciding whether some PSPACE-complete problems have
models of bounded size. Contrary to problems in NP, models of PSPACE-complete
problems may be exponentially large. However, such models may take polynomial
space in a succinct representation. For example, the models of a QBF are
explicitely represented by and-or trees (which are always of exponential size)
but can be succinctely represented by circuits (which can be polynomial or
exponential). We investigate the complexity of deciding the existence of such
succinct models when a bound on size is given.


title: Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively

abstract:
  To test incomplete search algorithms for constraint satisfaction problems
such as 3-SAT, we need a source of hard, but satisfiable, benchmark instances.
A simple way to do this is to choose a random truth assignment A, and then
choose clauses randomly from among those satisfied by A. However, this method
tends to produce easy problems, since the majority of literals point toward the
``hidden'' assignment A. Last year, Achlioptas, Jia and Moore proposed a
problem generator that cancels this effect by hiding both A and its complement.
While the resulting formulas appear to be just as hard for DPLL algorithms as
random 3-SAT formulas with no hidden assignment, they can be solved by WalkSAT
in only polynomial time. Here we propose a new method to cancel the attraction
to A, by choosing a clause with t > 0 literals satisfied by A with probability
proportional to q^t for some q < 1. By varying q, we can generate formulas
whose variables have no bias, i.e., which are equally likely to be true or
false; we can even cause the formula to ``deceptively'' point away from A. We
present theoretical and experimental results suggesting that these formulas are
exponentially hard both for DPLL algorithms and for incomplete algorithms such
as WalkSAT.


title: Contextual Constraint Modeling in Grid Application Workflows

abstract:
  This paper introduces a new mechanism for specifying constraints in
distributed workflows. By introducing constraints in a contextual form, it is
shown how different people and groups within collaborative communities can
cooperatively constrain workflows. A comparison with existing state-of-the-art
workflow systems is made. These ideas are explored in practice with an
illustrative example from High Energy Physics.


title: Hiding Satisfying Assignments: Two are Better than One

abstract:
  The evaluation of incomplete satisfiability solvers depends critically on the
availability of hard satisfiable instances. A plausible source of such
instances consists of random k-SAT formulas whose clauses are chosen uniformly
from among all clauses satisfying some randomly chosen truth assignment A.
Unfortunately, instances generated in this manner tend to be relatively easy
and can be solved efficiently by practical heuristics. Roughly speaking, as the
formula's density increases, for a number of different algorithms, A acts as a
stronger and stronger attractor. Motivated by recent results on the geometry of
the space of satisfying truth assignments of random k-SAT and NAE-k-SAT
formulas, we introduce a simple twist on this basic model, which appears to
dramatically increase its hardness. Namely, in addition to forbidding the
clauses violated by the hidden assignment A, we also forbid the clauses
violated by its complement, so that both A and complement of A are satisfying.
It appears that under this "symmetrization'' the effects of the two attractors
largely cancel out, making it much harder for algorithms to find any truth
assignment. We give theoretical and experimental evidence supporting this
assertion.

categories: cs.AI cond-mat.dis-nn cond-mat.stat-mech cs.CC


title:
On Multiflows in Random Unit-Disk Graphs, and the Capacity of Some
  Wireless Networks

abstract:
  We consider the capacity problem for wireless networks. Networks are modeled
as random unit-disk graphs, and the capacity problem is formulated as one of
finding the maximum value of a multicommodity flow. In this paper, we develop a
proof technique based on which we are able to obtain a tight characterization
of the solution to the linear program associated with the multiflow problem, to
within constants independent of network size. We also use this proof method to
analyze network capacity for a variety of transmitter/receiver architectures,
for which we obtain some conclusive results. These results contain as a special
case (and strengthen) those of Gupta and Kumar for random networks, for which a
new derivation is provided using only elementary counting and discrete
probability tools.


title:
Is entanglement necessary to have unconditional security in quantum bit
  commitment ?

abstract:
  A simple un-entanglement based quantum bit commitment scheme is presented.
Although commitment is unconditionally secure but concealment is not.


title:
Enforcing and Defying Associativity, Commutativity, Totality, and Strong
  Noninvertibility for One-Way Functions in Complexity Theory

abstract:
  Rabi and Sherman [RS97,RS93] proved that the hardness of factoring is a
sufficient condition for there to exist one-way functions (i.e., p-time
computable, honest, p-time noninvertible functions; this paper is in the
worst-case model, not the average-case model) that are total, commutative, and
associative but not strongly noninvertible. In this paper we improve the
sufficient condition to ``P does not equal NP.''
  More generally, in this paper we completely characterize which types of
one-way functions stand or fall together with (plain) one-way
functions--equivalently, stand or fall together with P not equaling NP. We look
at the four attributes used in Rabi and Sherman's seminal work on algebraic
properties of one-way functions (see [RS97,RS93]) and subsequent
papers--strongness (of noninvertibility), totality, commutativity, and
associativity--and for each attribute, we allow it to be required to hold,
required to fail, or ``don't care.'' In this categorization there are 3^4 = 81
potential types of one-way functions. We prove that each of these 81
feature-laden types stand or fall together with the existence of (plain)
one-way functions.


title: Systematic Method for Path-Complete White Box Testing

abstract:
  A systematic, language-independent method of finding a minimal set of paths
covering the code of a sequential program is proposed for application in White
Box testing. Execution of all paths from the set ensures also statement
coverage. Execution fault marks problematic areas of the code. The method
starts from a UML activity diagram of a program. The diagram is transformed
into a directed graph: graph's nodes substitute decision and action points;
graph's directed edges substitute action arrows.
  The number of independent paths equals easy-to-compute cyclomatic complexity
of the graph. Association of a vector to each path creates a path vector space.
Independence of the paths is equivalent to linear independence of the vectors.
It is sufficient to test any base of the path space to complete the procedure.
An effective algorithm for choosing the base paths is presented.


title:
Construction of Small Worlds in the Physical Topology of Wireless
  Networks

abstract:
  The concept of small worlds is introduced into the physical topology of
wireless networks in this work. A. Helmy provided two con- struction schemes of
small worlds for the wireless networks, link rewiring and link addition, but he
mainly focused on the virtual topology. Based on the broadcasting nature of the
radio transmission, we propose a con- struction scheme of small worlds for the
physical topology of Multiple- Input Multiple-Output (MIMO) wireless networks.
Besides the topology- related topics, we also evaluate the reduction of the
power required by a request.


title: Zeta-Dimension

abstract:
  The zeta-dimension of a set A of positive integers is the infimum s such that
the sum of the reciprocals of the s-th powers of the elements of A is finite.
  Zeta-dimension serves as a fractal dimension on the positive integers that
extends naturally usefully to discrete lattices such as the set of all integer
lattice points in d-dimensional space.
  This paper reviews the origins of zeta-dimension (which date to the
eighteenth and nineteenth centuries) and develops its basic theory, with
particular attention to its relationship with algorithmic information theory.
New results presented include extended connections between zeta-dimension and
classical fractal dimensions, a gale characterization of zeta-dimension, and a
theorem on the zeta-dimensions of pointwise sums and products of sets of
positive integers.


title: A hybrid MLP-PNN architecture for fast image superresolution

abstract:
  Image superresolution methods process an input image sequence of a scene to
obtain a still image with increased resolution. Classical approaches to this
problem involve complex iterative minimization procedures, typically with high
computational costs. In this paper is proposed a novel algorithm for
super-resolution that enables a substantial decrease in computer load. First, a
probabilistic neural network architecture is used to perform a scattered-point
interpolation of the image sequence data. The network kernel function is
optimally determined for this problem by a multi-layer perceptron trained on
synthetic data. Network parameters dependence on sequence noise level is
quantitatively analyzed. This super-sampled image is spatially filtered to
correct finite pixel size effects, to yield the final high-resolution estimate.
Results on a real outdoor sequence are presented, showing the quality of the
proposed method.


title: Analytic Definition of Curves and Surfaces by Parabolic Blending

abstract:
  A procedure for interpolating between specified points of a curve or surface
is described. The method guarantees slope continuity at all junctions. A
surface panel divided into p x q contiguous patches is completely specified by
the coordinates of (p+1) x (q+1) points. Each individual patch, however,
depends parametrically on the coordinates of 16 points, allowing shape
flexibility and global conformity.


title: Optimality in Goal-Dependent Analysis of Sharing

abstract:
  We face the problems of correctness, optimality and precision for the static
analysis of logic programs, using the theory of abstract interpretation. We
propose a framework with a denotational, goal-dependent semantics equipped with
two unification operators for forward unification (calling a procedure) and
backward unification (returning from a procedure). The latter is implemented
through a matching operation. Our proposal clarifies and unifies many different
frameworks and ideas on static analysis of logic programming in a single,
formal setting. On the abstract side, we focus on the domain Sharing by Jacobs
and Langen and provide the best correct approximation of all the primitive
semantic operators, namely, projection, renaming, forward and backward
unification. We show that the abstract unification operators are strictly more
precise than those in the literature defined over the same abstract domain. In
some cases, our operators are more precise than those developed for more
complex domains involving linearity and freeness.
  To appear in Theory and Practice of Logic Programming (TPLP)


title:
Semi-automatic vectorization of linear networks on rasterized
  cartographic maps

abstract:
  A system for semi-automatic vectorization of linear networks (roads, rivers,
etc.) on rasterized cartographic maps is presented. In this system, human
intervention is limited to a graphic, interactive selection of the color
attributes of the information to be obtained. Using this data, the system
performs a preliminary extraction of the linear network, which is subsequently
completed, refined and vectorized by means of an automatic procedure. Results
on maps of different sources and scales are included.
  -----
  Se presenta un sistema semi-automatico de vectorizacion de redes de objetos
lineales (carreteras, rios, etc.) en mapas cartograficos digitalizados. En este
sistema, la intervencion humana queda reducida a la seleccion grafica
interactiva de los atributos de color de la informacion a obtener. Con estos
datos, el sistema realiza una extraccion preliminar de la red lineal, que se
completa, refina y vectoriza mediante un procedimiento automatico. Se presentan
resultados de la aplicacion del sistema sobre imagenes digitalizadas de mapas
de distinta procedencia y escala.


title: Exact and Approximation Algorithms for DNA Tag Set Design

abstract:
  In this paper we propose new solution methods for designing tag sets for use
in universal DNA arrays. First, we give integer linear programming formulations
for two previous formalizations of the tag set design problem, and show that
these formulations can be solved to optimality for instance sizes of practical
interest by using general purpose optimization packages. Second, we note the
benefits of periodic tags, and establish an interesting connection between the
tag design problem and the problem of packing the maximum number of
vertex-disjoint directed cycles in a given graph. We show that combining a
simple greedy cycle packing algorithm with a previously proposed alphabetic
tree search strategy yields an increase of over 40% in the number of tags
compared to previous methods.


title: On the Stopping Distance and the Stopping Redundancy of Codes

abstract:
  It is now well known that the performance of a linear code $C$ under
iterative decoding on a binary erasure channel (and other channels) is
determined by the size of the smallest stopping set in the Tanner graph for
$C$. Several recent papers refer to this parameter as the \emph{stopping
distance} $s$ of $C$. This is somewhat of a misnomer since the size of the
smallest stopping set in the Tanner graph for $C$ depends on the corresponding
choice of a parity-check matrix. It is easy to see that $s \le d$, where $d$ is
the minimum Hamming distance of $C$, and we show that it is always possible to
choose a parity-check matrix for $C$ (with sufficiently many dependent rows)
such that $s = d$. We thus introduce a new parameter, termed the \emph{stopping
redundancy} of $C$, defined as the minimum number of rows in a parity-check
matrix $H$ for $C$ such that the corresponding stopping distance $s(H)$ attains
its largest possible value, namely $s(H) = d$.
  We then derive general bounds on the stopping redundancy of linear codes. We
also examine several simple ways of constructing codes from other codes, and
study the effect of these constructions on the stopping redundancy.
Specifically, for the family of binary Reed-Muller codes (of all orders), we
prove that their stopping redundancy is at most a constant times their
conventional redundancy. We show that the stopping redundancies of the binary
and ternary extended Golay codes are at most 35 and 22, respectively. Finally,
we provide upper and lower bounds on the stopping redundancy of MDS codes.