title:
Explicit Randomness is not Necessary when Modeling Probabilistic
  Encryption

abstract:
  Although good encryption functions are probabilistic, most symbolic models do
not capture this aspect explicitly. A typical solution, recently used to prove
the soundness of such models with respect to computational ones, is to
explicitly represent the dependency of ciphertexts on random coins as labels.
In order to make these label-based models useful, it seems natural to try to
extend the underlying decision procedures and the implementation of existing
tools. In this paper we put forth a more practical alternative based on the
following soundness theorem. We prove that for a large class of security
properties (that includes rather standard formulations for secrecy and
authenticity properties), security of protocols in the simpler model implies
security in the label-based model. Combined with the soundness result of
(\textbf{?}) our theorem enables the translation of security results in
unlabeled symbolic models to computational security.


title:
Complexity of Resolution of Parametric Systems of Polynomial Equations
  and Inequations

abstract:
  Consider a system of n polynomial equations and r polynomial inequations in n
indeterminates of degree bounded by d with coefficients in a polynomial ring of
s parameters with rational coefficients of bit-size at most $\sigma$. From the
real viewpoint, solving such a system often means describing some
semi-algebraic sets in the parameter space over which the number of real
solutions of the considered parametric system is constant. Following the works
of Lazard and Rouillier, this can be done by the computation of a discriminant
variety. In this report we focus on the case where for a generic specialization
of the parameters the system of equations generates a radical zero-dimensional
ideal, which is usual in the applications. In this case, we provide a
deterministic method computing the minimal discriminant variety reducing the
problem to a problem of elimination. Moreover, we prove that the degree of the
computed minimal discriminant variety is bounded by $D:=(n+r)d^{(n+1)}$ and
that the complexity of our method is $\sigma^{\mathcal{O}(1)}
D^{\mathcal{O}(n+s)}$ bit-operations on a deterministic Turing machine.


title: A secure archive for Voice-over-IP conversations

abstract:
  An efficient archive securing the integrity of VoIP-based two-party
conversations is presented. The solution is based on chains of hashes and
continuously chained electronic signatures. Security is concentrated in a
single, efficient component, allowing for a detailed analysis.


title: Natural Halting Probabilities, Partial Randomness, and Zeta Functions

abstract:
  We introduce the zeta number, natural halting probability and natural
complexity of a Turing machine and we relate them to Chaitin's Omega number,
halting probability, and program-size complexity. A classification of Turing
machines according to their zeta numbers is proposed: divergent, convergent and
tuatara. We prove the existence of universal convergent and tuatara machines.
Various results on (algorithmic) randomness and partial randomness are proved.
For example, we show that the zeta number of a universal tuatara machine is
c.e. and random. A new type of partial randomness, asymptotic randomness, is
introduced. Finally we show that in contrast to classical (algorithmic)
randomness--which cannot be naturally characterised in terms of plain
complexity--asymptotic randomness admits such a characterisation.


title: A constructive and unifying framework for zero-bit watermarking

abstract:
  In the watermark detection scenario, also known as zero-bit watermarking, a
watermark, carrying no hidden message, is inserted in content. The watermark
detector checks for the presence of this particular weak signal in content. The
article looks at this problem from a classical detection theory point of view,
but with side information enabled at the embedding side. This means that the
watermark signal is a function of the host content. Our study is twofold. The
first step is to design the best embedding function for a given detection
function, and the best detection function for a given embedding function. This
yields two conditions, which are mixed into one `fundamental' partial
differential equation. It appears that many famous watermarking schemes are
indeed solution to this `fundamental' equation. This study thus gives birth to
a constructive framework unifying solutions, so far perceived as very
different.


title: Finding roots of polynomials over finite fields

abstract:
  We propose an improved algorithm for finding roots of polynomials over finite
fields. This makes possible significant speedup of the decoding process of
Bose-Chaudhuri-Hocquenghem, Reed-Solomon, and some other error-correcting
codes.


title: Computational Euclid

abstract:
  We analyse the axioms of Euclidean geometry according to standard
object-oriented software development methodology. We find a perfect match: the
main undefined concepts of the axioms translate to object classes. The result
is a suite of C++ classes that efficiently supports the construction of complex
geometric configurations. Although all computations are performed in
floating-point arithmetic, they correctly implement as semi-decision algorithms
the tests for equality of points, a point being on a line or in a plane, a line
being in a plane, parallelness of lines, of a line and a plane, and of planes.
That is, in accordance to the fundamental limitations to computability
requiring that only negative outcomes are given with certainty, while positive
outcomes only imply possibility of these conditions being true.


title: Average-Case Complexity

abstract:
  We survey the average-case complexity of problems in NP.
  We discuss various notions of good-on-average algorithms, and present
completeness results due to Impagliazzo and Levin. Such completeness results
establish the fact that if a certain specific (but somewhat artificial) NP
problem is easy-on-average with respect to the uniform distribution, then all
problems in NP are easy-on-average with respect to all samplable distributions.
Applying the theory to natural distributional problems remain an outstanding
open question. We review some natural distributional problems whose
average-case complexity is of particular interest and that do not yet fit into
this theory.
  A major open question whether the existence of hard-on-average problems in NP
can be based on the P$\neq$NP assumption or on related worst-case assumptions.
We review negative results showing that certain proof techniques cannot prove
such a result. While the relation between worst-case and average-case
complexity for general NP problems remains open, there has been progress in
understanding the relation between different "degrees" of average-case
complexity. We discuss some of these "hardness amplification" results.


title: Tight Bounds on the Complexity of Recognizing Odd-Ranked Elements

abstract:
  Let S = <s_1, s_2, s_3, ..., s_n> be a given vector of n real numbers. The
rank of a real z with respect to S is defined as the number of elements s_i in
S such that s_i is less than or equal to z. We consider the following decision
problem: determine whether the odd-numbered elements s_1, s_3, s_5, ... are
precisely the elements of S whose rank with respect to S is odd. We prove a
bound of Theta(n log n) on the number of operations required to solve this
problem in the algebraic computation tree model.


title: Evolutionary Design: Philosophy, Theory, and Application Tactics

abstract:
  Although it has contributed to remarkable improvements in some specific
areas, attempts to develop a universal design theory are generally
characterized by failure. This paper sketches arguments for a new approach to
engineering design based on Semiotics - the science about signs. The approach
is to combine different design theories over all the product life cycle stages
into one coherent and traceable framework. Besides, it is to bring together the
designer's and user's understandings of the notion of 'good product'. Building
on the insight from natural sciences that complex systems always exhibit a
self-organizing meaning-influential hierarchical dynamics, objective laws
controlling product development are found through an examination of design as a
semiosis process. These laws are then applied to support evolutionary design of
products. An experiment validating some of the theoretical findings is
outlined, and concluding remarks are given.


title: Approximation Algorithms for Multi-Criteria Traveling Salesman Problems

abstract:
  In multi-criteria optimization problems, several objective functions have to
be optimized. Since the different objective functions are usually in conflict
with each other, one cannot consider only one particular solution as the
optimal solution. Instead, the aim is to compute a so-called Pareto curve of
solutions. Since Pareto curves cannot be computed efficiently in general, we
have to be content with approximations to them.
  We design a deterministic polynomial-time algorithm for multi-criteria
g-metric STSP that computes (min{1 +g, 2g^2/(2g^2 -2g +1)} + eps)-approximate
Pareto curves for all 1/2<=g<=1. In particular, we obtain a
(2+eps)-approximation for multi-criteria metric STSP. We also present two
randomized approximation algorithms for multi-criteria g-metric STSP that
achieve approximation ratios of (2g^3 +2g^2)/(3g^2 -2g +1) + eps and (1 +g)/(1
+3g -4g^2) + eps, respectively.
  Moreover, we present randomized approximation algorithms for multi-criteria
g-metric ATSP (ratio 1/2 + g^3/(1 -3g^2) + eps) for g < 1/sqrt(3)), STSP with
weights 1 and 2 (ratio 4/3) and ATSP with weights 1 and 2 (ratio 3/2). To do
this, we design randomized approximation schemes for multi-criteria cycle cover
and graph factor problems.


title: Characterization of Pentagons Determined by Two X-rays

abstract:
  This paper contains some results of pentagons which can be determined by two
X-rays. The results reveal this problem is more complicated.


title:
Enabling user-driven Checkpointing strategies in Reverse-mode Automatic
  Differentiation

abstract:
  This paper presents a new functionality of the Automatic Differentiation (AD)
tool Tapenade. Tapenade generates adjoint codes which are widely used for
optimization or inverse problems. Unfortunately, for large applications the
adjoint code demands a great deal of memory, because it needs to store a large
set of intermediates values. To cope with that problem, Tapenade implements a
sub-optimal version of a technique called checkpointing, which is a trade-off
between storage and recomputation. Our long-term goal is to provide an optimal
checkpointing strategy for every code, not yet achieved by any AD tool. Towards
that goal, we first introduce modifications in Tapenade in order to give the
user the choice to select the checkpointing strategy most suitable for their
code. Second, we conduct experiments in real-size scientific codes in order to
gather hints that help us to deduce an optimal checkpointing strategy. Some of
the experimental results show memory savings up to 35% and execution time up to
90%.


title:
Schedule generation schemes for the job-shop problem with
  sequence-dependent setup times: dominance properties and computational
  analysis

abstract:
  We consider the job-shop problem with sequence-dependent setup times. We
focus on the formal definition of schedule generation schemes (SGSs) based on
the semi-active, active, and non-delay schedule categories. We study dominance
properties of the sets of schedules obtainable with each SGS. We show how the
proposed SGSs can be used within single-pass and multi-pass priority rule based
heuristics. We study several priority rules for the problem and provide a
comparative computational analysis of the different SGSs on sets of instances
taken from the literature. The proposed SGSs significantly improve previously
best-known results on a set of hard benchmark instances.


title: Frugality ratios and improved truthful mechanisms for vertex cover

abstract:
  In {\em set-system auctions}, there are several overlapping teams of agents,
