title: Instance-Independent View Serializability for Semistructured Databases

abstract:
  Semistructured databases require tailor-made concurrency control mechanisms
since traditional solutions for the relational model have been shown to be
inadequate. Such mechanisms need to take full advantage of the hierarchical
structure of semistructured data, for instance allowing concurrent updates of
subtrees of, or even individual elements in, XML documents. We present an
approach for concurrency control which is document-independent in the sense
that two schedules of semistructured transactions are considered equivalent if
they are equivalent on all possible documents. We prove that it is decidable in
polynomial time whether two given schedules in this framework are equivalent.
This also solves the view serializability for semistructured schedules
polynomially in the size of the schedule and exponentially in the number of
transactions.


title: On Searching a Table Consistent with Division Poset

abstract:
  Suppose $P_n=\{1,2,...,n\}$ is a partially ordered set with the partial order
defined by divisibility, that is, for any two distinct elements $i,j\in P_n$
satisfying $i$ divides $j$, $i<_{P_n} j$. A table $A_n=\{a_i|i=1,2,...,n\}$ of
distinct real numbers is said to be \emph{consistent} with $P_n$, provided for
any two distinct elements $i,j\in \{1,2,...,n\}$ satisfying $i$ divides $j$,
$a_i< a_j$. Given an real number $x$, we want to determine whether $x\in A_n$,
by comparing $x$ with as few entries of $A_n$ as possible. In this paper we
investigate the complexity $\tau(n)$, measured in the number of comparisons, of
the above search problem. We present a $\frac{55n}{72}+O(\ln^2 n)$ search
algorithm for $A_n$ and prove a lower bound $({3/4}+{17/2160})n+O(1)$ on
$\tau(n)$ by using an adversary argument.


title: On the Solution of Graph Isomorphism by Dynamical Algorithms

abstract:
  In the recent years, several polynomial algorithms of a dynamical nature have
been proposed to address the graph isomorphism problem. In this paper we
propose a generalization of an approach exposed in cond-mat/0209112 and find
that this dynamical algorithm is covered by a combinatorial approach. It is
possible to infer that polynomial dynamical algorithms addressing graph
isomorphism are covered by suitable polynomial combinatorial approaches and
thus are tackled by the same weaknesses as the last ones.


title: Efficient Approximation of Convex Recolorings

abstract:
  A coloring of a tree is convex if the vertices that pertain to any color
induce a connected subtree; a partial coloring (which assigns colors to some of
the vertices) is convex if it can be completed to a convex (total) coloring.
Convex coloring of trees arise in areas such as phylogenetics, linguistics,
etc. eg, a perfect phylogenetic tree is one in which the states of each
character induce a convex coloring of the tree. Research on perfect phylogeny
is usually focused on finding a tree so that few predetermined partial
colorings of its vertices are convex.
  When a coloring of a tree is not convex, it is desirable to know "how far" it
is from a convex one. In [19], a natural measure for this distance, called the
recoloring distance was defined: the minimal number of color changes at the
vertices needed to make the coloring convex. This can be viewed as minimizing
the number of "exceptional vertices" w.r.t. to a closest convex coloring. The
problem was proved to be NP-hard even for colored string.
  In this paper we continue the work of [19], and present a 2-approximation
algorithm of convex recoloring of strings whose running time O(cn), where c is
the number of colors and n is the size of the input, and an O(cn^2)-time
3-approximation algorithm for convex recoloring of trees.


title: On the Parity-Check Density and Achievable Rates of LDPC Codes

abstract:
  The paper introduces new bounds on the asymptotic density of parity-check
matrices and the achievable rates under ML decoding of binary linear block
codes transmitted over memoryless binary-input output-symmetric channels. The
lower bounds on the parity-check density are expressed in terms of the gap
between the channel capacity and the rate of the codes for which reliable
communication is achievable, and are valid for every sequence of binary linear
block codes. The bounds address the question, previously considered by Sason
and Urbanke, of how sparse can parity-check matrices of binary linear block
codes be as a function of the gap to capacity. The new upper bounds on the
achievable rates of binary linear block codes tighten previously reported
bounds by Burshtein et al., and therefore enable to obtain tighter upper bounds
on the thresholds of sequences of binary linear block codes under ML decoding.
The bounds are applied to low-density parity-check (LDPC) codes, and the
improvement in their tightness is exemplified numerically.


title:
Application of Kolmogorov complexity and universal codes to identity
  testing and nonparametric testing of serial independence for time series

abstract:
  We show that Kolmogorov complexity and such its estimators as universal codes
(or data compression methods) can be applied for hypotheses testing in a
framework of classical mathematical statistics. The methods for identity
testing and nonparametric testing of serial independence for time series are
suggested.


title:
Dominance Based Crossover Operator for Evolutionary Multi-objective
  Algorithms

abstract:
  In spite of the recent quick growth of the Evolutionary Multi-objective
Optimization (EMO) research field, there has been few trials to adapt the
general variation operators to the particular context of the quest for the
Pareto-optimal set. The only exceptions are some mating restrictions that take
in account the distance between the potential mates - but contradictory
conclusions have been reported. This paper introduces a particular mating
restriction for Evolutionary Multi-objective Algorithms, based on the Pareto
dominance relation: the partner of a non-dominated individual will be
preferably chosen among the individuals of the population that it dominates.
Coupled with the BLX crossover operator, two different ways of generating
offspring are proposed. This recombination scheme is validated within the
well-known NSGA-II framework on three bi-objective benchmark problems and one
real-world bi-objective constrained optimization problem. An acceleration of
the progress of the population toward the Pareto set is observed on all
problems.


title: An ontological approach to the construction of problem-solving models

abstract:
  Our ongoing work aims at defining an ontology-centered approach for building
expertise models for the CommonKADS methodology. This approach (which we have
named "OntoKADS") is founded on a core problem-solving ontology which
distinguishes between two conceptualization levels: at an object level, a set
of concepts enable us to define classes of problem-solving situations, and at a
meta level, a set of meta-concepts represent modeling primitives. In this
article, our presentation of OntoKADS will focus on the core ontology and, in
particular, on roles - the primitive situated at the interface between domain
knowledge and reasoning, and whose ontological status is still much debated. We
first propose a coherent, global, ontological framework which enables us to
account for this primitive. We then show how this novel characterization of the
primitive allows definition of new rules for the construction of expertise
models.


title:
Fast generators for the Diffie-Hellman key agreement protocol and
  malicious standards

abstract:
  The Diffie-Hellman key agreement protocol is based on taking large powers of
a generator of a prime-order cyclic group. Some generators allow faster
exponentiation. We show that to a large extent, using the fast generators is as
secure as using a randomly chosen generator. On the other hand, we show that if
there is some case in which fast generators are less secure, then this could be
used by a malicious authority to generate a standard for the Diffie-Hellman key
agreement protocol which has a hidden trapdoor.


title: Defensive forecasting

abstract:
  We consider how to make probability forecasts of binary labels. Our main
mathematical result is that for any continuous gambling strategy used for
detecting disagreement between the forecasts and the actual labels, there
exists a forecasting strategy whose forecasts are ideal as far as this gambling
strategy is concerned. A forecasting strategy obtained in this way from a
gambling strategy demonstrating a strong law of large numbers is simplified and
studied empirically.


title: An explicit formula for the number of tunnels in digital objects

abstract:
  An important concept in digital geometry for computer imagery is that of
tunnel. In this paper we obtain a formula for the number of tunnels as a
function of the number of the object vertices, pixels, holes, connected
components, and 2x2 grid squares. It can be used to test for tunnel-freedom a
digital object, in particular a digital curve.


title: Improving PARMA Trailing

abstract:
  Taylor introduced a variable binding scheme for logic variables in his PARMA
system, that uses cycles of bindings rather than the linear chains of bindings
used in the standard WAM representation. Both the HAL and dProlog languages
make use of the PARMA representation in their Herbrand constraint solvers.
Unfortunately, PARMA's trailing scheme is considerably more expensive in both
time and space consumption. The aim of this paper is to present several
techniques that lower the cost.
  First, we introduce a trailing analysis for HAL using the classic PARMA
trailing scheme that detects and eliminates unnecessary trailings. The
analysis, whose accuracy comes from HAL's determinism and mode declarations,
has been integrated in the HAL compiler and is shown to produce space
improvements as well as speed improvements. Second, we explain how to modify
the classic PARMA trailing scheme to halve its trailing cost. This technique is
illustrated and evaluated both in the context of dProlog and HAL. Finally, we
explain the modifications needed by the trailing analysis in order to be
combined with our modified PARMA trailing scheme. Empirical evidence shows that
the combination is more effective than any of the techniques when used in
isolation.
  To appear in Theory and Practice of Logic Programming.


title:
On the Ancestral Compatibility of Two Phylogenetic Trees with Nested
  Taxa

abstract:
  Compatibility of phylogenetic trees is the most important concept underlying
widely-used methods for assessing the agreement of different phylogenetic trees
with overlapping taxa and combining them into common supertrees to reveal the
tree of life. The notion of ancestral compatibility of phylogenetic trees with
nested taxa was introduced by Semple et al in 2004. In this paper we analyze in
detail the meaning of this compatibility from the points of view of the local
structure of the trees, of the existence of embeddings into a common supertree,
and of the joint properties of their cluster representations. Our analysis
leads to a very simple polynomial-time algorithm for testing this
compatibility, which we have implemented and is freely available for download
from the BioPerl collection of Perl modules for computational biology.


title: Feasible Proofs of Matrix Properties with Csanky's Algorithm

abstract:
  We show that Csanky's fast parallel algorithm for computing the
characteristic polynomial of a matrix can be formalized in the logical theory
LAP, and can be proved correct in LAP from the principle of linear
independence. LAP is a natural theory for reasoning about linear algebra
introduced by Cook and Soltys. Further, we show that several principles of
matrix algebra, such as linear independence or the Cayley-Hamilton Theorem, can
be shown equivalent in the logical theory QLA. Applying the separation between
complexity classes AC^0[2] contained in DET(GF(2)), we show that these
principles are in fact not provable in QLA. In a nutshell, we show that linear
independence is ``all there is'' to elementary linear algebra (from a proof
complexity point of view), and furthermore, linear independence cannot be
proved trivially (again, from a proof complexity point of view).


