title:
Inconsistent parameter estimation in Markov random fields: Benefits in
  the computation-limited setting

abstract:
  Consider the problem of joint parameter estimation and prediction in a Markov
random field: i.e., the model parameters are estimated on the basis of an
initial set of data, and then the fitted model is used to perform prediction
(e.g., smoothing, denoising, interpolation) on a new noisy observation. Working
under the restriction of limited computation, we analyze a joint method in
which the \emph{same convex variational relaxation} is used to construct an
M-estimator for fitting parameters, and to perform approximate marginalization
for the prediction step. The key result of this paper is that in the
computation-limited setting, using an inconsistent parameter estimator (i.e.,
an estimator that returns the ``wrong'' model even in the infinite data limit)
can be provably beneficial, since the resulting errors can partially compensate
for errors made by using an approximate prediction technique. En route to this
result, we analyze the asymptotic properties of M-estimators based on convex
variational relaxations, and establish a Lipschitz stability property that
holds for a broad class of variational methods. We show that joint
estimation/prediction based on the reweighted sum-product algorithm
substantially outperforms a commonly used heuristic based on ordinary
sum-product.


title: Rational stochastic languages

abstract:
  The goal of the present paper is to provide a systematic and comprehensive
study of rational stochastic languages over a semiring K \in {Q, Q +, R, R+}. A
rational stochastic language is a probability distribution over a free monoid
\Sigma^* which is rational over K, that is which can be generated by a
multiplicity automata with parameters in K. We study the relations between the
classes of rational stochastic languages S rat K (\Sigma). We define the notion
of residual of a stochastic language and we use it to investigate properties of
several subclasses of rational stochastic languages. Lastly, we study the
representation of rational stochastic languages by means of multiplicity
automata.


title: Effect of CSMA/CD on Self-Similarity of Network Traffic

abstract:
  It is now well known that Internet traffic exhibits self-similarity, which
cannot be described by traditional Markovian models such as the Poisson
process. The causes of self-similarity of network traffic must be identified
because understanding the nature of network traffic is critical in order to
properly design and implement computer networks and network services like the
World Wide Web. While some researchers have argued self similarity is generated
by the typical applications or caused by Transport layer Protocols, it is also
possible that the CSMA/CD protocol may cause or at least contribute to this
phenomenon. In this paper, we use NS simulator to study the effect of CSMA/CD
Exponential Backoff retransmission algorithm on Traffic Self similarity.


title: Epsilon-Unfolding Orthogonal Polyhedra

abstract:
  An unfolding of a polyhedron is produced by cutting the surface and
flattening to a single, connected, planar piece without overlap (except
possibly at boundary points). It is a long unsolved problem to determine
whether every polyhedron may be unfolded. Here we prove, via an algorithm, that
every orthogonal polyhedron (one whose faces meet at right angles) of genus
zero may be unfolded. Our cuts are not necessarily along edges of the
polyhedron, but they are always parallel to polyhedron edges. For a polyhedron
of n vertices, portions of the unfolding will be rectangular strips which, in
the worst case, may need to be as thin as epsilon = 1/2^{Omega(n)}.


title: Difficulties in the Implementation of Quantum Computers

abstract:
  This paper reviews various engineering hurdles facing the field of quantum
computing. Specifically, problems related to decoherence, state preparation,
error correction, and implementability of gates are considered.


title: The Cubic Public-Key Transformation

abstract:
  We propose the use of the cubic transformation for public-key applications
and digital signatures. Transformations modulo a prime p or a composite n=pq,
where p and q are primes, are used in such a fashion that each transformed
value has only 3 roots that makes it a more efficient transformation than the
squaring transformation of Rabin, which has 4 roots. Such a transformation,
together with additional tag information, makes it possible to uniquely invert
each transformed value. The method may be used for other exponents as well.


title: Compositional Semantics for the Procedural Interpretation of Logic

abstract:
  Semantics of logic programs has been given by proof theory, model theory and
by fixpoint of the immediate-consequence operator. If clausal logic is a
programming language, then it should also have a compositional semantics.
Compositional semantics for programming languages follows the abstract syntax
of programs, composing the meaning of a unit by a mathematical operation on the
meanings of its constituent units. The procedural interpretation of logic has
only yielded an incomplete abstract syntax for logic programs. We complete it
and use the result as basis of a compositional semantics. We present for
comparison Tarski's algebraization of first-order predicate logic, which is in
substance the compositional semantics for his choice of syntax. We characterize
our semantics by equivalence with the immediate-consequence operator.


title: Towards Applicative Relational Programming

abstract:
  Functional programming comes in two flavours: one where ``functions are
first-class citizens'' (we call this applicative) and one which is based on
equations (we call this declarative). In relational programming clauses play
the role of equations. Hence Prolog is declarative. The purpose of this paper
is to provide in relational programming a mathematical basis for the relational
analog of applicative functional programming. We use the cylindric semantics of
first-order logic due to Tarski and provide a new notation for the required
cylinders that we call tables. We define the Table/Relation Algebra with
operators sufficient to translate Horn clauses into algebraic form. We
establish basic mathematical properties of these operators. We show how
relations can be first-class citizens, and devise mechanisms for modularity,
for local scoping of predicates, and for exporting/importing relations between
programs.


title: BioSig - An application of Octave

abstract:
  BioSig is an open source software library for biomedical signal processing.
Most users in the field are using Matlab; however, significant effort was
undertaken to provide compatibility to Octave, too. This effort has been widely
successful, only some non-critical components relying on a graphical user
interface are missing. Now, installing BioSig on Octave is as easy as on
Matlab. Moreover, a benchmark test based on BioSig has been developed and the
benchmark results of several platforms are presented.


title: On comparing sums of square roots of small integers

abstract:
  Let $k$ and $n$ be positive integers, $n>k$. Define $r(n,k)$ to be the
minimum positive value of $$ |\sqrt{a_1} + ... + \sqrt{a_k} - \sqrt{b_1} - >...
-\sqrt{b_k} | $$ where $ a_1, a_2, ..., a_k, b_1, b_2, ..., b_k $ are positive
integers no larger than $n$. It is an important problem in computational
geometry to determine a good upper bound of $-\log r(n,k)$. In this paper we
prove an upper bound of $ 2^{O(n/\log n)} \log n$, which is better than the
best known result $O(2^{2k} \log n)$ whenever $ n \leq ck\log k$ for some
constant $c$. In particular, our result implies a {\em subexponential}
algorithm to compare two sums of square roots of integers of size $o(k\log k)$.


title: Analyse non standard du bruit

abstract:
  Thanks to the nonstandard formalization of fast oscillating functions, due to
P. Cartier and Y. Perrin, an appropriate mathematical framework is derived for
new non-asymptotic estimation techniques, which do not necessitate any
statistical analysis of the noises corrupting any sensor. Various applications
are deduced for multiplicative noises, for the length of the parametric
estimation windows, and for burst errors.


title:
Lamarckian Evolution and the Baldwin Effect in Evolutionary Neural
  Networks

abstract:
  Hybrid neuro-evolutionary algorithms may be inspired on Darwinian or
Lamarckian evolu- tion. In the case of Darwinian evolution, the Baldwin effect,
that is, the progressive incorporation of learned characteristics to the
genotypes, can be observed and leveraged to improve the search. The purpose of
this paper is to carry out an exper- imental study into how learning can
improve G-Prop genetic search. Two ways of combining learning and genetic
search are explored: one exploits the Baldwin effect, while the other uses a
Lamarckian strategy. Our experiments show that using a Lamarckian op- erator
makes the algorithm find networks with a low error rate, and the smallest size,
while using the Bald- win effect obtains MLPs with the smallest error rate, and
a larger size, taking longer to reach a solution. Both approaches obtain a
lower average error than other BP-based algorithms like RPROP, other evolu-
tionary methods and fuzzy logic based methods


title: A Basic Introduction on Math-Link in Mathematica

abstract:
  Starting from the basic ideas of mathematica, we give a detailed description
about the way of linking of external programs with mathematica through proper
mathlink commands. This article may be quite helpful for the beginners to start
with and write programs in mathematica.
  In the first part, we illustrate how to use a mathemtica notebook and write a
complete program in the notebook. Following with this, we also mention
elaborately about the utility of the local and global variables those are very
essential for writing a program in mathematica. All the commands needed for
doing different mathematical operations can be found with some proper examples
in the mathematica book written by Stephen Wolfram \cite{wolfram}.
  In the rest of this article, we concentrate our study on the most significant
issue which is the process of linking of {\em external programs} with
mathematica, so-called the mathlink operation. By using proper mathlink
commands one can run very tedious jobs efficiently and the operations become
extremely fast.


title: Pivotal and Pivotal-discriminative Consequence Relations

abstract:
  In the present paper, we investigate consequence relations that are both
paraconsistent and plausible (but still monotonic). More precisely, we put the
focus on pivotal consequence relations, i.e. those relations that can be
defined by a pivot (in the style of e.g. D. Makinson). A pivot is a fixed
subset of valuations which are considered to be the important ones in the
absolute sense. We worked with a general notion of valuation that covers e.g.
the classical valuations as well as certain kinds of many-valued valuations. In
the many-valued cases, pivotal consequence relations are paraconsistant (in
addition to be plausible), i.e. they are capable of drawing reasonable
conclusions which contain contradictions. We will provide in our general
framework syntactic characterizations of several families of pivotal relations.
In addition, we will provide, again in our general framework, characterizations
of several families of pivotal discriminative consequence relations. The latter
are defined exactly as the plain version, but contradictory conclusions are
rejected. We will also answer negatively a representation problem that was left
open by Makinson. Finally, we will put in evidence a connexion with X-logics
from Forget, Risch, and Siegel. The motivations and the framework of the
present paper are very close to those of a previous paper of the author which
is about preferential consequence relations.


title:
Complete Enumeration of Stopping Sets of Full-Rank Parity-Check Matrices
  of Hamming Codes

abstract:
  Stopping sets, and in particular their numbers and sizes, play an important
