title: Precoloring co-Meyniel graphs

abstract:
  The pre-coloring extension problem consists, given a graph $G$ and a subset
of nodes to which some colors are already assigned, in finding a coloring of
$G$ with the minimum number of colors which respects the pre-coloring
assignment. This can be reduced to the usual coloring problem on a certain
contracted graph. We prove that pre-coloring extension is polynomial for
complements of Meyniel graphs. We answer a question of Hujter and Tuza by
showing that ``PrExt perfect'' graphs are exactly the co-Meyniel graphs, which
also generalizes results of Hujter and Tuza and of Hertz. Moreover we show
that, given a co-Meyniel graph, the corresponding contracted graph belongs to a
restricted class of perfect graphs (``co-Artemis'' graphs, which are
``co-perfectly contractile'' graphs), whose perfectness is easier to establish
than the strong perfect graph theorem. However, the polynomiality of our
algorithm still depends on the ellipsoid method for coloring perfect graphs.


title:
Combining Structured Corporate Data and Document Content to Improve
  Expertise Finding

abstract:
  In this paper, we present an algorithm for automatically building expertise
evidence for finding experts within an organization by combining structured
corporate information with different content. We also describe our test data
collection and our evaluation method. Evaluation of the algorithm shows that
using organizational structure leads to a significant improvement in the
precision of finding an expert. Furthermore we evaluate the impact of using
different data sources on the quality of the results and conclude that Expert
Finding is not a "one engine fits all" solution. It requires an analysis of the
information space into which a solution will be placed and the appropriate
selection and weighting scheme of the data sources.


title:
Optimal space-time codes for the MIMO amplify-and-forward cooperative
  channel

abstract:
  In this work, we extend the non-orthogonal amplify-and-forward (NAF)
cooperative diversity scheme to the MIMO channel. A family of space-time block
codes for a half-duplex MIMO NAF fading cooperative channel with N relays is
constructed. The code construction is based on the non-vanishing determinant
criterion (NVD) and is shown to achieve the optimal diversity-multiplexing
tradeoff (DMT) of the channel. We provide a general explicit algebraic
construction, followed by some examples. In particular, in the single relay
case, it is proved that the Golden code and the 4x4 Perfect code are optimal
for the single-antenna and two-antenna case, respectively. Simulation results
reveal that a significant gain (up to 10dB) can be obtained with the proposed
codes, especially in the single-antenna case.


title:
Non-Data-Aided Parameter Estimation in an Additive White Gaussian Noise
  Channel

abstract:
  Non-data-aided (NDA) parameter estimation is considered for
binary-phase-shift-keying transmission in an additive white Gaussian noise
channel. Cramer-Rao lower bounds (CRLBs) for signal amplitude, noise variance,
channel reliability constant and bit-error rate are derived and it is shown how
these parameters relate to the signal-to-noise ratio (SNR). An alternative
derivation of the iterative maximum likelihood (ML) SNR estimator is presented
together with a novel, low complexity NDA SNR estimator. The performance of the
proposed estimator is compared to previously suggested estimators and the CRLB.
The results show that the proposed estimator performs close to the iterative ML
estimator at significantly lower computational complexity.


title:
Joint Equalization and Decoding for Nonlinear Two-Dimensional
  Intersymbol Interference Channels with Application to Optical Storage

abstract:
  An algorithm that performs joint equalization and decoding for nonlinear
two-dimensional intersymbol interference channels is presented. The algorithm
performs sum-product message-passing on a factor graph that represents the
underlying system. The two-dimensional optical storage (TWODOS) technology is
an example of a system with nonlinear two-dimensional intersymbol interference.
Simulations for the nonlinear channel model of TWODOS show significant
improvement in performance over uncoded performance. Noise tolerance thresholds
for the algorithm for the TWODOS channel, computed using density evolution, are
also presented and accurately predict the limiting performance of the algorithm
as the codeword length increases.


title:
Joint Equalization and Decoding for Nonlinear Two-Dimensional
  Intersymbol Interference Channels

abstract:
  An algorithm that performs joint equalization and decoding for channels with
nonlinear two-dimensional intersymbol interference is presented. The algorithm
performs sum-product message-passing on a factor graph that represents the
underlying system. The two-dimensional optical storage (TwoDOS) technology is
an example of a system with nonlinear two-dimensional intersymbol interference.
Simulations for the nonlinear channel model of TwoDOS show significant
improvement in performance over uncoded performance. Noise tolerance thresholds
for the TwoDOS channel computed using density evolution are also presented.


title:
Minimum Mean-Square-Error Equalization using Priors for Two-Dimensional
  Intersymbol Interference

abstract:
  Joint equalization and decoding schemes are described for two-dimensional
intersymbol interference (ISI) channels. Equalization is performed using the
minimum mean-square-error (MMSE) criterion. Low-density parity-check codes are
used for error correction. The MMSE schemes are the extension of those proposed
by Tuechler et al. (2002) for one-dimensional ISI channels. Extrinsic
information transfer charts, density evolution, and bit-error rate versus
signal-to-noise ratio curves are used to study the performance of the schemes.


title:
Clustering Mixed Numeric and Categorical Data: A Cluster Ensemble
  Approach

abstract:
  Clustering is a widely used technique in data mining applications for
discovering patterns in underlying data. Most traditional clustering algorithms
are limited to handling datasets that contain either numeric or categorical
attributes. However, datasets with mixed types of attributes are common in real
life data mining applications. In this paper, we propose a novel
divide-and-conquer technique to solve this problem. First, the original mixed
dataset is divided into two sub-datasets: the pure categorical dataset and the
pure numeric dataset. Next, existing well established clustering algorithms
designed for different types of datasets are employed to produce corresponding
clusters. Last, the clustering results on the categorical and numeric dataset
are combined as a categorical dataset, on which the categorical data clustering
algorithm is used to get the final clusters. Our contribution in this paper is
to provide an algorithm framework for the mixed attributes clustering problem,
in which existing clustering algorithms can be easily integrated, the
capabilities of different kinds of clustering algorithms and characteristics of
different types of datasets could be fully exploited. Comparisons with other
clustering algorithms on real life datasets illustrate the superiority of our
approach.


title: Kriging Scenario For Capital Markets

abstract: An introduction to numerical statistics.


title: On the variational distance of independently repeated experiments

abstract:
  Let P and Q be two probability distributions which differ only for values
with non-zero probability. We show that the variational distance between the
n-fold product distributions P^n and Q^n cannot grow faster than the square
root of n.


title: Density Evolution for Asymmetric Memoryless Channels

abstract:
  Density evolution is one of the most powerful analytical tools for
low-density parity-check (LDPC) codes and graph codes with message passing
decoding algorithms. With channel symmetry as one of its fundamental
assumptions, density evolution (DE) has been widely and successfully applied to
different channels, including binary erasure channels, binary symmetric
channels, binary additive white Gaussian noise channels, etc. This paper
generalizes density evolution for non-symmetric memoryless channels, which in
turn broadens the applications to general memoryless channels, e.g. z-channels,
composite white Gaussian noise channels, etc. The central theorem underpinning
this generalization is the convergence to perfect projection for any fixed size
supporting tree. A new iterative formula of the same complexity is then
presented and the necessary theorems for the performance concentration theorems
are developed. Several properties of the new density evolution method are
explored, including stability results for general asymmetric memoryless
channels. Simulations, code optimizations, and possible new applications
suggested by this new density evolution method are also provided. This result
is also used to prove the typicality of linear LDPC codes among the coset code
ensemble when the minimum check node degree is sufficiently large. It is shown
that the convergence to perfect projection is essential to the belief
propagation algorithm even when only symmetric channels are considered. Hence
the proof of the convergence to perfect projection serves also as a completion
of the theory of classical density evolution for symmetric memoryless channels.


title:
Optimal Prefix Codes with Fewer Distinct Codeword Lengths are Faster to
  Construct

abstract:
  A new method for constructing minimum-redundancy binary prefix codes is
described. Our method does not explicitly build a Huffman tree; instead it uses
a property of optimal prefix codes to compute the codeword lengths
corresponding to the input weights. Let $n$ be the number of weights and $k$ be
the number of distinct codeword lengths as produced by the algorithm for the
optimum codes. The running time of our algorithm is $O(k \cdot n)$. Following
our previous work in \cite{be}, no algorithm can possibly construct optimal
prefix codes in $o(k \cdot n)$ time. When the given weights are presorted our
algorithm performs $O(9^k \cdot \log^{2k}{n})$ comparisons.


title: NP-hardness of the cluster minimization problem revisited

abstract:
  The computational complexity of the "cluster minimization problem" is
revisited [L. T. Wille and J. Vennik, J. Phys. A 18, L419 (1985)]. It is argued
that the original NP-hardness proof does not apply to pairwise potentials of
physical interest, such as those that depend on the geometric distance between
the particles. A geometric analog of the original problem is formulated, and a
new proof for such potentials is provided by polynomial time transformation
from the independent set problem for unit disk graphs. Limitations of this
formulation are pointed out, and new subproblems that bear more direct
consequences to the numerical study of clusters are suggested.


title: Traders imprint themselves by adaptively updating their own avatar

abstract:
  Simulations of artificial stock markets were considered as early as 1964 and
multi-agent ones were introduced as early as 1989. Starting the early 90's,
collaborations of economists and physicists produced increasingly realistic
simulation platforms. Currently, the market stylized facts are easily
reproduced and one has now to address the realistic details of the Market
Microstructure and of the Traders Behaviour. This calls for new methods and
tools capable of bridging smoothly between simulations and experiments in
economics.
  We propose here the following Avatar-Based Method (ABM). The subjects
implement and maintain their Avatars (programs encoding their personal decision
making procedures) on NatLab, a market simulation platform. Once these
procedures are fed in a computer edible format, they can be operationally used
as such without the need for belabouring, interpreting or conceptualising them.
Thus ABM short-circuits the usual behavioural economics experiments that search
for the psychological mechanisms underlying the subjects behaviour. Finally,
ABM maintains a level of objectivity close to the classical behaviourism while
extending its scope to subjects' decision making mechanisms.
  We report on experiments where Avatars designed and maintained by humans from