title: 6-cycle double covers of cubic graphs

abstract:
  A cycle double cover (CDC) of an undirected graph is a collection of the
graph's cycles such that every edge of the graph belongs to exactly two cycles.
We describe a constructive method for generating all the cubic graphs that have
a 6-CDC (a CDC in which every cycle has length 6). As an application of the
method, we prove that all such graphs have a Hamiltonian cycle. A sense of
direction is an edge labeling on graphs that follows a globally consistent
scheme and is known to considerably reduce the complexity of several
distributed problems. In [9], a particular instance of sense of direction,
called a chordal sense of direction (CSD), is studied and the class of
k-regular graphs that admit a CSD with exactly k labels (a minimal CSD) is
analyzed. We now show that nearly all the cubic graphs in this class have a
6-CDC, the only exception being K4.


title:
SafeMPI - Extending MPI for Byzantine Error Detection on Parallel
  Clusters

abstract:
  Modern high-performance computing relies heavily on the use of commodity
processors arranged together in clusters. These clusters consist of individual
nodes (typically off-the-shelf single or dual processor machines) connected
together with a high speed interconnect. Using cluster computation has many
benefits, but also carries the liability of being failure prone due to the
sheer number of components involved. Many effective solutions have been
proposed to aid failure recovery in clusters, their one significant downside
being the failure models they support. Most of the work in the area has focused
on detecting and correcting fail-stop errors. We propose a system that will
also detect more general error models, such as Byzantine errors, thus allowing
existing failure recovery methods to handle them correctly.


title: HepToX: Heterogeneous Peer to Peer XML Databases

abstract:
  We study a collection of heterogeneous XML databases maintaining similar and
related information, exchanging data via a peer to peer overlay network. In
this setting, a mediated global schema is unrealistic. Yet, users/applications
wish to query the databases via one peer using its schema. We have recently
developed HepToX, a P2P Heterogeneous XML database system. A key idea is that
whenever a peer enters the system, it establishes an acquaintance with a small
number of peer databases, possibly with different schema. The peer
administrator provides correspondences between the local schema and the
acquaintance schema using an informal and intuitive notation of arrows and
boxes. We develop a novel algorithm that infers a set of precise mapping rules
between the schemas from these visual annotations. We pin down a semantics of
query translation given such mapping rules, and present a novel query
translation algorithm for a simple but expressive fragment of XQuery, that
employs the mapping rules in either direction. We show the translation
algorithm is correct. Finally, we demonstrate the utility and scalability of
our ideas and algorithms with a detailed set of experiments on top of the
Emulab, a large scale P2P network emulation testbed.


title: Authentication and routing in simple Quantum Key Distribution networks

abstract:
  We consider various issues which arise as soon as one tries to practically
implement simple networks of quantum relays for QKD. In particular we discuss
authentication and routing which are essential ingredients of any QKD network.
This paper aims to address some gaps between quantum and networking aspects of
QKD networks usually reserved to specialist in physics and computer science
respectively.


title: Non-asymptotic calibration and resolution

abstract:
  We analyze a new algorithm for probability forecasting of binary observations
on the basis of the available data, without making any assumptions about the
way the observations are generated. The algorithm is shown to be well
calibrated and to have good resolution for long enough sequences of
observations and for a suitable choice of its parameter, a kernel on the
Cartesian product of the forecast space $[0,1]$ and the data space. Our main
results are non-asymptotic: we establish explicit inequalities, shown to be
tight, for the performance of the algorithm.


title: Programming Finite-Domain Constraint Propagators in Action Rules

abstract:
  In this paper, we propose a new language, called AR ({\it Action Rules}), and
describe how various propagators for finite-domain constraints can be
implemented in it. An action rule specifies a pattern for agents, an action
that the agents can carry out, and an event pattern for events that can
activate the agents. AR combines the goal-oriented execution model of logic
programming with the event-driven execution model. This hybrid execution model
facilitates programming constraint propagators. A propagator for a constraint
is an agent that maintains the consistency of the constraint and is activated
by the updates of the domain variables in the constraint. AR has a much
stronger descriptive power than {\it indexicals}, the language widely used in
the current finite-domain constraint systems, and is flexible for implementing
not only interval-consistency but also arc-consistency algorithms. As examples,
we present a weak arc-consistency propagator for the {\tt all\_distinct}
constraint and a hybrid algorithm for n-ary linear equality constraints.
B-Prolog has been extended to accommodate action rules. Benchmarking shows that
B-Prolog as a CLP(FD) system significantly outperforms other CLP(FD) systems.


title: A batch scheduler with high level components

abstract:
  In this article we present the design choices and the evaluation of a batch
scheduler for large clusters, named OAR. This batch scheduler is based upon an
original design that emphasizes on low software complexity by using high level
tools. The global architecture is built upon the scripting language Perl and
the relational database engine Mysql. The goal of the project OAR is to prove
that it is possible today to build a complex system for ressource management
using such tools without sacrificing efficiency and scalability. Currently, our
system offers most of the important features implemented by other batch
schedulers such as priority scheduling (by queues), reservations, backfilling
and some global computing support. Despite the use of high level tools, our
experiments show that our system has performances close to other systems.
Furthermore, OAR is currently exploited for the management of 700 nodes (a
metropolitan GRID) and has shown good efficiency and robustness.


title: Defensive forecasting for linear protocols

abstract:
  We consider a general class of forecasting protocols, called "linear
protocols", and discuss several important special cases, including multi-class
forecasting. Forecasting is formalized as a game between three players:
Reality, whose role is to generate observations; Forecaster, whose goal is to
predict the observations; and Skeptic, who tries to make money on any lack of
agreement between Forecaster's predictions and the actual observations. Our
main mathematical result is that for any continuous strategy for Skeptic in a
linear protocol there exists a strategy for Forecaster that does not allow
Skeptic's capital to grow. This result is a meta-theorem that allows one to
transform any continuous law of probability in a linear protocol into a
forecasting strategy whose predictions are guaranteed to satisfy this law. We
apply this meta-theorem to a weak law of large numbers in Hilbert spaces to
obtain a version of the K29 prediction algorithm for linear protocols and show
that this version also satisfies the attractive properties of proper
calibration and resolution under a suitable choice of its kernel parameter,
with no assumptions about the way the data is generated.


title: Bounds on the Automata Size for Presburger Arithmetic

abstract:
  Automata provide a decision procedure for Presburger arithmetic. However,
until now only crude lower and upper bounds were known on the sizes of the
automata produced by this approach. In this paper, we prove an upper bound on
the the number of states of the minimal deterministic automaton for a
Presburger arithmetic formula. This bound depends on the length of the formula
and the quantifiers occurring in the formula. The upper bound is established by
comparing the automata for Presburger arithmetic formulas with the formulas
produced by a quantifier elimination method. We also show that our bound is
tight, even for nondeterministic automata. Moreover, we provide optimal
automata constructions for linear equations and inequations.


title: Approximate MAP Decoding on Tail-Biting Trellises

abstract:
  We propose two approximate algorithms for MAP decoding on tail-biting
trellises. The algorithms work on a subset of nodes of the tail-biting trellis,
judiciously selected. We report the results of simulations on an AWGN channel
using the approximate algorithms on tail-biting trellises for the $(24,12)$
Extended Golay Code and a rate 1/2 convolutional code with memory 6.


title: The OAI Data-Provider Registration and Validation Service

abstract:
  I present a summary of recent use of the Open Archives Initiative (OAI)
registration and validation services for data-providers. The registration
service has seen a steady stream of registrations since its launch in 2002, and
there are now over 220 registered repositories. I examine the validation logs
to produce a breakdown of reasons why repositories fail validation. This
breakdown highlights some common problems and will be used to guide work to
improve the validation service.


title:
On the dimensions of certain LDPC codes based on q-regular bipartite
  graphs

abstract:
  An explicit construction of a family of binary LDPC codes called LU(3,q),
where q is a power of a prime, was recently given. A conjecture was made for
the dimensions of these codes when q is odd. The conjecture is proved in this
note. The proof involves the geometry of a 4-dimensional symplectic vector
space and the action of the symplectic group and its subgroups.


title:
A Non-Cooperative Power Control Game in Delay-Constrained
  Multiple-Access Networks

abstract:
  A game-theoretic approach for studying power control in multiple-access
networks with transmission delay constraints is proposed. A non-cooperative
power control game is considered in which each user seeks to choose a transmit
power that maximizes its own utility while satisfying the user's delay
requirements. The utility function measures the number of reliable bits
transmitted per joule of energy and the user's delay constraint is modeled as
an upper bound on the delay outage probability. The Nash equilibrium for the
proposed game is derived, and its existence and uniqueness are proved. Using a
large-system analysis, explicit expressions for the utilities achieved at
equilibrium are obtained for the matched filter, decorrelating and minimum mean
square error multiuser detectors. The effects of delay constraints on the
users' utilities (in bits/Joule) and network capacity (i.e., the maximum number
of users that can be supported) are quantified.


title:
On the existence and characterization of the maxent distribution under
  general moment inequality constraints

abstract:
  A broad set of sufficient conditions that guarantees the existence of the
maximum entropy (maxent) distribution consistent with specified bounds on
certain generalized moments is derived. Most results in the literature are
either focused on the minimum cross-entropy distribution or apply only to
distributions with a bounded-volume support or address only equality
constraints. The results of this work hold for general moment inequality
constraints for probability distributions with possibly unbounded support, and
the technical conditions are explicitly on the underlying generalized moment
functions. An analytical characterization of the maxent distribution is also
derived using results from the theory of constrained optimization in
infinite-dimensional normed linear spaces. Several auxiliary results of
independent interest pertaining to certain properties of convex coercive
functions are also presented.


title:
The Equivalence Problem for Deterministic MSO Tree Transducers is
  Decidable

abstract:
  It is decidable for deterministic MSO definable graph-to-string or