role in determining the performance of iterative decoders of linear codes over
binary erasure channels. In the 2004 Shannon Lecture, McEliece presented an
expression for the number of stopping sets of size three for a full-rank
parity-check matrix of the Hamming code. In this correspondence, we derive an
expression for the number of stopping sets of any given size for the same
parity-check matrix.


title: Linear Secret Sharing from Algebraic-Geometric Codes

abstract:
  It is well-known that the linear secret-sharing scheme (LSSS) can be
constructed from linear error-correcting codes (Brickell [1], R.J. McEliece and
D.V.Sarwate [2],Cramer, el.,[3]). The theory of linear codes from
algebraic-geometric curves (algebraic-geometric (AG) codes or geometric Goppa
code) has been well-developed since the work of V.Goppa and Tsfasman, Vladut,
and Zink(see [17], [18] and [19]). In this paper the linear secret-sharing
scheme from algebraic-geometric codes, which are non-threshold scheme for
curves of genus greater than 0, are presented . We analysis the minimal access
structure, $d_{min}$ and $d_{cheat}$([8]), (strongly) multiplicativity and the
applications in verifiable secret-sharing (VSS) scheme and secure multi-party
computation (MPC) of this construction([3] and [10-11]). Our construction also
offers many examples of the self-dually $GF(q)$-representable matroids and many
examples of new ideal linear secret-sharing schemes addressing to the problem
of the characterization of the access structures for ideal secret-sharing
schemes([3] and [9]). The access structures of the linear secret-sharing
schemes from the codes on elliptic curves are given explicitly. From the work
in this paper we can see that the algebraic-geometric structure of the
underlying algebraic curves is an important resource for secret-sharing,
matroid theory, verifiable secret-sharing and secure multi-party computation.


title: An Achievability Result for the General Relay Channel

abstract:
  See cs.IT/0605135: R. Dabora, S. D. Servetto; On the Role of
Estimate-and-Forward with Time-Sharing in Cooperative Communications.


title:
Asymptotic constant-factor approximation algorithm for the Traveling
  Salesperson Problem for Dubins' vehicle

abstract:
  This article proposes the first known algorithm that achieves a
constant-factor approximation of the minimum length tour for a Dubins' vehicle
through $n$ points on the plane. By Dubins' vehicle, we mean a vehicle
constrained to move at constant speed along paths with bounded curvature
without reversing direction. For this version of the classic Traveling
Salesperson Problem, our algorithm closes the gap between previously
established lower and upper bounds; the achievable performance is of order
$n^{2/3}$.


title: Intrinsically Legal-For-Trade Objects by Digital Signatures

abstract:
  The established techniques for legal-for-trade registration of weight values
meet the legal requirements, but in praxis they show serious disadvantages. We
report on the first implementation of intrinsically legal-for-trade objects,
namely weight values signed by the scale, that is accepted by the approval
authority. The strict requirements from both the approval- and the
verification-authority as well as the limitations due to the hardware of the
scale were a special challenge. The presented solution fulfills all legal
requirements and eliminates the existing practical disadvantages.


title: Improved Bounds and Schemes for the Declustering Problem

abstract:
  The declustering problem is to allocate given data on parallel working
storage devices in such a manner that typical requests find their data evenly
distributed on the devices. Using deep results from discrepancy theory, we
improve previous work of several authors concerning range queries to
higher-dimensional data. We give a declustering scheme with an additive error
of $O_d(\log^{d-1} M)$ independent of the data size, where $d$ is the
dimension, $M$ the number of storage devices and $d-1$ does not exceed the
smallest prime power in the canonical decomposition of $M$ into prime powers.
In particular, our schemes work for arbitrary $M$ in dimensions two and three.
For general $d$, they work for all $M\geq d-1$ that are powers of two.
Concerning lower bounds, we show that a recent proof of a
$\Omega_d(\log^{\frac{d-1}{2}} M)$ bound contains an error. We close the gap in
the proof and thus establish the bound.


title: On the MacWilliams Identity for Convolutional Codes

abstract:
  The adjacency matrix associated with a convolutional code collects in a
detailed manner information about the weight distribution of the code. A
MacWilliams Identity Conjecture, stating that the adjacency matrix of a code
fully determines the adjacency matrix of the dual code, will be formulated, and
an explicit formula for the transformation will be stated. The formula involves
the MacWilliams matrix known from complete weight enumerators of block codes.
The conjecture will be proven for the class of convolutional codes where either
the code itself or its dual does not have Forney indices bigger than one. For
the general case the conjecture is backed up by many examples, and a weaker
version will be established.


title: Near orders and codes

abstract:
  Hoholdt, van Lint and Pellikaan used order functions to construct codes by
means of Linear Algebra and Semigroup Theory only. However, Geometric Goppa
codes that can be represented by this method are mainly those based on just one
point. In this paper we introduce the concept of near order function with the
aim of generalize this approach in such a way that a of wider family of
Geometric Goppa codes can be studied on a more elementary setting.


title: The Basic Kak Neural Network with Complex Inputs

abstract:
  The Kak family of neural networks is able to learn patterns quickly, and this
speed of learning can be a decisive advantage over other competing models in
many applications. Amongst the implementations of these networks are those
using reconfigurable networks, FPGAs and optical networks. In some
applications, it is useful to use complex data, and it is with that in mind
that this introduction to the basic Kak network with complex inputs is being
presented. The training algorithm is prescriptive and the network weights are
assigned simply upon examining the inputs. The input is mapped using quaternary
encoding for purpose of efficienty. This network family is part of a larger
hierarchy of learning schemes that include quantum models.


title: Object-Oriented Modeling of Programming Paradigms

abstract:
  For the right application, the use of programming paradigms such as
functional or logic programming can enormously increase productivity in
software development. But these powerful paradigms are tied to exotic
programming languages, while the management of software development dictates
standardization on a single language.
  This dilemma can be resolved by using object-oriented programming in a new
way. It is conventional to analyze an application by object-oriented modeling.
In the new approach, the analysis identifies the paradigm that is ideal for the
application; development starts with object-oriented modeling of the paradigm.
In this paper we illustrate the new approach by giving examples of
object-oriented modeling of dataflow and constraint programming. These examples
suggest that it is no longer necessary to embody a programming paradigm in a
language dedicated to it.


title: A Measure of Space for Computing over the Reals

abstract:
  We propose a new complexity measure of space for the BSS model of
computation. We define LOGSPACE\_W and PSPACE\_W complexity classes over the
reals. We prove that LOGSPACE\_W is included in NC^2\_R and in P\_W, i.e. is
small enough for being relevant. We prove that the Real Circuit Decision
Problem is P\_R-complete under LOGSPACE\_W reductions, i.e. that LOGSPACE\_W is
large enough for containing natural algorithms. We also prove that PSPACE\_W is
included in PAR\_R.


title:
On Non-coherent MIMO Channels in the Wideband Regime: Capacity and
  Reliability

abstract:
  We consider a multiple-input, multiple-output (MIMO) wideband Rayleigh block
fading channel where the channel state is unknown to both the transmitter and
the receiver and there is only an average power constraint on the input. We
compute the capacity and analyze its dependence on coherence length, number of
antennas and receive signal-to-noise ratio (SNR) per degree of freedom. We
establish conditions on the coherence length and number of antennas for the
non-coherent channel to have a "near coherent" performance in the wideband
regime. We also propose a signaling scheme that is near-capacity achieving in
this regime.
  We compute the error probability for this wideband non-coherent MIMO channel
and study its dependence on SNR, number of transmit and receive antennas and
coherence length. We show that error probability decays inversely with
coherence length and exponentially with the product of the number of transmit
and receive antennas. Moreover, channel outage dominates error probability in
the wideband regime. We also show that the critical as well as cut-off rates
are much smaller than channel capacity in this regime.


title:
Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal
  Logic

abstract:
  There has been a great of work on characterizing the complexity of the
satisfiability and validity problem for modal logics. In particular, Ladner
showed that the validity problem for all logics between K, T, and S4 is {\sl
PSPACE}-complete, while for S5 it is {\sl NP}-complete. We show that, in a
precise sense, it is \emph{negative introspection}, the axiom $\neg K p \rimp K
\neg K p$, that causes the gap. In a precise sense, if we require this axiom,
then the satisfiability problem is {\sl NP}-complete; without it, it is {\sl
PSPACE}-complete.


title: Reasoning About Knowledge of Unawareness

abstract:
  Awareness has been shown to be a useful addition to standard epistemic logic
for many applications. However, standard propositional logics for knowledge and
awareness cannot express the fact that an agent knows that there are facts of
which he is unaware without there being an explicit fact that the agent knows
he is unaware of. We propose a logic for reasoning about knowledge of
unawareness, by extending Fagin and Halpern's \emph{Logic of General
Awareness}. The logic allows quantification over variables, so that there is a
formula in the language that can express the fact that ``an agent explicitly
knows that there exists a fact of which he is unaware''. Moreover, that formula
can be true without the agent explicitly knowing that he is unaware of any
particular formula. We provide a sound and complete axiomatization of the
logic, using standard axioms from the literature to capture the quantification
operator. Finally, we show that the validity problem for the logic is
recursively enumerable, but not decidable.


title: Language Support for Optional Functionality

abstract:
  We recommend a programming construct - availability check - for programs that
need to automatically adjust to presence or absence of segments of code. The
idea is to check the existence of a valid definition before a function call is
invoked. The syntax is that of a simple 'if' statement. The vision is to enable
customization of application functionality through addition or removal of
optional components, but without requiring complete re-building. Focus is on
C-like compiled procedural languages and UNIX-based systems. Essentially, our
approach attempts to combine the flexibility of dynamic libraries with the
usability of utility (dependency) libraries. We outline the benefits over
prevalent strategies mainly in terms of development complexity, crudely
measured as lesser lines of code. We also allude to performance and flexibility
facets. A Preliminary implementation and figures from early experimental
evaluation are presented.


title:
On Separation, Randomness and Linearity for Network Codes over Finite
  Fields

abstract:
  We examine the issue of separation and code design for networks that operate