different backgrounds (including real traders) compete in a continuous
double-auction market. We hope this unbiased way of capturing the adaptive
evolution of real subjects behaviour may lead to a new kind of behavioural
economics experiments with a high degree of reliability, analysability and
reproducibility.


title: Requirements for Digital Preservation Systems: A Bottom-Up Approach

abstract:
  The field of digital preservation is being defined by a set of standards
developed top-down, starting with an abstract reference model (OAIS) and
gradually adding more specific detail. Systems claiming conformance to these
standards are entering production use. Work is underway to certify that systems
conform to requirements derived from OAIS.
  We complement these requirements derived top-down by presenting an alternate,
bottom-up view of the field. The fundamental goal of these systems is to ensure
that the information they contain remains accessible for the long term. We
develop a parallel set of requirements based on observations of how existing
systems handle this task, and on an analysis of the threats to achieving the
goal. On this basis we suggest disclosures that systems should provide as to
how they satisfy their goals.


title: Comparing hierarchies of total functionals

abstract:
  In this paper we consider two hierarchies of hereditarily total and
continuous functionals over the reals based on one extensional and one
intensional representation of real numbers, and we discuss under which
asumptions these hierarchies coincide. This coincidense problem is equivalent
to a statement about the topology of the Kleene-Kreisel continuous functionals.
As a tool of independent interest, we show that the Kleene-Kreisel functionals
may be embedded into both these hierarchies.


title:
Transitive Text Mining for Information Extraction and Hypothesis
  Generation

abstract:
  Transitive text mining - also named Swanson Linking (SL) after its primary
and principal researcher - tries to establish meaningful links between
literature sets which are virtually disjoint in the sense that each does not
mention the main concept of the other. If successful, SL may give rise to the
development of new hypotheses. In this communication we describe our approach
to transitive text mining which employs co-occurrence analysis of the medical
subject headings (MeSH), the descriptors assigned to papers indexed in PubMed.
In addition, we will outline the current state of our web-based information
system which will enable our users to perform literature-driven hypothesis
building on their own.


title: The Throughput-Reliability Tradeoff in MIMO Channels

abstract:
  In this paper, an outage limited MIMO channel is considered. We build on
Zheng and Tse's elegant formulation of the diversity-multiplexing tradeoff to
develop a better understanding of the asymptotic relationship between the
probability of error, transmission rate, and signal-to-noise ratio. In
particular, we identify the limitation imposed by the multiplexing gain notion
and develop a new formulation for the throughput-reliability tradeoff that
avoids this limitation. The new characterization is then used to elucidate the
asymptotic trends exhibited by the outage probability curves of MIMO channels.


title: Achievable Rates for Pattern Recognition

abstract:
  Biological and machine pattern recognition systems face a common challenge:
Given sensory data about an unknown object, classify the object by comparing
the sensory data with a library of internal representations stored in memory.
In many cases of interest, the number of patterns to be discriminated and the
richness of the raw data force recognition systems to internally represent
memory and sensory information in a compressed format. However, these
representations must preserve enough information to accommodate the variability
and complexity of the environment, or else recognition will be unreliable.
Thus, there is an intrinsic tradeoff between the amount of resources devoted to
data representation and the complexity of the environment in which a
recognition system may reliably operate.
  In this paper we describe a general mathematical model for pattern
recognition systems subject to resource constraints, and show how the
aforementioned resource-complexity tradeoff can be characterized in terms of
three rates related to number of bits available for representing memory and
sensory data, and the number of patterns populating a given statistical
environment. We prove single-letter information theoretic bounds governing the
achievable rates, and illustrate the theory by analyzing the elementary cases
where the pattern data is either binary or Gaussian.


title: Coloring vertices of a graph or finding a Meyniel obstruction

abstract:
  A Meyniel obstruction is an odd cycle with at least five vertices and at most
one chord. A graph is Meyniel if and only if it has no Meyniel obstruction as
an induced subgraph. Here we give a O(n^2) algorithm that, for any graph, finds
either a clique and coloring of the same size or a Meyniel obstruction. We also
give a O(n^3) algorithm that, for any graph, finds either aneasily recognizable
strong stable set or a Meyniel obstruction.


title: Well-founded and Stable Semantics of Logic Programs with Aggregates

abstract:
  In this paper, we present a framework for the semantics and the computation
of aggregates in the context of logic programming. In our study, an aggregate
can be an arbitrary interpreted second order predicate or function. We define
extensions of the Kripke-Kleene, the well-founded and the stable semantics for
aggregate programs. The semantics is based on the concept of a three-valued
immediate consequence operator of an aggregate program. Such an operator
approximates the standard two-valued immediate consequence operator of the
program, and induces a unique Kripke-Kleene model, a unique well-founded model
and a collection of stable models. We study different ways of defining such
operators and thus obtain a framework of semantics, offering different
trade-offs between precision and tractability. In particular, we investigate
conditions on the operator that guarantee that the computation of the three
types of semantics remains on the same level as for logic programs without
aggregates. Other results show that, in practice, even efficient three-valued
immediate consequence operators which are very low in the precision hierarchy,
still provide optimal precision.


title: A formally verified proof of the prime number theorem

abstract:
  The prime number theorem, established by Hadamard and de la Vall'ee Poussin
independently in 1896, asserts that the density of primes in the positive
integers is asymptotic to 1 / ln x. Whereas their proofs made serious use of
the methods of complex analysis, elementary proofs were provided by Selberg and
Erd"os in 1948. We describe a formally verified version of Selberg's proof,
obtained using the Isabelle proof assistant.


title: Sampling to estimate arbitrary subset sums

abstract:
  Starting with a set of weighted items, we want to create a generic sample of
a certain size that we can later use to estimate the total weight of arbitrary
subsets. For this purpose, we propose priority sampling which tested on
Internet data performed better than previous methods by orders of magnitude.
  Priority sampling is simple to define and implement: we consider a steam of
items i=0,...,n-1 with weights w_i. For each item i, we generate a random
number r_i in (0,1) and create a priority q_i=w_i/r_i. The sample S consists of
the k highest priority items. Let t be the (k+1)th highest priority. Each
sampled item i in S gets a weight estimate W_i=max{w_i,t}, while non-sampled
items get weight estimate W_i=0.
  Magically, it turns out that the weight estimates are unbiased, that is,
E[W_i]=w_i, and by linearity of expectation, we get unbiased estimators over
any subset sum simply by adding the sampled weight estimates from the subset.
Also, we can estimate the variance of the estimates, and surpricingly, there is
no co-variance between different weight estimates W_i and W_j.
  We conjecture an extremely strong near-optimality; namely that for any weight
sequence, there exists no specialized scheme for sampling k items with unbiased
estimators that gets smaller total variance than priority sampling with k+1
items. Very recently Mario Szegedy has settled this conjecture.


title: Haskell's overlooked object system

abstract:
  Haskell provides type-class-bounded and parametric polymorphism as opposed to
subtype polymorphism of object-oriented languages such as Java and OCaml. It is
a contentious question whether Haskell 98 without extensions, or with common
extensions, or with new extensions can fully support conventional
object-oriented programming with encapsulation, mutable state, inheritance,
overriding, statically checked implicit and explicit subtyping, and so on. We
systematically substantiate that Haskell 98, with some common extensions,
supports all the conventional OO features plus more advanced ones, including
first-class lexically scoped classes, implicitly polymorphic classes, flexible
multiple inheritance, safe downcasts and safe co-variant arguments. Haskell
indeed can support width and depth, structural and nominal subtyping. We
address the particular challenge to preserve Haskell's type inference even for
objects and object-operating functions. The OO features are introduced in
Haskell as the OOHaskell library. OOHaskell lends itself as a sandbox for typed
OO language design.


title: Projecting the Forward Rate Flow onto a Finite Dimensional Manifold

abstract:
  Given a Heath-Jarrow-Morton (HJM) interest rate model $\mathcal{M}$ and a
parametrized family of finite dimensional forward rate curves $\mathcal{G}$,
this paper provides a technique for projecting the infinite dimensional forward
rate curve $r_{t}$ given by $\mathcal{M}$ onto the finite dimensional manifold
$\mathcal{G}$.The Stratonovich dynamics of the projected finite dimensional
forward curve are derived and it is shown that, under the regularity
conditions, the given Stratonovich differential equation has a unique strong
solution. Moreover, this projection leads to an efficient algorithm for
implicit parametric estimation of the infinite dimensional HJM model. The
feasibility of this method is demonstrated by applying the generalized method
of moments.


title: Quickest detection of a minimum of disorder times

abstract:
  A multi-source quickest detection problem is considered. Assume there are two
independent Poisson processes $X^{1}$ and $X^{2}$ with disorder times
$\theta_{1}$ and $\theta_{2}$, respectively; that is, the intensities of $X^1$
and $X^2$ change at random unobservable times $\theta_1$ and $\theta_2$,
respectively. $\theta_1$ and $\theta_2$ are independent of each other and are
exponentially distributed. Define $\theta \triangleq \theta_1 \wedge
\theta_2=\min\{\theta_{1},\theta_{2}\}$ . For any stopping time $\tau$ that is
measurable with respect to the filtration generated by the observations define
a penalty function of the form \[ R_{\tau}=\mathbb{P}(\tau<\theta)+c
\mathbb{E}[(\tau-\theta)^{+}], \] where $c>0$ and $(\tau-\theta)^{+}$ is the
positive part of $\tau-\theta$. It is of interest to find a stopping time
$\tau$ that minimizes the above performance index. Since both observations
$X^{1}$ and $X^{2}$ reveal information about the disorder time $\theta$, even
this simple problem is more involved than solving the disorder problems for
$X^{1}$ and $X^{2}$ separately. This problem is formulated in terms of a three
dimensional sufficient statistic, and the corresponding optimal stopping
problem is examined. A two dimensional optimal stopping problem whose optimal
stopping time turns out to coincide with the optimal stopping time of the
original problem for some range of parameters is also solved. The value
function of this problem serves as a tight upper bound for the original
problem's value function. The two solutions are characterized by iterating
suitable functional operators.


title: Multi-Proxy Multi-Signcryption Scheme from Pairings

