title: Distributed Selfish Load Balancing

abstract:
  Suppose that a set of $m$ tasks are to be shared as equally as possible
amongst a set of $n$ resources. A game-theoretic mechanism to find a suitable
allocation is to associate each task with a ``selfish agent'', and require each
agent to select a resource, with the cost of a resource being the number of
agents to select it. Agents would then be expected to migrate from overloaded
to underloaded resources, until the allocation becomes balanced.
  Recent work has studied the question of how this can take place within a
distributed setting in which agents migrate selfishly without any centralized
control. In this paper we discuss a natural protocol for the agents which
combines the following desirable features: It can be implemented in a strongly
distributed setting, uses no central control, and has good convergence
properties. For $m\gg n$, the system becomes approximately balanced (an
$\epsilon$-Nash equilibrium) in expected time $O(\log\log m)$. We show using a
martingale technique that the process converges to a perfectly balanced
allocation in expected time $O(\log\log m+n^4)$. We also give a lower bound of
$\Omega(\max\{\log\log m,n\})$ for the convergence time.


title: DIMES: Let the Internet Measure Itself

abstract:
  Today's Internet maps, which are all collected from a small number of vantage
points, are falling short of being accurate. We suggest here a paradigm shift
for this task. DIMES is a distributed measurement infrastructure for the
Internet that is based on the deployment of thousands of light weight
measurement agents around the globe.
  We describe the rationale behind DIMES deployment, discuss its design
trade-offs and algorithmic challenges, and analyze the structure of the
Internet as it seen with DIMES.


title: On the NP-Completeness of Some Graph Cluster Measures

abstract:
  Graph clustering is the problem of identifying sparsely connected dense
subgraphs (clusters) in a given graph. Proposed clustering algorithms usually
optimize various fitness functions that measure the quality of a cluster within
the graph. Examples of such cluster measures include the conductance, the local
and relative densities, and single cluster editing. We prove that the decision
problems associated with the optimization tasks of finding the clusters that
are optimal with respect to these fitness measures are NP-complete.


title: Efficient Multiclass Implementations of L1-Regularized Maximum Entropy

abstract:
  This paper discusses the application of L1-regularized maximum entropy
modeling or SL1-Max [9] to multiclass categorization problems. A new
modification to the SL1-Max fast sequential learning algorithm is proposed to
handle conditional distributions. Furthermore, unlike most previous studies,
the present research goes beyond a single type of conditional distribution. It
describes and compares a variety of modeling assumptions about the class
distribution (independent or exclusive) and various types of joint or
conditional distributions. It results in a new methodology for combining binary
regularized classifiers to achieve multiclass categorization. In this context,
Maximum Entropy can be considered as a generic and efficient regularized
classification tool that matches or outperforms the state-of-the art
represented by AdaBoost and SVMs.


title: On $m$-dimensional toric codes

abstract:
  Toric codes are a class of $m$-dimensional cyclic codes introduced recently
by J. Hansen. They may be defined as evaluation codes obtained from monomials
corresponding to integer lattice points in an integral convex polytope $P
\subseteq \R^m$. As such, they are in a sense a natural extension of
Reed-Solomon codes. Several authors have used intersection theory on toric
surfaces to derive bounds on the minimum distance of some toric codes with $m =
2$. In this paper, we will provide a more elementary approach that applies
equally well to many toric codes for all $m \ge 2$. Our methods are based on a
sort of multivariate generalization of Vandermonde determinants that has also
been used in the study of multivariate polynomial interpolation. We use these
Vandermonde determinants to determine the minimum distance of toric codes from
rectangular polytopes and simplices. We also prove a general result showing
that if there is a unimodular integer affine transformation taking one polytope
$P_1$ to a second polytope $P_2$, then the corresponding toric codes are
monomially equivalent (hence have the same parameters). We use this to begin a
classification of two-dimensional toric codes with small dimension.


title: Security of mobile agents: a new concept of the integrity protection

abstract:
  The recent developments in the mobile technology (mobile phones, middleware)
created a need for new methods of protecting the code transmitted through the
network. The proposed mechanisms not only secure the compiled program, but also
the data, that can be gathered during its "journey". The oldest and the
simplest methods are more concentrated on integrity of the code itself and on
the detection of unauthorized manipulation. Other, more advanced proposals
protect not only the code but also the execution state and the collected data.
The paper is divided into two parts. The first one is mostly devoted to
different methods of securing the code and protecting its integrity; starting
from watermarking and fingerprinting, up to methods designed specially for
mobile agent systems: encrypted function, cryptographic traces, time limited
black-box security, chained-MAC protocol, publicly-verifiable chained digital
signatures The second part presents new concept for providing mobile agents
with integrity protection, based on a zero-knowledge proof system.


title: Computing minimal models, stable models and answer sets

abstract:
  We propose and study algorithms to compute minimal models, stable models and
answer sets of t-CNF theories, and normal and disjunctive t-programs. We are
especially interested in algorithms with non-trivial worst-case performance
bounds. The bulk of the paper is concerned with the classes of 2- and 3-CNF
theories, and normal and disjunctive 2- and 3-programs, for which we obtain
significantly stronger results than those implied by our general
considerations. We show that one can find all minimal models of 2-CNF theories
and all answer sets of disjunctive 2-programs in time O(m 1.4422..^n). Our main
results concern computing stable models of normal 3-programs, minimal models of
3-CNF theories and answer sets of disjunctive 3-programs. We design algorithms
that run in time O(m 1.6701..^n), in the case of the first problem, and in time
O(mn^2 2.2782..^n), in the case of the latter two. All these bounds improve by
exponential factors the best algorithms known previously. We also obtain
closely related upper bounds on the number of minimal models, stable models and
answer sets a t-CNF theory, a normal t-program or a disjunctive t-program may
have.
  To appear in Theory and Practice of Logic Programming (TPLP).


title: A protected password change protocol

abstract:
  Some protected password change protocols were proposed. However, the previous
protocols were easily vulnerable to several attacks such as denial of service,
password guessing, stolen-verifier and impersonation atacks etc. Recently,
Chang et al. proposed a simple authenticated key agreement and protected
password change protocol for enhancing the security and efficiency. In this
paper, authors shall show that password guessing, denial of service and
known-key attacks can work in their password change protocol. At the same time,
authors shall propose a new password change protocol to withstand all the
threats of security.


title: Asymptotically Optimal Tree-based Group Key Management Schemes

abstract:
  In key management schemes that realize secure multicast communications
encrypted by group keys on a public network, tree structures are often used to
update the group keys efficiently. Selcuk and Sidhu have proposed an efficient
scheme which updates dynamically the tree structures based on the withdrawal
probabilities of members. In this paper, it is shown that Selcuk-Sidhu scheme
is asymptotically optimal for the cost of withdrawal. Furthermore, a new key
management scheme, which takes account of key update costs of joining in
addition to withdrawal, is proposed. It is proved that the proposed scheme is
also asymptotically optimal, and it is shown by simulation that it can attain
good performance for nonasymptotic cases.


title:
The Three Node Wireless Network: Achievable Rates and Cooperation
  Strategies

abstract:
  We consider a wireless network composed of three nodes and limited by the
half-duplex and total power constraints. This formulation encompasses many of
the special cases studied in the literature and allows for capturing the common
features shared by them. Here, we focus on three special cases, namely 1) Relay
Channel, 2) Multicast Channel, and 3) Conference Channel. These special cases
are judicially chosen to reflect varying degrees of complexity while
highlighting the common ground shared by the different variants of the three
node wireless network. For the relay channel, we propose a new cooperation
scheme that exploits the wireless feedback gain. This scheme combines the
benefits of decode-and-forward and compress-and-forward strategies and avoids
the idealistic feedback assumption adopted in earlier works. Our analysis of
the achievable rate of this scheme reveals the diminishing feedback gain at
both the low and high signal-to-noise ratio regimes. Inspired by the proposed
feedback strategy, we identify a greedy cooperation framework applicable to
both the multicast and conference channels. Our performance analysis reveals
several nice properties of the proposed greedy approach and the central role of
cooperative source-channel coding in exploiting the receiver side information
in the wireless network setting. Our proofs for the cooperative multicast with
side-information rely on novel nested and independent binning encoders along
with a list decoder.


title: The role of Quantum Interference in Quantum Computing

abstract: Quantum interference is proposed as a tool to augment Quantum Computation.


title:
An End-to-End Probabilistic Network Calculus with Moment Generating
  Functions

abstract:
  Network calculus is a min-plus system theory for performance evaluation of
queuing networks. Its elegance stems from intuitive convolution formulas for
concatenation of deterministic servers. Recent research dispenses with the
worst-case assumptions of network calculus to develop a probabilistic
equivalent that benefits from statistical multiplexing. Significant
achievements have been made, owing for example to the theory of effective
bandwidths, however, the outstanding scalability set up by concatenation of
deterministic servers has not been shown.
  This paper establishes a concise, probabilistic network calculus with moment
generating functions. The presented work features closed-form, end-to-end,
probabilistic performance bounds that achieve the objective of scaling linearly
in the number of servers in series. The consistent application of moment
generating functions put forth in this paper utilizes independence beyond the
scope of current statistical multiplexing of flows. A relevant additional gain
is demonstrated for tandem servers with independent cross-traffic.


title:
A Genetic Algorithm Based Finger Selection Scheme for UWB MMSE Rake
  Receivers

abstract:
  Due to a large number of multipath components in a typical ultra wideband
(UWB) system, selective Rake (SRake) receivers, which combine energy from a
subset of multipath components, are commonly employed. In order to optimize
system performance, an optimal selection of multipath components to be employed
at fingers of an SRake receiver needs to be considered. In this paper, this
finger selection problem is investigated for a minimum mean square error (MMSE)
UWB SRake receiver. Since the optimal solution is NP hard, a genetic algorithm
(GA) based iterative scheme is proposed, which can achieve near-optimal
performance after a reasonable number of iterations. Simulation results are
presented to compare the performance of the proposed finger selection algorithm
with those of the conventional and optimal schemes.