over finite fields. We demonstrate that source-channel (or source-network)
separation holds for several canonical network examples like the noisy multiple
access channel and the erasure degraded broadcast channel, when the whole
network operates over a common finite field. This robustness of separation is
predicated on the fact that noise and inputs are independent, and we examine
the failure of separation when noise is dependent on inputs in multiple access
channels.
  Our approach is based on the sufficiency of linear codes. Using a simple and
unifying framework, we not only re-establish with economy the optimality of
linear codes for single-transmitter, single-receiver channels and for
Slepian-Wolf source coding, but also establish the optimality of linear codes
for multiple access and for erasure degraded broadcast channels. The linearity
allows us to obtain simple optimal code constructions and to study capacity
regions of the noisy multiple access and the degraded broadcast channel. The
linearity of both source and network coding blurs the delineation between
source and network codes. While our results point to the fact that separation
of source coding and channel coding is optimal in some canonical networks, we
show that decomposing networks into canonical subnetworks may not be effective.
Thus, we argue that it may be the lack of decomposability of a network into
canonical network modules, rather than the lack of separation between source
and channel coding, that presents major challenges for coding over networks.


title:
Metric State Space Reinforcement Learning for a Vision-Capable Mobile
  Robot

abstract:
  We address the problem of autonomously learning controllers for
vision-capable mobile robots. We extend McCallum's (1995) Nearest-Sequence
Memory algorithm to allow for general metrics over state-action trajectories.
We demonstrate the feasibility of our approach by successfully running our
algorithm on a real mobile robot. The algorithm is novel and unique in that it
(a) explores the environment and learns directly on a mobile robot without
using a hand-made computer model as an intermediate step, (b) does not require
manual discretization of the sensor input space, (c) works in piecewise
continuous perceptual spaces, and (d) copes with partial observability.
Together this allows learning from much less experience compared to previous
methods.


title: Representing Contextualized Information in the NSDL

abstract:
  The NSDL (National Science Digital Library) is funded by the National Science
Foundation to advance science and match education. The inital product was a
metadata-based digital library providing search and access to distributed
resources. Our recent work recognizes the importance of context - relations,
metadata, annotations - for the pedagogical value of a digital library. This
new architecture uses Fedora, a tool for representing complex content, data,
metadata, web-based services, and semantic relationships, as the basis of an
information network overlay (INO). The INO provides an extensible knowl-edge
base for an expanding suite of digital library services.


title: Open Answer Set Programming with Guarded Programs

abstract:
  Open answer set programming (OASP) is an extension of answer set programming
where one may ground a program with an arbitrary superset of the program's
constants. We define a fixed point logic (FPL) extension of Clark's completion
such that open answer sets correspond to models of FPL formulas and identify a
syntactic subclass of programs, called (loosely) guarded programs. Whereas
reasoning with general programs in OASP is undecidable, the FPL translation of
(loosely) guarded programs falls in the decidable (loosely) guarded fixed point
logic (mu(L)GF). Moreover, we reduce normal closed ASP to loosely guarded OASP,
enabling for the first time, a characterization of an answer set semantics by
muLGF formulas. We further extend the open answer set semantics for programs
with generalized literals. Such generalized programs (gPs) have interesting
properties, e.g., the ability to express infinity axioms. We restrict the
syntax of gPs such that both rules and generalized literals are guarded. Via a
translation to guarded fixed point logic, we deduce 2-exptime-completeness of
satisfiability checking in such guarded gPs (GgPs). Bound GgPs are restricted
GgPs with exptime-complete satisfiability checking, but still sufficiently
expressive to optimally simulate computation tree logic (CTL). We translate
Datalog lite programs to GgPs, establishing equivalence of GgPs under an open
answer set semantics, alternation-free muGF, and Datalog lite.


title: The Snowblower Problem

abstract:
  We introduce the snowblower problem (SBP), a new optimization problem that is
closely related to milling problems and to some material-handling problems. The
objective in the SBP is to compute a short tour for the snowblower to follow to
remove all the snow from a domain (driveway, sidewalk, etc.). When a snowblower
passes over each region along the tour, it displaces snow into a nearby region.
The constraint is that if the snow is piled too high, then the snowblower
cannot clear the pile.
  We give an algorithmic study of the SBP. We show that in general, the problem
is NP-complete, and we present polynomial-time approximation algorithms for
removing snow under various assumptions about the operation of the snowblower.
Most commercially-available snowblowers allow the user to control the direction
in which the snow is thrown. We differentiate between the cases in which the
snow can be thrown in any direction, in any direction except backwards, and
only to the right. For all cases, we give constant-factor approximation
algorithms; the constants increase as the throw direction becomes more
restricted.
  Our results are also applicable to robotic vacuuming (or lawnmowing) with
bounded capacity dust bin and to some versions of material-handling problems,
in which the goal is to rearrange cartons on the floor of a warehouse.


title:
On the Second-Order Statistics of the Instantaneous Mutual Information
  in Rayleigh Fading Channels

abstract:
  In this paper, the second-order statistics of the instantaneous mutual
information are studied, in time-varying Rayleigh fading channels, assuming
general non-isotropic scattering environments. Specifically, first the
autocorrelation function, correlation coefficient, level crossing rate, and the
average outage duration of the instantaneous mutual information are
investigated in single-input single-output (SISO) systems. Closed-form exact
expressions are derived, as well as accurate approximations in low- and
high-SNR regimes. Then, the results are extended to multiple-input
single-output and single-input multiple-output systems, as well as
multiple-input multiple-output systems with orthogonal space-time block code
transmission. Monte Carlo simulations are provided to verify the accuracy of
the analytical results. The results shed more light on the dynamic behavior of
the instantaneous mutual information in mobile fading channels.


title: On the tree-transformation power of XSLT

abstract:
  XSLT is a standard rule-based programming language for expressing
transformations of XML data. The language is currently in transition from
version 1.0 to 2.0. In order to understand the computational consequences of
this transition, we restrict XSLT to its pure tree-transformation capabilities.
Under this focus, we observe that XSLT~1.0 was not yet a computationally
complete tree-transformation language: every 1.0 program can be implemented in
exponential time. A crucial new feature of version~2.0, however, which allows
nodesets over temporary trees, yields completeness. We provide a formal
operational semantics for XSLT programs, and establish confluence for this
semantics.


title: A d-Sequence based Recursive Random Number Generator

abstract:
  This paper proposes a new recursive technique using d-sequences to generate
random numbers.


title: A Service-Centric Approach to a Parameterized RBAC Service

abstract:
  Significant research has been done in the area of Role Based Access Control
[RBAC]. Within this research there has been a thread of work focusing on adding
parameters to the role and permissions within RBAC. The primary benefit of
parameter support in RBAC comes in the form of a significant increase in
specificity in how permissions may be granted. This paper focuses on
implementing a parameterized implementation based heavily upon existing
standards.


title:
Performance Analysis of CDMA Signature Optimization with Finite Rate
  Feedback

abstract:
  We analyze the performance of CDMA signature optimization with finite rate
feedback. For a particular user, the receiver selects a signature vector from a
signature codebook to avoid the interference from other users, and feeds the
corresponding index back to this user through a finite rate and error-free
feedback link. We assume the codebook is randomly constructed where the entries
are independent and isotropically distributed. It has been shown that the
randomly constructed codebook is asymptotically optimal. In this paper, we
consider two types of signature selection criteria. One is to select the
signature vector that minimizes the interference from other users. The other
one is to select the signature vector to match the weakest interference
directions. By letting the processing gain, number of users and feedback bits
approach infinity with fixed ratios, we derive the exact asymptotic formulas to
calculate the average interference for both criteria. Our simulations
demonstrate the theoretical formulas. The analysis can be extended to evaluate
the signal-to-interference plus noise ratio performance for both match filter
and linear minimum mean-square error receivers.


title:
Market Equilibrium for Bundle Auctions and the Matching Core of
  Nonnegative TU Games

abstract:
  We discuss bundle auctions within the framework of an integer allocation
problem. We show that for multi-unit auctions, of which bundle auctions are a
special case, market equilibrium and constrained market equilibrium are
equivalent concepts. This equivalence, allows us to obtain a computable
necessary and sufficient condition for the existence of constrained market
equilibrium for bundle auctions. We use this result to obtain a necessary and
sufficient condition for the existence of market equilibrium for multi-unit
auctions. After obtaining the induced bundle auction of a nonnegative TU game,
we show that the existence of market equilibrium implies the existence of a
possibly different market equilibrium as well, which corresponds very naturally
to an outcome in the matching core of the TU game. Consequently we show that
the matching core of the nonnegative TU game is non-empty if and only if the
induced market game has a market equilibrium.


title: Inter-component communication methods in object-oriented frameworks

abstract:
  Modern frameworks for development of graphical interfaces are using the
native controls of the operating system. Because of that they are using
operating system events model for inter-component communication. We consider a
method to increase inter-component communication speed by sending messages from
one component to the other passing over the operating system. Besides the
messages subscription helps to avoid receiving of unnecessary messages.


title: Metatheory of actions: beyond consistency

abstract:
  Consistency check has been the only criterion for theory evaluation in
logic-based approaches to reasoning about actions. This work goes beyond that
and contributes to the metatheory of actions by investigating what other
properties a good domain description in reasoning about actions should have. We
state some metatheoretical postulates concerning this sore spot. When all
postulates are satisfied together we have a modular action theory. Besides
being easier to understand and more elaboration tolerant in McCarthy's sense,
modular theories have interesting properties. We point out the problems that
arise when the postulates about modularity are violated and propose algorithmic
checks that can help the designer of an action theory to overcome them.


title: Final Results from and Exploitation Plans for MammoGrid

abstract:
  The MammoGrid project has delivered the first deployed instance of a
healthgrid for clinical mammography that spans national boundaries. During the
last year, the final MammoGrid prototype has undergone a series of rigorous
tests undertaken by radiologists in the UK and Italy and this paper draws
conclusions from those tests for the benefit of the Healthgrid community. In
addition, lessons learned during the lifetime of the project are detailed and
recommendations drawn for future health applications using grids. Following the
completion of the project, plans have been put in place for the
commercialisation of the MammoGrid system and this is also reported in this
article. Particular emphasis is placed on the issues surrounding the transition
from collaborative research project to a marketable product. This paper
concludes by highlighting some of the potential areas of future development and
research.