graph-to-tree transducers whether they are equivalent on a context-free set of
graphs.


title: Cryptanalysis of Key Issuing Protocols in ID-based Cryptosystems

abstract:
  To remove key escrow problem and avoid the need of secure channel in ID based
cryptosystem Lee et al. proposed a secure key issuing protocol. However we show
that it suffers from impersonation, insider attacks and incompetency of the key
privacy authorities. We also cryptanalyze Sui et al.'s separable and anonymous
key issuing protocol.


title: Compressing Probability Distributions

abstract:
  We show how to store good approximations of probability distributions in
small space.


title:
Treillis de concepts et ontologies pour l'interrogation d'un annuaire de
  sources de donn\'{e}es biologiques (BioRegistry)

abstract:
  Bioinformatic data sources available on the web are multiple and
heterogenous. The lack of documentation and the difficulty of interaction with
these data sources require users competence in both informatics and biological
fields for an optimal use of sources contents that remain rather under
exploited. In this paper we present an approach based on formal concept
analysis to classify and search relevant bioinformatic data sources for a given
query. It consists in building the concept lattice from the binary relation
between bioinformatic data sources and their associated metadata. The concept
built from a given query is then merged into the concept lattice. The result is
given by the extraction of the set of sources belonging to the extents of the
query concept subsumers in the resulting concept lattice. The sources ranking
is given by the concept specificity order in the concept lattice. An
improvement of the approach consists in automatic query refinement thanks to
domain ontologies. Two forms of refinement are possible by generalisation and
by specialisation.
  -----
  Les sources de donn\'{e}es biologiques disponibles sur le web sont multiples