abstract:
  A first multi-proxy multi-signcryption scheme from pairings, which
efficiently combines a multi-proxy multi-signature scheme with a signcryption,
is proposed. Its security is analyzed in detail. In our scheme, a proxy
signcrypter group could be authorized as a proxy agent by the cooperation of
all members in the original signcrypter group. Then the proxy signcryptions can
be generated by the cooperation of all the signcrypters in the authorized proxy
signcrypter group on behalf of the original signcrypter group. The correctness
and the security of this scheme are proved.


title:
On the Worst-case Performance of the Sum-of-Squares Algorithm for Bin
  Packing

abstract:
  The Sum of Squares algorithm for bin packing was defined in [2] and studied
in great detail in [1], where it was proved that its worst case performance
ratio is at most 3. In this note, we improve the asymptotic worst case bound to
2.7777...


title: A Simple Model to Generate Hard Satisfiable Instances

abstract:
  In this paper, we try to further demonstrate that the models of random CSP
instances proposed by [Xu and Li, 2000; 2003] are of theoretical and practical
interest. Indeed, these models, called RB and RD, present several nice
features. First, it is quite easy to generate random instances of any arity
since no particular structure has to be integrated, or property enforced, in
such instances. Then, the existence of an asymptotic phase transition can be
guaranteed while applying a limited restriction on domain size and on
constraint tightness. In that case, a threshold point can be precisely located
and all instances have the guarantee to be hard at the threshold, i.e., to have
an exponential tree-resolution complexity. Next, a formal analysis shows that
it is possible to generate forced satisfiable instances whose hardness is
similar to unforced satisfiable ones. This analysis is supported by some
representative results taken from an intensive experimentation that we have
carried out, using complete and incomplete search methods.


title: K-Histograms: An Efficient Clustering Algorithm for Categorical Dataset

abstract:
  Clustering categorical data is an integral part of data mining and has
attracted much attention recently. In this paper, we present k-histogram, a new
efficient algorithm for clustering categorical data. The k-histogram algorithm
extends the k-means algorithm to categorical domain by replacing the means of
clusters with histograms, and dynamically updates histograms in the clustering
process. Experimental results on real datasets show that k-histogram algorithm
can produce better clustering results than k-modes algorithm, the one related
with our work most closely.


title: N-free extensions of posets.Note on a theorem of P.A.Grillet

abstract:
  Let $S\_{N}(P)$ be the poset obtained by adding a dummy vertex on each
diagonal edge of the $N$'s of a finite poset $P$. We show that
$S\_{N}(S\_{N}(P))$ is $N$-free. It follows that this poset is the smallest
$N$-free barycentric subdivision of the diagram of $P$, poset whose existence
was proved by P.A. Grillet. This is also the poset obtained by the algorithm
starting with $P\_0:=P$ and consisting at step $m$ of adding a dummy vertex on
a diagonal edge of some $N$ in $P\_m$, proving that the result of this
algorithm does not depend upon the particular choice of the diagonal edge
choosen at each step. These results are linked to drawing of posets.


title:
Cryptanalysis of an MPEG-Video Encryption Scheme Based on Secret Huffman
  Tables

abstract:
  This paper studies the security of a recently-proposed MPEG-video encryption
scheme based on secret Huffman tables. Our cryptanalysis shows that: 1) the key
space of the encryption scheme is not sufficiently large against
divide-and-conquer (DAC) attack and known-plaintext attack; 2) it is possible
to decrypt a cipher-video with a partially-known key, thus dramatically
reducing the complexity of the DAC brute-force attack in some cases; 3) its
security against the chosen-plaintext attack is very weak. Some experimental
results are included to support the cryptanalytic results with a brief discuss
on how to improve this MPEG-video encryption scheme.


title: Security Problems with Improper Implementations of Improved FEA-M

abstract:
  This paper reports security problems with improper implementations of an
improved version of FEA-M (fast encryption algorithm for multimedia). It is
found that an implementation-dependent differential chosen-plaintext attack or
its chosen-ciphertext counterpart can reveal the secret key of the
cryptosystem, if the involved (pseudo-)random process can be tampered (for
example, through a public time service). The implementation-dependent
differential attack is very efficient in complexity and needs only $O(n^2)$
chosen plaintext or ciphertext bits. In addition, this paper also points out a
minor security problem with the selection of the session key. In real
implementations of the cryptosystem, these security problems should be
carefully avoided, or the cryptosystem has to be further enhanced to work under
such weak implementations.


title:
Friends for Free: Self-Organizing Artificial Social Networks for Trust
  and Cooperation

abstract:
  By harvesting friendship networks from e-mail contacts or instant message
"buddy lists" Peer-to-Peer (P2P) applications can improve performance in low
trust environments such as the Internet. However, natural social networks are
not always suitable, reliable or available. We propose an algorithm (SLACER)
that allows peer nodes to create and manage their own friendship networks.
  We evaluate performance using a canonical test application, requiring
cooperation between peers for socially optimal outcomes. The Artificial Social
Networks (ASN) produced are connected, cooperative and robust - possessing many
of the disable properties of human friendship networks such as trust between
friends (directly linked peers) and short paths linking everyone via a chain of
friends.
  In addition to new application possibilities, SLACER could supply ASN to P2P
applications that currently depend on human social networks thus transforming
them into fully autonomous, self-managing systems.


title: Algorithms for Max Hamming Exact Satisfiability

abstract:
  We here study Max Hamming XSAT, ie, the problem of finding two XSAT models at
maximum Hamming distance. By using a recent XSAT solver as an auxiliary
function, an O(1.911^n) time algorithm can be constructed, where n is the
number of variables. This upper time bound can be further improved to
O(1.8348^n) by introducing a new kind of branching, more directly suited for
finding models at maximum Hamming distance. The techniques presented here are
likely to be of practical use as well as of theoretical value, proving that
there are non-trivial algorithms for maximum Hamming distance problems.


title:
Coding for the feedback Gel'fand-Pinsker channel and the feedforward
  Wyner-Ziv source

abstract:
  We consider both channel coding and source coding, with perfect past
feedback/feedforward, in the presence of side information. It is first observed
that feedback does not increase the capacity of the Gel'fand-Pinsker channel,
nor does feedforward improve the achievable rate-distortion performance in the
Wyner-Ziv problem. We then focus on the Gaussian case showing that, as in the
absence of side information, feedback/feedforward allows to efficiently attain
the respective performance limits. In particular, we derive schemes via
variations on that of Schalkwijk and Kailath. These variants, which are as
simple as their origins and require no binning, are shown to achieve,
respectively, the capacity of Costa's channel, and the Wyner-Ziv rate
distortion function. Finally, we consider the finite-alphabet setting and
derive schemes for both the channel and the source coding problems that attain
the fundamental limits, using variations on schemes of Ahlswede and Ooi and
Wornell, and of Martinian and Wornell, respectively.


title: Authoring case based training by document data extraction

abstract:
  In this paper, we propose an scalable approach to modeling based upon word
processing documents, and we describe the tool Phoenix providing the technical
infrastructure.
  For our training environment d3web.Train, we developed a tool to extract case
knowledge from existing documents, usually dismissal records, extending Phoenix
to d3web.CaseImporter. Independent authors used this tool to develop training
systems, observing a significant decrease of time for setteling-in and a
decrease of time necessary for developing a case.


title:
Efficient Reconciliation of Correlated Continuous Random Variables using
  LDPC Codes

abstract:
  This paper investigates an efficient and practical information reconciliation
method in the case where two parties have access to correlated continuous
random variables. We show that reconciliation is a special case of channel
coding and that existing coded modulation techniques can be adapted for
reconciliation. We describe an explicit reconciliation method based on LDPC
codes in the case of correlated Gaussian variables. We believe that the
proposed method can improve the efficiency of quantum key distribution
protocols based on continuous-spectrum quantum states.


title: Computing over the Reals: Foundations for Scientific Computing

abstract:
  We give a detailed treatment of the ``bit-model'' of computability and
complexity of real functions and subsets of R^n, and argue that this is a good
way to formalize many problems of scientific computation. In the introduction
we also discuss the alternative Blum-Shub-Smale model. In the final section we
discuss the issue of whether physical systems could defeat the Church-Turing
Thesis.


title: Optimal Power Control for Multiuser CDMA Channels

abstract:
  In this paper, we define the power region as the set of power allocations for
K users such that everybody meets a minimum signal-to-interference ratio (SIR).
The SIR is modeled in a multiuser CDMA system with fixed linear receiver and
signature sequences. We show that the power region is convex in linear and
logarithmic scale. It furthermore has a componentwise minimal element. Power
constraints are included by the intersection with the set of all viable power
adjustments.
  In this framework, we aim at minimizing the total expended power by
minimizing a componentwise monotone functional. If the feasible power region is
nonempty, the minimum is attained. Otherwise, as a solution to balance
conflicting interests, we suggest the projection of the minimum point in the
power region onto the set of viable power settings. Finally, with an
appropriate utility function, the problem of minimizing the total expended
power can be seen as finding the Nash bargaining solution, which sheds light on
power assignment from a game theoretic point of view. Convexity and
componentwise monotonicity are essential prerequisites for this result.


title:
Accumulate-Repeat-Accumulate Codes: Systematic Codes Achieving the
  Binary Erasure Channel Capacity with Bounded Complexity

abstract:
  The paper introduces ensembles of accumulate-repeat-accumulate (ARA) codes
which asymptotically achieve capacity on the binary erasure channel (BEC) with
{\em bounded complexity} per information bit. It also introduces symmetry
properties which play a central role in the construction of capacity-achieving
ensembles for the BEC. The results here improve on the tradeoff between
performance and complexity provided by the first capacity-achieving ensembles
of irregular repeat-accumulate (IRA) codes with bounded complexity per
information bit; these IRA ensembles were previously constructed by Pfister,
Sason and Urbanke. The superiority of ARA codes with moderate to large block
length is exemplified by computer simulations which compare their performance
with those of previously reported capacity-achieving ensembles of LDPC and IRA
codes. The ARA codes also have the advantage of being systematic.


title: On Hats and other Covers

abstract:
  We study a game puzzle that has enjoyed recent popularity among