title:
Health-e-Child : An Integrated Biomedical Platform for Grid-Based
  Paediatric Applications

abstract:
  There is a compelling demand for the integration and exploitation of
heterogeneous biomedical information for improved clinical practice, medical
research, and personalised healthcare across the EU. The Health-e-Child project
aims at developing an integrated healthcare platform for European Paediatrics,
providing seamless integration of traditional and emerging sources of
biomedical information. The long-term goal of the project is to provide
uninhibited access to universal biomedical knowledge repositories for
personalised and preventive healthcare, large-scale information-based
biomedical research and training, and informed policy making. The project focus
will be on individualised disease prevention, screening, early diagnosis,
therapy and follow-up of paediatric heart diseases, inflammatory diseases, and
brain tumours. The project will build a Grid-enabled European network of
leading clinical centres that will share and annotate biomedical data, validate
systems clinically, and diffuse clinical excellence across Europe by setting up
new technologies, clinical workflows, and standards. This paper outlines the
design approach being adopted in Health-e-Child to enable the delivery of an
integrated biomedical information platform.


title:
Deriving Conceptual Data Models from Domain Ontologies for
  Bioinformatics

abstract:
  This paper studies the role that ontologies can play in establishing
conceptual data models during the process of information systems development. A
mapping algorithm has been proposed and embedded in a special purpose
Transformation-Engine to generate a conceptual data model from a given domain
ontology. In addition, this paper focuses on applying the proposed approach to
a bioinformatics context as the nature of biological data is considered a
barrier in representing biological conceptual data models. Both quantitative
and qualitative methods have been adopted to critically evaluate this new
approach. The results of this evaluation indicate that the quality of the
generated conceptual data models can reflect the problem domain entities and
the associations between them. The results are encouraging and support the
potential role that this approach can play in providing a suitable starting
point for conceptual data model development.


title:
Estimation of linear, non-gaussian causal models in the presence of
  confounding latent variables

abstract:
  The estimation of linear causal models (also known as structural equation
models) from data is a well-known problem which has received much attention in
the past. Most previous work has, however, made an explicit or implicit
assumption of gaussianity, limiting the identifiability of the models. We have
recently shown (Shimizu et al, 2005; Hoyer et al, 2006) that for non-gaussian
distributions the full causal model can be estimated in the no hidden variables
case. In this contribution, we discuss the estimation of the model when
confounding latent variables are present. Although in this case uniqueness is
no longer guaranteed, there is at most a finite set of models which can fit the
data. We develop an algorithm for estimating this set, and describe numerical
simulations which confirm the theoretical arguments and demonstrate the
practical viability of the approach. Full Matlab code is provided for all
simulations.


title:
Quantization Bounds on Grassmann Manifolds and Applications to MIMO
  Communications

abstract:
  This paper considers the quantization problem on the Grassmann manifold
\mathcal{G}_{n,p}, the set of all p-dimensional planes (through the origin) in
the n-dimensional Euclidean space. The chief result is a closed-form formula
for the volume of a metric ball in the Grassmann manifold when the radius is
sufficiently small. This volume formula holds for Grassmann manifolds with
arbitrary dimension n and p, while previous results pertained only to p=1, or a
fixed p with asymptotically large n. Based on this result, several quantization
bounds are derived for sphere packing and rate distortion tradeoff. We
establish asymptotically equivalent lower and upper bounds for the rate
distortion tradeoff. Since the upper bound is derived by constructing random
codes, this result implies that the random codes are asymptotically optimal.
The above results are also extended to the more general case, in which
\mathcal{G}_{n,q} is quantized through a code in \mathcal{G}_{n,p}, where p and
q are not necessarily the same. Finally, we discuss some applications of the
derived results to multi-antenna communication systems.


title:
On the Information Rate of MIMO Systems with Finite Rate Channel State
  Feedback Using Beamforming and Power On/Off Strategy

abstract:
  It is well known that Multiple-Input Multiple-Output (MIMO) systems have high
spectral efficiency, especially when channel state information at the
transmitter (CSIT) is available. When CSIT is obtained by feedback, it is
practical to assume that the channel state feedback rate is finite and the CSIT
is not perfect. For such a system, we consider beamforming and power on/off
strategy for its simplicity and near optimality, where power on/off means that
a beamforming vector (beam) is either turned on with a constant power or turned
off. The main contribution of this paper is to accurately evaluate the
information rate as a function of the channel state feedback rate. Name a beam
turned on as an on-beam and the minimum number of the transmit and receive
antennas as the dimension of a MIMO system. We prove that the ratio of the
optimal number of on-beams and the system dimension converges to a constant for
a given signal-to-noise ratio (SNR) when the numbers of transmit and receive
antennas approach infinity simultaneously and when beamforming is perfect.
Asymptotic formulas are derived to evaluate this ratio and the corresponding
information rate per dimension. The asymptotic results can be accurately
applied to finite dimensional systems and suggest a power on/off strategy with
a constant number of on-beams. For this suboptimal strategy, we take a novel
approach to introduce power efficiency factor, which is a function of the
feedback rate, to quantify the effect of imperfect beamforming. By combining
power efficiency factor and the asymptotic formulas for perfect beamforming
case, the information rate of the power on/off strategy with a constant number
of on-beams is accurately characterized.


title: Locally Adaptive Block Thresholding Method with Continuity Constraint

abstract:
  We present an algorithm that enables one to perform locally adaptive block
thresholding, while maintaining image continuity. Images are divided into
sub-images based some standard image attributes and thresholding technique is
employed over the sub-images. The present algorithm makes use of the thresholds
of neighboring sub-images to calculate a range of values. The image continuity
is taken care by choosing the threshold of the sub-image under consideration to
lie within the above range. After examining the average range values for
various sub-image sizes of a variety of images, it was found that the range of
acceptable threshold values is substantially high, justifying our assumption of
exploiting the freedom of range for bringing out local details.


title: The NoN Approach to Autonomic Face Recognition

abstract:
  A method of autonomic face recognition based on the biologically plausible
network of networks (NoN) model of information processing is presented. The NoN
model is based on locally parallel and globally coordinated transformations in
which the neurons or computational units form distributed networks, which
themselves link to form larger networks. This models the structures in the
cerebral cortex described by Mountcastle and the architecture based on that
proposed for information processing by Sutton. In the proposed implementation,
face images are processed by a nested family of locally operating networks
along with a hierarchically superior network that classifies the information
from each of the local networks. The results of the experiments yielded a
maximum of 98.5% recognition accuracy and an average of 97.4% recognition
accuracy on a benchmark database.


title: Time-Space Trade-Offs for Predecessor Search

abstract:
  We develop a new technique for proving cell-probe lower bounds for static
data structures. Previous lower bounds used a reduction to communication games,
which was known not to be tight by counting arguments. We give the first lower
bound for an explicit problem which breaks this communication complexity
barrier. In addition, our bounds give the first separation between polynomial
and near linear space. Such a separation is inherently impossible by
communication complexity.
  Using our lower bound technique and new upper bound constructions, we obtain
tight bounds for searching predecessors among a static set of integers. Given a
set Y of n integers of l bits each, the goal is to efficiently find
predecessor(x) = max{y in Y | y <= x}, by representing Y on a RAM using space
S.
  In external memory, it follows that the optimal strategy is to use either