and a task that can be completed by any of these teams. The buyer's goal is to
hire a team and pay as little as possible. Recently, Karlin, Kempe and Tamir
introduced a new definition of {\em frugality ratio} for this setting.
Informally, the frugality ratio is the ratio of the total payment of a
mechanism to perceived fair cost. In this paper, we study this together with
alternative notions of fair cost, and how the resulting frugality ratios relate
to each other for various kinds of set systems.
  We propose a new truthful polynomial-time auction for the vertex cover
problem (where the feasible sets correspond to the vertex covers of a given
graph), based on the {\em local ratio} algorithm of Bar-Yehuda and Even. The
mechanism guarantees to find a winning set whose cost is at most twice the
optimal. In this situation, even though it is NP-hard to find a lowest-cost
feasible set, we show that {\em local optimality} of a solution can be used to
derive frugality bounds that are within a constant factor of best possible. To
prove this result, we use our alternative notions of frugality via a
bootstrapping technique, which may be of independent interest.


title: Trusted Computing in Mobile Action

abstract:
  Due to the convergence of various mobile access technologies like UMTS, WLAN,
and WiMax the need for a new supporting infrastructure arises. This
infrastructure should be able to support more efficient ways to authenticate
users and devices, potentially enabling novel services based on the security
provided by the infrastructure. In this paper we exhibit some usage scenarios
from the mobile domain integrating trusted computing, which show that trusted
computing offers new paradigms for implementing trust and by this enables new
technical applications and business scenarios. The scenarios show how the
traditional boundaries between technical and authentication domains become
permeable while a high security level is maintained.


title: Authorised Translations of Electronic Documents

abstract:
  A concept is proposed to extend authorised translations of documents to
electronically signed, digital documents. Central element of the solution is an
electronic seal, embodied as an XML data structure, which attests to the
correctness of the translation and the authorisation of the translator. The
seal contains a digital signature binding together original and translated
document, thus enabling forensic inspection and therefore legal security in the
appropriation of the translation. Organisational aspects of possible
implementation variants of electronic authorised translations are discussed and
a realisation as a stand-alone web-service is presented.


title:
Asynchronous iterative computations with Web information retrieval
  structures: The PageRank case

abstract:
  There are several ideas being used today for Web information retrieval, and
specifically in Web search engines. The PageRank algorithm is one of those that
introduce a content-neutral ranking function over Web pages. This ranking is
applied to the set of pages returned by the Google search engine in response to
posting a search query. PageRank is based in part on two simple common sense
concepts: (i)A page is important if many important pages include links to it.
(ii)A page containing many links has reduced impact on the importance of the
pages it links to. In this paper we focus on asynchronous iterative schemes to
compute PageRank over large sets of Web pages. The elimination of the
synchronizing phases is expected to be advantageous on heterogeneous platforms.
The motivation for a possible move to such large scale distributed platforms
lies in the size of matrices representing Web structure. In orders of
magnitude: $10^{10}$ pages with $10^{11}$ nonzero elements and $10^{12}$ bytes
just to store a small percentage of the Web (the already crawled); distributed
memory machines are necessary for such computations. The present research is
part of our general objective, to explore the potential of asynchronous
computational models as an underlying framework for very large scale
computations over the Grid. The area of ``internet algorithmics'' appears to
offer many occasions for computations of unprecedent dimensionality that would
be good candidates for this framework.


title: A New Quartet Tree Heuristic for Hierarchical Clustering

abstract:
  We consider the problem of constructing an an optimal-weight tree from the
3*(n choose 4) weighted quartet topologies on n objects, where optimality means
that the summed weight of the embedded quartet topologiesis optimal (so it can
be the case that the optimal tree embeds all quartets as non-optimal
topologies). We present a heuristic for reconstructing the optimal-weight tree,
and a canonical manner to derive the quartet-topology weights from a given
distance matrix. The method repeatedly transforms a bifurcating tree, with all
objects involved as leaves, achieving a monotonic approximation to the exact
single globally optimal tree. This contrasts to other heuristic search methods
from biological phylogeny, like DNAML or quartet puzzling, which, repeatedly,
incrementally construct a solution from a random order of objects, and
subsequently add agreement values.

categories: cs.DS cs.CV cs.DM math.ST physics.data-an q-bio.QM stat.TH


title: Decentralized Erasure Codes for Distributed Networked Storage

abstract:
  We consider the problem of constructing an erasure code for storage over a
network when the data sources are distributed. Specifically, we assume that
there are n storage nodes with limited memory and k<n sources generating the
data. We want a data collector, who can appear anywhere in the network, to
query any k storage nodes and be able to retrieve the data. We introduce
Decentralized Erasure Codes, which are linear codes with a specific randomized
structure inspired by network coding on random bipartite graphs. We show that
decentralized erasure codes are optimally sparse, and lead to reduced
communication, storage and computation cost over random linear coding.


title:
Syntactic Characterisations of Polynomial-Time Optimisation Classes
  (Syntactic Characterizations of Polynomial-Time Optimization Classes)

abstract:
  In Descriptive Complexity, there is a vast amount of literature on decision
problems, and their classes such as \textbf{P, NP, L and NL}. ~ However,
research on the descriptive complexity of optimisation problems has been
limited. Optimisation problems corresponding to the \textbf{NP} class have been
characterised in terms of logic expressions by Papadimitriou and Yannakakis,
Panconesi and Ranjan, Kolaitis and Thakur, Khanna et al, and by Zimand.
Gr\"{a}del characterised the polynomial class \textbf{P} of decision problems.
In this paper, we attempt to characterise the optimisation versions of
\textbf{P} via expressions in second order logic, many of them using universal
Horn formulae with successor relations. The polynomially bound versions of
maximisation (maximization) and minimisation (minimization) problems are
treated first, and then the maximisation problems in the "not necessarily
polynomially bound" class.


title: Minimum Pseudo-Weight and Minimum Pseudo-Codewords of LDPC Codes

abstract:
  In this correspondence, we study the minimum pseudo-weight and minimum
pseudo-codewords of low-density parity-check (LDPC) codes under linear
programming (LP) decoding. First, we show that the lower bound of Kelly,
Sridhara, Xu and Rosenthal on the pseudo-weight of a pseudo-codeword of an LDPC
code with girth greater than 4 is tight if and only if this pseudo-codeword is
a real multiple of a codeword. Then, we show that the lower bound of Kashyap
and Vardy on the stopping distance of an LDPC code is also a lower bound on the
pseudo-weight of a pseudo-codeword of this LDPC code with girth 4, and this
lower bound is tight if and only if this pseudo-codeword is a real multiple of
a codeword. Using these results we further show that for some LDPC codes, there
are no other minimum pseudo-codewords except the real multiples of minimum
codewords. This means that the LP decoding for these LDPC codes is
asymptotically optimal in the sense that the ratio of the probabilities of
decoding errors of LP decoding and maximum-likelihood decoding approaches to 1
as the signal-to-noise ratio leads to infinity. Finally, some LDPC codes are
listed to illustrate these results.


title: Topology for Distributed Inference on Graphs

abstract:
  Let $N$ local decision makers in a sensor network communicate with their
neighbors to reach a decision \emph{consensus}. Communication is local, among
neighboring sensors only, through noiseless or noisy links. We study the design
of the network topology that optimizes the rate of convergence of the iterative
decision consensus algorithm. We reformulate the topology design problem as a
spectral graph design problem, namely, maximizing the eigenratio~$\gamma$ of
two eigenvalues of the graph Laplacian~$L$, a matrix that is naturally
associated with the interconnectivity pattern of the network. This
reformulation avoids costly Monte Carlo simulations and leads to the class of
non-bipartite Ramanujan graphs for which we find a lower bound on~$\gamma$. For
Ramanujan topologies and noiseless links, the local probability of error
converges much faster to the overall global probability of error than for
structured graphs, random graphs, or graphs exhibiting small-world
characteristics. With noisy links, we determine the optimal number of
iterations before calling a decision. Finally, we introduce a new class of
random graphs that are easy to construct, can be designed with arbitrary number
of sensors, and whose spectral and convergence properties make them practically
equivalent to Ramanujan topologies.


title: Context-Sensitive Languages, Rational Graphs and Determinism

abstract:
We investigate families of infinite automata for context-sensitive languages.
An infinite automaton is an infinite labeled graph with two sets of initial and
final vertices. Its language is the set of all words labelling a path from an
initial vertex to a final vertex. In 2001, Morvan and Stirling proved that
rational graphs accept the context-sensitive languages between rational sets of
initial and final vertices. This result was later extended to sub-families of
rational graphs defined by more restricted classes of transducers.
languages.

  Our contribution is to provide syntactical and self-contained proofs of the
above results, when earlier constructions relied on a non-trivial normal form
of context-sensitive grammars defined by Penttonen in the 1970's. These new
proof techniques enable us to summarize and refine these results by considering
several sub-families defined by restrictions on the type of transducers, the
degree of the graph or the size of the set of initial vertices.


title: Threshold-Controlled Global Cascading in Wireless Sensor Networks

abstract:
  We investigate cascade dynamics in threshold-controlled (multiplex)
propagation on random geometric networks. We find that such local dynamics can
serve as an efficient, robust, and reliable prototypical activation protocol in
sensor networks in responding to various alarm scenarios. We also consider the
same dynamics on a modified network by adding a few long-range communication
links, resulting in a small-world network. We find that such construction can
further enhance and optimize the speed of the network's response, while keeping
energy consumption at a manageable level.


title:
Simple Methods For Drawing Rational Surfaces as Four or Six Bezier
  Patches

abstract:
  In this paper, we give several simple methods for drawing a whole rational