et h\'{e}t\'{e}rog\`{e}nes. L'utilisation optimale de ces ressources
n\'{e}cessite aujourd'hui de la part des utilisateurs des comp\'{e}tences \`{a}
la fois en informatique et en biologie, du fait du manque de documentation et
des difficult\'{e}s d'interaction avec les sources de donn\'{e}es. De fait, les
contenus de ces ressources restent souvent sous-exploit\'{e}s. Nous
pr\'{e}sentons ici une approche bas\'{e}e sur l'analyse de concepts formels,
pour organiser et rechercher des sources de donn\'{e}es biologiques pertinentes
pour une requ\^{e}te donn\'{e}e. Le travail consiste \`{a} construire un
treillis de concepts \`{a} partir des m\'{e}ta-donn\'{e}es associ\'{e}es aux
sources. Le concept construit \`{a} partir d'une requ\^{e}te donn\'{e}e est
alors int\'{e}gr\'{e} au treillis. La r\'{e}ponse \`{a} la requ\^{e}te est
ensuite fournie par l'extraction des sources de donn\'{e}es appartenant aux
extensions des concepts subsumant le concept requ\^{e}te dans le treillis. Les
sources ainsi retourn\'{e}es peuvent \^{e}tre tri\'{e}es selon l'ordre de
sp\'{e}cificit\'{e} des concepts dans le treillis. Une proc\'{e}dure de
raffinement de requ\^{e}te, bas\'{e}e sur des ontologies du domaine, permet
d'am\'{e}liorer le rappel par g\'{e}n\'{e}ralisation ou par sp\'{e}cialisation


title:
On the Achievable Diversity-Multiplexing Tradeoffs in Half-Duplex
  Cooperative Channels

abstract:
  In this paper, we propose novel cooperative transmission protocols for delay
limited coherent fading channels consisting of N (half-duplex and
single-antenna) partners and one cell site. In our work, we differentiate
between the relay, cooperative broadcast (down-link), and cooperative
multiple-access (up-link) channels. For the relay channel, we investigate two
classes of cooperation schemes; namely, Amplify and Forward (AF) protocols and
Decode and Forward (DF) protocols. For the first class, we establish an upper
bound on the achievable diversity-multiplexing tradeoff with a single relay. We
then construct a new AF protocol that achieves this upper bound. The proposed
algorithm is then extended to the general case with N-1 relays where it is
shown to outperform the space-time coded protocol of Laneman and Worenell
without requiring decoding/encoding at the relays. For the class of DF
protocols, we develop a dynamic decode and forward (DDF) protocol that achieves
the optimal tradeoff for multiplexing gains 0 < r < 1/N. Furthermore, with a
single relay, the DDF protocol is shown to dominate the class of AF protocols
for all multiplexing gains. The superiority of the DDF protocol is shown to be
more significant in the cooperative broadcast channel. The situation is
reversed in the cooperative multiple-access channel where we propose a new AF
protocol that achieves the optimal tradeoff for all multiplexing gains. A
distinguishing feature of the proposed protocols in the three scenarios is that
they do not rely on orthogonal subspaces, allowing for a more efficient use of
resources. In fact, using our results one can argue that the sub-optimality of
previously proposed protocols stems from their use of orthogonal subspaces
rather than the half-duplex constraint.


title:
An Efficient Approximation Algorithm for Point Pattern Matching Under
  Noise

abstract:
  Point pattern matching problems are of fundamental importance in various
areas including computer vision and structural bioinformatics. In this paper,
we study one of the more general problems, known as LCP (largest common point
set problem): Let $\PP$ and $\QQ$ be two point sets in $\mathbb{R}^3$, and let
$\epsilon \geq 0$ be a tolerance parameter, the problem is to find a rigid
motion $\mu$ that maximizes the cardinality of subset $\II$ of $Q$, such that
the Hausdorff distance $\distance(\PP,\mu(\II)) \leq \epsilon$. We denote the
size of the optimal solution to the above problem by $\LCP(P,Q)$. The problem
is called exact-LCP for $\epsilon=0$, and \tolerant-LCP when $\epsilon>0$ and
the minimum interpoint distance is greater than $2\epsilon$. A
$\beta$-distance-approximation algorithm for tolerant-LCP finds a subset $I
\subseteq \QQ$ such that $|I|\geq \LCP(P,Q)$ and $\distance(\PP,\mu(\II)) \leq
\beta \epsilon$ for some $\beta \ge 1$.
  This paper has three main contributions. (1) We introduce a new algorithm,
called {\DA}, which gives the fastest known deterministic
4-distance-approximation algorithm for \tolerant-LCP. (2) For the exact-LCP,
when the matched set is required to be large, we give a simple sampling
strategy that improves the running times of all known deterministic algorithms,
yielding the fastest known deterministic algorithm for this problem. (3) We use
expander graphs to speed-up the \DA algorithm for \tolerant-LCP when the size
of the matched set is required to be large, at the expense of approximation in
the matched set size. Our algorithms also work when the transformation $\mu$ is
allowed to be scaling transformation.


title: On the Throughput-Delay Tradeoff in Cellular Multicast

abstract:
  In this paper, we adopt a cross layer design approach for analyzing the
throughput-delay tradeoff of the multicast channel in a single cell system. To
illustrate the main ideas, we start with the single group case, i.e., pure
multicast, where a common information stream is requested by all the users. We
consider three classes of scheduling algorithms with progressively increasing
complexity. The first class strives for minimum complexity by resorting to a
static scheduling strategy along with memoryless decoding. Our analysis for
this class of scheduling algorithms reveals the existence of a static
scheduling policy that achieves the optimal scaling law of the throughput at
the expense of a delay that increases exponentially with the number of users.
The second scheduling policy resorts to a higher complexity incremental
redundancy encoding/decoding strategy to achieve a superior throughput-delay
tradeoff. The third, and most complex, scheduling strategy benefits from the
cooperation between the different users to minimize the delay while achieving
the optimal scaling law of the throughput. In particular, the proposed
cooperative multicast strategy is shown to simultaneously achieve the optimal
scaling laws of both throughput and delay. Then, we generalize our scheduling
algorithms to exploit the multi-group diversity available when different
information streams are requested by different subsets of the user population.
Finally, we discuss the effect of the potential gains of equipping the base
station with multi-transmit antennas and present simulation results that
validate our theoretical claims.


title:
Analysis of Relationship between Strategic and Aggregate Energy
  Minimization in Delay-Constrained Wireless Networks

abstract:
  We formulate two versions of the power control problem for wireless networks
with latency constraints arising from duty cycle allocations In the first
version, strategic power optimization, wireless nodes are modeled as rational
agents in a power game, who strategically adjust their powers to minimize their
own energy. In the other version, joint power optimization, wireless nodes
jointly minimize the aggregate energy expenditure. Our analysis of these models
yields insights into the different energy outcomes of strategic versus joint
power optimization. We derive analytical solutions for power allocation under
both models and study how they are affected by data loads and channel quality.
We derive simple necessary conditions for the existence of Nash equilibria in
the power game and also provide numerical examples of optimal power allocation
under both models. Finally, we show that joint optimization can (sometimes) be
Pareto-optimal and dominate strategic optimization, i.e the energy expenditure
of all nodes is lower than if they were using strategic optimization.


title: Asymptotics of Discrete MDL for Online Prediction

abstract:
  Minimum Description Length (MDL) is an important principle for induction and
prediction, with strong relations to optimal Bayesian learning. This paper
deals with learning non-i.i.d. processes by means of two-part MDL, where the
underlying model class is countable. We consider the online learning framework,
i.e. observations come in one by one, and the predictor is allowed to update
his state of mind after each time step. We identify two ways of predicting by
MDL for this setup, namely a static} and a dynamic one. (A third variant,
hybrid MDL, will turn out inferior.) We will prove that under the only
assumption that the data is generated by a distribution contained in the model
class, the MDL predictions converge to the true values almost surely. This is
accomplished by proving finite bounds on the quadratic, the Hellinger, and the
Kullback-Leibler loss of the MDL learner, which are however exponentially worse
than for Bayesian prediction. We demonstrate that these bounds are sharp, even
for model classes containing only Bernoulli distributions. We show how these
bounds imply regret bounds for arbitrary loss functions. Our results apply to a
wide range of setups, namely sequence prediction, pattern classification,
regression, and universal induction in the sense of Algorithmic Information
Theory among others.


title: Sparse Covariance Selection via Robust Maximum Likelihood Estimation

abstract:
  We address a problem of covariance selection, where we seek a trade-off
between a high likelihood against the number of non-zero elements in the
inverse covariance matrix. We solve a maximum likelihood problem with a penalty
term given by the sum of absolute values of the elements of the inverse
covariance matrix, and allow for imposing bounds on the condition number of the
solution. The problem is directly amenable to now standard interior-point
algorithms for convex optimization, but remains challenging due to its size. We
first give some results on the theoretical computational complexity of the
problem, by showing that a recent methodology for non-smooth convex
optimization due to Nesterov can be applied to this problem, to greatly improve
on the complexity estimate given by interior-point algorithms. We then examine
two practical algorithms aimed at solving large-scale, noisy (hence dense)
instances: one is based on a block-coordinate descent approach, where columns
and rows are updated sequentially, another applies a dual version of Nesterov's
method.


title: The Hyper-Cortex of Human Collective-Intelligence Systems

abstract:
  Individual-intelligence research, from a neurological perspective, discusses
the hierarchical layers of the cortex as a structure that performs conceptual
abstraction and specification. This theory has been used to explain how
motor-cortex regions responsible for different behavioral modalities such as
writing and speaking can be utilized to express the same general concept
represented higher in the cortical hierarchy. For example, the concept of a
dog, represented across a region of high-level cortical-neurons, can either be
written or spoken about depending on the individual's context. The higher-layer
cortical areas project down the hierarchy, sending abstract information to
specific regions of the motor-cortex for contextual implementation. In this
paper, this idea is expanded to incorporate collective-intelligence within a
hyper-cortical construct. This hyper-cortex is a multi-layered network used to
represent abstract collective concepts. These ideas play an important role in
understanding how collective-intelligence systems can be engineered to handle
problem abstraction and solution specification. Finally, a collection of common
problems in the scientific community are solved using an artificial
hyper-cortex generated from digital-library metadata.


title: Dynamic Asymmetric Communication

abstract:
  We show how any dynamic instantaneous compression algorithm can be converted
to an asymmetric communication protocol, with which a server with high
bandwidth can help clients with low bandwidth send it messages. Unlike previous
authors, we do not assume the server knows the messages' distribution, and our
protocols are the first to use only one round of communication for each
message.


title: Database Reformulation with Integrity Constraints (extended abstract)

abstract:
  In this paper we study the problem of reducing the evaluation costs of
queries on finite databases in presence of integrity constraints, by designing
and materializing views. Given a database schema, a set of queries defined on
the schema, a set of integrity constraints, and a storage limit, to find a
solution to this problem means to find a set of views that satisfies the
storage limit, provides equivalent rewritings of the queries under the
constraints (this requirement is weaker than equivalence in the absence of
constraints), and reduces the total costs of evaluating the queries. This
problem, database reformulation, is important for many applications, including
data warehousing and query optimization. We give complexity results and
algorithms for database reformulation in presence of constraints, for
conjunctive queries, views, and rewritings and for several types of
constraints, including functional and inclusion dependencies. To obtain better
complexity results, we introduce an unchase technique, which reduces the
problem of query equivalence under constraints to equivalence in the absence of
constraints without increasing query size.


title: Sorting a Low-Entropy Sequence

abstract:
  We give the first sorting algorithm with bounds in terms of higher-order
entropies: let $S$ be a sequence of length $m$ containing $n$ distinct elements
and let (H_\ell (S)) be the $\ell$th-order empirical entropy of $S$, with
(n^{\ell + 1} \log n \in O (m)); our algorithm sorts $S$ using ((H_\ell (S) + O
(1)) m) comparisons.


title:
Neyman-Pearson Detection of Gauss-Markov Signals in Noise: Closed-Form
  Error Exponent and Properties

abstract:
  The performance of Neyman-Pearson detection of correlated stochastic signals
using noisy observations is investigated via the error exponent for the miss
probability with a fixed level. Using the state-space structure of the signal
and observation model, a closed-form expression for the error exponent is
derived, and the connection between the asymptotic behavior of the optimal
detector and that of the Kalman filter is established. The properties of the
error exponent are investigated for the scalar case. It is shown that the error
exponent has distinct characteristics with respect to correlation strength: for
signal-to-noise ratio (SNR) >1 the error exponent decreases monotonically as
the correlation becomes stronger, whereas for SNR <1 there is an optimal
correlation that maximizes the error exponent for a given SNR.


title:
A Unified Framework for Tree Search Decoding : Rediscovering the
  Sequential Decoder

abstract:
  We consider receiver design for coded transmission over linear Gaussian
channels. We restrict ourselves to the class of lattice codes and formulate the
joint detection and decoding problem as a closest lattice point search (CLPS).
Here, a tree search framework for solving the CLPS is adopted. In our
framework, the CLPS algorithm decomposes into the preprocessing and tree search
stages. The role of the preprocessing stage is to expose the tree structure in
a form {\em matched} to the search stage. We argue that the minimum mean square
error decision feedback (MMSE-DFE) frontend is instrumental for solving the
joint detection and decoding problem in a single search stage. It is further
shown that MMSE-DFE filtering allows for using lattice reduction methods to
reduce complexity, at the expense of a marginal performance loss, and solving
under-determined linear systems. For the search stage, we present a generic
method, based on the branch and bound (BB) algorithm, and show that it
encompasses all existing sphere decoders as special cases. The proposed generic
algorithm further allows for an interesting classification of tree search
decoders, sheds more light on the structural properties of all known sphere
decoders, and inspires the design of more efficient decoders. In particular, an
efficient decoding algorithm that resembles the well known Fano sequential
decoder is identified. The excellent performance-complexity tradeoff achieved
by the proposed MMSE-Fano decoder is established via simulation results and
analytical arguments in several MIMO and ISI scenarios.


title: Preferential and Preferential-discriminative Consequence relations

abstract:
  The present paper investigates consequence relations that are both
non-monotonic and paraconsistent. More precisely, we put the focus on
preferential consequence relations, i.e. those relations that can be defined by
a binary preference relation on states labelled by valuations. We worked with a
general notion of valuation that covers e.g. the classical valuations as well
as certain kinds of many-valued valuations. In the many-valued cases,
preferential consequence relations are paraconsistant (in addition to be
non-monotonic), i.e. they are capable of drawing reasonable conclusions which
contain contradictions. The first purpose of this paper is to provide in our
general framework syntactic characterizations of several families of
preferential relations. The second and main purpose is to provide, again in our
general framework, characterizations of several families of preferential
discriminative consequence relations. They are defined exactly as the plain
version, but any conclusion such that its negation is also a conclusion is
rejected (these relations bring something new essentially in the many-valued
cases).


title: A Constrained Object Model for Configuration Based Workflow Composition

abstract:
  Automatic or assisted workflow composition is a field of intense research for
applications to the world wide web or to business process modeling. Workflow
composition is traditionally addressed in various ways, generally via theorem
proving techniques. Recent research observed that building a composite workflow
bears strong relationships with finite model search, and that some workflow
languages can be defined as constrained object metamodels . This lead to
consider the viability of applying configuration techniques to this problem,
which was proven feasible. Constrained based configuration expects a
constrained object model as input. The purpose of this document is to formally
specify the constrained object model involved in ongoing experiments and
research using the Z specification language.


title:
Framework for Hopfield Network based Adaptive routing - A design level
  approach for adaptive routing phenomena with Artificial Neural Network

abstract:
  Routing, as a basic phenomena, by itself, has got umpteen scopes to analyse,
discuss and arrive at an optimal solution for the technocrats over years.
Routing is analysed based on many factors; few key constraints that decide the
factors are communication medium, time dependency, information source nature.
Parametric routing has become the requirement of the day, with some kind of
adaptation to the underlying network environment. Satellite constellations,
particularly LEO satellite constellations have become a reality in operational
to have a non-breaking voice/data communication around the world.Routing in
these constellations has to be treated in a non conventional way, taking their
network geometry into consideration. One of the efficient methods of
optimization is putting Neural Networks to use. Few Artificial Neural Network
models are very much suitable for the adaptive control mechanism, by their
nature of network arrangement. One such efficient model is Hopfield Network
model.
  This paper is an attempt to design a framework for the Hopfield Network based
adaptive routing phenomena in satellite constellations.


title:
An Event-driven Operator Model for Dynamic Simulation of Construction
  Machinery

abstract:
  Prediction and optimisation of a wheel loader's dynamic behaviour is a
challenge due to tightly coupled, non-linear subsystems of different technical
domains. Furthermore, a simulation regarding performance, efficiency, and
operability cannot be limited to the machine itself, but has to include
operator, environment, and work task. This paper presents some results of our
approach to an event-driven simulation model of a human operator. Describing
the task and the operator model independently of the machine's technical
parameters, gives the possibility to change whole sub-system characteristics
without compromising the relevance and validity of the simulation.


title:
A Taxonomy of Data Grids for Distributed Data Sharing, Management and
  Processing

abstract:
  Data Grids have been adopted as the platform for scientific communities that
need to share, access, transport, process and manage large data collections
distributed worldwide. They combine high-end computing technologies with
high-performance networking and wide-area storage management techniques. In
this paper, we discuss the key concepts behind Data Grids and compare them with
other data sharing and distribution paradigms such as content delivery
networks, peer-to-peer networks and distributed databases. We then provide
comprehensive taxonomies that cover various aspects of architecture, data
transportation, data replication and resource allocation and scheduling.
Finally, we map the proposed taxonomy to various Data Grid systems not only to
validate the taxonomy but also to identify areas for future exploration.
Through this taxonomy, we aim to categorise existing systems to better
understand their goals and their methodology. This would help evaluate their
applicability for solving similar problems. This taxonomy also provides a "gap
analysis" of this area through which researchers can potentially identify new
issues for investigation. Finally, we hope that the proposed taxonomy and
mapping also helps to provide an easy way for new practitioners to understand
this complex area of research.


title: Fast Recompilation of Object Oriented Modules

abstract:
  Once a program file is modified, the recompilation time should be minimized,
without sacrificing execution speed or high level object oriented features. The
recompilation time is often a problem for the large graphical interactive
distributed applications tackled by modern OO languages. A compilation server
and fast code generator were developed and integrated with the SRC Modula-3
compiler and Linux ELF dynamic linker. The resulting compilation and
recompilation speedups are impressive. The impact of different language
features, processor speed, and application size are discussed.


title: Non prefix-free codes for constrained sequences

abstract:
  In this paper we consider the use of variable length non prefix-free codes
for coding constrained sequences of symbols. We suppose to have a Markov source
where some state transitions are impossible, i.e. the stochastic matrix
associated with the Markov chain has some null entries. We show that classic
Kraft inequality is not a necessary condition, in general, for unique
decodability under the above hypothesis and we propose a relaxed necessary
inequality condition. This allows, in some cases, the use of non prefix-free
codes that can give very good performance, both in terms of compression and
computational efficiency. Some considerations are made on the relation between
the proposed approach and other existing coding paradigms.


title: Tradeoff Between Source and Channel Coding for Erasure Channels

abstract:
  In this paper, we investigate the optimal tradeoff between source and channel
coding for channels with bit or packet erasure. Upper and Lower bounds on the
optimal channel coding rate are computed to achieve minimal end-to-end
distortion. The bounds are calculated based on a combination of sphere packing,
straight line and expurgated error exponents and also high rate vector
quantization theory. By modeling a packet erasure channel in terms of an
equivalent bit erasure channel, we obtain bounds on the packet size for a
specified limit on the distortion.


title:
A Game Theoretic Economics Framework to understanding Information
  Security Oursourcing Market

abstract:
  On information security outsourcing market, an important reason that firms do
not want to let outside firms(usually called MSSPs-Managed Security Service
Providers) to take care of their security need is that they worry about service
quality MSSPs provide because they cannot monitor effort of the MSSPs. Since
MSSPs action is unobservable to buyers, MSSPs can lower cost by working less
hard than required in the contract and get higher profit. In the asymmetric
information literature, this possible secret shirking behavior is termed as
moral hazard problem. This paper considers a game theoretic economic framework
to show that under information asymmetry, an optimal contract can be designed
so that MSSPs will stick to their promised effort level. We also show that the
optimal contract should be performance-based, i.e., payment to MSSP should base
on performance of MSSP's security service period by period. For comparison, we
also showed that if the moral hazard problem does not exist, the optimal
contract does not depend on MSSP's performance. A contract that specifies
constant payment to MSSP will be optimal. Besides these, we show that for no
matter under perfect information scenario or imperfect information scenario,
the higher the transaction cost is, the lower payment to MSSPs will be.


title: Antenna array geometry and coding performance

abstract:
  This paper provides details about experiments in realistic, urban, and
frequency flat channels with space-time coding that specifically examines the
impact of the number of receive antennas and the design criteria for code
selection on the performance. Also the performance characteristics are examined
of the coded modulations in the presence of finite size array geometries. This
paper gives some insight into which of the theories are most useful in
realistic deployments.


title: A Fixed-Length Coding Algorithm for DNA Sequence Compression

abstract:
  While achieving a compression ratio of 2.0 bits/base, the new algorithm codes
non-N bases in fixed length. It dramatically reduces the time of coding and
decoding than previous DNA compression algorithms and some universal
compression programs.


title: Competitive on-line learning with a convex loss function

abstract:
  We consider the problem of sequential decision making under uncertainty in
which the loss caused by a decision depends on the following binary
observation. In competitive on-line learning, the goal is to design decision
algorithms that are almost as good as the best decision rules in a wide
benchmark class, without making any assumptions about the way the observations
are generated. However, standard algorithms in this area can only deal with
finite-dimensional (often countable) benchmark classes. In this paper we give
similar results for decision rules ranging over an arbitrary reproducing kernel
Hilbert space. For example, it is shown that for a wide class of loss functions
(including the standard square, absolute, and log loss functions) the average
loss of the master algorithm, over the first $N$ observations, does not exceed
the average loss of the best decision rule with a bounded norm plus
$O(N^{-1/2})$. Our proof technique is very different from the standard ones and
is based on recent results about defensive forecasting. Given the probabilities
produced by a defensive forecasting algorithm, which are known to be well
calibrated and to have good resolution in the long run, we use the expected
loss minimization principle to find a suitable decision.


title: Tree-Based Construction of LDPC Codes

abstract:
  We present a construction of LDPC codes that have minimum pseudocodeword
weight equal to the minimum distance, and perform well with iterative decoding.
The construction involves enumerating a d-regular tree for a fixed number of
layers and employing a connection algorithm based on mutually orthogonal Latin
squares to close the tree. Methods are presented for degrees d=p^s and d =
p^s+1, for p a prime, -- one of which includes the well-known
finite-geometry-based LDPC codes.


title:
A Decision Feedback Based Scheme for Slepian-Wolf Coding of sources with
  Hidden Markov Correlation

abstract:
  We consider the problem of compression of two memoryless binary sources, the
correlation between which is defined by a Hidden Markov Model (HMM). We propose
a Decision Feedback (DF) based scheme which when used with low density parity
check codes results in compression close to the Slepian Wolf limits.


title: Minimal Network Coding for Multicast

abstract:
  We give an information flow interpretation for multicasting using network
coding. This generalizes the fluid model used to represent flows to a single
receiver. Using the generalized model, we present a decentralized algorithm to
minimize the number of packets that undergo network coding. We also propose a
decentralized algorithm to construct capacity achieving multicast codes when
the processing at some nodes is restricted to routing. The proposed algorithms
can be coupled with existing decentralized schemes to achieve minimum cost
muticast.


title:
Decision Feedback Based Scheme for Slepian-Wolf Coding of sources with
  Hidden Markov Correlation


title: Dictionaries merger for text expansion in question answering

abstract:
  This paper presents an original way to add new data in a reference dictionary
from several other lexical resources, without loosing any consistence. This
operation is carried in order to get lexical information classified by the
sense of the entry. This classification makes it possible to enrich utterances
(in QA: the queries) following the meaning, and to reduce noise. An analysis of
the experienced problems shows the interest of this method, and insists on the
points that have to be tackled.


title: Analyse et expansion des textes en question-r\'{e}ponse

abstract:
  This paper presents an original methodology to consider question answering.
We noticed that query expansion is often incorrect because of a bad
understanding of the question. But the automatic good understanding of an
utterance is linked to the context length, and the question are often short.
This methodology proposes to analyse the documents and to construct an
informative structure from the results of the analysis and from a semantic text
expansion. The linguistic analysis identifies words (tokenization and
morphological analysis), links between words (syntactic analysis) and word
sense (semantic disambiguation). The text expansion adds to each word the
synonyms matching its sense and replaces the words in the utterances by
derivatives, modifying the syntactic schema if necessary. In this way, whatever
enrichment may be, the text keeps the same meaning, but each piece of
information matches many realisations. The questioning method consists in
constructing a local informative structure without enrichment, and matches it
with the documentary structure. If a sentence in the informative structure
matches the question structure, this sentence is the answer to the question.


title: Enriching a Text by Semantic Disambiguation for Information Extraction

abstract:
  External linguistic resources have been used for a very long time in
information extraction. These methods enrich a document with data that are
semantically equivalent, in order to improve recall. For instance, some of
these methods use synonym dictionaries. These dictionaries enrich a sentence
with words that have a similar meaning. However, these methods present some
serious drawbacks, since words are usually synonyms only in restricted
contexts. The method we propose here consists of using word sense
disambiguation rules (WSD) to restrict the selection of synonyms to only these
that match a specific syntactico-semantic context. We show how WSD rules are
built and how information extraction techniques can benefit from the
application of these rules.


title:
Exploitation de dictionnaires \'{e}lectroniques pour la
  d\'{e}sambigu\"{i}sation s\'{e}mantique lexicale

abstract:
  This paper presents a lexical disambiguation system, initially developed for
English and now adapted to French. This system associates a word with its
meaning in a given context using electronic dictionaries as semantically
annotated corpora in order to extract semantic disambiguation rules. We
describe the rule extraction and application process as well as the evaluation
of the system. The results for French give us insight information on some
possible improvments of the nature and content of lexical resources adapted for
disambiguation in this framework.


title: The Workshop - Implementing Well Structured Enterprise Applications

abstract:
  We specify an abstraction layer to be used between an enterprise application
and the utilized enterprise framework (like J2EE or .NET). This specification
is called the Workshop. It provides an intuitive metaphor supporting the
programmer in designing easy understandable code. We present an implementation
of this specification. It is based upon the J2EE framework and is called the
JWorkshop. As a proof of concept we implement a special certification authority
called the Key Authority based upon the JWorkshop. The mentioned certification
authority runs very successfully in a variety of different real world projects.


title:
Comparison of two different implementations of a
  finite-difference-method for first-order pde in mathematica and matlab

abstract:
  In this article two implementations of a symmetric finite difference
algorithm for a first-order partial differential equation are discussed. The
considered partial differential equation discribes the time evolution of the
crack length distribution of microcracks in brittle materia.


title: Comments on `Bit Interleaved Coded Modulation'