standard B-trees, or a RAM algorithm ignoring the larger block size. In the
important case of l = c*lg n, for c>1 (i.e. polynomial universes), and near
linear space (such as S = n*poly(lg n)), the optimal search time is Theta(lg
l). Thus, our lower bound implies the surprising conclusion that van Emde Boas'
classic data structure from [FOCS'75] is optimal in this case. Note that for
space n^{1+eps}, a running time of O(lg l / lglg l) was given by Beame and Fich
[STOC'99].


title: First Steps in Relational Lattice

abstract:
  Relational lattice reduces the set of six classic relational algebra
operators to two binary lattice operations: natural join and inner union. We
give an introduction to this theory with emphasis on formal algebraic laws. New
results include Spight distributivity criteria and its applications to query
transformations.


title: Information and Errors in Quantum Teleportation

abstract:
  This article considers the question of the teleportation protocol from an
engineering perspective. The protocol ideally requires an authority that
ensures that the two communicating parties have a perfectly entangled pair of
particles available to them. But this cannot be unconditionally established to
the satisfaction of the parties due to the fact that an unknown quantum state
cannot be copied. This supports the view that quantum information cannot be
treated on the same basis as classical information.


title: Trusted Certificates in Quantum Cryptography

abstract:
  This paper analyzes the performance of Kak's three stage quantum
cryptographic protocol based on public key cryptography against a
man-in-the-middle attack. A method for protecting against such an attack is
presented using certificates distributed by a trusted third party.


title: The Quantum Separability Problem for Gaussian States

abstract:
  Determining whether a quantum state is separable or entangled is a problem of
fundamental importance in quantum information science. This is a brief review
in which we consider the problem for states in infinite dimensional Hilbert
spaces. We show how the problem becomes tractable for a class of Gaussian
states.


title:
Homogeneity vs. Adjacency: generalising some graph decomposition
  algorithms

abstract:
  In this paper, a new general decomposition theory inspired from modular graph
decomposition is presented. Our main result shows that, within this general
theory, most of the nice algorithmic tools developed for modular decomposition
are still efficient. This theory not only unifies the usual modular
decomposition generalisations such as modular decomposition of directed graphs
or decomposition of 2-structures, but also star cutsets and bimodular
decomposition. Our general framework provides a decomposition algorithm which
improves the best known algorithms for bimodular decomposition.


title:
State Space Realizations and Monomial Equivalence for Convolutional
  Codes

abstract:
  We will study convolutional codes with the help of state space realizations.
It will be shown that two such minimal realizations belong to the same code if
and only if they are equivalent under the full state feedback group. This
result will be used in order to prove that two codes with positive Forney
indices are monomially equivalent if and only if they share the same adjacency
matrix. The adjacency matrix counts in a detailed way the weights of all
possible outputs and thus contains full information about the weights of the
codewords in the given code.


title: Multiple serial episode matching

abstract:
  In a previous paper we generalized the Knuth-Morris-Pratt (KMP) pattern
matching algorithm and defined a non-conventional kind of RAM, the MP--RAMs
(RAMS equipped with extra operations), and designed an O(n) on-line algorithm
for solving the serial episode matching problem on MP--RAMs when there is only
one single episode. We here give two extensions of this algorithm to the case
when we search for several patterns simultaneously and compare them. More
preciseley, given $q+1$ strings (a text $t$ of length $n$ and $q$ patterns
$m\_1,...,m\_q$) and a natural number $w$, the {\em multiple serial episode
matching problem} consists in finding the number of size $w$ windows of text
$t$ which contain patterns $m\_1,...,m\_q$ as subsequences, i.e. for each
$m\_i$, if $m\_i=p\_1,..., p\_k$, the letters $p\_1,..., p\_k$ occur in the
window, in the same order as in $m\_i$, but not necessarily consecutively (they
may be interleaved with other letters).} The main contribution is an algorithm
solving this problem on-line in time $O(nq)$.


title: Transitive trust in mobile scenarios

abstract:
  Horizontal integration of access technologies to networks and services should
be accompanied by some kind of convergence of authentication technologies. The
missing link for the federation of user identities across the technological
boundaries separating authentication methods can be provided by trusted
computing platforms. The concept of establishing transitive trust by trusted
computing enables the desired crossdomain authentication functionality. The
focus of target application scenarios lies in the realm of mobile networks and
devices.


title:
Evaluation of interval extension of the power function by graph
  decomposition

abstract:
  The subject of our talk is the correct evaluation of interval extension of
the function specified by the expression x^y without any constraints on the
values of x and y. The core of our approach is a decomposition of the graph of
x^y into a small number of parts which can be transformed into subsets of the
graph of x^y for non-negative bases x. Because of this fact, evaluation of
interval extension of x^y, without any constraints on x and y, is not much
harder than evaluation of interval extension of x^y for non-negative bases x.


title:
Automatic generation of simplified weakest preconditions for integrity
  constraint verification

abstract:
  Given a constraint $c$ assumed to hold on a database $B$ and an update $u$ to
be performed on $B$, we address the following question: will $c$ still hold
after $u$ is performed? When $B$ is a relational database, we define a
confluent terminating rewriting system which, starting from $c$ and $u$,
automatically derives a simplified weakest precondition $wp(c,u)$ such that,
whenever $B$ satisfies $wp(c,u)$, then the updated database $u(B)$ will satisfy
$c$, and moreover $wp(c,u)$ is simplified in the sense that its computation
depends only upon the instances of $c$ that may be modified by the update. We
then extend the definition of a simplified $wp(c,u)$ to the case of deductive
databases; we prove it using fixpoint induction.


title: Testing Graph Isomorphism in Parallel by Playing a Game

abstract:
  Our starting point is the observation that if graphs in a class C have low
descriptive complexity in first order logic, then the isomorphism problem for C
is solvable by a fast parallel algorithm (essentially, by a simple
combinatorial algorithm known as the multidimensional Weisfeiler-Lehman
algorithm). Using this approach, we prove that isomorphism of graphs of bounded
treewidth is testable in TC1, answering an open question posed by
Chandrasekharan. Furthermore, we obtain an AC1 algorithm for testing
isomorphism of rotation systems (combinatorial specifications of graph
embeddings). The AC1 upper bound was known before, but the fact that this bound
can be achieved by the simple Weisfeiler-Lehman algorithm is new. Combined with
other known results, it also yields a new AC1 isomorphism algorithm for planar
graphs.


title: Improved Watermarking Scheme Using Decimal Sequences

abstract:
  This paper presents watermarking algorithms using d-sequences so that the
peak signal to noise ratio (PSNR) is maximized and the distortion introduced in
the image due to the embedding is minimized. By exploiting the cross
correlation property of decimal sequences, the concept of embedding more than
one watermark in the same cover image is investigated.


title:
Does the arXiv lead to higher citations and reduced publisher downloads
  for mathematics articles?

abstract:
  An analysis of 2,765 articles published in four math journals from 1997 to
2005 indicate that articles deposited in the arXiv received 35% more citations
on average than non-deposited articles (an advantage of about 1.1 citations per
article), and that this difference was most pronounced for highly-cited
articles. Open Access, Early View, and Quality Differential were examined as
three non-exclusive postulates for explaining the citation advantage. There was
little support for a universal Open Access explanation, and no empirical
support for Early View. There was some inferential support for a Quality
Differential brought about by more highly-citable articles being deposited in
the arXiv. In spite of their citation advantage, arXiv-deposited articles
received 23% fewer downloads from the publisher's website (about 10 fewer
downloads per article) in all but the most recent two years after publication.
The data suggest that arXiv and the publisher's website may be fulfilling
distinct functional needs of the reader.


title: Guard Placement For Wireless Localization

abstract:
  Motivated by secure wireless networking, we consider the problem of placing
fixed localizers that enable mobile communication devices to prove they belong
to a secure region that is defined by the interior of a polygon. Each localizer
views an infinite wedge of the plane, and a device can prove membership in the
secure region if it is inside the wedges for a set of localizers whose common
intersection contains no points outside the polygon. This model leads to a
broad class of new art gallery type problems, for which we provide upper and
lower bounds.


title: Convergence of Min-Sum Message Passing for Quadratic Optimization

abstract:
  We establish the convergence of the min-sum message passing algorithm for
minimization of a broad class of quadratic objective functions: those that
admit a convex decomposition. Our results also apply to the equivalent problem
of the convergence of Gaussian belief propagation.


title: Derivatives of Entropy Rate in Special Families of Hidden Markov Chains

abstract:
  Consider a hidden Markov chain obtained as the observation process of an
ordinary Markov chain corrupted by noise. Zuk, et. al. [13], [14] showed how,
in principle, one can explicitly compute the derivatives of the entropy rate of
at extreme values of the noise. Namely, they showed that the derivatives of
standard upper approximations to the entropy rate actually stabilize at an
explicit finite time. We generalize this result to a natural class of hidden
Markov chains called ``Black Holes.'' We also discuss in depth special cases of
binary Markov chains observed in binary symmetric noise, and give an abstract
formula for the first derivative in terms of a measure on the simplex due to
Blackwell.


title: An Improved Exact Algorithm for the Domatic Number Problem

abstract:
  The 3-domatic number problem asks whether a given graph can be partitioned
intothree dominating sets. We prove that this problem can be solved by a
deterministic algorithm in time 2.695^n (up to polynomial factors). This result
improves the previous bound of 2.8805^n, which is due to Fomin, Grandoni,
Pyatkin, and Stepanov. To prove our result, we combine an algorithm by Fomin et
al. with Yamamoto's algorithm for the satisfiability problem. In addition, we
show that the 3-domatic number problem can be solved for graphs G with bounded
maximum degree Delta(G) by a randomized algorithm, whose running time is better
than the previous bound due to Riege and Rothe whenever Delta(G) >= 5. Our new
randomized algorithm employs Schoening's approach to constraint satisfaction
problems.


title: Quasi-Orthogonal STBC With Minimum Decoding Complexity

abstract:
  In this paper, we consider a quasi-orthogonal (QO) space-time block code
(STBC) with minimum decoding complexity (MDC-QO-STBC). We formulate its
algebraic structure and propose a systematic method for its construction. We
show that a maximum-likelihood (ML) decoder for this MDC-QOSTBC, for any number
of transmit antennas, only requires the joint detection of two real symbols.
Assuming the use of a square or rectangular quadratic-amplitude modulation
(QAM) or multiple phase-shift keying (MPSK) modulation for this MDC-QOSTBC, we
also obtain the optimum constellation rotation angle, in order to achieve full
diversity and optimum coding gain. We show that the maximum achievable code
rate of these MDC-QOSTBC is 1 for three and four antennas and 3/4 for five to
eight antennas. We also show that the proposed MDC-QOSTBC has several desirable
properties, such as a more even power distribution among antennas and better
scalability in adjusting the number of transmit antennas, compared with the
coordinate interleaved orthogonal design (CIOD) and asymmetric CIOD (ACIOD)
codes. For the case of an odd number of transmit antennas, MDC-QO-STBC also has
better decoding performance than CIOD.


title:
Implementation and Deployment of a Distributed Network Topology
  Discovery Algorithm

abstract:
  In the past few years, the network measurement community has been interested
in the problem of internet topology discovery using a large number (hundreds or
thousands) of measurement monitors. The standard way to obtain information
about the internet topology is to use the traceroute tool from a small number
of monitors. Recent papers have made the case that increasing the number of
monitors will give a more accurate view of the topology. However, scaling up
the number of monitors is not a trivial process. Duplication of effort close to
the monitors wastes time by reexploring well-known parts of the network, and
close to destinations might appear to be a distributed denial-of-service (DDoS)
attack as the probes converge from a set of sources towards a given
destination. In prior work, authors of this report proposed Doubletree, an
algorithm for cooperative topology discovery, that reduces the load on the
network, i.e., router IP interfaces and end-hosts, while discovering almost as
many nodes and links as standard approaches based on traceroute. This report
presents our open-source and freely downloadable implementation of Doubletree
in a tool we call traceroute@home. We describe the deployment and validation of
traceroute@home on the PlanetLab testbed and we report on the lessons learned
from this experience. We discuss how traceroute@home can be developed further
and discuss ideas for future improvements.


title: Unary Primitive Recursive Functions

abstract:
  In this article, we study some new characterizations of primitive recursive
functions based on restricted forms of primitive recursion, improving the
pioneering work of R. M. Robinson and M. D. Gladstone in this area. We reduce
certain recursion schemes (mixed/pure iteration without parameters) and we
characterize one-argument primitive recursive functions as the closure under
substitution and iteration of certain optimal sets.


title: Guessing under source uncertainty

abstract:
  This paper considers the problem of guessing the realization of a finite