mathematicians, computer scientist, coding theorists and even the mass press.
In the game, $n$ players are fitted with randomly assigned colored hats.
Individual players can see their teammates' hat colors, but not their own.
Based on this information, and without any further communication, each player
must attempt to guess his hat color, or pass. The team wins if there is at
least one correct guess, and no incorrect ones. The goal is to devise guessing
strategies that maximize the team winning probability. We show that for the
case of two hat colors, and for any value of $n$, playing strategies are
equivalent to binary covering codes of radius one. This link, in particular
with Hamming codes, had been observed for values of $n$ of the form $2^m-1$. We
extend the analysis to games with hats of $q$ colors, $q\geq 2$, where
1-coverings are not sufficient to characterize the best strategies. Instead, we
introduce the more appropriate notion of a {\em strong covering}, and show
efficient constructions of these coverings, which achieve winning probabilities
approaching unity. Finally, we briefly discuss results on variants of the
problem, including arbitrary input distributions, randomized playing
strategies, and symmetric strategies.


title: On the number of t-ary trees with a given path length

abstract:
  We show that the number of $t$-ary trees with path length equal to $p$ is
$\exp(h(t^{-1})t\log t \frac{p}{\log p}(1+o(1)))$, where
$\entropy(x){=}{-}x\log x {-}(1{-}x)\log (1{-}x)$ is the binary entropy
function. Besides its intrinsic combinatorial interest, the question recently
arose in the context of information theory, where the number of $t$-ary trees
with path length $p$ estimates the number of universal types, or, equivalently,
the number of different possible Lempel-Ziv'78 dictionaries for sequences of
length $p$ over an alphabet of size $t$.


title:
Secure multiplex coding to attain the channel capacity in wiretap
  channels

abstract:
  It is known that a message can be transmitted safely against any wiretapper
via a noisy channel without a secret key if the coding rate is less than the
so-called secrecy capacity $C_S$, which is usually smaller than the channel
capacity $C$. In order to remove the loss $C - C_S$, we propose a multiplex
coding scheme with plural independent messages. In this paper, it is shown that
the proposed multiplex coding scheme can attain the channel capacity as the
total rate of the plural messages and the perfect secrecy for each message. The
coding theorem is proved by extending Hayashi's proof, in which the coding of
the channel resolvability is applied to wiretap channels.


title: Capacity of Complexity-Constrained Noise-Free CDMA

abstract:
  An interference-limited noise-free CDMA downlink channel operating under a
complexity constraint on the receiver is introduced. According to this
paradigm, detected bits, obtained by performing hard decisions directly on the
channel's matched filter output, must be the same as the transmitted binary
inputs. This channel setting, allowing the use of the simplest receiver scheme,
seems to be worthless, making reliable communication at any rate impossible. We
prove, by adopting statistical mechanics notion, that in the large-system limit
such a complexity-constrained CDMA channel gives rise to a non-trivial
Shannon-theoretic capacity, rigorously analyzed and corroborated using
finite-size channel simulations.


title:
On the Achievable Information Rates of CDMA Downlink with Trivial
  Receivers

abstract:
  A noisy CDMA downlink channel operating under a strict complexity constraint
on the receiver is introduced. According to this constraint, detected bits,
obtained by performing hard decisions directly on the channel's matched filter
output, must be the same as the transmitted binary inputs. This channel
setting, allowing the use of the simplest receiver scheme, seems to be
worthless, making reliable communication at any rate impossible. However,
recently this communication paradigm was shown to yield valuable information
rates in the case of a noiseless channel. This finding calls for the
investigation of this attractive complexity-constrained transmission scheme for
the more practical noisy channel case. By adopting the statistical mechanics
notion of metastable states of the renowned Hopfield model, it is proved that
under a bounded noise assumption such complexity-constrained CDMA channel gives
rise to a non-trivial Shannon-theoretic capacity, rigorously analyzed and
corroborated using finite-size channel simulations. For unbounded noise the
channel's outage capacity is addressed and specifically described for the
popular additive white Gaussian noise.


title: Effect of door delay on aircraft evacuation time

abstract:
  The recent commercial launch of twin-deck Very Large Transport Aircraft
(VLTA) such as the Airbus A380 has raised questions concerning the speed at
which they may be evacuated. The abnormal height of emergency exits on the
upper deck has led to speculation that emotional factors such as fear may lead
to door delay, and thus play a significant role in increasing overall
evacuation time. Full-scale evacuation tests are financially expensive and
potentially hazardous, and systematic studies of the evacuation of VLTA are
rare. Here we present a computationally cheap agent-based framework for the
general simulation of aircraft evacuation, and apply it to the particular case
of the Airbus A380. In particular, we investigate the effect of door delay, and
conclude that even a moderate average delay can lead to evacuation times that
exceed the maximum for safety certification. The model suggests practical ways
to minimise evacuation time, as well as providing a general framework for the
simulation of evacuation.


title:
Club Formation by Rational Sharing : Content, Viability and Community
  Structure

abstract:
  A sharing community prospers when participation and contribution are both