abstract:
  Caire, Taricco and Biglieri presented a detailed analysis of bit interleaved
coded modulation, a simple and popular technique used to improve system
performance, especially in the context of fading channels. They derived an
upper bound to the probability of error, called the expurgated bound. In this
correspondence, the proof of the expurgated bound is shown to be flawed. A new
upper bound is also derived. It is not known whether the original expurgated
bound is valid for the important special case of square QAM with Gray labeling,
but the new bound is very close to, and slightly tighter than, the original
bound for a numerical example.


title:
Analysis on Transmit Antenna Selection for Spatial Multiplexing Systems:
  A Geometrical Approach

abstract:
  Recently, the remarkable potential of a multiple-input multiple-output (MIMO)
wireless communication system was unveiled for its ability to provide spatial
diversity or multiplexing gains. For MIMO diversity schemes, it is already
known that. by the optimal antenna selection maximizing the post-processing
signal-to-noise ratio, the diversity order of the full system can be
maintained. On the other hand, the diversity order achieved by antenna
selection in spatial multiplexing systems, especially those exploiting
practical coding and decoding schemes, has not been rigorously analyzed thus
far. In this paper, from a geometric standpoint, we propose a new framework for
theoretically analyzing the diversity order achieved by transmit antenna
selection for separately encoded spatial multiplexing systems with linear and
decision-feedback receivers. We rigorously show that a diversity order of
(Nt-1)(Nr-1) can be achieved for an Nr by Nt SM system when L=2 antennas are
selected from the transmit side; while for L>2 scenarios, we give bounds for
the achievable diversity order and show that the optimal diversity order is at
least (Nt-L+1)(Nr-L+1) . Furthermore, the same geometrical approach can be used
to evaluate the diversity-multiplexing tradeoff curves for the considered
spatial multiplexing systems with transmit antenna selection.