alphabet source when some side information is provided. The only knowledge the
guesser has about the source and the correlated side information is that the
joint source is one among a family. A notion of redundancy is first defined and
a new divergence quantity that measures this redundancy is identified. This
divergence quantity shares the Pythagorean property with the Kullback-Leibler
divergence. Good guessing strategies that minimize the supremum redundancy
(over the family) are then identified. The min-sup value measures the richness
of the uncertainty set. The min-sup redundancies for two examples - the
families of discrete memoryless sources and finite-state arbitrarily varying
sources - are then determined.


title: MIMO Broadcast Channels with Finite Rate Feedback

abstract:
  Multiple transmit antennas in a downlink channel can provide tremendous
capacity (i.e. multiplexing) gains, even when receivers have only single
antennas. However, receiver and transmitter channel state information is
generally required. In this paper, a system where each receiver has perfect
channel knowledge, but the transmitter only receives quantized information
regarding the channel instantiation is analyzed. The well known zero forcing
transmission technique is considered, and simple expressions for the throughput
degradation due to finite rate feedback are derived. A key finding is that the
feedback rate per mobile must be increased linearly with the SNR (in dB) in
order to achieve the full multiplexing gain, which is in sharp contrast to
point-to-point MIMO systems in which it is not necessary to increase the
feedback rate as a function of the SNR.


title: A Feedback Reduction Technique for MIMO Broadcast Channels

abstract:
  A multiple antenna broadcast channel with perfect channel state information
at the receivers is considered. If each receiver quantizes its channel
knowledge to a finite number of bits which are fed back to the transmitter, the
large capacity benefits of the downlink channel can be realized. However, the
required number of feedback bits per mobile must be scaled with both the number
of transmit antennas and the system SNR, and thus can be quite large in even
moderately sized systems. It is shown that a small number of antennas can be
used at each receiver to improve the quality of the channel estimate provided
to the transmitter. As a result, the required feedback rate per mobile can be
significantly decreased.


title: Implementing the Three-Stage Quantum Cryptography Protocol

abstract:
  We present simple implementations of Kak's three-stage quantum cryptography
protocol. The case where the transformation is applied to more than one qubit
at the same time is also considered.


title: Universal Lossless Compression with Unknown Alphabets - The Average Case

abstract:
  Universal compression of patterns of sequences generated by independently
identically distributed (i.i.d.) sources with unknown, possibly large,
alphabets is investigated. A pattern is a sequence of indices that contains all
consecutive indices in increasing order of first occurrence. If the alphabet of
a source that generated a sequence is unknown, the inevitable cost of coding
the unknown alphabet symbols can be exploited to create the pattern of the
sequence. This pattern can in turn be compressed by itself. It is shown that if
the alphabet size $k$ is essentially small, then the average minimax and
maximin redundancies as well as the redundancy of every code for almost every
source, when compressing a pattern, consist of at least 0.5 log(n/k^3) bits per
each unknown probability parameter, and if all alphabet letters are likely to
occur, there exist codes whose redundancy is at most 0.5 log(n/k^2) bits per
each unknown probability parameter, where n is the length of the data
sequences. Otherwise, if the alphabet is large, these redundancies are
essentially at least O(n^{-2/3}) bits per symbol, and there exist codes that
achieve redundancy of essentially O(n^{-1/2}) bits per symbol. Two sub-optimal
low-complexity sequential algorithms for compression of patterns are presented
and their description lengths analyzed, also pointing out that the pattern
average universal description length can decrease below the underlying i.i.d.\
entropy for large enough alphabets.


title:
The neighbor-scattering number can be computed in polynomial time for
  interval graphs

abstract:
  Neighbor-scattering number is a useful measure for graph vulnerability. For
some special kinds of graphs, explicit formulas are given for this number.
However, for general graphs it is shown that to compute this number is
NP-complete. In this paper, we prove that for interval graphs this number can
be computed in polynomial time.


title: Predicting the Path of an Open System

abstract:
  The expected path of an open system,which is a big Poincare system,has been
found in this paper.This path has been obtained from the actual and from the
expected droop of the open system.The actual droop has been reconstructed from
the variations in the power and in the frequency of the open system.The
expected droop has been found as a function of rotation from the expected
potential energy of the open system under synchronization of that system.


title: An Explicit Solution to Post's Problem over the Reals

abstract:
  In the BCSS model of real number computations we prove a concrete and
explicit semi-decidable language to be undecidable yet not reducible from (and
thus strictly easier than) the real Halting Language. This solution to Post's
Problem over the reals significantly differs from its classical, discrete
variant where advanced diagonalization techniques are only known to yield the
existence of such intermediate Turing degrees. Strengthening the above result,
we construct (that is, obtain again explicitly) as well an uncountable number
of incomparable semi-decidable Turing degrees below the real Halting problem in
the BCSS model. Finally we show the same to hold for the linear BCSS model,
that is over (R,+,-,<) rather than (R,+,-,*,/,<).


title: Distributed Transmit Beamforming using Feedback Control

abstract:
  A simple feedback control algorithm is presented for distributed beamforming
in a wireless network. A network of wireless sensors that seek to cooperatively
transmit a common message signal to a Base Station (BS) is considered. In this
case, it is well-known that substantial energy efficiencies are possible by
using distributed beamforming. The feedback algorithm is shown to achieve the
carrier phase coherence required for beamforming in a scalable and distributed
manner. In the proposed algorithm, each sensor independently makes a random
adjustment to its carrier phase. Assuming that the BS is able to broadcast one
bit of feedback each timeslot about the change in received signal to noise
ratio (SNR), the sensors are able to keep the favorable phase adjustments and
discard the unfavorable ones, asymptotically achieving perfect phase coherence.
A novel analytical model is derived that accurately predicts the convergence
rate. The analytical model is used to optimize the algorithm for fast
convergence and to establish the scalability of the algorithm.


title: VXA: A Virtual Architecture for Durable Compressed Archives

abstract:
  Data compression algorithms change frequently, and obsolete decoders do not
always run on new hardware and operating systems, threatening the long-term
usability of content archived using those algorithms. Re-encoding content into
new formats is cumbersome, and highly undesirable when lossy compression is
involved. Processor architectures, in contrast, have remained comparatively
stable over recent decades. VXA, an archival storage system designed around
this observation, archives executable decoders along with the encoded content
it stores. VXA decoders run in a specialized virtual machine that implements an
OS-independent execution environment based on the standard x86 architecture.
The VXA virtual machine strictly limits access to host system services, making
decoders safe to run even if an archive contains malicious code. VXA's adoption
of a "native" processor architecture instead of type-safe language technology
allows reuse of existing "hand-optimized" decoders in C and assembly language,
and permits decoders access to performance-enhancing architecture features such
as vector processing instructions. The performance cost of VXA's virtualization
is typically less than 15% compared with the same decoders running natively.
The storage cost of archived decoders, typically 30-130KB each, can be
amortized across many archived files sharing the same compression method.


title: Peer-to-Peer Communication Across Network Address Translators

abstract:
  Network Address Translation (NAT) causes well-known difficulties for
peer-to-peer (P2P) communication, since the peers involved may not be reachable
at any globally valid IP address. Several NAT traversal techniques are known,
but their documentation is slim, and data about their robustness or relative
merits is slimmer. This paper documents and analyzes one of the simplest but
most robust and practical NAT traversal techniques, commonly known as "hole
punching." Hole punching is moderately well-understood for UDP communication,
but we show how it can be reliably used to set up peer-to-peer TCP streams as
well. After gathering data on the reliability of this technique on a wide
variety of deployed NATs, we find that about 82% of the NATs tested support
hole punching for UDP, and about 64% support hole punching for TCP streams. As
NAT vendors become increasingly conscious of the needs of important P2P
applications such as Voice over IP and online gaming protocols, support for
hole punching is likely to increase in the future.


title: Unmanaged Internet Protocol: Taming the Edge Network Management Crisis

abstract:
  Though appropriate for core Internet infrastructure, the Internet Protocol is
unsuited to routing within and between emerging ad-hoc edge networks due to its
dependence on hierarchical, administratively assigned addresses. Existing
ad-hoc routing protocols address the management problem but do not scale to
Internet-wide networks. The promise of ubiquitous network computing cannot be
fulfilled until we develop an Unmanaged Internet Protocol (UIP), a scalable
routing protocol that manages itself automatically. UIP must route within and
between constantly changing edge networks potentially containing millions or
billions of nodes, and must still function within edge networks disconnected
from the main Internet, all without imposing the administrative burden of
hierarchical address assignment. Such a protocol appears challenging but
feasible. We propose an architecture based on self-certifying, cryptographic
node identities and a routing algorithm adapted from distributed hash tables.


title: User-Relative Names for Globally Connected Personal Devices

abstract:
  Nontechnical users who own increasingly ubiquitous network-enabled personal
devices such as laptops, digital cameras, and smart phones need a simple,
intuitive, and secure way to share information and services between their
devices. User Information Architecture, or UIA, is a novel naming and
peer-to-peer connectivity architecture addressing this need. Users assign UIA
names by "introducing" devices to each other on a common local-area network,
but these names remain securely bound to their target as devices migrate.
Multiple devices owned by the same user, once introduced, automatically merge
their namespaces to form a distributed "personal cluster" that the owner can
access or modify from any of his devices. Instead of requiring users to
allocate globally unique names from a central authority, UIA enables users to
assign their own "user-relative" names both to their own devices and to other
users. With UIA, for example, Alice can always access her iPod from any of her
own personal devices at any location via the name "ipod", and her friend Bob
can access her iPod via a relative name like "ipod.Alice".


title: Packrat Parsing: Simple, Powerful, Lazy, Linear Time

abstract:
  Packrat parsing is a novel technique for implementing parsers in a lazy
functional programming language. A packrat parser provides the power and
flexibility of top-down parsing with backtracking and unlimited lookahead, but
nevertheless guarantees linear parse time. Any language defined by an LL(k) or
LR(k) grammar can be recognized by a packrat parser, in addition to many
languages that conventional linear-time algorithms do not support. This
additional power simplifies the handling of common syntactic idioms such as the
widespread but troublesome longest-match rule, enables the use of sophisticated
disambiguation strategies such as syntactic and semantic predicates, provides
better grammar composition properties, and allows lexical analysis to be
integrated seamlessly into parsing. Yet despite its power, packrat parsing
shares the same simplicity and elegance as recursive descent parsing; in fact
converting a backtracking recursive descent parser into a linear-time packrat
parser often involves only a fairly straightforward structural change. This
paper describes packrat parsing informally with emphasis on its use in
practical applications, and explores its advantages and disadvantages with
respect to the more conventional alternatives.