high. We suggest the two, while being related decisions every peer makes,
should be given separate rational bases. Considered as such, a basic issue is
the viability of club formation, which necessitates the modelling of two major
sources of heterogeneity, namely, peers and shared content. This viability
perspective clearly explains why rational peers contribute (or free-ride when
they don't) and how their collective action determines viability as well as the
size of the club formed. It also exposes another fundamental source of
limitation to club formation apart from free-riding, in the community structure
in terms of the relation between peers' interest (demand) and sharing (supply).


title: Underwater Hacker Missile Wars: A Cryptography and Engineering Contest

abstract:
  For a recent student conference, the authors developed a day-long design
problem and competition suitable for engineering, mathematics and science
undergraduates. The competition included a cryptography problem, for which a
workshop was run during the conference. This paper describes the competition,
focusing on the cryptography problem and the workshop. Notes from the workshop
and code for the computer programs are made available via the Internet. The
results of a personal self-evaluation (PSE) are described.


title: Grid Vertex-Unfolding Orthogonal Polyhedra

abstract:
  An edge-unfolding of a polyhedron is produced by cutting along edges and
flattening the faces to a *net*, a connected planar piece with no overlaps. A
*grid unfolding* allows additional cuts along grid edges induced by coordinate
planes passing through every vertex. A vertex-unfolding permits faces in the
net to be connected at single vertices, not necessarily along edges. We show
that any orthogonal polyhedron of genus zero has a grid vertex-unfolding.
(There are orthogonal polyhedra that cannot be vertex-unfolded, so some type of
"gridding" of the faces is necessary.) For any orthogonal polyhedron P with n
vertices, we describe an algorithm that vertex-unfolds P in O(n^2) time.
Enroute to explaining this algorithm, we present a simpler vertex-unfolding
algorithm that requires a 3 x 1 refinement of the vertex grid.


title: Learning Optimal Augmented Bayes Networks

abstract:
  Naive Bayes is a simple Bayesian classifier with strong independence
assumptions among the attributes. This classifier, desipte its strong
independence assumptions, often performs well in practice. It is believed that
relaxing the independence assumptions of a naive Bayes classifier may improve
the classification accuracy of the resulting structure. While finding an
optimal unconstrained Bayesian Network (for most any reasonable scoring
measure) is an NP-hard problem, it is possible to learn in polynomial time
optimal networks obeying various structural restrictions. Several authors have
examined the possibilities of adding augmenting arcs between attributes of a
Naive Bayes classifier. Friedman, Geiger and Goldszmidt define the TAN
structure in which the augmenting arcs form a tree on the attributes, and
present a polynomial time algorithm that learns an optimal TAN with respect to
MDL score. Keogh and Pazzani define Augmented Bayes Networks in which the
augmenting arcs form a forest on the attributes (a collection of trees, hence a
relaxation of the stuctural restriction of TAN), and present heuristic search
methods for learning good, though not optimal, augmenting arc sets. The
authors, however, evaluate the learned structure only in terms of observed
misclassification error and not against a scoring metric, such as MDL. In this
paper, we present a simple, polynomial time greedy algorithm for learning an
optimal Augmented Bayes Network with respect to MDL score.


title: Pairing-based identification schemes

abstract:
  We propose four different identification schemes that make use of bilinear
pairings, and prove their security under certain computational assumptions.
Each of the schemes is more efficient and/or more secure than any known
pairing-based identification scheme.


title: Language embeddings that preserve staging and safety

abstract:
  We study embeddings of programming languages into one another that preserve
what reductions take place at compile-time, i.e., staging. A certain condition
-- what we call a `Turing complete kernel' -- is sufficient for a language to
be stage-universal in the sense that any language may be embedded in it while
preserving staging. A similar line of reasoning yields the notion of
safety-preserving embeddings, and a useful characterization of
safety-universality. Languages universal with respect to staging and safety are
good candidates for realizing domain-specific embedded languages (DSELs) and
`active libraries' that provide domain-specific optimizations and safety
checks.


title: Interactive Unawareness Revisited

abstract:
  We analyze a model of interactive unawareness introduced by Heifetz, Meier
and Schipper (HMS). We consider two axiomatizations for their model, which
capture different notions of validity. These axiomatizations allow us to
compare the HMS approach to both the standard (S5) epistemic logic and two
other approaches to unawareness: that of Fagin and Halpern and that of Modica
and Rustichini. We show that the differences between the HMS approach and the
others are mainly due to the notion of validity used and the fact that the HMS
is based on a 3-valued propositional logic.


title: On an authentication scheme based on the Root Problem in the braid group

abstract:
  Lal and Chaturvedi proposed two authentication schemes based on the
difficulty of the Root Problem in the braid group. We point out that the first
scheme is not really as secure as the Root Problem, and describe an efficient
way to crack it. The attack works for any group.


title: Cluster Computing and the Power of Edge Recognition

abstract:
  We study the robustness--the invariance under definition changes--of the
cluster class CL#P [HHKW05]. This class contains each #P function that is
computed by a balanced Turing machine whose accepting paths always form a
cluster with respect to some length-respecting total order with efficient
adjacency checks. The definition of CL#P is heavily influenced by the defining
paper's focus on (global) orders. In contrast, we define a cluster class,
CLU#P, to capture what seems to us a more natural model of cluster computing.
We prove that the naturalness is costless: CL#P = CLU#P. Then we exploit the
more natural, flexible features of CLU#P to prove new robustness results for
CL#P and to expand what is known about the closure properties of CL#P.
  The complexity of recognizing edges--of an ordered collection of computation
paths or of a cluster of accepting computation paths--is central to this study.
Most particularly, our proofs exploit the power of unique discovery of
edges--the ability of nondeterministic functions to, in certain settings,
discover on exactly one (in some cases, on at most one) computation path a
critical piece of information regarding edges of orderings or clusters.


title:
Guarantees for the Success Frequency of an Algorithm for Finding
  Dodgson-Election Winners

abstract:
  In the year 1876 the mathematician Charles Dodgson, who wrote fiction under
the now more famous name of Lewis Carroll, devised a beautiful voting system
that has long fascinated political scientists. However, determining the winner
of a Dodgson election is known to be complete for the \Theta_2^p level of the
polynomial hierarchy. This implies that unless P=NP no polynomial-time solution
to this problem exists, and unless the polynomial hierarchy collapses to NP the
problem is not even in NP. Nonetheless, we prove that when the number of voters
is much greater than the number of candidates--although the number of voters
may still be polynomial in the number of candidates--a simple greedy algorithm
very frequently finds the Dodgson winners in such a way that it ``knows'' that
it has found them, and furthermore the algorithm never incorrectly declares a
nonwinner to be a winner.


title:
Capacity-Achieving Codes with Bounded Graphical Complexity on Noisy
  Channels

abstract:
  We introduce a new family of concatenated codes with an outer low-density
parity-check (LDPC) code and an inner low-density generator matrix (LDGM) code,
and prove that these codes can achieve capacity under any memoryless
binary-input output-symmetric (MBIOS) channel using maximum-likelihood (ML)
decoding with bounded graphical complexity, i.e., the number of edges per
information bit in their graphical representation is bounded. In particular, we
also show that these codes can achieve capacity on the binary erasure channel
(BEC) under belief propagation (BP) decoding with bounded decoding complexity
per information bit per iteration for all erasure probabilities in (0, 1). By
deriving and analyzing the average weight distribution (AWD) and the
corresponding asymptotic growth rate of these codes with a rate-1 inner LDGM
code, we also show that these codes achieve the Gilbert-Varshamov bound with
asymptotically high probability. This result can be attributed to the presence
of the inner rate-1 LDGM code, which is demonstrated to help eliminate high
weight codewords in the LDPC code while maintaining a vanishingly small amount
of low weight codewords.


title: Order Independence and Rationalizability

abstract:
  Two natural strategy elimination procedures have been studied for strategic
games. The first one involves the notion of (strict, weak, etc) dominance and
the second the notion of rationalizability. In the case of dominance the
criterion of order independence allowed us to clarify which notions and under
what circumstances are robust. In the case of rationalizability this criterion
has not been considered. In this paper we investigate the problem of order
independence for rationalizability by focusing on three naturally entailed
reduction relations on games. These reduction relations are distinguished by
the adopted reference point for the notion of a better response. Additionally,
they are parametrized by the adopted system of beliefs. We show that for one
reduction relation the outcome of its (possibly transfinite) iterations does
not depend on the order of elimination of the strategies. This result does not
hold for the other two reduction relations. However, under a natural assumption
the iterations of all three reduction relations yield the same outcome. The
obtained order independence results apply to the frameworks considered in
Bernheim 84 and Pearce 84. For finite games the iterations of all three
reduction relations coincide and the order independence holds for three natural
systems of beliefs considered in the literature.


title: On joint coding for watermarking and encryption

abstract:
  In continuation to earlier works where the problem of joint information
embedding and lossless compression (of the composite signal) was studied in the
absence \cite{MM03} and in the presence \cite{MM04} of attacks, here we
consider the additional ingredient of protecting the secrecy of the watermark
against an unauthorized party, which has no access to a secret key shared by
the legitimate parties. In other words, we study the problem of joint coding
for three objectives: information embedding, compression, and encryption.Our
main result is a coding theorem that provides a single--letter characterization
of the best achievable tradeoffs among the following parameters: the distortion
between the composite signal and the covertext, the distortion in
reconstructing the watermark by the legitimate receiver, the compressibility of
the composite signal (with and without the key), and the equivocation of the
watermark, as well as its reconstructed version, given the composite signal. In
the attack--free case, if the key is independent of the covertext, this coding
theorem gives rise to a {\it threefold} separation principle that tells that
asymptotically, for long block codes, no optimality is lost by first applying a
rate--distortion code to the watermark source, then encrypting the compressed
codeword, and finally, embedding it into the covertext using the embedding
scheme of \cite{MM03}. In the more general case, however, this separation
principle is no longer valid, as the key plays an additional role of side
information used by the embedding unit.


title: On Deciding Deep Holes of Reed-Solomon Codes

abstract:
  For generalized Reed-Solomon codes, it has been proved \cite{GuruswamiVa05}
that the problem of determining if a received word is a deep hole is
co-NP-complete. The reduction relies on the fact that the evaluation set of the
code can be exponential in the length of the code -- a property that practical
codes do not usually possess. In this paper, we first presented a much simpler
proof of the same result. We then consider the problem for standard
Reed-Solomon codes, i.e. the evaluation set consists of all the nonzero
elements in the field. We reduce the problem of identifying deep holes to
deciding whether an absolutely irreducible hypersurface over a finite field
contains a rational point whose coordinates are pairwise distinct and nonzero.
By applying Schmidt and Cafure-Matera estimation of rational points on
algebraic varieties, we prove that the received vector $(f(\alpha))_{\alpha \in
\F_q}$ for Reed-Solomon $[q,k]_q$, $k < q^{1/7 - \epsilon}$, cannot be a deep
hole, whenever $f(x)$ is a polynomial of degree $k+d$ for $1\leq d < q^{3/13
-\epsilon}$.


title: A Model-driven Approach for Grid Services Engineering

abstract:
  As a consequence to the hype of Grid computing, such systems have seldom been
designed using formal techniques. The complexity and rapidly growing demand
around Grid technologies has favour the use of classical development
techniques, resulting in no guidelines or rules and unstructured engineering
processes. This paper advocates a formal approach to Grid applications
development in an effort to contribute to the rigorous development of Grids
software architectures. This approach addresses cross-platform interoperability
and quality of service; the model-driven paradigm is applied to a formal
architecture-centric engineering method in order to benefit from the formal
semantic description power in addition to model-based transformations. The
result of such a novel combined concept promotes the re-use of design models
and eases developments in Grid computing by providing an adapted development
process and ensuring correctness at each design step.


title:
Decomposing Solution Sets of Polynomial Systems: A New Parallel
  Monodromy Breakup Algorithm

abstract:
  We consider the numerical irreducible decomposition of a positive dimensional
solution set of a polynomial system into irreducible factors. Path tracking
techniques computing loops around singularities connect points on the same
irreducible components. The computation of a linear trace for each factor
certifies the decomposition. This factorization method exhibits a good
practical performance on solution sets of relative high degrees.
  Using the same concepts of monodromy and linear trace, we present a new
monodromy breakup algorithm. It shows a better performance than the old method
which requires construction of permutations of witness points in order to break
up the solution set. In contrast, the new algorithm assumes a finer approach
allowing us to avoid tracking unnecessary homotopy paths.
  As we designed the serial algorithm keeping in mind distributed computing, an
additional advantage is that its parallel version can be easily built.
Synchronization issues resulted in a performance loss of the straightforward
parallel version of the old algorithm. Our parallel implementation of the new
approach bypasses these issues, therefore, exhibiting a better performance,
especially on solution sets of larger degree.


title: Channel Uncertainty in Ultra Wideband Communication Systems

abstract:
  Wide band systems operating over multipath channels may spread their power
over bandwidth if they use duty cycle. Channel uncertainty limits the
achievable data rates of power constrained wide band systems; Duty cycle
transmission reduces the channel uncertainty because the receiver has to
estimate the channel only when transmission takes place. The optimal choice of
the fraction of time used for transmission depends on the spectral efficiency
of the signal modulation. The general principle is demonstrated by comparing
the channel conditions that allow different modulations to achieve the capacity
in the limit. Direct sequence spread spectrum and pulse position modulation
systems with duty cycle achieve the channel capacity, if the increase of the
number of channel paths with the bandwidth is not too rapid. The higher
spectral efficiency of the spread spectrum modulation lets it achieve the
channel capacity in the limit, in environments where pulse position modulation
with non-vanishing symbol time cannot be used because of the large number of
channel paths.


title: Fast and Compact Regular Expression Matching

abstract:
  We study 4 problems in string matching, namely, regular expression matching,
approximate regular expression matching, string edit distance, and subsequence
indexing, on a standard word RAM model of computation that allows
logarithmic-sized words to be manipulated in constant time. We show how to
improve the space and/or remove a dependency on the alphabet size for each
problem using either an improved tabulation technique of an existing algorithm
or by combining known algorithms in a new way.


title:
A Maple Package for Computing Groebner Bases for Linear Recurrence
  Relations

abstract:
  A Maple package for computing Groebner bases of linear difference ideals is
described. The underlying algorithm is based on Janet and Janet-like monomial
divisions associated with finite difference operators. The package can be used,
for example, for automatic generation of difference schemes for linear partial
differential equations and for reduction of multiloop Feynman integrals. These
two possible applications are illustrated by simple examples of the Laplace
equation and a one-loop scalar integral of propagator type


title: CP-nets and Nash equilibria

abstract:
  We relate here two formalisms that are used for different purposes in
reasoning about multi-agent systems. One of them are strategic games that are
used to capture the idea that agents interact with each other while pursuing
their own interest. The other are CP-nets that were introduced to express
qualitative and conditional preferences of the users and which aim at
facilitating the process of preference elicitation. To relate these two
formalisms we introduce a natural, qualitative, extension of the notion of a
strategic game. We show then that the optimal outcomes of a CP-net are exactly
the Nash equilibria of an appropriately defined strategic game in the above
sense. This allows us to use the techniques of game theory to search for
optimal outcomes of CP-nets and vice-versa, to use techniques developed for
CP-nets to search for Nash equilibria of the considered games.


title: Folksonomy as a Complex Network

abstract:
  Folksonomy is an emerging technology that works to classify the information
over WWW through tagging the bookmarks, photos or other web-based contents. It
is understood to be organized by every user while not limited to the authors of
the contents and the professional editors. This study surveyed the folksonomy
as a complex network. The result indicates that the network, which is composed
of the tags from the folksonomy, displays both properties of small world and
scale-free. However, the statistics only shows a local and static slice of the
vast body of folksonomy which is still evolving.


title: Distance-Increasing Maps of All Length by Simple Mapping Algorithms

abstract:
  Distance-increasing maps from binary vectors to permutations, namely DIMs,
are useful for the construction of permutation arrays. While a simple mapping
algorithm defining DIMs of even length is known, existing DIMs of odd length
are either recursively constructed by merging shorter DIMs or defined by much
complicated mapping algorithms. In this paper, DIMs of all length defined by
simple mapping algorithms are presented.


title: Planar Earthmover is not in $L_1$

abstract:
  We show that any $L_1$ embedding of the transportation cost (a.k.a.
Earthmover) metric on probability measures supported on the grid
$\{0,1,...,n\}^2\subseteq \R^2$ incurs distortion $\Omega(\sqrt{\log n})$. We
also use Fourier analytic techniques to construct a simple $L_1$ embedding of
this space which has distortion $O(\log n)$.


title: On the Capacity of Doubly Correlated MIMO Channels

abstract:
  In this paper, we analyze the capacity of multiple-input multiple-output
(MIMO) Rayleigh-fading channels in the presence of spatial fading correlation
at both the transmitter and the receiver, assuming that the channel is unknown
at the transmitter and perfectly known at the receiver. We first derive the
determinant representation for the exact characteristic function of the
capacity, which is then used to determine the trace representations for the
mean, variance, skewness, kurtosis, and other higher-order statistics (HOS).
These results allow us to exactly evaluate two relevant information-theoretic
capacity measures--ergodic capacity and outage capacity--and the HOS of the
capacity for such a MIMO channel. The analytical framework presented in the
paper is valid for arbitrary numbers of antennas and generalizes the previously
known results for independent and identically distributed or one-sided
correlated MIMO channels to the case when fading correlation exists on both
sides. We verify our analytical results by comparing them with Monte Carlo
simulations for a correlation model based on realistic channel measurements as
well as a classical exponential correlation model.


title: On Vulnerabilities, Constraints and Assumptions

abstract:
  This report presents a taxonomy of vulnerabilities created as a part of an
effort to develop a framework for deriving verification and validation
strategies to assess software security. This taxonomy is grounded in a
theoretical model of computing, which establishes the relationship between
vulnerabilities, software applications and the computer system resources. This
relationship illustrates that a software application is exploited by violating
constraints imposed by computer system resources and assumptions made about
their usage. In other words, a vulnerability exists in the software application
if it allows violation of these constraints and assumptions. The taxonomy
classifies these constraints and assumptions. The model also serves as a basis
for the classification scheme the taxonomy uses, in which the computer system
resources such as, memory, input/output, and cryptographic resources serve as
categories and subcategories. Vulnerabilities, which are expressed in the form
of constraints and assumptions, are classified according to these categories
and subcategories. This taxonomy is both novel and distinctively different from
other taxonomies found in the literature.


title:
Capacity Limits of Cognitive Radio with Distributed and Dynamic Spectral
  Activity

abstract:
  We investigate the capacity of opportunistic communication in the presence of
dynamic and distributed spectral activity, i.e. when the time varying spectral
holes sensed by the cognitive transmitter are correlated but not identical to
those sensed by the cognitive receiver. Using the information theoretic
framework of communication with causal and non-causal side information at the
transmitter and/or the receiver, we obtain analytical capacity expressions and
the corresponding numerical results. We find that cognitive radio communication
is robust to dynamic spectral environments even when the communication occurs
in bursts of only 3-5 symbols. The value of handshake overhead is investigated
for both lightly loaded and heavily loaded systems. We find that the capacity
benefits of overhead information flow from the transmitter to the receiver is
negligible while feedback information overhead in the opposite direction
significantly improves capacity.


title: On the Feedback Capacity of Stationary Gaussian Channels

abstract:
  The capacity of stationary additive Gaussian noise channels with feedback is
characterized as the solution to a variational problem. Toward this end, it is
proved that the optimal feedback coding scheme is stationary. When specialized
to the first-order autoregressive moving-average noise spectrum, this
variational characterization yields a closed-form expression for the feedback
capacity. In particular, this result shows that the celebrated
Schalkwijk--Kailath coding scheme achieves the feedback capacity for the
first-order autoregressive moving-average Gaussian channel, resolving a
long-standing open problem studied by Butman, Schalkwijk--Tiernan, Wolfowitz,
Ozarow, Ordentlich, Yang--Kavcic--Tatikonda, and others.


title: The WSSUS Pulse Design Problem in Multicarrier Transmission

abstract:
  Optimal link adaption to the scattering function of wide sense stationary
uncorrelated mobile communication channels is still an unsolved problem despite
its importance for next-generation system design. In multicarrier transmission
such link adaption is performed by pulse shaping, i.e. by properly adjusting
the transmit and receive filters. For example pulse shaped Offset--QAM systems
have been recently shown to have superior performance over standard cyclic
prefix OFDM (while operating at higher spectral efficiency).In this paper we
establish a general mathematical framework for joint transmitter and receiver
pulse shape optimization for so-called Weyl--Heisenberg or Gabor signaling with
respect to the scattering function of the WSSUS channel. In our framework the
pulse shape optimization problem is translated to an optimization problem over
trace class operators which in turn is related to fidelity optimization in
quantum information processing. By convexity relaxation the problem is shown to
be equivalent to a \emph{convex constraint quasi-convex maximization problem}
thereby revealing the non-convex nature of the overall WSSUS pulse design
problem. We present several iterative algorithms for optimization providing
applicable results even for large--scale problem constellations. We show that
with transmitter-side knowledge of the channel statistics a gain of $3 - 6$dB
in $\SINR$ can be expected.


title:
Capacity and Character Expansions: Moment generating function and other
  exact results for MIMO correlated channels

abstract:
  We apply a promising new method from the field of representations of Lie
groups to calculate integrals over unitary groups, which are important for
multi-antenna communications. To demonstrate the power and simplicity of this
technique, we first re-derive a number of results that have been used recently
in the community of wireless information theory, using only a few simple steps.
In particular, we derive the joint probability distribution of eigenvalues of
the matrix GG*, with G a semicorrelated Gaussian random matrix or a Gaussian
random matrix with a non-zero mean (and G* its hermitian conjugate) . These
joint probability distribution functions can then be used to calculate the
moment generating function of the mutual information for Gaussian channels with
multiple antennas on both ends with this probability distribution of their
channel matrices G. We then turn to the previously unsolved problem of
calculating the moment generating function of the mutual information of MIMO
(multiple input-multiple output) channels, which are correlated at both the
receiver and the transmitter. From this moment generating function we obtain
the ergodic average of the mutual information and study the outage probability.
These methods can be applied to a number of other problems. As a particular
example, we examine unitary encoded space-time transmission of MIMO systems and
we derive the received signal distribution when the channel matrix is
correlated at the transmitter end.

categories: cs.IT cond-mat.mes-hall cond-mat.stat-mech hep-lat math-ph math.IT math.MP


title: Automatic Face Recognition System Based on Local Fourier-Bessel Features

abstract:
  We present an automatic face verification system inspired by known properties
of biological systems. In the proposed algorithm the whole image is converted
from the spatial to polar frequency domain by a Fourier-Bessel Transform (FBT).
Using the whole image is compared to the case where only face image regions
(local analysis) are considered. The resulting representations are embedded in
a dissimilarity space, where each image is represented by its distance to all
the other images, and a Pseudo-Fisher discriminator is built. Verification test
results on the FERET database showed that the local-based algorithm outperforms
the global-FBT version. The local-FBT algorithm performed as state-of-the-art
methods under different testing conditions, indicating that the proposed system
is highly robust for expression, age, and illumination variations. We also
evaluated the performance of the proposed system under strong occlusion
conditions and found that it is highly robust for up to 50% of face occlusion.
Finally, we automated completely the verification system by implementing face
and eye detection algorithms. Under this condition, the local approach was only
slightly superior to the global approach.


title: Face Recognition Based on Polar Frequency Features

abstract:
  A novel biologically motivated face recognition algorithm based on polar
frequency is presented. Polar frequency descriptors are extracted from face
images by Fourier-Bessel transform (FBT). Next, the Euclidean distance between
all images is computed and each image is now represented by its dissimilarity
to the other images. A Pseudo-Fisher Linear Discriminant was built on this
dissimilarity space. The performance of Discrete Fourier transform (DFT)
descriptors, and a combination of both feature types was also evaluated. The
algorithms were tested on a 40- and 1196-subjects face database (ORL and FERET,
respectively). With 5 images per subject in the training and test datasets,
error rate on the ORL database was 3.8, 1.25 and 0.2% for the FBT, DFT, and the
combined classifier, respectively, as compared to 2.6% achieved by the best
previous algorithm. The most informative polar frequency features were
concentrated at low-to-medium angular frequencies coupled to low radial
frequencies. On the FERET database, where an affine normalization
pre-processing was applied, the FBT algorithm outperformed only the PCA in a
rank recognition test. However, it achieved performance comparable to
state-of-the-art methods when evaluated by verification tests. These results
indicate the high informative value of the polar frequency content of face
images in relation to recognition and verification tasks, and that the
Cartesian frequency content can complement information about the subjects'
identity, but possibly only when the images are not pre-normalized. Possible
implications for human face recognition are discussed.


title:
Face Verification in Polar Frequency Domain: a Biologically Motivated
  Approach

abstract:
  We present a novel local-based face verification system whose components are
analogous to those of biological systems. In the proposed system, after global
registration and normalization, three eye regions are converted from the
spatial to polar frequency domain by a Fourier-Bessel Transform. The resulting
representations are embedded in a dissimilarity space, where each image is
represented by its distance to all the other images. In this dissimilarity
space a Pseudo-Fisher discriminator is built. ROC and equal error rate
verification test results on the FERET database showed that the system
performed at least as state-of-the-art methods and better than a system based
on polar Fourier features. The local-based system is especially robust to
facial expression and age variations, but sensitive to registration errors.


title: Representing Digital Assets for Long-Term Preservation using MPEG-21 DID

abstract:
  Various efforts aimed at representing digital assets have emerged from
several communities over the last years, including the Metadata Encoding and
Transmission Standard (METS), the IMS Content Packaging (IMS-CP) XML Binding
and the XML Formatted Data Units (XFDU). The MPEG-21 Digital Item Declaration
(MPEG-21 DID) is another approach that can be used for the representation of
digital assets in XML. This paper will explore the potential of the MPEG-21 DID
in a Digital Preservation context, by looking at the core building blocks of
the OAIS Information Model and the way in which they map to the MPEG-21 DID
abstract model and the MPEG-21 DIDL XML syntax.


title:
An Improved Lower Bound to the Number of Neighbors Required for the
  Asymptotic Connectivity of Ad Hoc Networks

abstract:
  Xue and Kumar have established that the number of neighbors required for
connectivity of wireless networks with N uniformly distributed nodes must grow
as log(N), and they also established that the actual number required lies
between 0.074log(N) and 5.1774log(N). In this short paper, by recognizing that
connectivity results for networks where the nodes are distributed according to
a Poisson point process can often be applied to the problem for a network with
N nodes, we are able to improve the lower bound. In particular, we show that a
network with nodes distributed in a unit square according to a 2D Poisson point
process of parameter N will be asymptotically disconnected with probability one
if the number of neighbors is less than 0.129log(N). Moreover, similar number
of neighbors is not enough for an asymptotically connected network with N nodes
uniformly in a unit square, hence improving the lower bound.


title:
Statistical Mechanical Approach to Lossy Data Compression:Theory and
  Practice

abstract:
  The encoder and decoder for lossy data compression of binary memoryless
sources are developed on the basis of a specific-type nonmonotonic perceptron.
Statistical mechanical analysis indicates that the potential ability of the
perceptron-based code saturates the theoretically achievable limit in most
cases although exactly performing the compression is computationally difficult.
To resolve this difficulty, we provide a computationally tractable
approximation algorithm using belief propagation (BP), which is a current
standard algorithm of probabilistic inference. Introducing several
approximations and heuristics, the BP-based algorithm exhibits performance that
is close to the achievable limit in a practical time scale in optimal cases.


title:
On Time-Variant Distortions in Multicarrier Transmission with
  Application to Frequency Offsets and Phase Noise

abstract:
  Phase noise and frequency offsets are due to their time-variant behavior one
of the most limiting disturbances in practical OFDM designs and therefore
intensively studied by many authors. In this paper we present a generalized
framework for the prediction of uncoded system performance in the presence of
time-variant distortions including the transmitter and receiver pulse shapes as
well as the channel. Therefore, unlike existing studies, our approach can be
employed for more general multicarrier schemes. To show the usefulness of our
approach, we apply the results to OFDM in the context of frequency offset and
Wiener phase noise, yielding improved bounds on the uncoded performance. In
particular, we obtain exact formulas for the averaged performance in AWGN and
time-invariant multipath channels.


title:
Business intelligence systems and user's parameters: an application to a
  documents' database

abstract:
  This article presents earlier results of our research works in the area of
modeling Business Intelligence Systems. The basic idea of this research area is
presented first. We then show the necessity of including certain users'
parameters in Information systems that are used in Business Intelligence
systems in order to integrate a better response from such systems. We
identified two main types of attributes that can be missing from a base and we
showed why they needed to be included. A user model that is based on a
cognitive user evolution is presented. This model when used together with a
good definition of the information needs of the user (decision maker) will
accelerate his decision making process.


title:
Semantics of UML 2.0 Activity Diagram for Business Modeling by Means of
  Virtual Machine

abstract:
  The paper proposes a more formalized definition of UML 2.0 Activity Diagram
semantics. A subset of activity diagram constructs relevant for business
process modeling is considered. The semantics definition is based on the
original token flow methodology, but a more constructive approach is used. The
Activity Diagram Virtual machine is defined by means of a metamodel, with
operations defined by a mix of pseudocode and OCL pre- and postconditions. A
formal procedure is described which builds the virtual machine for any activity
diagram. The relatively complicated original token movement rules in control
nodes and edges are combined into paths from an action to action. A new
approach is the use of different (push and pull) engines, which move tokens
along the paths. Pull engines are used for paths containing join nodes, where
the movement of several tokens must be coordinated. The proposed virtual
machine approach makes the activity semantics definition more transparent where
the token movement can be easily traced. However, the main benefit of the
approach is the possibility to use the defined virtual machine as a basis for
UML activity diagram based workflow or simulation engine.


title:
Access Interfaces for Open Archival Information Systems based on the
  OAI-PMH and the OpenURL Framework for Context-Sensitive Services

abstract:
  In recent years, a variety of digital repository and archival systems have
been developed and adopted. All of these systems aim at hosting a variety of
compound digital assets and at providing tools for storing, managing and
accessing those assets. This paper will focus on the definition of common and
standardized access interfaces that could be deployed across such diverse
digital respository and archival systems. The proposed interfaces are based on
the two formal specifications that have recently emerged from the Digital
Library community: The Open Archive Initiative Protocol for Metadata Harvesting
(OAI-PMH) and the NISO OpenURL Framework for Context-Sensitive Services
(OpenURL Standard). As will be described, the former allows for the retrieval
of batches of XML-based representations of digital assets, while the latter
facilitates the retrieval of disseminations of a specific digital asset or of
one or more of its constituents. The core properties of the proposed interfaces
are explained in terms of the Reference Model for an Open Archival Information
System (OAIS).


title: Minimum Cost Homomorphisms to Semicomplete Multipartite Digraphs

abstract:
  For digraphs $D$ and $H$, a mapping $f: V(D)\dom V(H)$ is a {\em homomorphism
of $D$ to $H$} if $uv\in A(D)$ implies $f(u)f(v)\in A(H).$ For a fixed directed
or undirected graph $H$ and an input graph $D$, the problem of verifying
whether there exists a homomorphism of $D$ to $H$ has been studied in a large
number of papers. We study an optimization version of this decision problem.
Our optimization problem is motivated by a real-world problem in defence
logistics and was introduced very recently by the authors and M. Tso.
  Suppose we are given a pair of digraphs $D,H$ and a positive integral cost
$c_i(u)$ for each $u\in V(D)$ and $i\in V(H)$. The cost of a homomorphism $f$
of $D$ to $H$ is $\sum_{u\in V(D)}c_{f(u)}(u)$. Let $H$ be a fixed digraph. The
minimum cost homomorphism problem for $H$, MinHOMP($H$), is stated as follows:
For input digraph $D$ and costs $c_i(u)$ for each $u\in V(D)$ and $i\in V(H)$,
verify whether there is a homomorphism of $D$ to $H$ and, if it does exist,
find such a homomorphism of minimum cost. In our previous paper we obtained a
dichotomy classification of the time complexity of \MiP for $H$ being a
semicomplete digraph. In this paper we extend the classification to
semicomplete $k$-partite digraphs, $k\ge 3$, and obtain such a classification
for bipartite tournaments.


title: Automatic extraction of paraphrastic phrases from medium size corpora

abstract:
  This paper presents a versatile system intended to acquire paraphrastic
phrases from a representative corpus. In order to decrease the time spent on
the elaboration of resources for NLP system (for example Information
Extraction, IE hereafter), we suggest to use a machine learning system that
helps defining new templates and associated resources. This knowledge is
automatically derived from the text collection, in interaction with a large
semantic network.


title: On the Outage Capacity of Correlated Multiple-Path MIMO Channels

abstract:
  The use of multi-antenna arrays in both transmission and reception has been
shown to dramatically increase the throughput of wireless communication
systems. As a result there has been considerable interest in characterizing the
ergodic average of the mutual information for realistic correlated channels.
Here, an approach is presented that provides analytic expressions not only for
the average, but also the higher cumulant moments of the distribution of the
mutual information for zero-mean Gaussian (multiple-input multiple-output) MIMO
channels with the most general multipath covariance matrices when the channel
is known at the receiver. These channels include multi-tap delay paths, as well
as general channels with covariance matrices that cannot be written as a
Kronecker product, such as dual-polarized antenna arrays with general
correlations at both transmitter and receiver ends. The mathematical methods
are formally valid for large antenna numbers, in which limit it is shown that
all higher cumulant moments of the distribution, other than the first two scale
to zero. Thus, it is confirmed that the distribution of the mutual information
tends to a Gaussian, which enables one to calculate the outage capacity. These
results are quite accurate even in the case of a few antennas, which makes this
approach applicable to realistic situations.


title:
Telling Great Stories: An NSDL Content and Communications System for
  Aggregation, Display, and Distribution of News and Features

abstract:
  Education digital libraries contain cataloged resources as well as contextual
information about innovations in the use of educational technology, exemplar
stories about community activities, and news from various user communities that
include teachers, students, scholars, and developers. Long-standing library
traditions of service, preservation, democratization of knowledge, rich
discourse, equal access, and fair use are evident in library communications
models that both pull in and push out contextual information from multiple
sources integrated with editorial production processes. This paper argues that
a dynamic narrative flow [1] is enabled by effective management of complex
content and communications in a decentralized web-based education digital
library making publishing objects such as aggregations of resources, or
selected parts of objects [4] accessible through a Content and Communications
System. Providing services that encourage patrons to reuse, reflect out, and
contribute resources back [5] to the Library increases the reach and impact of
the National Science Digital Library (NSDL). This system is a model for
distributed content development and effective communications for education
digital libraries in general.


title:
Leveraging Social-Network Infrastructure to Improve Peer-to-Peer Overlay
  Performance: Results from Orkut

abstract:
  Application-level peer-to-peer (P2P) network overlays are an emerging
paradigm that facilitates decentralization and flexibility in the scalable
deployment of applications such as group communication, content delivery, and
data sharing. However the construction of the overlay graph topology optimized
for low latency, low link and node stress and lookup performance is still an
open problem. We present a design of an overlay constructed on top of a social
network and show that it gives a sizable improvement in lookups, average
round-trip delay and scalability as opposed to other overlay topologies. We
build our overlay on top of the topology of a popular real-world social network
namely Orkut. We show Orkuts suitability for our purposes by evaluating the
clustering behavior of its graph structure and the socializing pattern of its
members.


title:
Performance Analysis and Enhancement of Multiband OFDM for UWB
  Communications

abstract:
  In this paper, we analyze the frequency-hopping orthogonal frequency-division
multiplexing (OFDM) system known as Multiband OFDM for high-rate wireless
personal area networks (WPANs) based on ultra-wideband (UWB) transmission.
Besides considering the standard, we also propose and study system performance
enhancements through the application of Turbo and Repeat-Accumulate (RA) codes,
as well as OFDM bit-loading. Our methodology consists of (a) a study of the
channel model developed under IEEE 802.15 for UWB from a frequency-domain
perspective suited for OFDM transmission, (b) development and quantification of
appropriate information-theoretic performance measures, (c) comparison of these
measures with simulation results for the Multiband OFDM standard proposal as
well as our proposed extensions, and (d) the consideration of the influence of
practical, imperfect channel estimation on the performance. We find that the
current Multiband OFDM standard sufficiently exploits the frequency selectivity
of the UWB channel, and that the system performs in the vicinity of the channel
cutoff rate. Turbo codes and a reduced-complexity clustered bit-loading
algorithm improve the system power efficiency by over 6 dB at a data rate of
480 Mbps.


title: Iterative Algebraic Soft-Decision List Decoding of Reed-Solomon Codes

abstract:
  In this paper, we present an iterative soft-decision decoding algorithm for
Reed-Solomon codes offering both complexity and performance advantages over
previously known decoding algorithms. Our algorithm is a list decoding
algorithm which combines two powerful soft decision decoding techniques which
were previously regarded in the literature as competitive, namely, the
Koetter-Vardy algebraic soft-decision decoding algorithm and belief-propagation
based on adaptive parity check matrices, recently proposed by Jiang and
Narayanan. Building on the Jiang-Narayanan algorithm, we present a
belief-propagation based algorithm with a significant reduction in
computational complexity. We introduce the concept of using a
belief-propagation based decoder to enhance the soft-input information prior to
decoding with an algebraic soft-decision decoder. Our algorithm can also be
viewed as an interpolation multiplicity assignment scheme for algebraic
soft-decision decoding of Reed-Solomon codes.


title: Applications of correlation inequalities to low density graphical codes

abstract:
  This contribution is based on the contents of a talk delivered at the
Next-SigmaPhi conference held in Crete in August 2005. It is adressed to an
audience of physicists with diverse horizons and does not assume any background
in communications theory. Capacity approaching error correcting codes for
channel communication known as Low Density Parity Check (LDPC) codes have
attracted considerable attention from coding theorists in the last decade.
Surprisingly strong connections with the theory of diluted spin glasses have
been discovered. In this work we elucidate one new connection, namely that a
class of correlation inequalities valid for gaussian spin glasses can be
applied to the theoretical analysis of LDPC codes. This allows for a rigorous
comparison between the so called (optimal) maximum a posteriori and the
computationaly efficient belief propagation decoders. The main ideas of the
proofs are explained and we refer to recent works for the more lengthy
technical details.


title: State-Based Control of Fuzzy Discrete Event Systems

abstract:
  To effectively represent possibility arising from states and dynamics of a
system, fuzzy discrete event systems as a generalization of conventional
discrete event systems have been introduced recently. Supervisory control
theory based on event feedback has been well established for such systems.
Noting that the system state description, from the viewpoint of specification,
seems more convenient, we investigate the state-based control of fuzzy discrete
event systems in this paper. We first present an approach to finding all fuzzy
states that are reachable by controlling the system. After introducing the
notion of controllability for fuzzy states, we then provide a necessary and
sufficient condition for a set of fuzzy states to be controllable. We also find
that event-based control and state-based control are not equivalent and further
discuss the relationship between them. Finally, we examine the possibility of
driving a fuzzy discrete event system under control from a given initial state
to a prescribed set of fuzzy states and then keeping it there indefinitely.


title: Distance-2 Edge Coloring is NP-Complete

abstract:
  We prove that it is NP-complete to determine whether there exists a
distance-2 edge coloring (strong edge coloring) with 5 colors of a bipartite
2-inductive graph with girth 6 and maximum degree 3.


title:
Retinal Vessel Segmentation Using the 2-D Morlet Wavelet and Supervised
  Classification

abstract:
  We present a method for automated segmentation of the vasculature in retinal
images. The method produces segmentations by classifying each image pixel as
vessel or non-vessel, based on the pixel's feature vector. Feature vectors are
composed of the pixel's intensity and continuous two-dimensional Morlet wavelet
transform responses taken at multiple scales. The Morlet wavelet is capable of
tuning to specific frequencies, thus allowing noise filtering and vessel
enhancement in a single step. We use a Bayesian classifier with
class-conditional probability density functions (likelihoods) described as
Gaussian mixtures, yielding a fast classification, while being able to model
complex decision surfaces and compare its performance with the linear minimum
squared error classifier. The probability distributions are estimated based on
a training set of labeled pixels obtained from manual segmentations. The
method's performance is evaluated on publicly available DRIVE and STARE
databases of manually labeled non-mydriatic images. On the DRIVE database, it
achieves an area under the receiver operating characteristic (ROC) curve of
0.9598, being slightly superior than that presented by the method of Staal et
al.


title:
Optimal Relay Functionality for SNR Maximization in Memoryless Relay
  Networks

abstract:
  We explore the SNR-optimal relay functionality in a \emph{memoryless} relay
network, i.e. a network where, during each channel use, the signal transmitted
by a relay depends only on the last received symbol at that relay. We develop a
generalized notion of SNR for the class of memoryless relay functions. The
solution to the generalized SNR optimization problem leads to the novel concept
of minimum mean square uncorrelated error estimation(MMSUEE). For the elemental
case of a single relay, we show that MMSUEE is the SNR-optimal memoryless relay
function regardless of the source and relay transmit power, and the modulation
scheme. This scheme, that we call estimate and forward (EF), is also shown to
be SNR-optimal with PSK modulation in a parallel relay network. We demonstrate
that EF performs better than the best of amplify and forward (AF) and
demodulate and forward (DF), in both parallel and serial relay networks. We
also determine that AF is near-optimal at low transmit power in a parallel
network, while DF is near-optimal at high transmit power in a serial network.
For hybrid networks that contain both serial and parallel elements, and when
robust performance is desired, the advantage of EF over the best of AF and DF
is found to be significant. Error probabilities are provided to substantiate
the performance gain obtained through SNR optimality. We also show that, for
\emph{Gaussian} inputs, AF, DF and EF become identical.


title: Generalized ABBA Space-Time Block Codes

abstract:
  Linear space-time block codes (STBCs) of unitary rate and full diversity,
systematically constructed over arbitrary constellations for any number of
transmit antennas are introduced. The codes are obtained by generalizing the
existing ABBA STBCs, a.k.a quasi-orthogonal STBCs (QO-STBCs). Furthermore, a
fully orthogonal (symbol-by-symbol) decoder for the new generalized ABBA
(GABBA) codes is provided. This remarkably low-complexity decoder relies on
partition orthogonality properties of the code structure to decompose the
received signal vector into lower-dimension tuples, each dependent only on
certain subsets of the transmitted symbols. Orthogonal decodability results
from the nested application of this technique, with no matrix inversion or
iterative signal processing required. The exact bit-error-rate probability of
GABBA codes over generalized fading channels with maximum likelihood (ML)
decoding is evaluated analytically and compared against simulation results
obtained with the proposed orthogonal decoder. The comparison reveals that the
proposed GABBA solution, despite its very low complexity, achieves nearly the
same performance of the bound corresponding to the ML-decoded system,
especially in systems with large numbers of antennas.


title: The Hunting of the Bump: On Maximizing Statistical Discrepancy

abstract:
  Anomaly detection has important applications in biosurveilance and
environmental monitoring. When comparing measured data to data drawn from a
baseline distribution, merely, finding clusters in the measured data may not
actually represent true anomalies. These clusters may likely be the clusters of
the baseline distribution. Hence, a discrepancy function is often used to
examine how different measured data is to baseline data within a region. An
anomalous region is thus defined to be one with high discrepancy.
  In this paper, we present algorithms for maximizing statistical discrepancy
functions over the space of axis-parallel rectangles. We give provable
approximation guarantees, both additive and relative, and our methods apply to
any convex discrepancy function. Our algorithms work by connecting statistical
discrepancy to combinatorial discrepancy; roughly speaking, we show that in
order to maximize a convex discrepancy function over a class of shapes, one
needs only maximize a linear discrepancy function over the same set of shapes.
  We derive general discrepancy functions for data generated from a one-
parameter exponential family. This generalizes the widely-used Kulldorff scan
statistic for data from a Poisson distribution. We present an algorithm running
in $O(\smash[tb]{\frac{1}{\epsilon} n^2 \log^2 n})$ that computes the maximum
discrepancy rectangle to within additive error $\epsilon$, for the Kulldorff
scan statistic. Similar results hold for relative error and for discrepancy
functions for data coming from Gaussian, Bernoulli, and gamma distributions.
Prior to our work, the best known algorithms were exact and ran in time
$\smash[t]{O(n^4)}$.


title: Taylor series expansions for the entropy rate of Hidden Markov Processes

abstract:
  Finding the entropy rate of Hidden Markov Processes is an active research
topic, of both theoretical and practical importance. A recently used approach
is studying the asymptotic behavior of the entropy rate in various regimes. In
this paper we generalize and prove a previous conjecture relating the entropy
rate to entropies of finite systems. Building on our new theorems, we establish
series expansions for the entropy rate in two different regimes. We also study
the radius of convergence of the two series expansions.