title:
Efficiency Loss in a Network Resource Allocation Game: The Case of
  Elastic Supply

abstract:
  We consider a resource allocation problem where individual users wish to send
data across a network to maximize their utility, and a cost is incurred at each
link that depends on the total rate sent through the link. It is known that as
long as users do not anticipate the effect of their actions on prices, a simple
proportional pricing mechanism can maximize the sum of users' utilities minus
the cost (called aggregate surplus). Continuing previous efforts to quantify
the effects of selfish behavior in network pricing mechanisms, we consider the
possibility that users anticipate the effect of their actions on link prices.
Under the assumption that the links' marginal cost functions are convex, we
establish existence of a Nash equilibrium. We show that the aggregate surplus
at a Nash equilibrium is no worse than a factor of 4*sqrt{2} - 5 times the
optimal aggregate surplus; thus, the efficiency loss when users are selfish is
no more than approximately 34%.


title: The Complexity of Kings

abstract:
  A king in a directed graph is a node from which each node in the graph can be
reached via paths of length at most two. There is a broad literature on
tournaments (completely oriented digraphs), and it has been known for more than
half a century that all tournaments have at least one king [Lan53]. Recently,
kings have proven useful in theoretical computer science, in particular in the
study of the complexity of the semifeasible sets [HNP98,HT05] and in the study
of the complexity of reachability problems [Tan01,NT02].
  In this paper, we study the complexity of recognizing kings. For each
succinctly specified family of tournaments, the king problem is known to belong
to $\Pi_2^p$ [HOZZ]. We prove that this bound is optimal: We construct a
succinctly specified tournament family whose king problem is
$\Pi_2^p$-complete. It follows easily from our proof approach that the problem
of testing kingship in succinctly specified graphs (which need not be
tournaments) is $\Pi_2^p$-complete. We also obtain $\Pi_2^p$-completeness
results for k-kings in succinctly specified j-partite tournaments, $k,j \geq
2$, and we generalize our main construction to show that $\Pi_2^p$-completeness
holds for testing k-kingship in succinctly specified families of tournaments
for all $k \geq 2$.


title: Large Alphabets and Incompressibility

abstract:
  We briefly survey some concepts related to empirical entropy -- normal
numbers, de Bruijn sequences and Markov processes -- and investigate how well
it approximates Kolmogorov complexity. Our results suggest $\ell$th-order
empirical entropy stops being a reasonable complexity metric for almost all
strings of length $m$ over alphabets of size $n$ about when $n^\ell$ surpasses
$m$.


title: About one 3-parameter Model of Testing

abstract:
  This article offers a 3-parameter model of testing, with 1) the difference
between the ability level of the examinee and item difficulty; 2) the examinee
discrimination and 3) the item discrimination as model parameters.


title: An MSE Based Ttransfer Chart to Analyze Iterative Decoding Schemes

abstract:
  An alternative to extrinsic information transfer (EXIT) charts called mean
squared error (MSE) charts that use a measure related to the MSE instead of
mutual information is proposed. Using the relationship between mutual
information and minimum mean squared error (MMSE), a relationship between the
rate of any code and the area under a plot of MSE versus signal to noise ratio
(SNR) is obtained, when the log likelihood ratios (LLR) can be assumed to be
from a Gaussian channel. Using this result, a theoretical justification is
provided for designing concatenated codes by matching the EXIT charts of the
inner and outer decoders, when the LLRs are Gaussian which is typically assumed
for code design using EXIT charts. Finally, for the special case of AWGN
channel it is shown that any capacity achieving code has an EXIT curve that is
flat. This extends Ashikhmin et als results for erasure channels to the
Gaussian channel.


title: Existentially Restricted Quantified Constraint Satisfaction

abstract:
  The quantified constraint satisfaction problem (QCSP) is a powerful framework
for modelling computational problems. The general intractability of the QCSP
has motivated the pursuit of restricted cases that avoid its maximal
complexity. In this paper, we introduce and study a new model for investigating
QCSP complexity in which the types of constraints given by the existentially
quantified variables, is restricted. Our primary technical contribution is the
development and application of a general technology for proving positive
results on parameterizations of the model, of inclusion in the complexity class
coNP.


title:
Yet another normalisation proof for Martin-Lof's logical
  framework--Terms with correct arities are strongly normalising

abstract:
  In this paper, we prove the strong normalisation for Martin-L\"{o}f's Logical
Framework, and suggest that {}``correct arity'', a condition weaker than
well-typedness, will also guarantee the strong normalisation.


title: Security Policies as Membranes in Systems for Global Computing

abstract:
  We propose a simple global computing framework, whose main concern is code
migration. Systems are structured in sites, and each site is divided into two
parts: a computing body, and a membrane, which regulates the interactions
between the computing body and the external environment. More precisely,
membranes are filters which control access to the associated site, and they
also rely on the well-established notion of trust between sites. We develop a
basic theory to express and enforce security policies via membranes. Initially,
these only control the actions incoming agents intend to perform locally. We
then adapt the basic theory to encompass more sophisticated policies, where the
number of actions an agent wants to perform, and also their order, are
considered.


title: A CDMA multiuser detection algorithm based on survey propagation

abstract:
  A computationally tractable CDMA multiuser detection algorithm is developed
based on survey propagation.


title: Priority-Based Conflict Resolution in Inconsistent Relational Databases

abstract:
  We study here the impact of priorities on conflict resolution in inconsistent
relational databases. We extend the framework of repairs and consistent query
answers. We propose a set of postulates that an extended framework should
satisfy and consider two instantiations of the framework: (locally preferred)
l-repairs and (globally preferred) g-repairs. We study the relationships
between them and the impact each notion of repair has on the computational
complexity of repair checking and consistent query answers.


title:
Optimal multiple assignments based on integer programming in secret
  sharing schemes with general access structures

abstract:
  It is known that for any general access structure, a secret sharing scheme
(SSS) can be constructed from an (m,m)-threshold scheme by using the so-called
cumulative map or from a (t,m)-threshold SSS by a modified cumulative map.
However, such constructed SSSs are not efficient generally. In this paper, we
propose a new method to construct a SSS from a $(t,m)$-threshold scheme for any
given general access structure. In the proposed method, integer programming is
used to distribute optimally the shares of (t,m)-threshold scheme to each
participant of the general access structure. From the optimality, it can always
attain lower coding rate than the cumulative maps except the cases that they
give the optimal distribution. The same method is also applied to construct
SSSs for incomplete access structures and/or ramp access structures.


title:
Strongly secure ramp secret sharing schemes for general access
  structures

abstract:
  Ramp secret sharing (SS) schemes can be classified into strong ramp SS
schemes and weak ramp SS schemes. The strong ramp SS schemes do not leak out
any part of a secret explicitly even in the case where some information about
the secret leaks from a non-qualified set of shares, and hence, they are more
desirable than weak ramp SS schemes. However, it is not known how to construct
the strong ramp SS schemes in the case of general access structures. In this
paper, it is shown that a strong ramp SS scheme can always be constructed from
a SS scheme with plural secrets for any feasible general access structure. As a
byproduct, it is pointed out that threshold ramp SS schemes based on Shamir's
polynomial interpolation method are {\em not} always strong.


title: Impersonation with the Echo Protocol

abstract:
  The Echo protocol tries to do secure location verification using physical
limits imposed by the speeds of light and sound. While the protocol is able to
guarantee that a certain object is within a certain region, it cannot ensure
the authenticity of further messages from the object without using
cryptography. This paper describes an impersonation attack against the protocol
based on this weakness. It also describes a couple of approaches which can be
used to defend against the attack.


title: Measuring Woody: The Size of Debian 3.0

abstract:
  Debian is possibly the largest free software distribution, with well over
4,500 source packages in the latest stable release (Debian 3.0) and more than
8,000 source packages in the release currently in preparation. However, we wish
to know what these numbers mean. In this paper, we use David A. Wheeler's
SLOCCount system to determine the number of physical source lines of code
(SLOC) of Debian 3.0 (aka woody). We show that Debian 3.0 includes more than
105,000,000 physical SLOC (almost twice than Red Hat 9, released about 8 months
later), showing that the Debian development model (based on the work of a large
group of voluntary developers spread around the world) is at least as capable
as other development methods (like the more centralized one, based on the work
of employees, used by Red Hat or Microsoft) to manage distributions of this
size.
  It is also shown that if Debian had been developed using traditional
proprietary methods, the COCOMO model estimates that its cost would be close to
$6.1 billion USD to develop Debian 3.0. In addition, we offer both an analysis
of the programming languages used in the distribution (C amounts for about 65%,
C++ for about 12%, Shell for about 8% and LISP is around 4%, with many others
to follow), and the largest packages (The Linux kernel, Mozilla, XFree86, PM3,
etc.)


title: Quantum Arthur-Merlin Games

abstract:
  This paper studies quantum Arthur-Merlin games, which are Arthur-Merlin games
in which Arthur and Merlin can perform quantum computations and Merlin can send
Arthur quantum information. As in the classical case, messages from Arthur to
Merlin are restricted to be strings of uniformly generated random bits. It is
proved that for one-message quantum Arthur-Merlin games, which correspond to
the complexity class QMA, completeness and soundness errors can be reduced
exponentially without increasing the length of Merlin's message. Previous
constructions for reducing error required a polynomial increase in the length
of Merlin's message. Applications of this fact include a proof that logarithmic
length quantum certificates yield no increase in power over BQP and a simple
proof that QMA is contained in PP. Other facts that are proved include the
equivalence of three (or more) message quantum Arthur-Merlin games with
ordinary quantum interactive proof systems and some basic properties concerning
two-message quantum Arthur-Merlin games.