title: Consensus Propagation

abstract:
  We propose consensus propagation, an asynchronous distributed protocol for
averaging numbers across a network. We establish convergence, characterize the
convergence rate for regular graphs, and demonstrate that the protocol exhibits
better scaling properties than pairwise averaging, an alternative that has
received much recent attention. Consensus propagation can be viewed as a
special case of belief propagation, and our results contribute to the belief
propagation literature. In particular, beyond singly-connected graphs, there
are very few classes of relevant problems for which belief propagation is known
to converge.


title: A compositional Semantics for CHR

abstract:
  Constraint Handling Rules (CHR) are a committed-choice declarative language
which has been designed for writing constraint solvers. A CHR program consists
of multi-headed guarded rules which allow one to rewrite constraints into
simpler ones until a solved form is reached.
  CHR has received a considerable attention, both from the practical and from
the theoretical side. Nevertheless, due the use of multi-headed clauses, there
are several aspects of the CHR semantics which have not been clarified yet. In
particular, no compositional semantics for CHR has been defined so far.
  In this paper we introduce a fix-point semantics which characterizes the
input/output behavior of a CHR program and which is and-compositional, that is,
which allows to retrieve the semantics of a conjunctive query from the
semantics of its components. Such a semantics can be used as a basis to define
incremental and modular analysis and verification tools.


title: Yet Another Efficient Unification Algorithm

abstract:
  The unification algorithm is at the core of the logic programming paradigm,
the first unification algorithm being developed by Robinson [5]. More efficient
algorithms were developed later [3] and I introduce here yet another efficient
unification algorithm centered on a specific data structure, called the
Unification Table.


title:
Application of Support Vector Regression to Interpolation of Sparse
  Shock Physics Data Sets

abstract:
  Shock physics experiments are often complicated and expensive. As a result,
researchers are unable to conduct as many experiments as they would like -
leading to sparse data sets. In this paper, Support Vector Machines for
regression are applied to velocimetry data sets for shock damaged and melted
tin metal. Some success at interpolating between data sets is achieved.
Implications for future work are discussed.


title: Solving Sparse Integer Linear Systems

abstract:
  We propose a new algorithm to solve sparse linear systems of equations over
the integers. This algorithm is based on a $p$-adic lifting technique combined
with the use of block matrices with structured blocks. It achieves a sub-cubic
complexity in terms of machine operations subject to a conjecture on the
effectiveness of certain sparse projections. A LinBox-based implementation of
this algorithm is demonstrated, and emphasizes the practical benefits of this
new method over the previous state of the art.


title: Entropy-optimal Generalized Token Bucket Regulator

abstract:
  We derive the maximum entropy of a flow (information utility) which conforms
to traffic constraints imposed by a generalized token bucket regulator, by
taking into account the covert information present in the randomness of packet
lengths. Under equality constraints of aggregate tokens and aggregate bucket
depth, a generalized token bucket regulator can achieve higher information
utility than a standard token bucket regulator. The optimal generalized token
bucket regulator has a near-uniform bucket depth sequence and a decreasing
token increment sequence.


title: Random 3CNF formulas elude the Lovasz theta function

abstract:
  Let $\phi$ be a 3CNF formula with n variables and m clauses. A simple
nonconstructive argument shows that when m is sufficiently large compared to n,
most 3CNF formulas are not satisfiable. It is an open question whether there is
an efficient refutation algorithm that for most such formulas proves that they
are not satisfiable. A possible approach to refute a formula $\phi$ is: first,
translate it into a graph $G_{\phi}$ using a generic reduction from 3-SAT to
max-IS, then bound the maximum independent set of $G_{\phi}$ using the Lovasz
$\vartheta$ function. If the $\vartheta$ function returns a value $< m$, this
is a certificate for the unsatisfiability of $\phi$. We show that for random
formulas with $m < n^{3/2 -o(1)}$ clauses, the above approach fails, i.e. the
$\vartheta$ function is likely to return a value of m.


title: Access Control for Hierarchical Joint-Tenancy

abstract:
  Basic role based access control [RBAC] provides a mechanism for segregating
access privileges based upon a user's hierarchical roles within an
organization. This model doesn't scale well when there is tight integration of
multiple hierarchies. In a case where there is joint-tenancy and a requirement
for different levels of disclosure based upon a user's hierarchy, or in our
case, organization or company, basic RBAC requires these hierarchies to be
effectively merged. Specific roles that effectively represent both the user's
organizations and roles must be translated to fit within the merged hierarchy
to be used to control access. Essentially, users from multiple organizations
are served from a single role base with roles designed to constrain their
access as needed.
  Our work proposes, through parameterized roles and privileges, a means for
accurately representing both users' roles within their respective hierarchies
for providing access to controlled objects. Using this method will reduce the
amount of complexity required in terms of the number of roles and privileges.
The resulting set of roles, privileges, and objects will make modeling and
visualizing the access role hierarchy significantly simplified. This paper will
give some background on role based access control, parameterized roles and
privileges, and then focus on how RBAC with parameterized roles and privileges
can be leveraged as an access control solution for the problems presented by
joint tenancy.


title: Matching Edges in Images ; Application to Face Recognition

abstract:
  This communication describes a representation of images as a set of edges
characterized by their position and orientation. This representation allows the
comparison of two images and the computation of their similarity. The first
step in this computation of similarity is the seach of a geometrical basis of
the two dimensional space where the two images are represented simultaneously
after transformation of one of them. Presently, this simultaneous
representation takes into account a shift and a scaling ; it may be extended to
rotations or other global geometrical transformations. An elementary
probabilistic computation shows that a sufficient but not excessive number of
trials (a few tens) ensures that the exhibition of this common basis is
guaranteed in spite of possible errors in the detection of edges. When this
first step is performed, the search of similarity between the two images
reduces to counting the coincidence of edges in the two images. The approach
may be applied to many problems of pattern matching ; it was checked on face
recognition.


title:
IP over P2P: Enabling Self-configuring Virtual IP Networks for Grid
  Computing

abstract:
  Peer-to-peer (P2P) networks have mostly focused on task oriented networking,
where networks are constructed for single applications, i.e. file-sharing, DNS
caching, etc. In this work, we introduce IPOP, a system for creating virtual IP
networks on top of a P2P overlay. IPOP enables seamless access to Grid
resources spanning multiple domains by aggregating them into a virtual IP
network that is completely isolated from the physical network. The virtual IP
network provided by IPOP supports deployment of existing IP-based protocols
over a robust, self-configuring P2P overlay. We present implementation details
as well as experimental measurement results taken from LAN, WAN, and Planet-Lab
tests.


title:
Novel BCD Adders and Their Reversible Logic Implementation for IEEE 754r
  Format

abstract:
  IEEE 754r is the ongoing revision to the IEEE 754 floating point standard and
a major enhancement to the standard is the addition of decimal format. This
paper proposes two novel BCD adders called carry skip and carry look-ahead BCD
adders respectively. Furthermore, in the recent years, reversible logic has
emerged as a promising technology having its applications in low power CMOS,
quantum computing, nanotechnology, and optical computing. It is not possible to
realize quantum computing without reversible logic. Thus, this paper also paper
provides the reversible logic implementation of the conventional BCD adder as
the well as the proposed Carry Skip BCD adder using a recently proposed TSG
gate. Furthermore, a new reversible gate called TS-3 is also being proposed and
it has been shown that the proposed reversible logic implementation of the BCD
Adders is much better compared to recently proposed one, in terms of number of
reversible gates used and garbage outputs produced. The reversible BCD circuits
designed and proposed here form the basis of the decimal ALU of a primitive
quantum CPU.


title: Convex Separation from Optimization via Heuristics

abstract:
  Let $K$ be a full-dimensional convex subset of $\mathbb{R}^n$. We describe a
new polynomial-time Turing reduction from the weak separation problem for $K$
to the weak optimization problem for $K$ that is based on a geometric
heuristic. We compare our reduction, which relies on analytic centers, with the
standard, more general reduction.


title: Topological Grammars for Data Approximation

abstract:
  A method of {\it topological grammars} is proposed for multidimensional data
approximation. For data with complex topology we define a {\it principal cubic
complex} of low dimension and given complexity that gives the best
approximation for the dataset. This complex is a generalization of linear and
non-linear principal manifolds and includes them as particular cases. The
problem of optimal principal complex construction is transformed into a series
of minimization problems for quadratic functionals. These quadratic functionals
have a physically transparent interpretation in terms of elastic energy. For
the energy computation, the whole complex is represented as a system of nodes
and springs. Topologically, the principal complex is a product of
one-dimensional continuums (represented by graphs), and the grammars describe
how these continuums transform during the process of optimal complex
construction. This factorization of the whole process onto one-dimensional
transformations using minimization of quadratic energy functionals allow us to
construct efficient algorithms.


title:
A New Reversible TSG Gate and Its Application For Designing Efficient
  Adder Circuits

abstract:
  In the recent years, reversible logic has emerged as a promising technology
having its applications in low power CMOS, quantum computing, nanotechnology,
and optical computing. The classical set of gates such as AND, OR, and EXOR are
not reversible. This paper proposes a new 4 * 4 reversible gate called TSG
gate. The proposed gate is used to design efficient adder units. The most
significant aspect of the proposed gate is that it can work singly as a
reversible full adder i.e reversible full adder can now be implemented with a
single gate only. The proposed gate is then used to design reversible ripple
carry and carry skip adders. It is demonstrated that the adder architectures
designed using the proposed gate are much better and optimized, compared to
their existing counterparts in literature; in terms of number of reversible
gates and garbage outputs. Thus, this paper provides the initial threshold to
building of more complex system which can execute more complicated operations
using reversible logic.