title:
A Two-Step Time of Arrival Estimation Algorithm for Impulse Radio Ultra
  Wideband Systems

abstract:
  High time resolution of ultra wideband (UWB) signals facilitates very precise
positioning capabilities based on time-of-arrival (TOA) measurements. Although
the theoretical lower bound for TOA estimation can be achieved by the maximum
likelihood principle, it is impractical due to the need for extremely high-rate
sampling and the presence of large number of multipath components. On the other
hand, the conventional correlation-based algorithm, which serially searches
possible signal delays, takes a very long time to estimate the TOA of a
received UWB signal. Moreover, the first signal path does not always have the
strongest correlation output. Therefore, first path detection algorithms need
to be considered. In this paper, a data-aided two-step TOA estimation algorithm
is proposed. In order to speed up the estimation process, the first step
estimates the rough TOA of the received signal based on received signal energy.
Then, in the second step, the arrival time of the first signal path is
estimated by considering a hypothesis testing approach. The proposed scheme
uses low-rate correlation outputs, and is able to perform accurate TOA
estimation in reasonable time intervals. The simulation results are presented
to analyze the performance of the estimator.


title: Strong normalisation for applied lambda calculi

abstract:
  We consider the untyped lambda calculus with constructors and recursively
defined constants. We construct a domain-theoretic model such that any term not
denoting bottom is strongly normalising provided all its `stratified
approximations' are. From this we derive a general normalisation theorem for
applied typed lambda-calculi: If all constants have a total value, then all
typeable terms are strongly normalising. We apply this result to extensions of
G\"odel's system T and system F extended by various forms of bar recursion for
which strong normalisation was hitherto unknown.


title: Complexity Science for Simpletons

abstract:
  In this article, we shall describe some of the most interesting topics in the
subject of Complexity Science for a general audience. Anyone with a solid
foundation in high school mathematics (with some calculus) and an elementary
understanding of computer programming will be able to follow this article.
First, we shall explain the significance of the P versus NP problem and solve
it. Next, we shall describe two other famous mathematics problems, the Collatz
3n+1 Conjecture and the Riemann Hypothesis, and show how both Chaitin's
incompleteness theorem and Wolfram's notion of "computational irreducibility"
are important for understanding why no one has, as of yet, solved these two
problems.


title:
MAEC : A Movement-Assisted Energy Conserving Method in Event Driven
  Wireless Sensor Networks

abstract:
  Energy is one of the most important resources in wireless sensor networks.
Recently, the mobility of base station has been exploited to preserve the
energy. But in event driven networks, the mobility issue is quite different
from the continuous monitoring one because only a small portion of sensor node
has data to send at one time. The number of sensor node that forward traffic
should be minimized to prolong the network lifetime. In this paper, we propose
a movement-assisted energy conserving method which tries to reduce the amount
of forwarding sensor node by directing the base station to move close to the
hotspots. This method achieves good performance especially when applied to a
network with a set of cooperative mobile base station. Extensive simulation has
been done to verify the effectiveness of the propose schema.


title: A Study for the Feature Core of Dynamic Reduct

abstract:
  To the reduct problems of decision system, the paper proposes the notion of
dynamic core according to the dynamic reduct model. It describes various formal
definitions of dynamic core, and discusses some properties about dynamic core.
All of these show that dynamic core possesses the essential characters of the
feature core.


title:
A Utility-Based Approach to Power Control and Receiver Design in
  Wireless Data Networks

abstract:
  In this work, the cross-layer design problem of joint multiuser detection and
power control is studied using a game-theoretic approach. The uplink of a
direct-sequence code division multiple access (DS-CDMA) data network is
considered and a non-cooperative game is proposed in which users in the network
are allowed to choose their uplink receivers as well as their transmit powers
to maximize their own utilities. The utility function measures the number of
reliable bits transmitted by the user per joule of energy consumed. Focusing on
linear receivers, the Nash equilibrium for the proposed game is derived. It is
shown that the equilibrium is one where the powers are SIR-balanced with the
minimum mean square error (MMSE) detector as the receiver. In addition, this
framework is used to study power control games for the matched filter, the
decorrelator, and the MMSE detector; and the receivers' performance is compared
in terms of the utilities achieved at equilibrium (in bits/Joule). The optimal
cooperative solution is also discussed and compared with the non-cooperative
approach. Extensions of the results to the case of multiple receive antennas
are also presented. In addition, an admission control scheme based on
maximizing the total utility in the network is proposed.


title: Lattice Gas Cellular Automata for Computational Fluid Animation

abstract:
  The past two decades showed a rapid growing of physically-based modeling of
fluids for computer graphics applications. In this area, a common top down
approach is to model the fluid dynamics by Navier-Stokes equations and apply a
numerical techniques such as Finite Differences or Finite Elements for the
simulation. In this paper we focus on fluid modeling through Lattice Gas
Cellular Automata (LGCA) for computer graphics applications. LGCA are discrete
models based on point particles that move on a lattice, according to suitable
and simple rules in order to mimic a fully molecular dynamics. By
Chapman-Enskog expansion, a known multiscale technique in this area, it can be
demonstrated that the Navier-Stokes model can be reproduced by the LGCA
technique. Thus, with LGCA we get a fluid model that does not require solution
of complicated equations. Therefore, we combine the advantage of the low
computational cost of LGCA and its ability to mimic the realistic fluid
dynamics to develop a new animating framework for computer graphics
applications. In this work, we discuss the theoretical elements of our proposal
and show experimental results.


title: An O(n log n)-Time Algorithm for the Restricted Scaffold Assignment

abstract:
  The assignment problem takes as input two finite point sets S and T and
establishes a correspondence between points in S and points in T, such that
each point in S maps to exactly one point in T, and each point in T maps to at
least one point in S. In this paper we show that this problem has an O(n log
n)-time solution, provided that the points in S and T are restricted to lie on
a line (linear time, if S and T are presorted).


title: Isomorphism of graphs-a polynomial test

abstract:
  An explicit algorithm is presented for testing whether two non-directed
graphs are isomorphic or not. It is shown that for a graph of n vertices, the
number of n independent operations needed for the test is polynomial in n. A
proof that the algorithm actually performs the test is presented.


title: Duality between Packings and Coverings of the Hamming Space

abstract:
  We investigate the packing and covering densities of linear and nonlinear
binary codes, and establish a number of duality relationships between the
packing and covering problems. Specifically, we prove that if almost all codes
(in the class of linear or nonlinear codes) are good packings, then only a
vanishing fraction of codes are good coverings, and vice versa: if almost all
codes are good coverings, then at most a vanishing fraction of codes are good
packings. We also show that any specific maximal binary code is either a good
packing or a good covering, in a certain well-defined sense.


title: Minimizing makespan in flowshop with time lags

abstract:
  We consider the problem of minimizing the makespan in a flowshop involving
maximal and minimal time lags. Time lag constraints generalize the classical
precedence constraints between operations. We assume that such constraints are
only defined between operations of the same job. We propose a solution method
and present several extensions.


title: Minimum Cost and List Homomorphisms to Semicomplete Digraphs

abstract:
  The following optimization problem was introduced in \cite{gutinDAM}, where
it was motivated by a real-world problem in defence logistics. Suppose we are
given a pair of digraphs $D,H$ and a positive cost $c_i(u)$ for each $u\in
V(D)$ and $i\in V(H)$. The cost of a homomorphism $f$ of $D$ to $H$ is
$\sum_{u\in V(D)}c_{f(u)}(u)$. For a fixed digraph $H$, the minimum cost
homomorphism problem for $H$, MinHOMP($H$), is stated as follows: For an input
digraph $D$ and costs $c_i(u)$ for each $u\in V(D)$ and $i\in V(H)$, verify
whether there is a homomorphism of $D$ to $H$ and, if it exists, find such a
homomorphism of minimum cost.
  We obtain dichotomy classifications of the computational complexity of the
list homomorphism problem and MinHOMP($H$), when $H$ is a semicomplete digraph
(a digraph in which every two vertices have at least one arc between them). Our
dichotomy for the list homomorphism problem coincides with the one obtained by
Bang-Jensen, Hell and MacGillivray in 1988 for the homomorphism problem when
$H$ is a semicomplete digraph: both problems are polynomial solvable if $H$ has
at most one cycle; otherwise, both problems are NP-complete. The dichotomy for
\MiP is different: the problem is polynomial time solvable if $H$ is acyclic or
$H$ is a cycle of length 2 or 3; otherwise, the problem is NP-hard.


title:
Optimal and Suboptimal Detection of Gaussian Signals in Noise:
  Asymptotic Relative Efficiency

abstract:
  The performance of Bayesian detection of Gaussian signals using noisy
observations is investigated via the error exponent for the average error
probability. Under unknown signal correlation structure or limited processing
capability it is reasonable to use the simple quadratic detector that is
optimal in the case of an independent and identically distributed (i.i.d.)
signal. Using the large deviations principle, the performance of this detector
(which is suboptimal for non-i.i.d. signals) is compared with that of the
optimal detector for correlated signals via the asymptotic relative efficiency
defined as the ratio between sample sizes of two detectors required for the
same performance in the large-sample-size regime. The effects of SNR on the ARE
are investigated. It is shown that the asymptotic efficiency of the simple
quadratic detector relative to the optimal detector converges to one as the SNR
increases without bound for any bounded spectrum, and that the simple quadratic
detector performs as well as the optimal detector for a wide range of the
correlation values at high SNR.


title:
Making Space for Stories: Ambiguity in the Design of Personal
  Communication Systems

abstract:
  Pervasive personal communication technologies offer the potential for
important social benefits for individual users, but also the potential for
significant social difficulties and costs. In research on face-to-face social
interaction, ambiguity is often identified as an important resource for
resolving social difficulties. In this paper, we discuss two design cases of
personal communication systems, one based on fieldwork of a commercial system
and another based on an unrealized design concept. The cases illustrate how
user behavior concerning a particular social difficulty, unexplained
unresponsiveness, can be influenced by technological issues that result in
interactional ambiguity. The cases also highlight the need to balance the
utility of ambiguity against the utility of usability and communicative
clarity.


title:
First-order queries on structures of bounded degree are computable with
  constant delay

abstract:
  A bounded degree structure is either a relational structure all of whose
relations are of bounded degree or a functional structure involving bijective
functions only. In this paper, we revisit the complexity of the evaluation
problem of not necessarily Boolean first-order queries over structures of
bounded degree. Query evaluation is considered here as a dynamical process. We
prove that any query on bounded degree structures is $\constantdelaylin$, i.e.,
can be computed by an algorithm that has two separate parts: it has a
precomputation step of linear time in the size of the structure and then, it
outputs all tuples one by one with a constant (i.e. depending on the size of
the formula only) delay between each. Seen as a global process, this implies
that queries on bounded structures can be evaluated in total time
$O(f(|\phi|).(|\calS|+|\phi(\calS)|))$ and space $O(f(|\phi|).|\calS|)$ where
$\calS$ is the structure, $\phi$ is the formula, $\phi(\calS)$ is the result of
the query and $f$ is some function.
  Among other things, our results generalize a result of \cite{Seese-96} on the
data complexity of the model-checking problem for bounded degree structures.
Besides, the originality of our approach compared to that \cite{Seese-96} and
comparable results is that it does not rely on the Hanf's model-theoretic
technic (see \cite{Hanf-65}) and is completely effective.


title: Finding routes in anonymous sensor networks

abstract:
  We consider networks of anonymous sensors and address the problem of
constructing routes for the delivery of information from a group of sensors in
response to a query by a sink. In order to circumvent the restrictions imposed
by anonymity, we rely on using the power level perceived by the sensors in the
query from the sink. We introduce a simple distributed algorithm to achieve the
building of routes to the sink and evaluate its performance by means of
simulations.


title: On Hilberg's Law and Its Links with Guiraud's Law

abstract:
  Hilberg (1990) supposed that finite-order excess entropy of a random human
text is proportional to the square root of the text length. Assuming that
Hilberg's hypothesis is true, we derive Guiraud's law, which states that the
number of word types in a text is greater than proportional to the square root
of the text length. Our derivation is based on some mathematical conjecture in
coding theory and on several experiments suggesting that words can be defined
approximately as the nonterminals of the shortest context-free grammar for the
text. Such operational definition of words can be applied even to texts
deprived of spaces, which do not allow for Mandelbrot's ``intermittent
silence'' explanation of Zipf's and Guiraud's laws. In contrast to
Mandelbrot's, our model assumes some probabilistic long-memory effects in human
narration and might be capable of explaining Menzerath's law.


title:
Two-dimensional cellular automata and the analysis of correlated time
  series

abstract:
  Correlated time series are time series that, by virtue of the underlying
process to which they refer, are expected to influence each other strongly. We
introduce a novel approach to handle such time series, one that models their
interaction as a two-dimensional cellular automaton and therefore allows them
to be treated as a single entity. We apply our approach to the problems of
filling gaps and predicting values in rainfall time series. Computational
results show that the new approach compares favorably to Kalman smoothing and
filtering.


title:
Experiments in Clustering Homogeneous XML Documents to Validate an
  Existing Typology

abstract:
  This paper presents some experiments in clustering homogeneous XMLdocuments
to validate an existing classification or more generally anorganisational
structure. Our approach integrates techniques for extracting knowledge from
documents with unsupervised classification (clustering) of documents. We focus
on the feature selection used for representing documents and its impact on the
emerging classification. We mix the selection of structured features with fine
textual selection based on syntactic characteristics.We illustrate and evaluate
this approach with a collection of Inria activity reports for the year 2003.
The objective is to cluster projects into larger groups (Themes), based on the
keywords or different chapters of these activity reports. We then compare the
results of clustering using different feature selections, with the official
theme structure used by Inria.


title: Comparison of Resampling Schemes for Particle Filtering

abstract:
  This contribution is devoted to the comparison of various resampling
approaches that have been proposed in the literature on particle filtering. It
is first shown using simple arguments that the so-called residual and
stratified methods do yield an improvement over the basic multinomial
resampling approach. A simple counter-example showing that this property does
not hold true for systematic resampling is given. Finally, some results on the
large-sample behavior of the simple bootstrap filter algorithm are given. In
particular, a central limit theorem is established for the case where
resampling is performed using the residual approach.


title: Hard Problems of Algebraic Geometry Codes

abstract:
  The minimum distance is one of the most important combinatorial
characterizations of a code. The maximum likelihood decoding problem is one of
the most important algorithmic problems of a code. While these problems are
known to be hard for general linear codes, the techniques used to prove their
hardness often rely on the construction of artificial codes. In general, much
less is known about the hardness of the specific classes of natural linear
codes. In this paper, we show that both problems are
  NP-hard for algebraic geometry codes. We achieve this by reducing a
well-known NP-complete problem to these problems using a randomized algorithm.
The family of codes in the reductions are based on elliptic curves. They have
positive rates, but the alphabet sizes are exponential in the block lengths.


title: Anyone but Him: The Complexity of Precluding an Alternative

abstract:
  Preference aggregation in a multiagent setting is a central issue in both
human and computer contexts. In this paper, we study in terms of complexity the
vulnerability of preference aggregation to destructive control. That is, we
study the ability of an election's chair to, through such mechanisms as
voter/candidate addition/suppression/partition, ensure that a particular
candidate (equivalently, alternative) does not win. And we study the extent to
which election systems can make it impossible, or computationally costly
(NP-complete), for the chair to execute such control. Among the systems we
study--plurality, Condorcet, and approval voting--we find cases where systems
immune or computationally resistant to a chair choosing the winner nonetheless
are vulnerable to the chair blocking a victory. Beyond that, we see that among
our studied systems no one system offers the best protection against
destructive control. Rather, the choice of a preference aggregation system will
depend closely on which types of control one wishes to be protected against. We
also find concrete cases where the complexity of or susceptibility to control
varies dramatically based on the choice among natural tie-handling rules.


title: Adapting CBPP platforms for instructional use

abstract:
  Commons based peer-production (CBPP) is the de-centralized, net-based
approach to the creation and dissemination of information resources. Underlying
every CBPP system is a virtual community brought together by an internet tool
(such as a web site) and structured by a specific collaboration protocol. In
this talk we will argue that the value of such platforms can be leveraged by
adapting them for pedagogical purposes.
  We report on one such recent adaptation. The Noosphere system is a web-based
collaboration environment that underlies the popular Planetmath website, a
collaboratively written encyclopedia of mathematics licensed under the GNU Free
Documentation License (FDL). Recently, the system was used to host a
graduate-level mathematics course at Dalhousie University, in Halifax, Canada.
The course consisted of regular lectures and assignment problems. The students
in the course collaborated on a set of course notes, encapsulating the lecture
content and giving solutions of assigned problems. The successful outcome of
this experiment demonstrated that a dedicated Noosphere system is well suited
for classroom applications. We argue that this ``proof of concept'' experience
also strongly suggests that every successful CBPP platform possesses latent
pedagogical value.


title: ATNoSFERES revisited

abstract:
  ATNoSFERES is a Pittsburgh style Learning Classifier System (LCS) in which
the rules are represented as edges of an Augmented Transition Network.
Genotypes are strings of tokens of a stack-based language, whose execution
builds the labeled graph. The original ATNoSFERES, using a bitstring to
represent the language tokens, has been favorably compared in previous work to
several Michigan style LCSs architectures in the context of Non Markov
problems. Several modifications of ATNoSFERES are proposed here: the most
important one conceptually being a representational change: each token is now
represented by an integer, hence the genotype is a string of integers; several
other modifications of the underlying grammar language are also proposed. The
resulting ATNoSFERES-II is validated on several standard animat Non Markov
problems, on which it outperforms all previously published results in the LCS
literature. The reasons for these improvement are carefully analyzed, and some
assumptions are proposed on the underlying mechanisms in order to explain these
good results.


title: Strictly convex drawings of planar graphs

abstract:
  Every three-connected planar graph with n vertices has a drawing on an O(n^2)
x O(n^2) grid in which all faces are strictly convex polygons. These drawings
are obtained by perturbing (not strictly) convex drawings on O(n) x O(n) grids.
More generally, a strictly convex drawing exists on a grid of size O(W) x
O(n^4/W), for any choice of a parameter W in the range n<W<n^2. Tighter bounds
are obtained when the faces have fewer sides.
  In the proof, we derive an explicit lower bound on the number of primitive
vectors in a triangle.


title: The error-floor of LDPC codes in the Laplacian channel

abstract:
  We analyze the performance of Low-Density-Parity-Check codes in the
error-floor domain where the Signal-to-Noise-Ratio, s, is large, s >> 1. We
describe how the instanton method of theoretical physics, recently adapted to
coding theory, solves the problem of characterizing the error-floor domain in
the Laplacian channel. An example of the (155,64,20) LDPC code with four
iterations (each iteration consisting of two semi-steps: from bits-to-checks
and from checks-to-bits) of the min-sum decoding is discussed. A generalized
computational tree analysis is devised to explain the rational structure of the
leading instantons. The asymptotic for the symbol Bit-Error-Rate in the
error-floor domain is comprised of individual instanton contributions, each
estimated as ~ \exp(-l_{inst;L} s), where the effective distances, l_{inst;L},
of the the leading instantons are 7.6, 8.0 and 8.0 respectively. (The Hamming
distance of the code is 20.) The analysis shows that the instantons are
distinctly different from the ones found for the same coding/decoding scheme
performing over the Gaussian channel. We validate instanton results against
direct simulations and offer an explanation for remarkable performance of the
instanton approximation not only in the extremal, s -> \infty, limit but also
at the moderate s values of practical interest.


title: Introduction to Quantum Message Space

abstract:
  This paper develops the quantum analog of the message ensemble of classical
information theory as developed by Shannon and Khinchin. The principal
mathematical tool is harmonic analysis on the free group with two generators.


title: Multiresolution Kernels

abstract:
  We present in this work a new methodology to design kernels on data which is
structured with smaller components, such as text, images or sequences. This
methodology is a template procedure which can be applied on most kernels on
measures and takes advantage of a more detailed "bag of components"
representation of the objects. To obtain such a detailed description, we
consider possible decompositions of the original bag into a collection of
nested bags, following a prior knowledge on the objects' structure. We then
consider these smaller bags to compare two objects both in a detailed
perspective, stressing local matches between the smaller bags, and in a global
or coarse perspective, by considering the entire bag. This multiresolution
approach is likely to be best suited for tasks where the coarse approach is not
precise enough, and where a more subtle mixture of both local and global
similarities is necessary to compare objects. The approach presented here would
not be computationally tractable without a factorization trick that we
introduce before presenting promising results on an image retrieval task.


title: Papillon: Greedy Routing in Rings

abstract:
  We study {\sc greedy} routing over $n$ nodes placed in a ring, with the
\emph{distance} between two nodes defined to be the clockwise or the absolute
distance between them along the ring. Such graphs arise in the context of
modeling social networks and in routing networks for peer-to-peer systems. We
construct the first network over $n$ nodes in which {\sc greedy} routing takes
$O(\log n / \log d)$ hops in the worst-case, with $d$ out-going links per node.
Our result has the first asymptotically optimal greedy routing complexity.
Previous constructions required $O(\frac{\log^2 n}{d})$ hops.


title: Enhancing Global SLS-Resolution with Loop Cutting and Tabling Mechanisms

abstract:
  Global SLS-resolution is a well-known procedural semantics for top-down
computation of queries under the well-founded model. It inherits from
SLDNF-resolution the {\em linearity} property of derivations, which makes it
easy and efficient to implement using a simple stack-based memory structure.
However, like SLDNF-resolution it suffers from the problem of infinite loops
and redundant computations. To resolve this problem, in this paper we develop a
new procedural semantics, called {\em SLTNF-resolution}, by enhancing Global
SLS-resolution with loop cutting and tabling mechanisms. SLTNF-resolution is
sound and complete w.r.t. the well-founded semantics for logic programs with
the bounded-term-size property, and is superior to existing linear tabling
procedural semantics such as SLT-resolution.


title: Improved Inference for Checking Annotations

abstract:
  We consider type inference in the Hindley/Milner system extended with type
annotations and constraints with a particular focus on Haskell-style type
classes. We observe that standard inference algorithms are incomplete in the
presence of nested type annotations. To improve the situation we introduce a
novel inference scheme for checking type annotations. Our inference scheme is
also incomplete in general but improves over existing implementations as found
e.g. in the Glasgow Haskell Compiler (GHC). For certain cases (e.g. Haskell 98)
our inference scheme is complete. Our approach has been fully implemented as
part of the Chameleon system (experimental version of Haskell).


title: Type Inference for Guarded Recursive Data Types

abstract:
  We consider type inference for guarded recursive data types (GRDTs) -- a
recent generalization of algebraic data types. We reduce type inference for
GRDTs to unification under a mixed prefix. Thus, we obtain efficient type
inference. Inference is incomplete because the set of type constraints allowed
to appear in the type system is only a subset of those type constraints
generated by type inference. Hence, inference only succeeds if the program is
sufficiently type annotated. We present refined procedures to infer types
incrementally and to assist the user in identifying which pieces of type
information are missing. Additionally, we introduce procedures to test if a
type is not principal and to find a principal type if one exists.


title:
Upper Bound on the Number of Vertices of Polyhedra with $0,1$-Constraint
  Matrices

abstract:
  In this note we show that the maximum number of vertices in any polyhedron
$P=\{x\in \mathbb{R}^d : Ax\leq b\}$ with $0,1$-constraint matrix $A$ and a
real vector $b$ is at most $d!$.


title:
Distributed Regression in Sensor Networks: Training Distributively with
  Alternating Projections

abstract:
  Wireless sensor networks (WSNs) have attracted considerable attention in
recent years and motivate a host of new challenges for distributed signal
processing. The problem of distributed or decentralized estimation has often
been considered in the context of parametric models. However, the success of
parametric methods is limited by the appropriateness of the strong statistical
assumptions made by the models. In this paper, a more flexible nonparametric
model for distributed regression is considered that is applicable in a variety
of WSN applications including field estimation. Here, starting with the
standard regularized kernel least-squares estimator, a message-passing
algorithm for distributed estimation in WSNs is derived. The algorithm can be
viewed as an instantiation of the successive orthogonal projection (SOP)
algorithm. Various practical aspects of the algorithm are discussed and several
numerical simulations validate the potential of the approach.


title: Pattern Recognition for Conditionally Independent Data

abstract:
  In this work we consider the task of relaxing the i.i.d assumption in pattern
recognition (or classification), aiming to make existing learning algorithms
applicable to a wider range of tasks. Pattern recognition is guessing a
discrete label of some object based on a set of given examples (pairs of
objects and labels). We consider the case of deterministically defined labels.
Traditionally, this task is studied under the assumption that examples are
independent and identically distributed. However, it turns out that many
results of pattern recognition theory carry over a weaker assumption. Namely,
under the assumption of conditional independence and identical distribution of
objects, while the only assumption on the distribution of labels is that the
rate of occurrence of each label should be above some positive threshold.
  We find a broad class of learning algorithms for which estimations of the
probability of a classification error achieved under the classical i.i.d.
assumption can be generalised to the similar estimates for the case of
conditionally i.i.d. examples.


title: Monotone Conditional Complexity Bounds on Future Prediction Errors

abstract:
  We bound the future loss when predicting any (computably) stochastic sequence
online. Solomonoff finitely bounded the total deviation of his universal
predictor M from the true distribution m by the algorithmic complexity of m.
Here we assume we are at a time t>1 and already observed x=x_1...x_t. We bound
the future prediction performance on x_{t+1}x_{t+2}... by a new variant of
algorithmic complexity of m given x, plus the complexity of the randomness
deficiency of x. The new complexity is monotone in its condition in the sense
that this complexity can only decrease if the condition is prolonged. We also
briefly discuss potential generalizations to Bayesian model classes and to
classification problems.


title: The MammoGrid Virtual Organisation - Federating Distributed Mammograms

abstract:
  The MammoGrid project aims to deliver a prototype which enables the effective
collaboration between radiologists using grid, service-orientation and database
solutions. The grid technologies and service-based database management solution
provide the platform for integrating diverse and distributed resources,
creating what is called a virtual organisation. The MammoGrid Virtual
Organisation facilitates the sharing and coordinated access to mammography
data, medical imaging software and computing resources of participating
hospitals. Hospitals manage their local database of mammograms, but in
addition, radiologists who are part of this organisation can share mammograms,
reports, results and image analysis software. The MammoGrid Virtual
Organisation is a federation of autonomous multi-centres sites which transcends
national boundaries. This paper outlines the service-based approach in the
creation and management of the federated distributed mammography database and
discusses the role of virtual organisations in distributed image analysis.


title: Proof rules for purely quantum programs

abstract:
  We apply the notion of quantum predicate proposed by D'Hondt and Panangaden
to analyze a purely quantum language fragment which describes the quantum part
of a future quantum computer in Knill's architecture. The denotational
semantics, weakest precondition semantics, and weakest liberal precondition
semantics of this language fragment are introduced. To help reasoning about
quantum programs involving quantum loops, we extend proof rules for classical
probabilistic programs to our purely quantum programs.


title: Defensive Universal Learning with Experts

abstract:
  This paper shows how universal learning can be achieved with expert advice.
To this aim, 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 a master
algorithm for "reactive" 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. The resulting universal learner
performs -- in a certain sense -- almost as well as any computable strategy,
for any online decision problem. We also specify the (worst-case) convergence
speed, which is very slow.


title: In the beginning was game semantics

abstract:
  This article presents an overview of computability logic -- the
game-semantically constructed logic of interactive computational tasks and
resources. There is only one non-overview, technical section in it, devoted to
a proof of the soundness of affine logic with respect to the semantics of
computability logic. A comprehensive online source on the subject can be found
at http://www.cis.upenn.edu/~giorgi/cl.html


title: Revisiting Internet AS-level Topology Discovery

abstract:
  The development of veracious models of the Internet topology has received a
lot of attention in the last few years. Many proposed models are based on
topologies derived from RouteViews BGP table dumps (BTDs). However, BTDs do not
capture all AS-links of the Internet topology and most importantly the number
of the hidden AS-links is unknown, resulting in AS-graphs of questionable
quality. As a first step to address this problem, we introduce a new
AS-topology discovery methodology that results in more complete and accurate
graphs. Moreover, we use data available from existing measurement facilities,
circumventing the burden of additional measurement infrastructure. We deploy
our methodology and construct an AS-topology that has at least 61.5% more
AS-links than BTD-derived AS-topologies we examined. Finally, we analyze the
temporal and topological properties of the augmented graph and pinpoint the
differences from BTD-derived AS-topologies.


title: Inferring AS Relationships: Dead End or Lively Beginning?

abstract:
  Recent techniques for inferring business relationships between ASs have
yielded maps that have extremely few invalid BGP paths in the terminology of
Gao. However, some relationships inferred by these newer algorithms are
incorrect, leading to the deduction of unrealistic AS hierarchies. We
investigate this problem and discover what causes it. Having obtained such
insight, we generalize the problem of AS relationship inference as a
multiobjective optimization problem with node-degree-based corrections to the
original objective function of minimizing the number of invalid paths. We solve
the generalized version of the problem using the semidefinite programming
relaxation of the MAX2SAT problem. Keeping the number of invalid paths small,
we obtain a more veracious solution than that yielded by recent heuristics.


title: Redundancy in Logic III: Non-Mononotonic Reasoning

abstract:
  Results about the redundancy of circumscriptive and default theories are
presented. In particular, the complexity of establishing whether a given theory
is redundant is establihsed.


title:
The Skip Quadtree: A Simple Dynamic Data Structure for Multidimensional
  Data

abstract:
  We present a new multi-dimensional data structure, which we call the skip
quadtree (for point data in R^2) or the skip octree (for point data in R^d,
with constant d>2). Our data structure combines the best features of two
well-known data structures, in that it has the well-defined "box"-shaped
regions of region quadtrees and the logarithmic-height search and update
hierarchical structure of skip lists. Indeed, the bottom level of our structure
is exactly a region quadtree (or octree for higher dimensional data). We
describe efficient algorithms for inserting and deleting points in a skip
quadtree, as well as fast methods for performing point location and approximate
range queries.


title:
Skip-Webs: Efficient Distributed Data Structures for Multi-Dimensional
  Data Sets

abstract:
  We present a framework for designing efficient distributed data structures
for multi-dimensional data. Our structures, which we call skip-webs, extend and
improve previous randomized distributed data structures, including skipnets and
skip graphs. Our framework applies to a general class of data querying
scenarios, which include linear (one-dimensional) data, such as sorted sets, as
well as multi-dimensional data, such as d-dimensional octrees and digital tries
of character strings defined over a fixed alphabet. We show how to perform a
query over such a set of n items spread among n hosts using O(log n / log log
n) messages for one-dimensional data, or O(log n) messages for
fixed-dimensional data, while using only O(log n) space per host. We also show
how to make such structures dynamic so as to allow for insertions and deletions
in O(log n) messages for quadtrees, octrees, and digital tries, and O(log n /
log log n) messages for one-dimensional data. Finally, we show how to apply a
blocking strategy to skip-webs to further improve message complexity for
one-dimensional data when hosts can store more data.


title: Confluent Layered Drawings

abstract:
  We combine the idea of confluent drawings with Sugiyama style drawings, in
order to reduce the edge crossings in the resultant drawings. Furthermore, it
is easier to understand the structures of graphs from the mixed style drawings.
The basic idea is to cover a layered graph by complete bipartite subgraphs
(bicliques), then replace bicliques with tree-like structures. The biclique
cover problem is reduced to a special edge coloring problem and solved by
heuristic coloring algorithms. Our method can be extended to obtain multi-depth
confluent layered drawings.


title: Finite automata for testing uniqueness of Eulerian trails

abstract:
  We investigate the condition under which the Eulerian trail of a digraph is
unique, and design a finite automaton to examine it. The algorithm is
effective, for if the condition is violated, it will be noticed immediately
without the need to trace through the whole trail.


title: Nonrepetitive Paths and Cycles in Graphs with Application to Sudoku

abstract:
  We provide a simple linear time transformation from a directed or undirected
graph with labeled edges to an unlabeled digraph, such that paths in the input
graph in which no two consecutive edges have the same label correspond to paths
in the transformed graph and vice versa. Using this transformation, we provide
efficient algorithms for finding paths and cycles with no two consecutive equal
labels. We also consider related problems where the paths and cycles are
required to be simple; we find efficient algorithms for the undirected case of
these problems but show the directed case to be NP-complete. We apply our path
and cycle finding algorithms in a program for generating and solving Sudoku
puzzles, and show experimentally that they lead to effective puzzle-solving
rules that may also be of interest to human Sudoku puzzle solvers.


title: f2mma: FORTRAN to Mathematica translator

abstract:
  f2mma program can be used to translate programs written in some subset of the
FORTRAN language into {\sl Mathematica} system's programming language. This
subset have been enough to translate GAPP (Global Analysis of Particle
Properties) programm into {\sl Mathematica} language automatically. Observables
table calculated with GAPP({\sl Mathematica}) is presented.


title: ReacProc: A Tool to Process Reactions Describing Particle Interactions

abstract:
  ReacProc is a program written in C/C++ programming language which can be used
(1) to check out of reactions describing particles interactions against
conservation laws and (2) to reduce input reaction into some canonical form. A
table with particles properties is available within ReacProc package.


title: Explorations in engagement for humans and robots

abstract:
  This paper explores the concept of engagement, the process by which
individuals in an interaction start, maintain and end their perceived
connection to one another. The paper reports on one aspect of engagement among
human interactors--the effect of tracking faces during an interaction. It also
describes the architecture of a robot that can participate in conversational,
collaborative interactions with engagement gestures. Finally, the paper reports
on findings of experiments with human participants who interacted with a robot
when it either performed or did not perform engagement gestures. Results of the
human-robot studies indicate that people become engaged with robots: they
direct their attention to the robot more often in interactions where engagement
gestures are present, and they find interactions more appropriate when
engagement gestures are present than when they are not.


title: A new sibling of BQP

abstract:
  We present a new quantum complexity class, called MQ^2, which is contained in
AWPP. This class has a compact and simple mathematical definition, involving
only polynomial-time computable functions and a unitarity condition. It
contains both Deutsch-Jozsa's and Shor's algorithm, while its relation to BQP
is unknown. This shows that in the complexity class hierarchy, BQP is not an
extraordinary isolated island, but has ''siblings'' which as well can solve
prime-factorization.


title:
Paving the Way for Image Understanding: A New Kind of Image
  Decomposition is Desired

abstract:
  In this paper we present an unconventional image segmentation approach which
is devised to meet the requirements of image understanding and pattern
recognition tasks. Generally image understanding assumes interplay of two
sub-processes: image information content discovery and image information
content interpretation. Despite of its widespread use, the notion of "image
information content" is still ill defined, intuitive, and ambiguous. Most
often, it is used in the Shannon's sense, which means information content
assessment averaged over the whole signal ensemble. Humans, however,rarely
resort to such estimates. They are very effective in decomposing images into
their meaningful constituents and focusing attention to the perceptually
relevant image parts. We posit that following the latest findings in human
attention vision studies and the concepts of Kolmogorov's complexity theory an
unorthodox segmentation approach can be proposed that provides effective image
decomposition to information preserving image fragments well suited for
subsequent image interpretation. We provide some illustrative examples,
demonstrating effectiveness of this approach.


title:
Data complexity of answering conjunctive queries over SHIQ knowledge
  bases

abstract:
  An algorithm for answering conjunctive queries over SHIQ knowledge bases that
is coNP in data complexity is given. The algorithm is based on the tableau
algorithm for reasoning with individuals in SHIQ. The blocking conditions of
the tableau are weakened in such a way that the set of models the modified
algorithm yields suffices to check query entailment. The modified blocking
conditions are based on the ones proposed by Levy and Rousset for reasoning
with Horn Rules in the description logic ALCNR.


title: The Entropy of a Binary Hidden Markov Process

abstract:
  The entropy of a binary symmetric Hidden Markov Process is calculated as an
expansion in the noise parameter epsilon. We map the problem onto a
one-dimensional Ising model in a large field of random signs and calculate the
expansion coefficients up to second order in epsilon. Using a conjecture we
extend the calculation to 11th order and discuss the convergence of the
resulting series.

categories: cs.IT cond-mat.stat-mech math.IT math.ST stat.TH


title: Software Architecture Overview

abstract:
  What is Software Architecture? The rules, paradigmen, pattern that help to
construct, build and test a serious piece of software. It is the practical
experience boiled down to abstract level. Software Architecture builds on
System Engineering and the scientific method as established by Galileo Galilei:
Measure what you can and make measureable what you can not. The experiment
(test) is more important then the deduction. Pieces of information about
software architecture are all over the internet. This paper uses citation as
much as possible. The aim is to bring together an overview, not to rephrase the
wording.


title: FPL Analysis for Adaptive Bandits

abstract:
  A main problem of "Follow the Perturbed Leader" strategies for online
decision problems is that regret bounds are typically proven against oblivious
adversary. In partial observation cases, it was not clear how to obtain
performance guarantees against adaptive adversary, without worsening the
bounds. We propose a conceptually simple argument to resolve this problem.
Using this, a regret bound of O(t^(2/3)) for FPL in the adversarial multi-armed
bandit problem is shown. This bound holds for the common FPL variant using only
the observations from designated exploration rounds. Using all observations
allows for the stronger bound of O(t^(1/2)), matching the best bound known so
far (and essentially the known lower bound) for adversarial bandits.
Surprisingly, this variant does not even need explicit exploration, it is
self-stabilizing. However the sampling probabilities have to be either
externally provided or approximated to sufficient accuracy, using O(t^2 log t)
samples in each step.


title: Theoretical cryptanalysis of the Klimov-Shamir number generator TF-1

abstract:
  The internal state of the Klimov-Shamir number generator TF-1 consists of
four words of size w bits each, whereas its intended strength is 2^{2w}. We
exploit an asymmetry in its output function to show that the internal state can
be recovered after having 2^w outputs, using 2^{1.5w} operations. For w=32 the
attack is practical, but for their recommended w=64 it is only of theoretical
interest.


title: Termination of rewriting strategies: a generic approach

abstract:
  We propose a generic termination proof method for rewriting under strategies,
based on an explicit induction on the termination property. Rewriting trees on
ground terms are modeled by proof trees, generated by alternatively applying
narrowing and abstracting steps. The induction principle is applied through the
abstraction mechanism, where terms are replaced by variables representing any
of their normal forms. The induction ordering is not given a priori, but
defined with ordering constraints, incrementally set during the proof.
Abstraction constraints can be used to control the narrowing mechanism, well
known to easily diverge. The generic method is then instantiated for the
innermost, outermost and local strategies.


title: A Fast Greedy Algorithm for Outlier Mining

abstract:
  The task of outlier detection is to find small groups of data objects that
are exceptional when compared with rest large amount of data. In [38], the
problem of outlier detection in categorical data is defined as an optimization
problem and a local-search heuristic based algorithm (LSA) is presented.
However, as is the case with most iterative type algorithms, the LSA algorithm
is still very time-consuming on very large datasets. In this paper, we present
a very fast greedy algorithm for mining outliers under the same optimization
model. Experimental results on real datasets and large synthetic datasets show
that: (1) Our algorithm has comparable performance with respect to those
state-of-art outlier detection algorithms on identifying true outliers and (2)
Our algorithm can be an order of magnitude faster than LSA algorithm.


title: Authentication Schemes Using Braid Groups

abstract:
  In this paper we proposed two identification schemes based on the root
problem. The proposed schemes are secure against passive attacks assuming that
the root problem (RP) is hard in braid groups.


title:
Conjunctive Query Containment and Answering under Description Logics
  Constraints

abstract:
  Query containment and query answering are two important computational tasks
in databases. While query answering amounts to compute the result of a query
over a database, query containment is the problem of checking whether for every
database, the result of one query is a subset of the result of another query.
  In this paper, we deal with unions of conjunctive queries, and we address
query containment and query answering under Description Logic constraints.
Every such constraint is essentially an inclusion dependencies between concepts
and relations, and their expressive power is due to the possibility of using
complex expressions, e.g., intersection and difference of relations, special
forms of quantification, regular expressions over binary relations, in the
specification of the dependencies. These types of constraints capture a great
variety of data models, including the relational, the entity-relationship, and
the object-oriented model, all extended with various forms of constraints, and
also the basic features of the ontology languages used in the context of the
Semantic Web.
  We present the following results on both query containment and query
answering. We provide a method for query containment under Description Logic
constraints, thus showing that the problem is decidable, and analyze its
computational complexity. We prove that query containment is undecidable in the
case where we allow inequalities in the right-hand side query, even for very
simple constraints and queries. We show that query answering under Description
Logic constraints can be reduced to query containment, and illustrate how such
a reduction provides upper bound results with respect to both combined and data
complexity.


title:
On parity check collections for iterative erasure decoding that correct
  all correctable erasure patterns of a given size

abstract:
  Recently there has been interest in the construction of small parity check
sets for iterative decoding of the Hamming code with the property that each
uncorrectable (or stopping) set of size three is the support of a codeword and
hence uncorrectable anyway. Here we reformulate and generalise the problem, and
improve on this construction. First we show that a parity check collection that
corrects all correctable erasure patterns of size m for the r-th order Hamming
code (i.e, the Hamming code with codimension r) provides for all codes of
codimension $r$ a corresponding ``generic'' parity check collection with this
property. This leads naturally to a necessary and sufficient condition on such
generic parity check collections. We use this condition to construct a generic
parity check collection for codes of codimension r correcting all correctable
erasure patterns of size at most m, for all r and m <= r, thus generalising the
known construction for m=3. Then we discussoptimality of our construction and
show that it can be improved for m>=3 and r large enough. Finally we discuss
some directions for further research.


title:
Users and Assessors in the Context of INEX: Are Relevance Dimensions
  Relevant?

abstract:
  The main aspects of XML retrieval are identified by analysing and comparing
the following two behaviours: the behaviour of the assessor when judging the
relevance of returned document components; and the behaviour of users when
interacting with components of XML documents. We argue that the two INEX
relevance dimensions, Exhaustivity and Specificity, are not orthogonal
dimensions; indeed, an empirical analysis of each dimension reveals that the
grades of the two dimensions are correlated to each other. By analysing the
level of agreement between the assessor and the users, we aim at identifying
the best units of retrieval. The results of our analysis show that the highest
level of agreement is on highly relevant and on non-relevant document
components, suggesting that only the end points of the INEX 10-point relevance
scale are perceived in the same way by both the assessor and the users. We
propose a new definition of relevance for XML retrieval and argue that its
corresponding relevance scale would be a better choice for INEX.


title:
Hybrid XML Retrieval: Combining Information Retrieval and a Native XML
  Database

abstract:
  This paper investigates the impact of three approaches to XML retrieval:
using Zettair, a full-text information retrieval system; using eXist, a native
XML database; and using a hybrid system that takes full article answers from
Zettair and uses eXist to extract elements from those articles. For the
content-only topics, we undertake a preliminary analysis of the INEX 2003
relevance assessments in order to identify the types of highly relevant
document components. Further analysis identifies two complementary sub-cases of
relevance assessments ("General" and "Specific") and two categories of topics
("Broad" and "Narrow"). We develop a novel retrieval module that for a
content-only topic utilises the information from the resulting answer list of a
native XML database and dynamically determines the preferable units of
retrieval, which we call "Coherent Retrieval Elements". The results of our
experiments show that -- when each of the three systems is evaluated against
different retrieval scenarios (such as different cases of relevance
assessments, different topic categories and different choices of evaluation
metrics) -- the XML retrieval systems exhibit varying behaviour and the best
performance can be reached for different values of the retrieval parameters. In
the case of INEX 2003 relevance assessments for the content-only topics, our
newly developed hybrid XML retrieval system is substantially more effective
than either Zettair or eXist, and yields a robust and a very effective XML
retrieval.


title:
Security for Distributed Web-Applications via Aspect-Oriented
  Programming

abstract:
  Identity Management is becoming more and more important in business systems
as they are opened for third parties including trading partners, consumers and
suppliers. This paper presents an approach securing a system without any
knowledge of the system source code. The security module adds to the existing
system authentication and authorisation based on aspect oriented programming
and the liberty alliance framework, an upcoming industrie standard providing
single sign on. In an initial training phase the module is adapted to the
application which is to be secured. Moreover the use of hardware tokens and
proactive computing is demonstrated. The high modularisation is achived through
use of AspectJ, a programming language extension of Java.


title: Reliable Data Storage in Distributed Hash Tables

abstract:
  Distributed Hash Tables offer a resilient lookup service for unstable
distributed environments. Resilient data storage, however, requires additional
data replication and maintenance algorithms. These algorithms can have an
impact on both the performance and the scalability of the system. In this
paper, we describe the goals and design space of these replication algorithms.
  We examine an existing replication algorithm, and present a new analysis of
its reliability. We then present a new dynamic replication algorithm which can
operate in unstable environments. We give several possible replica placement
strategies for this algorithm, and show how they impact reliability and
performance.
  Finally we compare all replication algorithms through simulation, showing
quantitatively the difference between their bandwidth use, fault tolerance and
performance.


title: Software Performance Analysis

abstract:
  The key to speeding up applications is often understanding where the elapsed
time is spent, and why. This document reviews in depth the full array of
performance analysis tools and techniques available on Linux for this task,
from the traditional tools like gcov and gprof, to the more advanced tools
still under development like oprofile and the Linux Trace Toolkit. The focus is
more on the underlying data collection and processing algorithms, and their
overhead and precision, than on the cosmetic details of the graphical user
interface frontends.


title: Dimensions of Copeland-Erdos Sequences

abstract:
  The base-$k$ {\em Copeland-Erd\"os sequence} given by an infinite set $A$ of
positive integers is the infinite sequence $\CE_k(A)$ formed by concatenating
the base-$k$ representations of the elements of $A$ in numerical order. This
paper concerns the following four quantities.
  The {\em finite-state dimension} $\dimfs (\CE_k(A))$, a finite-state version
of classical Hausdorff dimension introduced in 2001.
  The {\em finite-state strong dimension} $\Dimfs(\CE_k(A))$, a finite-state
version of classical packing dimension introduced in 2004. This is a dual of
$\dimfs(\CE_k(A))$ satisfying $\Dimfs(\CE_k(A))$ $\geq \dimfs(\CE_k(A))$.
  The {\em zeta-dimension} $\Dimzeta(A)$, a kind of discrete fractal dimension
discovered many times over the past few decades.
  The {\em lower zeta-dimension} $\dimzeta(A)$, a dual of $\Dimzeta(A)$
satisfying $\dimzeta(A)\leq \Dimzeta(A)$.
  We prove the following.
  $\dimfs(\CE_k(A))\geq \dimzeta(A)$. This extends the 1946 proof by Copeland
and Erd\"os that the sequence $\CE_k(\mathrm{PRIMES})$ is Borel normal.
  $\Dimfs(\CE_k(A))\geq \Dimzeta(A)$.
  These bounds are tight in the strong sense that these four quantities can
have (simultaneously) any four values in $[0,1]$ satisfying the four
above-mentioned inequalities.


title:
Methods for Analytical Understanding of Agent-Based Modeling of Complex
  Systems

abstract:
  Von Neuman's work on universal machines and the hardware development have
allowed the simulation of dynamical systems through a large set of interacting
agents. This is a bottom-up approach which tries to derive global properties of
a complex system through local interaction rules and agent behaviour.
Traditionally, such systems are modeled and simulated through top-down methods
based on differential equations. Agent-Based Modeling has the advantage of
simplicity and low computational cost. However, unlike differential equations,
there is no standard way to express agent behaviour. Besides, it is not clear
how to analytically predict the results obtained by the simulation. In this
paper we survey some of these methods. For expressing agent behaviour formal
methods, like Stochastic Process Algebras have been used. Such approach is
useful if the global properties of interest can be expressed as a function of
stochastic time series. However, if space variables must be considered, we
shall change the focus. In this case, multiscale techniques, based on
Chapman-Enskog expansion, was used to establish the connection between the
microscopic dynamics and the macroscopic observables. Also, we use data mining
techniques,like Principal Component Analysis (PCA), to study agent systems like
Cellular Automata. With the help of these tools we will discuss a simple
society model, a Lattice Gas Automaton for fluid modeling, and knowledge
discovery in CA databases. Besides, we show the capabilities of the NetLogo, a
software for agent simulation of complex system and show our experience about.


title: Model Checking Probabilistic Pushdown Automata

abstract:
  We consider the model checking problem for probabilistic pushdown automata
(pPDA) and properties expressible in various probabilistic logics. We start
with properties that can be formulated as instances of a generalized random
walk problem. We prove that both qualitative and quantitative model checking
for this class of properties and pPDA is decidable. Then we show that model
checking for the qualitative fragment of the logic PCTL and pPDA is also
decidable. Moreover, we develop an error-tolerant model checking algorithm for
PCTL and the subclass of stateless pPDA. Finally, we consider the class of
omega-regular properties and show that both qualitative and quantitative model
checking for pPDA is decidable.


title: A three-valued semantics for logic programmers

abstract:
  This paper describes a simpler way for programmers to reason about the
correctness of their code. The study of semantics of logic programs has shown
strong links between the model theoretic semantics (truth and falsity of atoms
in the programmer's interpretation of a program), procedural semantics (for
example, SLD resolution) and fixpoint semantics (which is useful for program
analysis and alternative execution mechanisms). Most of this work assumes that
intended interpretations are two-valued: a ground atom is true (and should
succeed according to the procedural semantics) or false (and should not
succeed). In reality, intended interpretations are less precise. Programmers
consider that some atoms "should not occur" or are "ill-typed" or
"inadmissible". Programmers don't know and don't care whether such atoms
succeed. In this paper we propose a three-valued semantics for (essentially)
pure Prolog programs with (ground) negation as failure which reflects this. The
semantics of Fitting is similar but only associates the third truth value with
non-termination. We provide tools to reason about correctness of programs
without the need for unnatural precision or undue restrictions on programming
style. As well as theoretical results, we provide a programmer-oriented
synopsis. This work has come out of work on declarative debugging, where it has
been recognised that inadmissible calls are important. This paper has been
accepted to appear in Theory and Practice of Logic Programming.


title: Logic Column 13: Reasoning Formally about Quantum Systems: An Overview

abstract:
  This article is intended as an introduction to the subject of quantum logic,
and as a brief survey of the relevant literature. Also discussed here are
logics for specification and analysis of quantum information systems, in
particular, recent work by P. Mateus and A. Sernadas, and also by R. van der
Meyden and M. Patra. Overall, our objective is to provide a high-level
presentation of the logical aspects of quantum theory. Mateus' and Sernadas'
EQPL logic is illustrated with a small example, namely the state of an
entangled pair of qubits. The "KT" logic of van der Meyden and Patra is
demonstrated briefly in the context of the B92 protocol for quantum key
distribution.


title: A New Approach for Boundary Recognition in Geometric Sensor Networks

abstract:
  We describe a new approach for dealing with the following central problem in
the self-organization of a geometric sensor network: Given a polygonal region
R, and a large, dense set of sensor nodes that are scattered uniformly at
random in R. There is no central control unit, and nodes can only communicate
locally by wireless radio to all other nodes that are within communication
radius r, without knowing their coordinates or distances to other nodes. The
objective is to develop a simple distributed protocol that allows nodes to
identify themselves as being located near the boundary of R and form connected
pieces of the boundary. We give a comparison of several centrality measures
commonly used in the analysis of social networks and show that restricted
stress centrality is particularly suited for geometric networks; we provide
mathematical as well as experimental evidence for the quality of this measure.


title: Regularity of Position Sequences

abstract:
  A person is given a numbered sequence of positions on a sheet of paper. The
person is asked, "Which will be the next (or the next after that) position?"
Everyone has an opinion as to how he or she would proceed. There are regular
sequences for which there is general agreement on how to continue. However,
there are less regular sequences for which this assessment is less certain.
There are sequences for which every continuation is perceived to be arbitrary.
I would like to present a mathematical model that reflects these opinions and
perceptions with the aid of a valuation function. It is necessary to apply a
rich set of invariant features of position sequences to ensure the quality of
this model. All other properties of the model are arbitrary.


title:
The accurate optimal-success/error-rate calculations applied to the
  realizations of the reliable and short-period integer ambiguity resolution in
  carrier-phase GPS/GNSS positioning

abstract:
  The maximum-marginal-a-posteriori success rate of statistical decision under
multivariate Gaussian error distribution on an integer lattice is almost
rigorously calculated by using union-bound approximation and Monte Carlo
integration. These calculations are applied to the revelation of the various
possible realizations of the reliable and short-period integer ambiguity
resolution in precise carrier-phase relative positioning by GPS/GNSS. The
theoretical foundation and efficient methodology are systematically developed,
and two types of the enhancement of union-bound approximation are proposed and
examined.
  The results revealed include an extremely high reliability under the
condition of accurate carrier-phase measurements and a large number of visible
satellites, its heavy degradation caused by the slight amount of differentiated
ionospheric delays due to the nonvanishing baseline length between rover and
reference receivers, and the advantages of the use of the multiple carrier
frequencies. The succeeding initialization of the integer ambiguities is shown
to overcome the disadvantageous condition of the nonvanishing baseline length
effectively due to the reasonably assumed temporal and spatial constancy of
differentiated ionospheric delays.


title:
IMPACT: Investigation of Mobile-user Patterns Across University Campuses
  using WLAN Trace Analysis

abstract:
  We conduct the most comprehensive study of WLAN traces to date. Measurements
collected from four major university campuses are analyzed with the aim of
developing fundamental understanding of realistic user behavior in wireless
networks. Both individual user and inter-node (group) behaviors are
investigated and two classes of metrics are devised to capture the underlying
structure of such behaviors.
  For individual user behavior we observe distinct patterns in which most users
are 'on' for a small fraction of the time, the number of access points visited
is very small and the overall on-line user mobility is quite low. We clearly
identify categories of heavy and light users. In general, users exhibit high
degree of similarity over days and weeks.
  For group behavior, we define metrics for encounter patterns and friendship.
Surprisingly, we find that a user, on average, encounters less than 6% of the
network user population within a month, and that encounter and friendship
relations are highly asymmetric. We establish that number of encounters follows
a biPareto distribution, while friendship indexes follow an exponential
distribution. We capture the encounter graph using a small world model, the
characteristics of which reach steady state after only one day.
  We hope for our study to have a great impact on realistic modeling of network
usage and mobility patterns in wireless networks.


title: ATTENTION: ATTackEr traceback using MAC layer abNormality detecTION

abstract:
  Denial-of-Service (DoS) and Distributed DoS (DDoS) attacks can cause serious
problems in wireless networks due to limited network and host resources.
Attacker traceback is a promising solution to take a proper countermeasure near
the attack origins, to discourage attackers from launching attacks, and for
forensics. However, attacker traceback in Mobile Ad-hoc Networks (MANETs) is a
challenging problem due to the dynamic topology, and limited network resources.
It is especially difficult to trace back attacker(s) when they are moving to
avoid traceback. In this paper, we introduce the ATTENTION protocol framework,
which pays special attention to MAC layer abnormal activity under attack.
ATTENTION consists of three classes, namely, coarse-grained traceback,
fine-grained traceback and spatio-temporal fusion architecture. For
energy-efficient attacker searching in MANETs, we also utilize small-world
model. Our simulation analysis shows 79% of success rate in DoS attacker
traceback with coarse-grained attack signature. In addition, with fine-grained
attack signature, it shows 97% of success rate in DoS attacker traceback and
83% of success rate in DDoS attacker traceback. We also show that ATTENTION has
robustness against node collusion and mobility.


title: A Secure Traitor Tracing Scheme against Key Exposure

abstract:
  Copyright protection is a major issue in distributing digital content. On the
other hand, improvements to usability are sought by content users. In this
paper, we propose a secure {\it traitor tracing scheme against key exposure
(TTaKE)} which contains the properties of both a traitor tracing scheme and a
forward secure public key cryptosystem. Its structure fits current digital
broadcasting systems and it may be useful in preventing traitors from making
illegal decoders and in minimizing the damage from accidental key exposure. It
can improve usability through these properties.


title: n-Channel Asymmetric Multiple-Description Lattice Vector Quantization

abstract:
  We present analytical expressions for optimal entropy-constrained
multiple-description lattice vector quantizers which, under high-resolutions
assumptions, minimize the expected distortion for given packet-loss
probabilities. We consider the asymmetric case where packet-loss probabilities
and side entropies are allowed to be unequal and find optimal quantizers for
any number of descriptions in any dimension. We show that the normalized second
moments of the side-quantizers are given by that of an $L$-dimensional sphere
independent of the choice of lattices. Furthermore, we show that the optimal
bit-distribution among the descriptions is not unique. In fact, within certain
limits, bits can be arbitrarily distributed.


title:
Relations between the Local Weight Distributions of a Linear Block Code,
  Its Extended Code, and Its Even Weight Subcode

abstract:
  Relations between the local weight distributions of a binary linear code, its
extended code, and its even weight subcode are presented. In particular, for a
code of which the extended code is transitive invariant and contains only
codewords with weight multiples of four, the local weight distribution can be
obtained from that of the extended code. Using the relations, the local weight
distributions of the $(127,k)$ primitive BCH codes for $k\leq50$, the
$(127,64)$ punctured third-order Reed-Muller, and their even weight subcodes
are obtained from the local weight distribution of the $(128,k)$ extended
primitive BCH codes for $k\leq50$ and the $(128,64)$ third-order Reed-Muller
code. We also show an approach to improve an algorithm for computing the local
weight distribution proposed before.


title: The Benefit of Thresholding in LP Decoding of LDPC Codes

abstract:
  Consider data transmission over a binary-input additive white Gaussian noise
channel using a binary low-density parity-check code. We ask the following
question: Given a decoder that takes log-likelihood ratios as input, does it
help to modify the log-likelihood ratios before decoding? If we use an optimal
decoder then it is clear that modifying the log-likelihoods cannot possibly
help the decoder's performance, and so the answer is "no." However, for a
suboptimal decoder like the linear programming decoder, the answer might be
"yes": In this paper we prove that for certain interesting classes of
low-density parity-check codes and large enough SNRs, it is advantageous to
truncate the log-likelihood ratios before passing them to the linear
programming decoder.


title: Chosen-ciphertext attack on noncommutative Polly Cracker

abstract:
  We propose a chosen-ciphertext attack on recently presented noncommutative
variant of the well-known Polly Cracker cryptosystem. We show that if one
chooses parameters for this noncommutative Polly Cracker as initially proposed,
than the system should be claimed as insecure.


title: Distributed Algorithms for Optimal Rate-Reliability Tradeoff in Networks

abstract:
  The current framework of network utility maximization for distributed rate
allocation assumes fixed channel code rates. However, by adapting the physical
layer channel coding, different rate-reliability tradeoffs can be achieved on
each link and for each end user. Consider a network where each user has a
utility function that depends on both signal quality and data rate, and each
link may provide a `fatter' (`thinner') information `pipe' by allowing a higher
(lower) decoding error probability. We propose two distributed, pricing-based
algorithms to attain optimal rate-reliability tradeoff, with an interpretation
that each user provides its willingness to pay for reliability to the network
and the network feeds back congestion prices to users. The proposed algorithms
converge to a tradeoff point between rate and reliability, which is proved to
be globally optimal for codes with sufficiently large codeword lengths and user
utilities with sufficiently negative curvatures.


title:
Enhancing Content-And-Structure Information Retrieval using a Native XML
  Database

abstract:
  Three approaches to content-and-structure XML retrieval are analysed in this
paper: first by using Zettair, a full-text information retrieval system; second
by using eXist, a native XML database, and third by using a hybrid XML
retrieval system that uses eXist to produce the final answers from likely
relevant articles retrieved by Zettair. INEX 2003 content-and-structure topics
can be classified in two categories: the first retrieving full articles as
final answers, and the second retrieving more specific elements within articles
as final answers. We show that for both topic categories our initial hybrid
system improves the retrieval effectiveness of a native XML database. For
ranking the final answer elements, we propose and evaluate a novel retrieval
model that utilises the structural relationships between the answer elements of
a native XML database and retrieves Coherent Retrieval Elements. The final
results of our experiments show that when the XML retrieval task focusses on
highly relevant elements our hybrid XML retrieval system with the Coherent
Retrieval Elements module is 1.8 times more effective than Zettair and 3 times
more effective than eXist, and yields an effective content-and-structure XML
retrieval.


title:
Spectral Factorization, Whitening- and Estimation Filter -- Stability,
  Smoothness Properties and FIR Approximation Behavior

abstract:
  A Wiener filter can be interpreted as a cascade of a whitening- and an
estimation filter. This paper gives a detailed investigates of the properties
of these two filters. Then the practical consequences for the overall Wiener
filter are ascertained. It is shown that if the given spectral densities are
smooth (Hoelder continuous) functions, the resulting Wiener filter will always
be stable and can be approximated arbitrarily well by a finite impulse response
(FIR) filter. Moreover, the smoothness of the spectral densities characterizes
how fast the FIR filter approximates the desired filter characteristic. If on
the other hand the spectral densities are continuous but not smooth enough, the
resulting Wiener filter may not be stable.


title: On the Minimal Pseudo-Codewords of Codes from Finite Geometries

abstract:
  In order to understand the performance of a code under maximum-likelihood
(ML) decoding, it is crucial to know the minimal codewords. In the context of
linear programming (LP) decoding, it turns out to be necessary to know the
minimal pseudo-codewords. This paper studies the minimal codewords and minimal
pseudo-codewords of some families of codes derived from projective and
Euclidean planes. Although our numerical results are only for codes of very
modest length, they suggest that these code families exhibit an interesting
property. Namely, all minimal pseudo-codewords that are not multiples of a
minimal codeword have an AWGNC pseudo-weight that is strictly larger than the
minimum Hamming weight of the code. This observation has positive consequences
not only for LP decoding but also for iterative decoding.


title: Capacity Gain from Transmitter and Receiver Cooperation

abstract:
  Capacity gain from transmitter and receiver cooperation are compared in a
relay network where the cooperating nodes are close together. When all nodes
have equal average transmit power along with full channel state information
(CSI), it is proved that transmitter cooperation outperforms receiver
cooperation, whereas the opposite is true when power is optimally allocated
among the nodes but only receiver phase CSI is available. In addition, when the
nodes have equal average power with receiver phase CSI only, cooperation is
shown to offer no capacity improvement over a non-cooperative scheme with the
same average network power. When the system is under optimal power allocation
with full CSI, the decode-and-forward transmitter cooperation rate is close to
its cut-set capacity upper bound, and outperforms compress-and-forward receiver
cooperation. Moreover, it is shown that full CSI is essential in transmitter
cooperation, while optimal power allocation is essential in receiver
cooperation.


title: Toward Compact Interdomain Routing

abstract:
  Despite prevailing concerns that the current Internet interdomain routing
system will not scale to meet the needs of the 21st century global Internet,
networking research has not yet led to the construction of a new routing
architecture with satisfactory and mathematically provable scalability
characteristics. Worse, continuing empirical trends of the existing routing and
topology structure of the Internet are alarming: the foundational principles of
the current routing and addressing architecture are an inherently bad match for
the naturally evolving structure of Internet interdomain topology. We are
fortunate that a sister discipline, theory of distributed computation, has
developed routing algorithms that offer promising potential for genuinely
scalable routing on realistic Internet-like topologies. Indeed, there are many
recent breakthroughs in the area of compact routing, which has been shown to
drastically outperform, in terms of efficiency and scalability, even the
boldest proposals developed in networking research. Many open questions remain,
but we believe the applicability of compact routing techniques to Internet
interdomain routing is a research area whose potential payoff for the future of
networking is too high to ignore.


title: Matrix Construction Using Cyclic Shifts of a Column

abstract:
  This paper describes the synthesis of matrices with good correlation, from
cyclic shifts of pseudonoise columns. Optimum matrices result whenever the
shift sequence satisfies the constant difference property. Known shift
sequences with the constant (or almost constant) difference property are:
Quadratic (Polynomial) and Reciprocal Shift modulo prime, Exponential Shift,
Legendre Shift, Zech Logarithm Shift, and the shift sequences of some m-arrays.
We use these shift sequences to produce arrays for watermarking of digital
images. Matrices can also be unfolded into long sequences by diagonal unfolding
(with no deterioration in correlation) or row-by-row unfolding, with some
degradation in correlation.


title:
Software Libraries and Their Reuse: Entropy, Kolmogorov Complexity, and
  Zipf's Law

abstract:
  We analyze software reuse from the perspective of information theory and
Kolmogorov complexity, assessing our ability to ``compress'' programs by
expressing them in terms of software components reused from libraries. A common
theme in the software reuse literature is that if we can only get the right
environment in place-- the right tools, the right generalizations, economic
incentives, a ``culture of reuse'' -- then reuse of software will soar, with
consequent improvements in productivity and software quality. The analysis
developed in this paper paints a different picture: the extent to which
software reuse can occur is an intrinsic property of a problem domain, and
better tools and culture can have only marginal impact on reuse rates if the
domain is inherently resistant to reuse. We define an entropy parameter $H \in
[0,1]$ of problem domains that measures program diversity, and deduce from this
upper bounds on code reuse and the scale of components with which we may work.
For ``low entropy'' domains with $H$ near 0, programs are highly similar to one
another and the domain is amenable to the Component-Based Software Engineering
(CBSE) dream of programming by composing large-scale components. For problem
domains with $H$ near 1, programs require substantial quantities of new code,
with only a modest proportion of an application comprised of reused,
small-scale components. Preliminary empirical results from Unix platforms
support some of the predictions of our model.


title: New Codes for OFDM with Low PMEPR

abstract:
  In this paper new codes for orthogonal frequency-division multiplexing (OFDM)
with tightly controlled peak-to-mean envelope power ratio (PMEPR) are proposed.
We identify a new family of sequences occuring in complementary sets and show
that such sequences form subsets of a new generalization of the Reed--Muller
codes. Contrarily to previous constructions we present a compact description of
such codes, which makes them suitable even for larger block lengths. We also
show that some previous constructions just occur as special cases in our
construction.


title: Signature coding for OR channel with asynchronous access

abstract:
  Signature coding for multiple access OR channel is considered. We prove that
in block asynchronous case the upper bound on the minimum code length
asymptotically is the same as in the case of synchronous access.


title:
Simple Maximum-Likelihood Decoding of Generalized First-order
  Reed-Muller Codes

abstract:
  An efficient decoder for the generalized first-order Reed-Muller code
RM_q(1,m) is essential for the decoding of various block-coding schemes for
orthogonal frequency-division multiplexing with reduced peak-to-mean power
ratio. We present an efficient and simple maximum-likelihood decoding algorithm
for RM_q(1,m). It is shown that this algorithm has lower complexity than other
previously known maximum-likelihood decoders for RM_q(1,m).


title: Expectation maximization as message passing

abstract:
  Based on prior work by Eckford, it is shown how expectation maximization (EM)
may be viewed, and used, as a message passing algorithm in factor graphs.


title: Truth-telling Reservations

abstract:
  We present a mechanism for reservations of bursty resources that is both
truthful and robust. It consists of option contracts whose pricing structure
induces users to reveal the true likelihoods that they will purchase a given
resource. Users are also allowed to adjust their options as their likelihood
changes. This scheme helps users save cost and the providers to plan ahead so
as to reduce the risk of under-utilization and overbooking. The mechanism
extracts revenue similar to that of a monopoly provider practicing temporal
pricing discrimination with a user population whose preference distribution is
known in advance.


title: Selfish vs. Unselfish Optimization of Network Creation

abstract:
  We investigate several variants of a network creation model: a group of
agents builds up a network between them while trying to keep the costs of this
network small. The cost function consists of two addends, namely (i) a constant
amount for each edge an agent buys and (ii) the minimum number of hops it takes
sending messages to other agents. Despite the simplicity of this model, various
complex network structures emerge depending on the weight between the two
addends of the cost function and on the selfish or unselfish behaviour of the
agents.


title: Terminated LDPC Convolutional Codes with Thresholds Close to Capacity

abstract:
  An ensemble of LDPC convolutional codes with parity-check matrices composed
of permutation matrices is considered. The convergence of the iterative belief
propagation based decoder for terminated convolutional codes in the ensemble is
analyzed for binary-input output-symmetric memoryless channels using density
evolution techniques. We observe that the structured irregularity in the Tanner
graph of the codes leads to significantly better thresholds when compared to
corresponding LDPC block codes.