title: A generating function method for the average-case analysis of DPLL

abstract:
  A method to calculate the average size of Davis-Putnam-Loveland-Logemann
(DPLL) search trees for random computational problems is introduced, and
applied to the satisfiability of random CNF formulas (SAT) and the coloring of
random graph (COL) problems. We establish recursion relations for the
generating functions of the average numbers of (variable or color) assignments
at a given height in the search tree, which allow us to derive the asymptotics
of the expected DPLL tree size, 2^{N w + o(N)}, where N is the instance size. w
is calculated as a function of the input distribution parameters (ratio of
clauses per variable for SAT, average vertex degree for COL), and the branching
heuristics.


title: Data Visualization on Shared Usage Multi-Screen Environment

abstract:
  The modern multimedia technologies based on the whole palette of hardware and
software facilities of real-time high-speed information processing, in a
combination with effective facilities of the remote access to information
resources, allow us to visualize diverse types of information. Data
visualization facilities – is the face of the Automated Control System on
whom often judge about their efficiency. They take a special place, providing
visualization of the diverse information necessary for decision-making by a
final control link - the person allocated by certain powers.


title:
Signal transmission on lossy lines as a dissipative quantum state
  propagation

abstract:
  The transmission of electric signals on a coupled line with distributed
RLC-parameters is considered as a propagation of a dissipative quasi particle.
A calculation technique is developed, alternative to the one, accepted for
lumped lines. The relativistic wave equation for the transient response is
deduced following the common Ohm-low-type considerations. The exact expressions
for the Green function, for information transfer velocity and for time delay
are obtained on this base. The fundamental restrictions on the measurement
accuracy of the time delay are pointed out. The obtained results are naturally
generalized for the multilevel networks of the arbitrary dimension.


title:
Performance Analysis of Algebraic Soft Decoding of Reed-Solomon Codes
  over Binary Symmetric and Erasure Channels

abstract:
  In this paper, we characterize the decoding region of algebraic soft decoding
(ASD) of Reed-Solomon (RS) codes over erasure channels and binary symmetric
channel (BSC). Optimal multiplicity assignment strategies (MAS) are
investigated and tight bounds are derived to show the ASD can significantly
outperform conventional Berlekamp Massey (BM) decoding over these channels for
a wide code rate range. The analysis technique can also be extended to other
channel models, e.g., RS coded modulation over erasure channels.


title:
Iterative Soft Input Soft Output Decoding of Reed-Solomon Codes by
  Adapting the Parity Check Matrix

abstract:
  An iterative algorithm is presented for soft-input-soft-output (SISO)
decoding of Reed-Solomon (RS) codes. The proposed iterative algorithm uses the
sum product algorithm (SPA) in conjunction with a binary parity check matrix of
the RS code. The novelty is in reducing a submatrix of the binary parity check
matrix that corresponds to less reliable bits to a sparse nature before the SPA
is applied at each iteration. The proposed algorithm can be geometrically
interpreted as a two-stage gradient descent with an adaptive potential
function. This adaptive procedure is crucial to the convergence behavior of the
gradient descent algorithm and, therefore, significantly improves the
performance. Simulation results show that the proposed decoding algorithm and
its variations provide significant gain over hard decision decoding (HDD) and
compare favorably with other popular soft decision decoding methods.


title: Redundancy in Logic II: 2CNF and Horn Propositional Formulae

abstract:
  We report complexity results about redundancy of formulae in 2CNF form. We
first consider the problem of checking redundancy and show some algorithms that
are slightly better than the trivial one. We then analyze problems related to
finding irredundant equivalent subsets (I.E.S.) of a given set. The concept of
cyclicity proved to be relevant to the complexity of these problems. Some
results about Horn formulae are also shown.


title:
Seeing stars: Exploiting class relationships for sentiment
  categorization with respect to rating scales

abstract:
  We address the rating-inference problem, wherein rather than simply decide
whether a review is "thumbs up" or "thumbs down", as in previous sentiment
analysis work, one must determine an author's evaluation with respect to a
multi-point scale (e.g., one to five "stars"). This task represents an
interesting twist on standard multi-class text categorization because there are
several different degrees of similarity between class labels; for example,
"three stars" is intuitively closer to "four stars" than to "one star". We
first evaluate human performance at the task. Then, we apply a meta-algorithm,
based on a metric labeling formulation of the problem, that alters a given
n-ary classifier's output in an explicit attempt to ensure that similar items
receive similar labels. We show that the meta-algorithm can provide significant
improvements over both multi-class and regression versions of SVMs when we
employ a novel similarity measure appropriate to the problem.


title:
Alternative security architecture for IP Telephony based on digital
  watermarking

abstract:
  Problems with securing IP Telephony systems, insufficient standardization and
lack of security mechanisms emerged the need for new approaches and solutions.
In this paper a new, alternative security architecture for voice-systems is
presented. It is based on digital watermarking: a new, flexible and powerful
technology that is increasingly gaining more and more attention. Besides known
applications e.g. to solve copyright protection problems, we propose to use
digital watermarking to secure not only transmitted audio but also signaling
protocol that IP Telephony is based on.


title:
Stability of Scheduled Multi-access Communication over Quasi-static Flat
  Fading Channels with Random Coding and Independent Decoding

abstract:
  The stability of scheduled multiaccess communication with random coding and
independent decoding of messages is investigated. The number of messages that
may be scheduled for simultaneous transmission is limited to a given maximum
value, and the channels from transmitters to receiver are quasi-static, flat,
and have independent fades. Requests for message transmissions are assumed to
arrive according to an i.i.d. arrival process. Then, we show the following: (1)
in the limit of large message alphabet size, the stability region has an
interference limited information-theoretic capacity interpretation, (2)
state-independent scheduling policies achieve this asymptotic stability region,
and (3) in the asymptotic limit corresponding to immediate access, the
stability region for non-idling scheduling policies is shown to be identical
irrespective of received signal powers.


title: Dynamical Neural Network: Information and Topology

abstract:
  A neural network works as an associative memory device if it has large
storage capacity and the quality of the retrieval is good enough. The learning
and attractor abilities of the network both can be measured by the mutual
information (MI), between patterns and retrieval states. This paper deals with
a search for an optimal topology, of a Hebb network, in the sense of the
maximal MI. We use small-world topology. The connectivity $\gamma$ ranges from
an extremely diluted to the fully connected network; the randomness $\omega$
ranges from purely local to completely random neighbors. It is found that,
while stability implies an optimal $MI(\gamma,\omega)$ at
$\gamma_{opt}(\omega)\to 0$, for the dynamics, the optimal topology holds at
certain $\gamma_{opt}>0$ whenever $0\leq\omega<0.3$.


title: Quantitative Models and Implicit Complexity

abstract:
  We give new proofs of soundness (all representable functions on base types
lies in certain complexity classes) for Elementary Affine Logic, LFPL (a
language for polytime computation close to realistic functional programming
introduced by one of us), Light Affine Logic and Soft Affine Logic. The proofs
are based on a common semantical framework which is merely instantiated in four
different ways. The framework consists of an innovative modification of
realizability which allows us to use resource-bounded computations as realisers
as opposed to including all Turing computable functions as is usually the case
in realizability constructions. For example, all realisers in the model for
LFPL are polynomially bounded computations whence soundness holds by
construction of the model. The work then lies in being able to interpret all
the required constructs in the model. While being the first entirely semantical
proof of polytime soundness for light logi cs, our proof also provides a
notable simplification of the original already semantical proof of polytime
soundness for LFPL. A new result made possible by the semantic framework is the
addition of polymorphism and a modality to LFPL thus allowing for an internal
definition of inductive datatypes.


title: The Geometry of Linear Higher-Order Recursion

abstract:
  Linearity and ramification constraints have been widely used to weaken
higher-order (primitive) recursion in such a way that the class of
representable functions equals the class of polytime functions. We show that
fine-tuning these two constraints leads to different expressive strengths, some
of them lying well beyond polynomial time. This is done by introducing a new
semantics, called algebraic context semantics. The framework stems from
Gonthier's original work and turns out to be a versatile and powerful tool for
the quantitative analysis of normalization in presence of constants and
higher-order recursion.


title: Three lines proof of the lower bound for the matrix rigidity

abstract:
  The rigidity of a matrix describes the minimal number of entries one has to
change to reduce matrix's rank to r. We give very simple combinatorial proof of
the lower bound for the rigidity of Sylvester (special case of Hadamard) matrix
that matches the best known result by de Wolf(2005) for Hadamard matrices
proved by quantum information theoretical arguments.


title: Open Questions in the Theory of Semifeasible Computation

abstract:
  The study of semifeasible algorithms was initiated by Selman's work a quarter
of century ago [Sel79,Sel81,Sel82]. Informally put, this research stream
studies the power of those sets L for which there is a deterministic (or in
some cases, the function may belong to one of various nondeterministic function
classes) polynomial-time function f such that when at least one of x and y
belongs to L, then f(x,y) \in L \cap \{x,y\}. The intuition here is that it is
saying: ``Regarding membership in L, if you put a gun to my head and forced me
to bet on one of x or y as belonging to L, my money would be on f(x,y).''
  In this article, we present a number of open problems from the theory of
semifeasible algorithms. For each we present its background and review what
partial results, if any, are known.


title:
Maxwell Construction: The Hidden Bridge between Iterative and Maximum a
  Posteriori Decoding

abstract:
  There is a fundamental relationship between belief propagation and maximum a
posteriori decoding. A decoding algorithm, which we call the Maxwell decoder,
is introduced and provides a constructive description of this relationship.
Both, the algorithm itself and the analysis of the new decoder are reminiscent
of the Maxwell construction in thermodynamics. This paper investigates in
detail the case of transmission over the binary erasure channel, while the
extension to general binary memoryless channels is discussed in a companion
paper.