title:
An Extension to DNA Based Fredkin Gate Circuits: Design of Reversible
  Sequential Circuits using Fredkin Gates

abstract:
  In recent years, reversible logic has emerged as a promising computing
paradigm having its applications in low power computing, quantum computing,
nanotechnology, optical computing and DNA computing. The classical set of gates
such as AND, OR, and EXOR are not reversible. Recently, it has been shown how
to encode information in DNA and use DNA amplification to implement Fredkin
gates. Furthermore, in the past Fredkin gates have been constructed using DNA,
whose outputs are used as inputs for other Fredkin gates. Thus, it can be
concluded that arbitrary circuits of Fredkin gates can be constructed using
DNA. This paper provides the initial threshold to building of more complex
system having reversible sequential circuits and which can execute more
complicated operations. The novelty of the paper is the reversible designs of
sequential circuits using Fredkin gate. Since, Fredkin gate has already been
realized using DNA, it is expected that this work will initiate the building of
complex systems using DNA. The reversible circuits designed here are highly
optimized in terms of number of gates and garbage outputs. The modularization
approach that is synthesizing small circuits and thereafter using them to
construct bigger circuits is used for designing the optimal reversible
sequential circuits.


title:
About the domino problem in the hyperbolic plane from an algorithmic
  point of view

abstract:
  In this paper, we prove that the general problem of tiling the hyperbolic
plane with \`a la Wang tiles is undecidable.


title:
On the Capacity Achieving Transmit Covariance Matrices of MIMO
  Correlated Rician Channels: A Large System Approach

abstract:
  We determine the capacity-achieving input covariance matrices for coherent
block-fading correlated MIMO Rician channels. In contrast with the Rayleigh and
uncorrelated Rician cases, no closed-form expressions for the eigenvectors of
the optimum input covariance matrix are available. Both the eigenvectors and
eigenvalues have to be evaluated by using numerical techniques. As the
corresponding optimization algorithms are not very attractive, we evaluate the
limit of the average mutual information when the number of transmit and receive
antennas converge to infinity at the same rate. If the channel is
semi-correlated, we propose an attractive optimization algorithm of the large
system approximant, and establish some convergence results. Simulation results
show that our approach provide reliable results even for a quite moderate
number of transmit and receive antennas.


title: A Turbo Coding System for High Speed Communications

abstract:
  Conventional turbo codes (CTCs) usually employ a block-oriented interleaving
so that each block is separately encoded and decoded. As interleaving and
de-interleaving are performed within a block, the message-passing process
associated with an iterative decoder is limited to proceed within the
corresponding range. This paper presents a new turbo coding scheme that uses a
special interleaver structure and a multiple-round early termination test
involving both sign check and a CRC code. The new interleaver structure is
naturally suited for high speed parallel processing and the resulting coding
system offers new design options and tradeoffs that are not available to CTCs.
In particular, it becomes possible for the decoder to employ an efficient
inter-block collaborative decoding algorithm, passing the information obtained
from termination test proved blocks to other unproved blocks. It also becomes
important to have a proper decoding schedule. The combined effect is improved
performance and reduction in the average decoding delay (whence the required
computing power). A memory (storage) management mechanism is included as a
critical part of the decoder so as to provide additional design tradeoff
between performance and memory size. It is shown that the latter has a
modular-like effect in that additional memory units render enhanced performance
due not only to less forced early terminations but to possible increases of the
interleaving depth. Depending on the decoding schedule, the degree of
parallelism and other decoding resources available, the proposed scheme admits
a variety of decoder architectures that meet a large range of throughput and
performance demands.


title: On Reduced Complexity Soft-Output MIMO ML detection

abstract:
  In multiple-input multiple-output (MIMO) fading channels maximum likelihood
(ML) detection is desirable to achieve high performance, but its complexity
grows exponentially with the spectral efficiency. The current state of the art
in MIMO detection is list decoding and lattice decoding. This paper proposes a
new class of lattice detectors that combines some of the principles of both
list and lattice decoding, thus resulting in an efficient parallelizable
implementation and near optimal soft-ouput ML performance. The novel detector
is called layered orthogonal lattice detector (LORD), because it adopts a new
lattice formulation and relies on a channel orthogonalization process. It
should be noted that the algorithm achieves optimal hard-output ML performance
in case of two transmit antennas. For two transmit antennas max-log bit
soft-output information can be generated and for greater than two antennas
approximate max-log detection is achieved. Simulation results show that LORD,
in MIMO system employing orthogonal frequency division multiplexing (OFDM) and
bit interleaved coded modulation (BICM) is able to achieve very high
signal-to-noise ratio (SNR) gains compared to practical soft-output detectors
such as minimum-mean square error (MMSE), in either linear or nonlinear
iterative scheme. Besides, the performance comparison with hard-output decoded
algebraic space time codes shows the fundamental importance of soft-output
generation capability for practical wireless applications.


title:
On Pinsker's Type Inequalities and Csiszar's f-divergences. Part I:
  Second and Fourth-Order Inequalities

abstract:
  We study conditions on $f$ under which an $f$-divergence $D_f$ will satisfy
$D_f \geq c_f V^2$ or $D_f \geq c_{2,f} V^2 + c_{4,f} V^4$, where $V$ denotes
variational distance and the coefficients $c_f$, $c_{2,f}$ and $c_{4,f}$ are
{\em best possible}. As a consequence, we obtain lower bounds in terms of $V$
for many well known distance and divergence measures. For instance, let
$D_{(\alpha)} (P,Q) = [\alpha (\alpha-1)]^{-1} [\int q^{\alpha} p^{1-\alpha} d
\mu -1]$ and ${\cal I}_\alpha (P,Q) = (\alpha -1)^{-1} \log [\int p^\alpha
q^{1-\alpha} d \mu]$ be respectively the {\em relative information of type}
($1-\alpha$) and {\em R\'{e}nyi's information gain of order} $\alpha$. We show
that $D_{(\alpha)} \geq {1/2} V^2 + {1/72} (\alpha+1)(2-\alpha) V^4$ whenever
$-1 \leq \alpha \leq 2$, $\alpha \not= 0,1$ and that ${\cal I}_{\alpha} =
\frac{\alpha}{2} V^2 + {1/36} \alpha (1 + 5 \alpha - 5 \alpha^2) V^4$ for $0 <
\alpha < 1$. Pinsker's inequality $D \geq {1/2}
  V^2$ and its extension $D \geq {1/2} V^2 + {1/36} V^4$ are special cases of
each one of these.


title: A SIMO Fiber Aided Wireless Network Architecture

abstract:
  The concept of a fiber aided wireless network architecture (FAWNA) is
introduced in [Ray et al., Allerton Conference 2005], which allows high-speed
mobile connectivity by leveraging the speed of optical networks. In this paper,
we consider a single-input, multiple-output (SIMO) FAWNA, which consists of a
SIMO wireless channel and an optical fiber channel, connected through
wireless-optical interfaces. We propose a scheme where the received wireless
signal at each interface is quantized and sent over the fiber. Though our
architecture is similar to that of the classical CEO problem, our problem is
different from it. We show that the capacity of our scheme approaches the
capacity of the architecture, exponentially with fiber capacity. We also show
that for a given fiber capacity, there is an optimal operating wireless
bandwidth and an optimal number of wireless-optical interfaces. The
wireless-optical interfaces of our scheme have low complexity and do not
require knowledge of the transmitter code book. They are also extendable to
FAWNAs with large number of transmitters and interfaces and, offer adaptability
to variable rates, changing channel conditions and node positions.


title: Benchmark Problems for Constraint Solving

abstract:
  Constraint Programming is roughly a new software technology introduced by
Jaffar and Lassez in 1987 for description and effective solving of large,
particularly combinatorial, problems especially in areas of planning and
scheduling. In the following we define three problems for constraint solving
from the domain of electrical networks; based on them we define 43 related
problems. For the defined set of problems we benchmarked five systems: ILOG
OPL, AMPL, GAMS, Mathematica and UniCalc. As expected some of the systems
performed very well for some problems while others performed very well on
others.


title: Efficient Compression of Prolog Programs

abstract:
  We propose a special-purpose class of compression algorithms for efficient
compression of Prolog programs. It is a dictionary-based compression method,
specially designed for the compression of Prolog code, and therefore we name it
PCA (Prolog Compression Algorithm). According to the experimental results this
method provides better compression than state-of-the-art general-purpose
compression algorithms. Since the algorithm works with Prolog syntactic
entities (e.g. atoms, terms, etc.) the implementation of a Prolog prototype is
straightforward and very easy to use in any Prolog application that needs
compression. Although the algorithm is designed for Prolog programs, the idea
can be easily applied for the compression of programs written in other (logic)
languages.


title: Prolog Server Pages

abstract:
  Prolog Server Pages (PSP) is a scripting language, based on Prolog, than can
be embedded in HTML documents. To run PSP applications one needs a web server,
a web browser and a PSP interpreter. The code is executed, by the interpreter,
on the server-side (web server) and the output (together with the html code in
witch the PSP code is embedded) is sent to the client-side (browser). The
current implementation supports Apache Web Server. We implemented an Apache web
server module that handles PSP files, and sends the result (an html document)
to the client. PSP supports both GET and POST http requests. It also provides
methods for working with http cookies.


title: Enhanced Prolog Remote Predicate Call Protocol

abstract:
  Following the ideas of the Remote Procedure Call model, we have developed a
logic programming counterpart, naturally called Prolog Remote Predicate Call
(Prolog RPC). The Prolog RPC protocol facilitates the integration of Prolog
code in multi-language applications as well as the development of distributed
intelligent applications. One use of the protocol's most important uses could
be the development of distributed applications that use Prolog at least
partially to achieve their goals. Most notably the Distributed Artificial
Intelligence (DAI) applications that are suitable for logic programming can
profit from the use of the protocol. After proving its usefulness, we went
further, developing a new version of the protocol, making it more reliable and
extending its functionality. Because it has a new syntax and the new set of
commands, we call this version Enhanced Prolog Remote Procedure Call. This
paper describes the new features and modifications this second version
introduced.