surface (without base points) as several Bezier patches. The first two methods
apply to surfaces specified by triangular control nets and partition the real
projective plane RP2 into four and six triangles respectively. The third method
applies to surfaces specified by rectangular control nets and partitions the
torus RP1 X RP1 into four rectangular regions. In all cases, the new control
nets are obtained by sign flipping and permutation of indices from the original
control net. The proofs that these formulae are correct involve very little
computations and instead exploit the geometry of the parameter space (RP2 or
RP1 X RP1). We illustrate our method on some classical examples. We also
propose a new method for resolving base points using a simple ``blowing up''
technique involving the computation of ``resolved'' control nets.


title: Fast and Simple Methods For Computing Control Points

abstract:
  The purpose of this paper is to present simple and fast methods for computing
control points for polynomial curves and polynomial surfaces given explicitly
in terms of polynomials (written as sums of monomials). We give recurrence
formulae w.r.t. arbitrary affine frames. As a corollary, it is amusing that we
can also give closed-form expressions in the case of the frame (r, s) for
curves, and the frame ((1, 0, 0), (0, 1, 0), (0, 0, 1) for surfaces. Our
methods have the same low polynomial (time and space) complexity as the other
best known algorithms, and are very easy to implement.


title: Approximability of Bounded Occurrence Max Ones

abstract:
  We study the approximability of Max Ones when the number of variable
occurrences is bounded by a constant. For conservative constraint languages
(i.e., when the unary relations are included) we give a complete classification
when the number of occurrences is three or more and a partial classification
when the bound is two.
  For the non-conservative case we prove that it is either trivial or
equivalent to the corresponding conservative problem under polynomial-time
many-one reductions.


title:
Lower bounds and complete problems in nondeterministic linear time and
  sublinear space complexity classes

abstract:
  Proving lower bounds remains the most difficult of tasks in computational
complexity theory. In this paper, we show that whereas most natural NP-complete
problems belong to NLIN (linear time on nondeterministic RAMs), some of them,
typically the planar versions of many NP-complete problems are recognized by
nondeterministic RAMs in linear time and sublinear space. The main results of
this paper are the following: as the second author did for NLIN, we give exact
logical characterizations of nondeterministic polynomial time-space complexity
classes; we derive from them a class of problems, which are complete in these
classes, and as a consequence of such a precise result and of some recent
separation theorems using diagonalization, prove time-space lower bounds for
these problems.


title: Tromino tilings of Domino-Deficient Rectangles

abstract:
  We consider tromino tilings of $m\times n$ domino-deficient rectangles, where
$3|(mn-2)$ and $m,n\geq0$, and characterize all cases of domino removal that
admit such tilings, thereby settling the open problem posed by J. M. Ash and S.
Golomb in \cite {marshall}. Based on this characterization, we design a
procedure for constructing such a tiling if one exists. We also consider the
problem of counting such tilings and derive the exact formula for the number of
tilings for $2\times(3t+1)$ rectangles, the exact generating function for
$4\times(3t+2)$ rectangles, where $t\geq0$, and an upper bound on the number of
tromino tilings for $m\times n$ domino-deficient rectangles. We also consider
general 2-deficiency in $n\times4$ rectangles, where $n\geq8$, and characterize
all pairs of squares which do not permit a tromino tiling.


title:
Complex Networks: New Concepts and Tools for Real-Time Imaging and
  Vision

abstract:
  This article discusses how concepts and methods of complex networks can be
applied to real-time imaging and computer vision. After a brief introduction of
complex networks basic concepts, their use as means to represent and
characterize images, as well as for modeling visual saliency, are briefly
described. The possibility to apply complex networks in order to model and
simulate the performance of parallel and distributed computing systems for
performance of visual methods is also proposed.


title:
On the Efficiency of Strategies for Subdividing Polynomial Triangular
  Surface Patches

abstract:
  In this paper, we investigate the efficiency of various strategies for
subdividing polynomial triangular surface patches. We give a simple algorithm
performing a regular subdivision in four calls to the standard de Casteljau
algorithm (in its subdivision version). A naive version uses twelve calls. We
also show that any method for obtaining a regular subdivision using the
standard de Casteljau algorithm requires at least 4 calls. Thus, our method is
optimal. We give another subdivision algorithm using only three calls to the de
Casteljau algorithm. Instead of being regular, the subdivision pattern is
diamond-like. Finally, we present a ``spider-like'' subdivision scheme
producing six subtriangles in four calls to the de Casteljau algorithm.


title: Logics for Unranked Trees: An Overview

abstract:
  Labeled unranked trees are used as a model of XML documents, and logical
languages for them have been studied actively over the past several years. Such
logics have different purposes: some are better suited for extracting data,
some for expressing navigational properties, and some make it easy to relate
complex properties of trees to the existence of tree automata for those
properties. Furthermore, logics differ significantly in their model-checking
properties, their automata models, and their behavior on ordered and unordered
trees. In this paper we present a survey of logics for unranked trees.


title:
FLAIM: A Multi-level Anonymization Framework for Computer and Network
  Logs

abstract:
  FLAIM (Framework for Log Anonymization and Information Management) addresses
two important needs not well addressed by current log anonymizers. First, it is
extremely modular and not tied to the specific log being anonymized. Second, it
supports multi-level anonymization, allowing system administrators to make
fine-grained trade-offs between information loss and privacy/security concerns.
In this paper, we examine anonymization solutions to date and note the above
limitations in each. We further describe how FLAIM addresses these problems,
and we describe FLAIM's architecture and features in detail.


title: Improved Exponential Time Lower Bound of Knapsack Problem under BT model

abstract:
  M.Alekhnovich et al. recently have proposed a model of algorithms, called BT
model, which covers Greedy, Backtrack and Simple Dynamic Programming methods
and can be further divided into fixed, adaptive and fully adaptive three kinds,
and have proved exponential time lower bounds of exact and approximation
algorithms under adaptive BT model for Knapsack problem which are
$\Omega(2^{n/2}/\sqrt n)=\Omega(2^{0.5n}/\sqrt n)$ and
$\Omega((1/\epsilon)^{1/3.17})\approx\Omega((1/\epsilon)^{0.315})$(for
approximation ratio $1-\epsilon$) respectively (M. Alekhovich, A. Borodin, J.
Buresh-Oppenheim, R. Impagliazzo, A. Magen, and T. Pitassi, Toward a Model for
Backtracking and Dynamic Programming, \emph{Proceedings of Twentieth Annual
IEEE Conference on Computational Complexity}, pp308-322, 2005). In this note,
we slightly improved their lower bounds to
$\Omega(2^{(2-\epsilon)n/3}/\sqrt{n})\approx \Omega(2^{0.66n}/\sqrt{n})$ and
$\Omega((1/\epsilon)^{1/2.38})\approx\Omega((1/\epsilon)^{0.420})$, and
proposed as an open question what is the best achievable lower bounds for
knapsack under adaptive BT models.


title:
On the complexity of XPath containment in the presence of disjunction,
  DTDs, and variables

abstract:
  XPath is a simple language for navigating an XML-tree and returning a set of
answer nodes. The focus in this paper is on the complexity of the containment
problem for various fragments of XPath. We restrict attention to the most
common XPath expressions which navigate along the child and/or descendant axis.
In addition to basic expressions using only node tests and simple predicates,
we also consider disjunction and variables (ranging over nodes). Further, we
investigate the containment problem relative to a given DTD. With respect to
variables we study two semantics, (1) the original semantics of XPath, where
the values of variables are given by an outer context, and (2) an existential
semantics introduced by Deutsch and Tannen, in which the values of variables
are existentially quantified. In this framework, we establish an exact
classification of the complexity of the containment problem for many XPath
fragments.


title: The Cumulative Rule for Belief Fusion

abstract:
  The problem of combining beliefs in the Dempster-Shafer belief theory has
attracted considerable attention over the last two decades. The classical
Dempster's Rule has often been criticised, and many alternative rules for
belief combination have been proposed in the literature. The consensus operator
for combining beliefs has nice properties and produces more intuitive results
than Dempster's rule, but has the limitation that it can only be applied to
belief distribution functions on binary state spaces. In this paper we present
a generalisation of the consensus operator that can be applied to Dirichlet
belief functions on state spaces of arbitrary size. This rule, called the
cumulative rule of belief combination, can be derived from classical
statistical theory, and corresponds well with human intuition.


title: Scheduling Algorithms for Procrastinators

abstract:
  This paper presents scheduling algorithms for procrastinators, where the
speed that a procrastinator executes a job increases as the due date
approaches. We give optimal off-line scheduling policies for linearly
increasing speed functions. We then explain the computational/numerical issues
involved in implementing this policy. We next explore the online setting,
showing that there exist adversaries that force any online scheduling policy to
miss due dates. This impossibility result motivates the problem of minimizing
the maximum interval stretch of any job; the interval stretch of a job is the
job's flow time divided by the job's due date minus release time. We show that
several common scheduling strategies, including the "hit-the-highest-nail"
strategy beloved by procrastinators, have arbitrarily large maximum interval
stretch. Then we give the "thrashing" scheduling policy and show that it is a
\Theta(1) approximation algorithm for the maximum interval stretch.


title: Security and Non-Repudiation for Voice-Over-IP Conversations

abstract:
  We present a concept to achieve non-repudiation for natural language
conversations by electronically signing packet-based, digital, voice
communication. Signing a VoIP-based conversation means to protect the integrity
and authenticity of the bidirectional data stream and its temporal sequence
which together establish the security context of the communication. Our concept
is conceptually close to the protocols that embody VoIP and provides a high
level of inherent security. It enables signatures over voice as true
declarations of will, in principle between unacquainted speakers. We point to
trusted computing enabled devices as possible trusted signature terminals for
voice communication.


title:
Inference and Evaluation of the Multinomial Mixture Model for Text
  Clustering

abstract:
  In this article, we investigate the use of a probabilistic model for
unsupervised clustering in text collections. Unsupervised clustering has become
a basic module for many intelligent text processing applications, such as
information retrieval, text classification or information extraction. The model
considered in this contribution consists of a mixture of multinomial
distributions over the word counts, each component corresponding to a different
theme. We present and contrast various estimation procedures, which apply both
in supervised and unsupervised contexts. In supervised learning, this work
suggests a criterion for evaluating the posterior odds of new documents which
is more statistically sound than the "naive Bayes" approach. In an unsupervised
context, we propose measures to set up a systematic evaluation framework and
start with examining the Expectation-Maximization (EM) algorithm as the basic
tool for inference. We discuss the importance of initialization and the
influence of other features such as the smoothing strategy or the size of the
vocabulary, thereby illustrating the difficulties incurred by the high
dimensionality of the parameter space. We also propose a heuristic algorithm
based on iterative EM with vocabulary reduction to solve this problem. Using
the fact that the latent variables can be analytically integrated out, we
finally show that Gibbs sampling algorithm is tractable and compares favorably
to the basic expectation maximization approach.


title: Is there an Elegant Universal Theory of Prediction?

abstract:
  Solomonoff's inductive learning model is a powerful, universal and highly
elegant theory of sequence prediction. Its critical flaw is that it is
incomputable and thus cannot be used in practice. It is sometimes suggested
that it may still be useful to help guide the development of very general and
powerful theories of prediction which are computable. In this paper it is shown
that although powerful algorithms exist, they are necessarily highly complex.
This alone makes their theoretical analysis problematic, however it is further
shown that beyond a moderate level of complexity the analysis runs into the
deeper problem of Goedel incompleteness. This limits the power of mathematics
to analyse and study prediction algorithms, and indeed intelligent systems in
general.


title:
Scheduling and Codeword Length Optimization in Time Varying Wireless
  Networks

abstract:
  In this paper, a downlink scenario in which a single-antenna base station
communicates with K single antenna users, over a time-correlated fading
channel, is considered. It is assumed that channel state information is
perfectly known at each receiver, while the statistical characteristics of the
fading process and the fading gain at the beginning of each frame are known to
the transmitter. By evaluating the random coding error exponent of the
time-correlated fading channel, it is shown that there is an optimal codeword
length which maximizes the throughput. The throughput of the conventional
scheduling that transmits to the user with the maximum signal to noise ratio is
examined using both fixed length codewords and variable length codewords.
Although optimizing the codeword length improves the performance, it is shown
that using the conventional scheduling, the gap between the achievable
throughput and the maximum possible throughput of the system tends to infinity
as K goes to infinity. A simple scheduling that considers both the signal to
noise ratio and the channel time variation is proposed. It is shown that by
using this scheduling, the gap between the achievable throughput and the
maximum throughput of the system approaches zero.


title: Relational Parametricity and Control

abstract:
  We study the equational theory of Parigot's second-order
λμ-calculus in connection with a call-by-name continuation-passing
style (CPS) translation into a fragment of the second-order λ-calculus.
It is observed that the relational parametricity on the target calculus induces
a natural notion of equivalence on the λμ-terms. On the other hand,
the unconstrained relational parametricity on the λμ-calculus turns
out to be inconsistent with this CPS semantics. Following these facts, we
propose to formulate the relational parametricity on the λμ-calculus
in a constrained way, which might be called ``focal parametricity''.


title:
Comparison of the estimation of the degree of polarization from four or
  two intensity images degraded by speckle noise

abstract:
  Active polarimetric imagery is a powerful tool for accessing the information
present in a scene. Indeed, the polarimetric images obtained can reveal
polarizing properties of the objects that are not avalaible using conventional
imaging systems. However, when coherent light is used to illuminate the scene,
the images are degraded by speckle noise. The polarization properties of a
scene are characterized by the degree of polarization. In standard polarimetric
imagery system, four intensity images are needed to estimate this degree . If
we assume the uncorrelation of the measurements, this number can be decreased
to two images using the Orthogonal State Contrast Image (OSCI). However, this
approach appears too restrictive in some cases. We thus propose in this paper a
new statistical parametric method to estimate the degree of polarization
assuming correlated measurements with only two intensity images. The estimators
obtained from four images, from the OSCI and from the proposed method, are
compared using simulated polarimetric data degraded by speckle noise.


title: Rate Regions for Relay Broadcast Channels

abstract:
  A partially cooperative relay broadcast channel (RBC) is a three-node network
with one source node and two destination nodes (destinations 1 and 2) where
destination 1 can act as a relay to assist destination 2. Inner and outer
bounds on the capacity region of the discrete memoryless partially cooperative
RBC are obtained. When the relay function is disabled, the inner and outer
bounds reduce to new bounds on the capacity region of broadcast channels. Four
classes of RBCs are studied in detail. For the partially cooperative RBC with
degraded message sets, inner and outer bounds are obtained. For the
semideterministic partially cooperative RBC and the orthogonal partially
cooperative RBC, the capacity regions are established. For the parallel
partially cooperative RBC with unmatched degraded subchannels, the capacity
region is established for the case of degraded message sets. The capacity is
also established when the source node has only a private message for
destination 2, i.e., the channel reduces to a parallel relay channel with
unmatched degraded subchannels.


title:
10^(10^6) Worlds and Beyond: Efficient Representation and Processing of
  Incomplete Information

abstract:
  Current systems and formalisms for representing incomplete information
generally suffer from at least one of two weaknesses. Either they are not
strong enough for representing results of simple queries, or the handling and
processing of the data, e.g. for query evaluation, is intractable.
  In this paper, we present a decomposition-based approach to addressing this
problem. We introduce world-set decompositions (WSDs), a space-efficient
formalism for representing any finite set of possible worlds over relational
databases. WSDs are therefore a strong representation system for any relational
query language. We study the problem of efficiently evaluating relational
algebra queries on sets of worlds represented by WSDs. We also evaluate our
technique experimentally in a large census data scenario and show that it is
both scalable and efficient.


title:
A Flexible Bandwidth Reservation Framework for Bulk Data Transfers in
  Grid Networks

abstract:
  In grid networks, distributed resources are interconnected by wide area
network to support compute and data-intensive applications, which require
reliable and efficient transfer of gigabits (even terabits) of data. Different
from best-effort traffic in Internet, bulk data transfer in grid requires
bandwidth reservation as a fundamental service. Existing reservation schemes
such as RSVP are designed for real-time traffic specified by reservation rate,
transfer start time but with unknown lifetime. In comparison, bulk data
transfer requests are defined in terms of volume and deadline, which provide
more information, and allow more flexibility in reservation schemes, i.e.,
transfer start time can be flexibly chosen, and reservation for a single
request can be divided into multiple intervals with different reservation
rates. We define a flexible reservation framework using time-rate function
algebra, and identify a series of practical reservation scheme families with
increasing generality and potential performance, namely, FixTime-FixRate,
FixTime-FlexRate, FlexTime-FlexRate, and Multi-Interval. Simple heuristics are
used to select representative scheme from each family for performance
comparison. Simulation results show that the increasing flexibility can
potentially improve system performance, minimizing both blocking probability
and mean flow time. We also discuss the distributed implementation of proposed
framework.


title: On Sequence Prediction for Arbitrary Measures

abstract:
  Suppose we are given two probability measures on the set of one-way infinite
finite-alphabet sequences and consider the question when one of the measures
predicts the other, that is, when conditional probabilities converge (in a
certain sense) when one of the measures is chosen to generate the sequence.
This question may be considered a refinement of the problem of sequence
prediction in its most general formulation: for a given class of probability
measures, does there exist a measure which predicts all of the measures in the
class? To address this problem, we find some conditions on local absolute
continuity which are sufficient for prediction and which generalize several
different notions which are known to be sufficient for prediction. We also
formulate some open questions to outline a direction for finding the conditions
on classes of measures for which prediction is possible.


title: Dimension Extractors and Optimal Decompression

abstract:
  A *dimension extractor* is an algorithm designed to increase the effective
dimension -- i.e., the amount of computational randomness -- of an infinite
binary sequence, in order to turn a "partially random" sequence into a "more
random" sequence. Extractors are exhibited for various effective dimensions,
including constructive, computable, space-bounded, time-bounded, and
finite-state dimension. Using similar techniques, the Kucera-Gacs theorem is
examined from the perspective of decompression, by showing that every infinite
sequence S is Turing reducible to a Martin-Loef random sequence R such that the
asymptotic number of bits of R needed to compute n bits of S, divided by n, is
precisely the constructive dimension of S, which is shown to be the optimal
ratio of query bits to computed bits achievable with Turing reductions. The
extractors and decompressors that are developed lead directly to new
characterizations of some effective dimensions in terms of optimal
decompression by Turing reductions.


title:
Ten-Year Cross-Disciplinary Comparison of the Growth of Open Access and
  How it Increases Research Citation Impact

abstract:
  Lawrence (2001)found computer science articles that were openly accessible
(OA) on the Web were cited more. We replicated this in physics. We tested
1,307,038 articles published across 12 years (1992-2003) in 10 disciplines
(Biology, Psychology, Sociology, Health, Political Science, Economics,
Education, Law, Business, Management). A robot trawls the Web for full-texts
using reference metadata ISI citation data (signal detectability d'=2.45; bias
= 0.52). Percentage OA (relative to total OA + NOA) articles varies from 5%-16%
(depending on discipline, year and country) and is slowly climbing annually
(correlation r=.76, sample size N=12, probability p < 0.005). Comparing OA and
NOA articles in the same journal/year, OA articles have consistently more
citations, the advantage varying from 36%-172% by discipline and year.
Comparing articles within six citation ranges (0, 1, 2-3, 4-7, 8-15, 16+
citations), the annual percentage of OA articles is growing significantly
faster than NOA within every citation range (r > .90, N=12, p < .0005) and the
effect is greater with the more highly cited articles (r = .98, N=6, p < .005).
Causality cannot be determined from these data, but our prior finding of a
similar pattern in physics, where percent OA is much higher (and even
approaches 100% in some subfields), makes it unlikely that the OA citation
advantage is merely or mostly a self-selection bias (for making only one's
better articles OA). Further research will analyze the effect's timing, causal
components and relation to other variables.


title: On the structure of linear-time reducibility

abstract:
  In 1975, Ladner showed that under the hypothesis that P is not equal to NP,
there exists a language which is neither in P, nor NP-complete. This result was
latter generalized by Schoning and several authors to various polynomial-time
complexity classes. We show here that such results also apply to linear-time
reductions on RAMs (resp. Turing machines), and hence allow for separation
results in linear-time classes similar to Ladner's ones for polynomial time.


title: New Millennium AI and the Convergence of History

abstract:
  Artificial Intelligence (AI) has recently become a real formal science: the
new millennium brought the first mathematically sound, asymptotically optimal,
universal problem solvers, providing a new, rigorous foundation for the
previously largely heuristic field of General AI and embedded agents. At the
same time there has been rapid progress in practical methods for learning true
sequence-processing programs, as opposed to traditional methods limited to
stationary pattern association. Here we will briefly review some of the new
results, and speculate about future developments, pointing out that the time
intervals between the most notable events in over 40,000 years or 2^9 lifetimes
of human history have sped up exponentially, apparently converging to zero
within the next few decades. Or is this impression just a by-product of the way
humans allocate memory space to past events?


title: Lack of Finite Characterizations for the Distance-based Revision

abstract:
  Lehmann, Magidor, and Schlechta developed an approach to belief revision
based on distances between any two valuations. Suppose we are given such a
distance D. This defines an operator |D, called a distance operator, which
transforms any two sets of valuations V and W into the set V |D W of all
elements of W that are closest to V. This operator |D defines naturally the
revision of K by A as the set of all formulas satisfied in M(K) |D M(A) (i.e.
those models of A that are closest to the models of K). This constitutes a
distance-based revision operator. Lehmann et al. characterized families of them
using a loop condition of arbitrarily big size. An interesting question is
whether this loop condition can be replaced by a finite one. Extending the
results of Schlechta, we will provide elements of negative answer. In fact, we
will show that for families of distance operators, there is no "normal"
characterization. Approximatively, a normal characterization contains only
finite and universally quantified conditions. These results have an interest of
their own for they help to understand the limits of what is possible in this
area. Now, we are quite confident that this work can be continued to show
similar impossibility results for distance-based revision operators, which
suggests that the big loop condition cannot be simplified.


title: The Diversity Order of the Semidefinite Relaxation Detector

abstract:
  We consider the detection of binary (antipodal) signals transmitted in a
spatially multiplexed fashion over a fading multiple-input multiple-output
(MIMO) channel and where the detection is done by means of semidefinite
relaxation (SDR). The SDR detector is an attractive alternative to maximum
likelihood (ML) detection since the complexity is polynomial rather than
exponential. Assuming that the channel matrix is drawn with i.i.d. real valued
Gaussian entries, we study the receiver diversity and prove that the SDR
detector achieves the maximum possible diversity. Thus, the error probability
of the receiver tends to zero at the same rate as the optimal maximum
likelihood (ML) receiver in the high signal to noise ratio (SNR) limit. This
significantly strengthens previous performance guarantees available for the
semidefinite relaxation detector. Additionally, it proves that full diversity
detection is in certain scenarios also possible when using a non-combinatorial
receiver structure.


title:
The Completeness of Propositional Resolution: A Simple and
  Constructive<br> Proof

abstract:
  It is well known that the resolution method (for propositional logic) is
complete. However, completeness proofs found in the literature use an argument
by contradiction showing that if a set of clauses is unsatisfiable, then it
must have a resolution refutation. As a consequence, none of these proofs
actually gives an algorithm for producing a resolution refutation from an
unsatisfiable set of clauses. In this note, we give a simple and constructive
proof of the completeness of propositional resolution which consists of an
algorithm together with a proof of its correctness.


title: Provably Secure Universal Steganographic Systems

abstract:
  We propose a simple universal (that is, distribution--free) steganographic
system in which covertexts with and without hidden texts are statistically
indistinguishable. The stegosystem can be applied to any source generating
i.i.d. covertexts with unknown distribution, and the hidden text is transmitted
exactly, with zero probability of error. Moreover, the proposed steganographic
system has two important properties. First, the rate of transmission of hidden
information approaches the Shannon entropy of the covertext source as the size
of blocks used for hidden text encoding tends to infinity. Second, if the size
of the alphabet of the covertext source and its minentropy tend to infinity
then the number of bits of hidden text per letter of covertext tends to
$\log(n!)/n$ where $n$ is the (fixed) size of blocks used for hidden text
encoding. The proposed stegosystem uses randomization.


title: Uniform Random Sampling of Traces in Very Large Models

abstract:
  This paper presents some first results on how to perform uniform random walks
(where every trace has the same probability to occur) in very large models. The
models considered here are described in a succinct way as a set of
communicating reactive modules. The method relies upon techniques for counting
and drawing uniformly at random words in regular languages. Each module is
considered as an automaton defining such a language. It is shown how it is
possible to combine local uniform drawings of traces, and to obtain some global
uniform random sampling, without construction of the global model.


title: Violator Spaces: Structure and Algorithms

abstract:
  Sharir and Welzl introduced an abstract framework for optimization problems,
called LP-type problems or also generalized linear programming problems, which
proved useful in algorithm design. We define a new, and as we believe, simpler
and more natural framework: violator spaces, which constitute a proper
generalization of LP-type problems. We show that Clarkson's randomized
algorithms for low-dimensional linear programming work in the context of
violator spaces. For example, in this way we obtain the fastest known algorithm
for the P-matrix generalized linear complementarity problem with a constant
number of blocks. We also give two new characterizations of LP-type problems:
they are equivalent to acyclic violator spaces, as well as to concrete LP-type
problems (informally, the constraints in a concrete LP-type problem are subsets
of a linearly ordered ground set, and the value of a set of constraints is the
minimum of its intersection).


title:
Breaking barriers for people with voice disabilities: Combining virtual
  keyboards with speech synthesizers, and VoIP applications

abstract:
  Text-to-speech technology has been broadly used to help people with voice
disabilities to overcome their difficulties. With text-to-speech, a person
types at a keyboard, the text is synthesized, and the sound comes out through
the computer speakers.
  In recent years, Voice over IP (VoIP) applications have become very popular
and have been used by people worldwide. These applications allow people to talk
for free over the Internet and also to make traditional calls through the
Public-Switched Telephone Network (PSTN) at a small fraction of the cost
offered by traditional phone companies.
  We have created a system, called EasyVoice, which integrates speech
synthesizers with VoIP applications. The result allows a person with motor
impairments and voice disabilities to talk with another person located anywhere
in the world. The benefits in this case are much stronger than the ones
obtained by non-disabled people using VoIP applications. People with motor
impairments sometimes can hardly use a regular or mobile phone. Thus, the
advantage is not only the reduction in cost, but more important, the ability to
talk at all.


title:
NVision-PA: A Tool for Visual Analysis of Command Behavior Based on
  Process Accounting Logs (with a Case Study in HPC Cluster Security)

abstract:
  In the UNIX/Linux environment the kernel can log every command process
created by every user with process accounting. Thus process accounting logs
have many potential uses, particularly the monitoring and forensic
investigation of security events. Previous work successfully leveraged the use
of process accounting logs to identify a difficult to detect and damaging
intrusion against high performance computing (HPC) clusters, masquerade
attacks, where intruders masquerade as legitimate users with purloined
authentication credentials. While masqueraders on HPC clusters were found to be
identifiable with a high accuracy (greater than 90%), this accuracy is still
not high enough for HPC production environments where greater than 99% accuracy
is needed.
  This paper incrementally advances the goal of more accurately identifying
masqueraders on HPC clusters by seeking to identify features within command
sets that distinguish masqueraders. To accomplish this goal, we created
NVision-PA, a software tool that produces text and graphic statistical
summaries describing input processing accounting logs. We report NVision-PA
results describing two different process accounting logs; one from Internet
usage and one from HPC cluster usage. These results identify the distinguishing
features of Internet users (as proxies for masqueraders) posing as clusters
users. This research is both a promising next step toward creating a real-time
masquerade detection sensor for production HPC clusters as well as providing
another tool for system administrators to use for statistically monitoring and
managing legitimate workloads (as indicated by command usage) in HPC
environments.


title:
Error Rate Analysis for Coded Multicarrier Systems over Quasi-Static
  Fading Channels

abstract:
  Several recent standards such as IEEE 802.11a/g, IEEE 802.16, and ECMA
Multiband Orthogonal Frequency Division Multiplexing (MB-OFDM) for high
data-rate Ultra-Wideband (UWB), employ bit-interleaved convolutionally-coded
multicarrier modulation over quasi-static fading channels. Motivated by the
lack of appropriate error rate analysis techniques for this popular type of
system and channel model, we present two novel analytical methods for bit error
rate (BER) estimation of coded multicarrier systems operating over
frequency-selective quasi-static channels with non-ideal interleaving. In the
first method, the approximate performance of the system is calculated for each
realization of the channel, which is suitable for obtaining the outage BER
performance (a common performance measure for e.g. MB-OFDM systems). The second
method assumes Rayleigh distributed frequency-domain subcarrier channel gains
and knowledge of their correlation matrix, and can be used to directly obtain
the average BER performance. Both methods are applicable to
convolutionally-coded interleaved multicarrier systems employing Quadrature
Amplitude Modulation (QAM), and are also able to account for narrowband
interference (modeled as a sum of tone interferers). To illustrate the
application of the proposed analysis, both methods are used to study the
performance of a tone-interference-impaired MB-OFDM system.


title:
On computing fixpoints in well-structured regular model checking, with
  applications to lossy channel systems

abstract:
  We prove a general finite convergence theorem for "upward-guarded" fixpoint
expressions over a well-quasi-ordered set. This has immediate applications in
regular model checking of well-structured systems, where a main issue is the
eventual convergence of fixpoint computations. In particular, we are able to
directly obtain several new decidability results on lossy channel systems.


title: Static Analysis using Parameterised Boolean Equation Systems

abstract:
  The well-known problem of state space explosion in model checking is even
more critical when applying this technique to programming languages, mainly due
to the presence of complex data structures. One recent and promising approach
to deal with this problem is the construction of an abstract and correct
representation of the global program state allowing to match visited states
during program model exploration. In particular, one powerful method to
implement abstract matching is to fill the state vector with a minimal amount
of relevant variables for each program point. In this paper, we combine the
on-the-fly model-checking approach (incremental construction of the program
state space) and the static analysis method called influence analysis
(extraction of significant variables for each program point) in order to
automatically construct an abstract matching function. Firstly, we describe the
problem as an alternation-free value-based mu-calculus formula, whose validity
can be checked on the program model expressed as a labeled transition system
(LTS). Secondly, we translate the analysis into the local resolution of a
parameterised boolean equation system (PBES), whose representation enables a
more efficient construction of the resulting abstract matching function.
Finally, we show how our proposal may be elegantly integrated into CADP, a
generic framework for both the design and analysis of distributed systems and
the development of verification tools.


title: Predictions as statements and decisions

abstract:
  Prediction is a complex notion, and different predictors (such as people,
computer programs, and probabilistic theories) can pursue very different goals.
In this paper I will review some popular kinds of prediction and argue that the
theory of competitive on-line learning can benefit from the kinds of prediction
that are now foreign to it.


title:
On Typechecking Top-Down XML Tranformations: Fixed Input or Output
  Schemas

abstract:
  Typechecking consists of statically verifying whether the output of an XML
transformation always conforms to an output type for documents satisfying a
given input type. In this general setting, both the input and output schema as
well as the transformation are part of the input for the problem. However,
scenarios where the input or output schema can be considered to be fixed, are
quite common in practice. In the present work, we investigate the computational
complexity of the typechecking problem in the latter setting.


title: A verification algorithm for Declarative Concurrent Programming

abstract:
  A verification method for distributed systems based on decoupling forward and
backward behaviour is proposed. This method uses an event structure based
algorithm that, given a CCS process, constructs its causal compression relative
to a choice of observable actions. Verifying the original process equipped with
distributed backtracking on non-observable actions, is equivalent to verifying
its relative compression which in general is much smaller. We call this method
Declarative Concurrent Programming (DCP). DCP technique compares well with
direct bisimulation based methods. Benchmarks for the classic dining
philosophers problem show that causal compression is rather efficient both
time- and space-wise. State of the art verification tools can successfully
handle more than 15 agents, whereas they can handle no more than 5 following
the traditional direct method; an altogether spectacular improvement, since in
this example the specification size is exponential in the number of agents.


title: Building a resource for studying translation shifts

abstract:
  This paper describes an interdisciplinary approach which brings together the
fields of corpus linguistics and translation studies. It presents ongoing work
on the creation of a corpus resource in which translation shifts are explicitly
annotated. Translation shifts denote departures from formal correspondence
between source and target text, i.e. deviations that have occurred during the
translation process. A resource in which such shifts are annotated in a
systematic way will make it possible to study those phenomena that need to be
addressed if machine translation output is to resemble human translation. The
resource described in this paper contains English source texts (parliamentary
proceedings) and their German translations. The shift annotation is based on
predicate-argument structures and proceeds in two steps: first, predicates and
their arguments are annotated monolingually in a straightforward manner. Then,
the corresponding English and German predicates and arguments are aligned with
each other. Whenever a shift - mainly grammatical or semantic -has occurred,
the alignment is tagged accordingly.


title: Synonym search in Wikipedia: Synarcher

abstract:
  The program Synarcher for synonym (and related terms) search in the text
corpus of special structure (Wikipedia) was developed. The results of the
search are presented in the form of graph. It is possible to explore the graph
and search for graph elements interactively. Adapted HITS algorithm for synonym
search, program architecture, and program work evaluation with test examples
are presented in the paper. The proposed algorithm can be applied to a query
expansion by synonyms (in a search engine) and a synonym dictionary forming.


title: Outlier Robust ICP for Minimizing Fractional RMSD

abstract:
  We describe a variation of the iterative closest point (ICP) algorithm for
aligning two point sets under a set of transformations. Our algorithm is
superior to previous algorithms because (1) in determining the optimal
alignment, it identifies and discards likely outliers in a statistically robust
manner, and (2) it is guaranteed to converge to a locally optimal solution. To
this end, we formalize a new distance measure, fractional root mean squared
distance (frmsd), which incorporates the fraction of inliers into the distance
function. We lay out a specific implementation, but our framework can easily
incorporate most techniques and heuristics from modern registration algorithms.
We experimentally validate our algorithm against previous techniques on 2 and 3
dimensional data exposed to a variety of outlier types.


title: Fairness in Multiuser Systems with Polymatroid Capacity Region

abstract:
  For a wide class of multi-user systems, a subset of capacity region which
includes the corner points and the sum-capacity facet has a special structure
known as polymatroid. Multiaccess channels with fixed input distributions and
multiple-antenna broadcast channels are examples of such systems. Any interior
point of the sum-capacity facet can be achieved by time-sharing among corner
points or by an alternative method known as rate-splitting. The main purpose of
this paper is to find a point on the sum-capacity facet which satisfies a
notion of fairness among active users. This problem is addressed in two cases:
(i) where the complexity of achieving interior points is not feasible, and (ii)
where the complexity of achieving interior points is feasible. For the first
case, the corner point for which the minimum rate of the active users is
maximized (max-min corner point) is desired for signaling. A simple greedy
algorithm is introduced to find the optimum max-min corner point. For the
second case, the polymatroid properties are exploited to locate a rate-vector
on the sum-capacity facet which is optimally fair in the sense that the minimum
rate among all users is maximized (max-min rate). In the case that the rate of
some users can not increase further (attain the max-min value), the algorithm
recursively maximizes the minimum rate among the rest of the users. It is shown
that the problems of deriving the time-sharing coefficients or rate-spitting
scheme can be solved by decomposing the problem to some lower-dimensional
subproblems. In addition, a fast algorithm to compute the time-sharing
coefficients to attain a general point on the sum-capacity facet is proposed.


title:
The generating function of the polytope of transport matrices $U(r,c)$
  as a positive semidefinite kernel of the marginals $r$ and $c$

abstract:
  This paper has been withdrawn by the author due to a crucial error in the
proof of Lemma 5.


title:
Stochastic Formal Methods: An application to accuracy of numeric
  software

abstract:
  This paper provides a bound on the number of numeric operations (fixed or
floating point) that can safely be performed before accuracy is lost. This work
has important implications for control systems with safety-critical software,
as these systems are now running fast enough and long enough for their errors
to impact on their functionality. Furthermore, worst-case analysis would
blindly advise the replacement of existing systems that have been successfully
running for years. We present here a set of formal theorems validated by the
PVS proof assistant. These theorems will allow code analyzing tools to produce
formal certificates of accurate behavior. For example, FAA regulations for
aircraft require that the probability of an error be below $10^{-9}$ for a 10
hour flight.


title: Toward Functionality Oriented Programming

abstract:
  The concept of functionality oriented programming is proposed, and some of
its aspects are discussed, such as: (1) implementation independent basic types
and generic collection types; (2) syntax requirements and recommendations for
implementation independence; (3) unified documentation and code; (4)
cross-module interface; and (5) cross-language program making scheme. A
prototype example is given to demonstrate functionality oriented programming.


title: Precision Arithmetic: A New Floating-Point Arithmetic

abstract:
  A new deterministic floating-point arithmetic called precision arithmetic is
developed to track precision for arithmetic calculations. It uses a novel
rounding scheme to avoid excessive rounding error propagation of conventional
floating-point arithmetic. Unlike interval arithmetic, its uncertainty tracking
is based on statistics and the central limit theorem, with a much tighter
bounding range. Its stable rounding error distribution is approximated by a
truncated normal distribution. Generic standards and systematic methods for
validating uncertainty-bearing arithmetics are discussed. The precision
arithmetic is found to be better than interval arithmetic in both
uncertainty-tracking and uncertainty-bounding for normal usages.
  The precision arithmetic is available publicly at
http://precisionarithm.sourceforge.net.


title: An information-spectrum approach to large deviation theorems

abstract:
  In this paper we show a some new look at large deviation theorems from the
viewpoint of the information-spectrum (IS) methods, which has been first
exploited in information theory, and also demonstrate a new basic formula for
the large deviation rate function in general, which is a pair of the lower and
upper IS rate functions. In particular, we are interested in establishing the
general large deviation rate functions that can be derivable as the
Fenchel-Legendre transform of the cumulant generating function. The final goal
is to show a necessary and sufficient condition for the rate function to be of
Cram\'er-G\"artner-Ellis type.


title:
Iso9000 Based Advanced Quality Approach for Continuous Improvement of
  Manufacturing Processes

abstract:
  The continuous improvement in TQM is considered as the core value by which
organisation could maintain a competitive edge. Several techniques and tools
are known to support this core value but most of the time these techniques are
informal and without modelling the interdependence between the core value and
tools. Thus, technique formalisation is one of TQM challenges for increasing
efficiency of quality process implementation. In that way, the paper proposes
and experiments an advanced quality modelling approach based on meta-modelling
the "process approach" as advocated by the standard ISO9000:2000. This
meta-model allows formalising the interdependence between technique, tools and
core value


title:
Self-orthogonality of $q$-ary Images of $q^m$-ary Codes and Quantum Code
  Construction

abstract:
  A code over GF$(q^m)$ can be imaged or expanded into a code over GF$(q)$
using a basis for the extension field over the base field. The properties of
such an image depend on the original code and the basis chosen for imaging.
Problems relating the properties of a code and its image with respect to a
basis have been of great interest in the field of coding theory. In this work,
a generalized version of the problem of self-orthogonality of the $q$-ary image
of a $q^m$-ary code has been considered. Given an inner product (more
generally, a biadditive form), necessary and sufficient conditions have been
derived for a code over a field extension and an expansion basis so that an
image of that code is self-orthogonal. The conditions require that the original
code be self-orthogonal with respect to several related biadditive forms
whenever certain power sums of the dual basis elements do not vanish. Numerous
interesting corollaries have been derived by specializing the general
conditions. An interesting result for the canonical or regular inner product in
fields of characteristic two is that only self-orthogonal codes result in
self-orthogonal images. Another result is that image of a code is
self-orthogonal for all bases if and only if trace of the code is
self-orthogonal, except for the case of binary images of 4-ary codes. The
conditions are particularly simple to state and apply for cyclic codes. To
illustrate a possible application, new quantum error-correcting codes have been
constructed with larger minimum distance than previously known.


title: Human Information Processing with the Personal Memex

abstract:
  In this report, we describe the work done in a project that explored the
human information processing aspects of a personal memex (a memex to organize
personal information). In the project, we considered the use of the personal
memex, focusing on information recall, by three populations: people with Mild
Cognitive Impairment, those diagnosed with Macular Degeneration, and a
high-functioning population. The outcomes of the project included human
information processing-centered design guidelines for the memex interface, a
low-fidelity prototype, and an annotated bibliography for human information
processing, usability and design literature relating to the memex and the
populations we explored.


title:
A Product Oriented Modelling Concept: Holons for systems synchronisation
  and interoperability

abstract:
  Nowadays, enterprises are confronted to growing needs for traceability,
product genealogy and product life cycle management. To meet those needs, the
enterprise and applications in the enterprise environment have to manage flows
of information that relate to flows of material and that are managed in shop
floor level. Nevertheless, throughout product lifecycle coordination needs to
be established between reality in the physical world (physical view) and the
virtual world handled by manufacturing information systems (informational
view). This paper presents the "Holon" modelling concept as a means for the
synchronisation of both physical view and informational views. Afterwards, we
show how the concept of holon can play a major role in ensuring
interoperability in the enterprise context.


title: Maximum gradient embeddings and monotone clustering

abstract:
  Let (X,d_X) be an n-point metric space. We show that there exists a
distribution D over non-contractive embeddings into trees f:X-->T such that for
every x in X, the expectation with respect to D of the maximum over y in X of
the ratio d_T(f(x),f(y)) / d_X(x,y) is at most C (log n)^2, where C is a
universal constant. Conversely we show that the above quadratic dependence on
log n cannot be improved in general. Such embeddings, which we call maximum
gradient embeddings, yield a framework for the design of approximation
algorithms for a wide range of clustering problems with monotone costs,
including fault-tolerant versions of k-median and facility location.


title: Optimal Scheduling of Peer-to-Peer File Dissemination

abstract:
  Peer-to-peer (P2P) overlay networks such as BitTorrent and Avalanche are
increasingly used for disseminating potentially large files from a server to
many end users via the Internet. The key idea is to divide the file into many
equally-sized parts and then let users download each part (or, for network
coding based systems such as Avalanche, linear combinations of the parts)
either from the server or from another user who has already downloaded it.
However, their performance evaluation has typically been limited to comparing
one system relative to another and typically been realized by means of
simulation and measurements. In contrast, we provide an analytic performance
analysis that is based on a new uplink-sharing version of the well-known
broadcasting problem. Assuming equal upload capacities, we show that the
minimal time to disseminate the file is the same as for the simultaneous
send/receive version of the broadcasting problem. For general upload
capacities, we provide a mixed integer linear program (MILP) solution and a
complementary fluid limit solution. We thus provide a lower bound which can be
used as a performance benchmark for any P2P file dissemination system. We also
investigate the performance of a decentralized strategy, providing evidence
that the performance of necessarily decentralized P2P file dissemination
systems should be close to this bound and therefore that it is useful in
practice.


title: Models simulation and interoperability using MDA and HLA

abstract:
  In the manufacturing context, there have been numerous efforts to use
modeling and simulation tools and techniques to improve manufacturing
efficiency over the last four decades. While an increasing number of
manufacturing system decisions are being made based on the use of models, their
use is still sporadic in many manufacturing environments. Our paper advocates
for an approach combining MDA (model driven architecture) and HLA (High Level
Architecture), the IEEE standard for modeling and simulation, in order to
overcome the deficiencies of current simulation methods at the level of
interoperability and reuse.


title:
Product Centric Holons for Synchronisation and Interoperability in
  Manufacturing Environments

abstract:
  In the last few years, lot of work has been done in order to ensure
enterprise applications interoperability; however, proposed solutions focus
mainly on enterprise processes. Indeed, throughout product lifecycle
coordination needs to be established between reality in the physical world
(physical view) and the virtual world handled by manufacturing information
systems (informational view). This paper presents a holonic approach that
enables synchronisation of both physical and informational views. A model
driven approach for interoperability is proposed to ensure interoperability of
holon based models with other applications in the enterprise.


title: A common framework for aspect mining based on crosscutting concern sorts

abstract:
  The increasing number of aspect mining techniques proposed in literature
calls for a methodological way of comparing and combining them in order to
assess, and improve on, their quality. This paper addresses this situation by
proposing a common framework based on crosscutting concern sorts which allows
for consistent assessment, comparison and combination of aspect mining
techniques. The framework identifies a set of requirements that ensure
homogeneity in formulating the mining goals, presenting the results and
assessing their quality.
  We demonstrate feasibility of the approach by retrofitting an existing aspect
mining technique to the framework, and by using it to design and implement two
new mining techniques. We apply the three techniques to a known aspect mining
benchmark and show how they can be consistently assessed and combined to
increase the quality of the results. The techniques and combinations are
implemented in FINT, our publicly available free aspect mining tool.


title:
Hidden Markov Process: A New Representation, Entropy Rate and Estimation
  Entropy

abstract:
  We consider a pair of correlated processes {Z_n} and {S_n} (two sided), where
the former is observable and the later is hidden. The uncertainty in the
estimation of Z_n upon its finite past history is H(Z_n|Z_0^{n-1}), and for
estimation of S_n upon this observation is H(S_n|Z_0^{n-1}), which are both
sequences of n. The limits of these sequences (and their existence) are of
practical and theoretical interest. The first limit, if exists, is the entropy
rate. We call the second limit the estimation entropy. An example of a process
jointly correlated to another one is the hidden Markov process. It is the
memoryless observation of the Markov state process where state transitions are
independent of past observations. We consider a new representation of hidden
Markov process using iterated function system. In this representation the state
transitions are deterministically related to the process. This representation
provides a unified framework for the analysis of the two limiting entropies for
this process, resulting in integral expressions for the limits. This analysis
shows that under mild conditions the limits exist and provides a simple method
for calculating the elements of the corresponding sequences.


title:
Evaluating Variable Length Markov Chain Models for Analysis of User Web
  Navigation Sessions

abstract:
  Markov models have been widely used to represent and analyse user web
navigation data. In previous work we have proposed a method to dynamically
extend the order of a Markov chain model and a complimentary method for
assessing the predictive power of such a variable length Markov chain. Herein,
we review these two methods and propose a novel method for measuring the
ability of a variable length Markov model to summarise user web navigation
sessions up to a given length. While the summarisation ability of a model is
important to enable the identification of user navigation patterns, the ability
to make predictions is important in order to foresee the next link choice of a
user after following a given trail so as, for example, to personalise a web
site. We present an extensive experimental evaluation providing strong evidence
that prediction accuracy increases linearly with summarisation ability.


title: New Algorithms for Regular Expression Matching

abstract:
  In this paper we revisit the classical regular expression matching problem,
namely, given a regular expression $R$ and a string $Q$, decide if $Q$ matches
one of the strings specified by $R$. Let $m$ and $n$ be the length of $R$ and
$Q$, respectively. On a standard unit-cost RAM with word length $w \geq \log
n$, we show that the problem can be solved in $O(m)$ space with the following
running times: \begin{equation*} \begin{cases}
  O(n\frac{m \log w}{w} + m \log w) & \text{if $m > w$} \\
  O(n\log m + m\log m) & \text{if $\sqrt{w} < m \leq w$} \\
  O(\min(n+ m^2, n\log m + m\log m)) & \text{if $m \leq \sqrt{w}$.} \end{cases}
\end{equation*} This improves the best known time bound among algorithms using
$O(m)$ space. Whenever $w \geq \log^2 n$ it improves all known time bounds
regardless of how much space is used.


title:
Performance comparison of multi-user detectors for the downlink of a
  broadband MC-CDMA system

abstract:
  In this paper multi-user detection techniques, such as Parallel and Serial
Interference Cancellations (PIC & SIC), General Minimum Mean Square Error
(GMMSE) and polynomial MMSE, for the downlink of a broadband Multi-Carrier Code
Division Multiple Access (MCCDMA) system are investigated. The Bit Error Rate
(BER) and Frame Error Rate (FER) results are evaluated, and compared with
single-user detection (MMSEC, EGC) approaches, as well. The performance
evaluation takes into account the system load, channel coding and modulation
schemes.


title: Adapting a general parser to a sublanguage

abstract:
  In this paper, we propose a method to adapt a general parser (Link Parser) to
sublanguages, focusing on the parsing of texts in biology. Our main proposal is
the use of terminology (identication and analysis of terms) in order to reduce
the complexity of the text to be parsed. Several other strategies are explored
and finally combined among which text normalization, lexicon and
morpho-guessing module extensions and grammar rules adaptation. We compare the
parsing results before and after these adaptations.


title:
Lexical Adaptation of Link Grammar to the Biomedical Sublanguage: a
  Comparative Evaluation of Three Approaches

abstract:
  We study the adaptation of Link Grammar Parser to the biomedical sublanguage
with a focus on domain terms not found in a general parser lexicon. Using two
biomedical corpora, we implement and evaluate three approaches to addressing
unknown words: automatic lexicon expansion, the use of morphological clues, and
disambiguation using a part-of-speech tagger. We evaluate each approach
separately for its effect on parsing performance and consider combinations of
these approaches. In addition to a 45% increase in parsing efficiency, we find
that the best approach, incorporating information from a domain part-of-speech
tagger, offers a statistically signicant 10% relative decrease in error. The
adapted parser is available under an open-source license at
http://www.it.utu.fi/biolg.


title: On symmetric sandpiles

abstract:
  A symmetric version of the well-known SPM model for sandpiles is introduced.
We prove that the new model has fixed point dynamics. Although there might be
several fixed points, a precise description of the fixed points is given.
Moreover, we provide a simple closed formula for counting the number of fixed
points originated by initial conditions made of a single column of grains.


title: Performance of Orthogonal Beamforming for SDMA with Limited Feedback

abstract:
  On the multi-antenna broadcast channel, the spatial degrees of freedom
support simultaneous transmission to multiple users. The optimal multiuser
transmission, known as dirty paper coding, is not directly realizable.
Moreover, close-to-optimal solutions such as Tomlinson-Harashima precoding are
sensitive to CSI inaccuracy. This paper considers a more practical design
called per user unitary and rate control (PU2RC), which has been proposed for
emerging cellular standards. PU2RC supports multiuser simultaneous
transmission, enables limited feedback, and is capable of exploiting multiuser
diversity. Its key feature is an orthogonal beamforming (or precoding)
constraint, where each user selects a beamformer (or precoder) from a codebook
of multiple orthonormal bases. In this paper, the asymptotic throughput scaling
laws for PU2RC with a large user pool are derived for different regimes of the
signal-to-noise ratio (SNR). In the multiuser-interference-limited regime, the
throughput of PU2RC is shown to scale logarithmically with the number of users.
In the normal SNR and noise-limited regimes, the throughput is found to scale
double logarithmically with the number of users and also linearly with the
number of antennas at the base station. In addition, numerical results show
that PU2RC achieves higher throughput and is more robust against CSI
quantization errors than the popular alternative of zero-forcing beamforming if
the number of users is sufficiently large.


title: Comparison of Image Similarity Queries in P2P Systems

abstract:
  Given some of the recent advances in Distributed Hash Table (DHT) based
Peer-To-Peer (P2P) systems we ask the following questions: Are there
applications where unstructured queries are still necessary (i.e., the
underlying queries do not efficiently map onto any structured framework), and
are there unstructured P2P systems that can deliver the high bandwidth and
computing performance necessary to support such applications. Toward this end,
we consider an image search application which supports queries based on image
similarity metrics, such as color histogram intersection, and discuss why in
this setting, standard DHT approaches are not directly applicable. We then
study the feasibility of implementing such an image search system on two
different unstructured P2P systems: power-law topology with percolation search,
and an optimized super-node topology using structured broadcasts. We examine
the average and maximum values for node bandwidth, storage and processing
requirements in the percolation and super-node models, and show that current
high-end computers and high-speed links have sufficient resources to enable
deployments of large-scale complex image search systems.


title: Use MPLS in Lan's

abstract:
  To demonstrate the result of researches in laboratory with the focus in
exhibiting the real impact of the use of the technology MPLS in LAN. Through
these researches we will verify that the investment in this technology is
shown, of the point of view cost/benefit, very interesting, being necessary,
however, the adoption of another measured, in order to settle down a
satisfactory level in the items Quality and safety in the sending of packages
in VPN but assisting to the requirement latency of the net very well being
shown in the tests that it consumes on average one Tuesday leaves of the time
spend for the same function in routing IP.


title: Weighted hierarchical alignment of directed acyclic graph

abstract:
  In some applications of matching, the structural or hierarchical properties
of the two graphs being aligned must be maintained. The hierarchical properties
are induced by the direction of the edges in the two directed graphs. These
structural relationships defined by the hierarchy in the graphs act as a
constraint on the alignment. In this paper, we formalize the above problem as
the weighted alignment between two directed acyclic graphs. We prove that this
problem is NP-complete, show several upper bounds for approximating the
solution, and finally introduce polynomial time algorithms for sub-classes of
directed acyclic graphs.


title: Formalizing typical crosscutting concerns

abstract:
  We present a consistent system for referring crosscutting functionality,
relating crosscutting concerns to specific implementation idioms, and
formalizing their underlying relations through queries. The system is based on
generic crosscutting concerns that we organize and describe in a catalog.
  We have designed and implemented a tool support for querying source code for
instances of the proposed generic concerns and organizing them in composite
concern models. The composite concern model adds a new dimension to the
dominant decomposition of the system for describing and making explicit source
code relations specific to crosscutting concerns implementations.
  We use the proposed approach to describe crosscutting concerns in design
patterns and apply the tool to an opensource system (JHotDraw).


title: May We Have Your Attention: Analysis of a Selective Attention Task

abstract:
  In this paper we present a deeper analysis than has previously been carried
out of a selective attention problem, and the evolution of continuous-time
recurrent neural networks to solve it. We show that the task has a rich
structure, and agents must solve a variety of subproblems to perform well. We
consider the relationship between the complexity of an agent and the ease with
which it can evolve behavior that generalizes well across subproblems, and
demonstrate a shaping protocol that improves generalization.


title: Approximately Efficient Cost-Sharing Mechanisms

abstract:
  We make three different types of contributions to cost-sharing: First, we
identify several new classes of combinatorial cost functions that admit
incentive-compatible mechanisms achieving both a constant-factor approximation
of budget-balance and a polylogarithmic approximation of the social cost
formulation of efficiency. Second, we prove a new, optimal lower bound on the
approximate efficiency of every budget-balanced Moulin mechanism for Steiner
tree or SSRoB cost functions. This lower bound exposes a latent approximation
hierarchy among different cost-sharing problems. Third, we show that weakening
the definition of incentive-compatibility to strategyproofness can permit
exponentially more efficient approximately budget-balanced mechanisms, in
particular for set cover cost-sharing problems.


title:
Automatic forming lists of semantically related terms based on texts
  rating in the corpus with hyperlinks and categories (In Russian)

abstract:
  HITS adapted algorithm for synonym search, the program architecture, and the
program work evaluation with test examples are presented in the paper.
Synarcher program for synonym (and related terms) search in the text corpus of
special structure (Wikipedia) was developed. The results of search are
presented in the form of a graph. It is possible to explore the graph and
search graph elements interactively. The proposed algorithm could be applied to
the search request extending and for synonym dictionary forming.


title:
A Novel Application of Lifting Scheme for Multiresolution Correlation of
  Complex Radar Signals

abstract:
  The lifting scheme of discrete wavelet transform (DWT) is now quite well
established as an efficient technique for image compression, and has been
incorporated into the JPEG2000 standards. However, the potential of the lifting
scheme has not been exploited in the context of correlationbased processing,
such as encountered in radar applications. This paper presents a complete and
consistent framework for the application of DWT for correlation of complex
signals. In particular, lifting scheme factorization of biorthogonal
filterbanks is carried out in dual analysis basis spaces for multiresolution
correlation of complex radar signals in the DWT domain only. A causal
formulation of lifting for orthogonal filterbank is also developed. The
resulting parallel algorithms and consequent saving of computational effort are
briefly dealt with.


title:
Coding for Parallel Channels: Gallager Bounds for Binary Linear Codes
  with Applications to Repeat-Accumulate Codes and Variations

abstract:
  This paper is focused on the performance analysis of binary linear block
codes (or ensembles) whose transmission takes place over independent and
memoryless parallel channels. New upper bounds on the maximum-likelihood (ML)
decoding error probability are derived. These bounds are applied to various
ensembles of turbo-like codes, focusing especially on repeat-accumulate codes
and their recent variations which possess low encoding and decoding complexity
and exhibit remarkable performance under iterative decoding. The framework of
the second version of the Duman and Salehi (DS2) bounds is generalized to the
case of parallel channels, along with the derivation of their optimized tilting
measures. The connection between the generalized DS2 and the 1961 Gallager
bounds, addressed by Divsalar and by Sason and Shamai for a single channel, is
explored in the case of an arbitrary number of independent parallel channels.
The generalization of the DS2 bound for parallel channels enables to re-derive
specific bounds which were originally derived by Liu et al. as special cases of
the Gallager bound. In the asymptotic case where we let the block length tend
to infinity, the new bounds are used to obtain improved inner bounds on the
attainable channel regions under ML decoding. The tightness of the new bounds
for independent parallel channels is exemplified for structured ensembles of
turbo-like codes. The improved bounds with their optimized tilting measures
show, irrespectively of the block length of the codes, an improvement over the
union bound and other previously reported bounds for independent parallel
channels; this improvement is especially pronounced for moderate to large block
lengths.


title:
Tightened Upper Bounds on the ML Decoding Error Probability of Binary
  Linear Block Codes

abstract:
  The performance of maximum-likelihood (ML) decoded binary linear block codes
is addressed via the derivation of tightened upper bounds on their decoding
error probability. The upper bounds on the block and bit error probabilities
are valid for any memoryless, binary-input and output-symmetric communication
channel, and their effectiveness is exemplified for various ensembles of
turbo-like codes over the AWGN channel. An expurgation of the distance spectrum
of binary linear block codes further tightens the resulting upper bounds.


title: On the Error Exponents of Some Improved Tangential-Sphere Bounds

abstract:
  The performance of maximum-likelihood (ML) decoded binary linear block codes
over the AWGN channel is addressed via the tangential-sphere bound (TSB) and
two of its recent improved versions. The paper is focused on the derivation of
the error exponents of these bounds. Although it was exemplified that some
recent improvements of the TSB tighten this bound for finite-length codes, it
is demonstrated in this paper that their error exponents coincide. For an
arbitrary ensemble of binary linear block codes, the common value of these
error exponents is explicitly expressed in terms of the asymptotic growth rate
of the average distance spectrum.


title: Belief Conditioning Rules (BCRs)

abstract:
  In this paper we propose a new family of Belief Conditioning Rules (BCRs) for
belief revision. These rules are not directly related with the fusion of
several sources of evidence but with the revision of a belief assignment
available at a given time according to the new truth (i.e. conditioning
constraint) one has about the space of solutions of the problem.