title: The One Page Model Checker

abstract:
  We show how standard IPC mechanisms can be used with the fork() system call
to perform explicit state model checking on all interleavings of a
multithreaded application. We specifically show how to check for deadlock and
race conditions in programs with two threads. Our techniques are easy to apply
to other languages, and require only the most rudimentary parsing of the target
language. Our fundamental system fits in one page of C code.


title: On the Job Training

abstract:
  We propose a new framework for building and evaluating machine learning
algorithms. We argue that many real-world problems require an agent which must
quickly learn to respond to demands, yet can continue to perform and respond to
new training throughout its useful life. We give a framework for how such
agents can be built, describe several metrics for evaluating them, and show
that subtle changes in system construction can significantly affect agent
performance.


title:
Large System Decentralized Detection Performance Under Communication
  Constraints

abstract:
  The problem of decentralized detection in a sensor network subjected to a
total average power constraint and all nodes sharing a common bandwidth is
investigated. The bandwidth constraint is taken into account by assuming
non-orthogonal communication between sensors and the data fusion center via
direct-sequence code-division multiple-access (DS-CDMA). In the case of large
sensor systems and random spreading, the asymptotic decentralized detection
performance is derived assuming independent and identically distributed (iid)
sensor observations via random matrix theory. The results show that, even under
both power and bandwidth constraints, it is better to combine many not-so-good
local decisions rather than relying on one (or a few) very-good local
decisions.


title:
Primal-dual distance bounds of linear codes with application to
  cryptography

abstract:
  Let $N(d,d^\perp)$ denote the minimum length $n$ of a linear code $C$ with
$d$ and $d^{\bot}$, where $d$ is the minimum Hamming distance of $C$ and
$d^{\bot}$ is the minimum Hamming distance of $C^{\bot}$. In this paper, we
show a lower bound and an upper bound on $N(d,d^\perp)$. Further, for small
values of $d$ and $d^\perp$, we determine $N(d,d^\perp)$ and give a generator
matrix of the optimum linear code. This problem is directly related to the
design method of cryptographic Boolean functions suggested by Kurosawa et al.


title:
An Alternative to Huffman's Algorithm for Constructing Variable-Length
  Codes

abstract: This paper has been withdrawn by the author.


title:
Field geology with a wearable computer: 1st results of the Cyborg
  Astrobiologist System

abstract:
  We present results from the first geological field tests of the `Cyborg
Astrobiologist', which is a wearable computer and video camcorder system that
we are using to test and train a computer-vision system towards having some of
the autonomous decision-making capabilities of a field-geologist. The Cyborg
Astrobiologist platform has thus far been used for testing and development of
these algorithms and systems: robotic acquisition of quasi-mosaics of images,
real-time image segmentation, and real-time determination of interesting points
in the image mosaics. This work is more of a test of the whole system, rather
than of any one part of the system. However, beyond the concept of the system
itself, the uncommon map (despite its simplicity) is the main innovative part
of the system. The uncommon map helps to determine interest-points in a
context-free manner. Overall, the hardware and software systems function
reliably, and the computer-vision algorithms are adequate for the first field
tests. In addition to the proof-of-concept aspect of these field tests, the
main result of these field tests is the enumeration of those issues that we can
improve in the future, including: dealing with structural shadow and
microtexture, and also, controlling the camera's zoom lens in an intelligent
manner. Nonetheless, despite these and other technical inadequacies, this
Cyborg Astrobiologist system, consisting of a camera-equipped wearable-computer
and its computer-vision algorithms, has demonstrated its ability of finding
genuinely interesting points in real-time in the geological scenery, and then
gathering more information about these interest points in an automated manner.
We use these capabilities for autonomous guidance towards geological
points-of-interest.


title: An Exact 2.9416^n Algorithm for the Three Domatic Number Problem

abstract:
  The three domatic number problem asks whether a given undirected graph can be
partitioned into at least three dominating sets, i.e., sets whose closed
neighborhood equals the vertex set of the graph. Since this problem is
NP-complete, no polynomial-time algorithm is known for it. The naive
deterministic algorithm for this problem runs in time 3^n, up to polynomial
factors. In this paper, we design an exact deterministic algorithm for this
problem running in time 2.9416^n. Thus, our algorithm can handle problem
instances of larger size than the naive algorithm in the same amount of time.
We also present another deterministic and a randomized algorithm for this
problem that both have an even better performance for graphs with small maximum
degree.


title:
A New Construction for LDPC Codes using Permutation Polynomials over
  Integer Rings

abstract:
  A new construction is proposed for low density parity check (LDPC) codes
using quadratic permutation polynomials over finite integer rings. The
associated graphs for the new codes have both algebraic and pseudo-random
nature, and the new codes are quasi-cyclic. Graph isomorphisms and
automorphisms are identified and used in an efficient search for good codes.
Graphs with girth as large as 12 were found. Upper bounds on the minimum
Hamming distance are found both analytically and algorithmically. The bounds
indicate that the minimum distance grows with block length. Near-codewords are
one of the causes for error floors in LDPC codes; the new construction provides
a good framework for studying near-codewords in LDPC codes. Nine example codes
are given, and computer simulation results show the excellent error performance
of these codes. Finally, connections are made between this new LDPC
construction and turbo codes using interleavers generated by quadratic
permutation polynomials.


title:
Emergent Statistical Wealth Distributions in Simple Monetary Exchange
  Models: A Critical Review

abstract:
  This paper reviews recent attempts at modelling inequality of wealth as an
emergent phenomenon of interacting-agent processes. We point out that recent
models of wealth condensation which draw their inspiration from molecular
dynamics have, in fact, reinvented a process introduced quite some time ago by
Angle (1986) in the sociological literature. We emphasize some problematic
aspects of simple wealth exchange models and contrast them with a monetary
model based on economic principles of market mediated exchange. The paper also
reports new results on the influence of market power on the wealth distribution
in statistical equilibrium. As it turns out, inequality increases but market
power alone is not sufficient for changing the exponential tails of simple
exchange models into Pareto tails.


title:
On Maximum Contention-Free Interleavers and Permutation Polynomials over
  Integer Rings

abstract:
  An interleaver is a critical component for the channel coding performance of
turbo codes. Algebraic constructions are of particular interest because they
admit analytical designs and simple, practical hardware implementation.
Contention-free interleavers have been recently shown to be suitable for
parallel decoding of turbo codes. In this correspondence, it is shown that
permutation polynomials generate maximum contention-free interleavers, i.e.,
every factor of the interleaver length becomes a possible degree of parallel
processing of the decoder. Further, it is shown by computer simulations that
turbo codes using these interleavers perform very well for the 3rd Generation
Partnership Project (3GPP) standard.


title:
Universal Codes as a Basis for Nonparametric Testing of Serial
  Independence for Time Series

abstract:
  We consider a stationary and ergodic source $p$ generated symbols $x_1 ...
x_t$ from some finite set $A$ and a null hypothesis $H_0$ that $p$ is Markovian
source with memory (or connectivity) not larger than $m, (m >= 0).$ The
alternative hypothesis $H_1$ is that the sequence is generated by a stationary
and ergodic source, which differs from the source under $H_0$. In particular,
if $m= 0$ we have the null hypothesis $H_0$ that the sequence is generated by
Bernoully source (or the hypothesis that $x_1 ...x_t$ are independent.) Some
new tests which are based on universal codes and universal predictors, are
suggested.


title:
Deriving a Stationary Dynamic Bayesian Network from a Logic Program with
  Recursive Loops

abstract:
  Recursive loops in a logic program present a challenging problem to the PLP
framework. On the one hand, they loop forever so that the PLP backward-chaining
inferences would never stop. On the other hand, they generate cyclic
influences, which are disallowed in Bayesian networks. Therefore, in existing
PLP approaches logic programs with recursive loops are considered to be
problematic and thus are excluded. In this paper, we propose an approach that
makes use of recursive loops to build a stationary dynamic Bayesian network.
Our work stems from an observation that recursive loops in a logic program
imply a time sequence and thus can be used to model a stationary dynamic
Bayesian network without using explicit time parameters. We introduce a
Bayesian knowledge base with logic clauses of the form $A \leftarrow
A_1,...,A_l, true, Context, Types$, which naturally represents the knowledge
that the $A_i$s have direct influences on $A$ in the context $Context$ under
the type constraints $Types$. We then use the well-founded model of a logic
program to define the direct influence relation and apply SLG-resolution to
compute the space of random variables together with their parental connections.
We introduce a novel notion of influence clauses, based on which a declarative
semantics for a Bayesian knowledge base is established and algorithms for
building a two-slice dynamic Bayesian network from a logic program are
developed.


title: Polynomial Synthesis of Asynchronous Automata

abstract:
  Zielonka's theorem shows that each regular set of Mazurkiewicz traces can be
implemented as a system of synchronized processes with a distributed control
structure called asynchronous automaton. This paper gives a polynomial
algorithm for the synthesis of a non-deterministic asynchronous automaton from
a regular Mazurkiewicz trace language. This new construction is based on an
unfolding approach that improves the complexity of Zielonka's and Pighizzini's
techniques in terms of the number of states.


title: A Flexible Thread Scheduler for Hierarchical Multiprocessor Machines

abstract:
  With the current trend of multiprocessor machines towards more and more
hierarchical architectures, exploiting the full computational power requires
careful distribution of execution threads and data so as to limit expensive
remote memory accesses. Existing multi-threaded libraries provide only limited
facilities to let applications express distribution indications, so that
programmers end up with explicitly distributing tasks according to the
underlying architecture, which is difficult and not portable. In this article,
we present: (1) a model for dynamically expressing the structure of the
computation; (2) a scheduler interpreting this model so as to make judicious
hierarchical distribution decisions; (3) an implementation within the Marcel
user-level thread library. We experimented our proposal on a scientific
application running on a ccNUMA Bull NovaScale with 16 Intel Itanium II
processors; results show a 30% gain compared to a classical scheduler, and are
similar to what a handmade scheduler achieves in a non-portable way.