title:
Energy-Efficient Power and Rate Control with QoS Constraints: A
  Game-Theoretic Approach

abstract:
  A game-theoretic model is proposed to study the cross-layer problem of joint
power and rate control with quality of service (QoS) constraints in
multiple-access networks. In the proposed game, each user seeks to choose its
transmit power and rate in a distributed manner in order to maximize its own
utility and at the same time satisfy its QoS requirements. The user's QoS
constraints are specified in terms of the average source rate and average
delay. The utility function considered here measures energy efficiency and the
delay includes both transmission and queueing delays. The Nash equilibrium
solution for the proposed non-cooperative game is derived and a closed-form
expression for the utility achieved at equilibrium is obtained. It is shown
that the QoS requirements of a user translate into a "size" for the user which
is an indication of the amount of network resources consumed by the user. Using
this framework, the tradeoffs among throughput, delay, network capacity and
energy efficiency are also studied.


title:
Optimum Asymptotic Multiuser Efficiency of Pseudo-Orthogonal Randomly
  Spread CDMA

abstract:
  A $K$-user pseudo-orthogonal (PO) randomly spread CDMA system, equivalent to
transmission over a subset of $K'\leq K$ single-user Gaussian channels, is
introduced. The high signal-to-noise ratio performance of the PO-CDMA is
analyzed by rigorously deriving its asymptotic multiuser efficiency (AME) in
the large system limit. Interestingly, the $K'$-optimized PO-CDMA transceiver
scheme yields an AME which is practically equal to 1 for system loads smaller
than 0.1 and lower bounded by 1/4 for increasing loads. As opposed to the
vanishing efficiency of linear multiuser detectors, the derived efficiency is
comparable to the ultimate CDMA efficiency achieved for the intractable optimal
multiuser detector.


title:
A Recursive Method for Determining the One-Dimensional Submodules of
  Laurent-Ore Modules

abstract:
  We present a method for determining the one-dimensional submodules of a
Laurent-Ore module. The method is based on a correspondence between
hyperexponential solutions of associated systems and one-dimensional
submodules. The hyperexponential solutions are computed recursively by solving
a sequence of first-order ordinary matrix equations. As the recursion proceeds,
the matrix equations will have constant coefficients with respect to the
operators that have been considered.


title: Information in Quantum Description and Gate Implementation

abstract:
  This note considers Kak's observer-reference model of quantum information,
where it is shown that qubits carry information that is sqrt n / ln n times
classical information, where n is the number of components in the measurement
system, to analyze information processing in quantum gates. The obverse side of
this exponential nature of quantum information is that the computational
complexity of implementing unconditionally reliable quantum gates is also
exponential.


title: A Knowledge-Based Approach for Selecting Information Sources

abstract:
  Through the Internet and the World-Wide Web, a vast number of information
sources has become available, which offer information on various subjects by
different providers, often in heterogeneous formats. This calls for tools and
methods for building an advanced information-processing infrastructure. One
issue in this area is the selection of suitable information sources in query
answering. In this paper, we present a knowledge-based approach to this
problem, in the setting where one among a set of information sources
(prototypically, data repositories) should be selected for evaluating a user
query. We use extended logic programs (ELPs) to represent rich descriptions of
the information sources, an underlying domain theory, and user queries in a
formal query language (here, XML-QL, but other languages can be handled as
well). Moreover, we use ELPs for declarative query analysis and generation of a
query description. Central to our approach are declarative source-selection
programs, for which we define syntax and semantics. Due to the structured
nature of the considered data items, the semantics of such programs must
carefully respect implicit context information in source-selection rules, and
furthermore combine it with possible user preferences. A prototype
implementation of our approach has been realized exploiting the DLV KR system
and its plp front-end for prioritized ELPs. We describe a representative
example involving specific movie databases, and report about experimental
results.


title: Probabilistic Automata for Computing with Words

abstract:
  Usually, probabilistic automata and probabilistic grammars have crisp symbols
as inputs, which can be viewed as the formal models of computing with values.
In this paper, we first introduce probabilistic automata and probabilistic
grammars for computing with (some special) words in a probabilistic framework,
where the words are interpreted as probabilistic distributions or possibility
distributions over a set of crisp symbols. By probabilistic conditioning, we
then establish a retraction principle from computing with words to computing
with values for handling crisp inputs and a generalized extension principle
from computing with words to computing with all words for handling arbitrary
inputs. These principles show that computing with values and computing with all
words can be respectively implemented by computing with some special words. To
compare the transition probabilities of two near inputs, we also examine some
analytical properties of the transition probability functions of generalized
extensions. Moreover, the retractions and the generalized extensions are shown
to be equivalence-preserving. Finally, we clarify some relationships among the
retractions, the generalized extensions, and the extensions studied recently by
Qiu and Wang.


title: How to Run Mathematica Batch-files in Background ?

abstract:
  Mathematica is a versatile equipment for doing numeric and symbolic
computations and it has wide spread applications in all branches of science.
Mathematica has a complete consistency to design it at every stage that gives
it multilevel capability and helps advanced usage evolve naturally. Mathematica
functions work for any precision of number and it can be easily computed with
symbols, represented graphically to get the best answer. Mathematica is a
robust software development that can be used in any popular operating systems
and it can be communicated with external programs by using proper mathlink
commands.
  Sometimes it is quite desirable to run jobs in background of a computer which
can take considerable amount of time to finish, and this allows us to do work
on other tasks, while keeping the jobs running. Most of us are very familiar to
run jobs in background for the programs written in the languages like C, C++,
F77, F90, F95, etc. But the way of running jobs, written in a mathematica
notebook, in background is quite different from the conventional method. In
this article, we explore how to create a mathematica batch-file from a
mathematica notebook and run it in background. Here we concentrate our study
only for the Unix version, but one can run mathematica programs in background
for the Windows version as well by using proper mathematica batch-file.


title: Evolutionary Socioeconomics: a Schumpeterian Computer Simulation

abstract:
  The following note contains a computer simulation concerning the struggle
between two companies: the first one is "the biggest zaibatsu of all", while
the second one is "small, fast, ruthless". The model is based on a
neo-Schumpeterian framework operating in a Darwinian evolutionary environment.
After running the program a large number of times, two characteristics stand
out: -- There is always a winner which takes it all, while the loser
disappears. -- The key to success is the ability to employ efficiently the
technological innovations. The topic of the present paper is strictly related
with the content of the following notes: Michele Tucci, Evolution and
Gravitation: a Computer Simulation of a Non-Walrasian Equilibrium Model;
Michele Tucci, Oligopolistic Competition in an Evolutionary Environment: a
Computer Simulation. The texts can be downloaded respectively at the following
addresses: http://arxiv.org/abs/cs.CY/0209017
http://arxiv.org/abs/cs.CY/0501037 These references include some preliminary
considerations regarding the comparison between the evolutionary and the
gravitational paradigms and the evaluation of approaches belonging to rival
schools of economic thought.


title: Simplicial models of social aggregation I

abstract:
  This paper presents the foundational ideas for a new way of modeling social
aggregation. Traditional approaches have been using network theory, and the
theory of random networks. Under that paradigm, every social agent is
represented by a node, and every social interaction is represented by a segment
connecting two nodes. Early work in family interactions, as well as more recent
work in the study of terrorist organizations, shows that network modeling may
be insufficient to describe the complexity of human social structures.
Specifically, network theory does not seem to have enough flexibility to
represent higher order aggregations, where several agents interact as a group,
rather than as a collection of pairs. The model we present here uses a well
established mathematical theory, the theory of simplicial complexes, to address
this complex issue prevalent in interpersonal and intergroup communication. The
theory enables us to provide a richer graphical representation of social
interactions, and to determine quantitative mechanisms to describe the
robustness of a social structure. We also propose a methodology to create
random simplicial complexes, with the purpose of providing a new method to
simulate computationally the creation and disgregation of social structures.
Finally, we propose several measures which could be taken and observed in order
to describe and study an actual social aggregation occurring in interpersonal
and intergroup contexts.


title: Robust Distributed Source Coding

abstract:
  We consider a distributed source coding system in which several observations
are communicated to the decoder using limited transmission rate. The
observations must be separately coded. We introduce a robust distributed coding
scheme which flexibly trades off between system robustness and compression
efficiency. The optimality of this coding scheme is proved for various special
cases.


title:
Optimal and Suboptimal Finger Selection Algorithms for MMSE Rake
  Receivers in Impulse Radio UWB Systems

abstract:
  The problem of choosing the optimal multipath components to be employed at a
minimum mean square error (MMSE) selective Rake receiver is considered for an
impulse radio ultra-wideband system. First, the optimal finger selection
problem is formulated as an integer programming problem with a non-convex
objective function. Then, the objective function is approximated by a convex
function and the integer programming problem is solved by means of constraint
relaxation techniques. The proposed algorithms are suboptimal due to the
approximate objective function and the constraint relaxation steps. However,
they perform better than the conventional finger selection algorithm, which is
suboptimal since it ignores the correlation between multipath components, and
they can get quite close to the optimal scheme that cannot be implemented in
practice due to its complexity. In addition to the convex relaxation
techniques, a genetic algorithm (GA) based approach is proposed, which does not
need any approximations or integer relaxations. This iterative algorithm is
based on the direct evaluation of the objective function, and can achieve
near-optimal performance with a reasonable number of iterations. Simulation
results are presented to compare the performance of the proposed finger
selection algorithms with that of the conventional and the optimal schemes.


title: Perfect Space Time Block Codes

abstract:
  In this paper, we introduce the notion of perfect space-time block codes
(STBC). These codes have full rate, full diversity, non-vanishing constant
minimum determinant for increasing spectral efficiency, uniform average
transmitted energy per antenna and good shaping. We present algebraic
constructions of perfect STBCs for 2, 3, 4 and 6 antennas.


title:
A Fast and Accurate Nonlinear Spectral Method for Image Recognition and
  Registration

abstract:
  This article addresses the problem of two- and higher dimensional pattern
matching, i.e. the identification of instances of a template within a larger
signal space, which is a form of registration. Unlike traditional correlation,
we aim at obtaining more selective matchings by considering more strict
comparisons of gray-level intensity. In order to achieve fast matching, a
nonlinear thresholded version of the fast Fourier transform is applied to a
gray-level decomposition of the original 2D image. The potential of the method
is substantiated with respect to real data involving the selective
identification of neuronal cell bodies in gray-level images.


title: Fixed-Parameter Complexity of Minimum Profile Problems

abstract:
  Let $G=(V,E)$ be a graph. An ordering of $G$ is a bijection $\alpha: V\dom
\{1,2,..., |V|\}.$ For a vertex $v$ in $G$, its closed neighborhood is
$N[v]=\{u\in V: uv\in E\}\cup \{v\}.$ The profile of an ordering $\alpha$ of
$G$ is $\prf_{\alpha}(G)=\sum_{v\in V}(\alpha(v)-\min\{\alpha(u): u\in
N[v]\}).$ The profile $\prf(G)$ of $G$ is the minimum of $\prf_{\alpha}(G)$
over all orderings $\alpha$ of $G$. It is well-known that $\prf(G)$ is the
minimum number of edges in an interval graph $H$ that contains $G$ is a
subgraph. Since $|V|-1$ is a tight lower bound for the profile of connected
graphs $G=(V,E)$, the parametrization above the guaranteed value $|V|-1$ is of
particular interest. We show that deciding whether the profile of a connected
graph $G=(V,E)$ is at most $|V|-1+k$ is fixed-parameter tractable with respect
to the parameter $k$. We achieve this result by reduction to a problem kernel
of linear size.


title: Polynomial-time algorithms for coding across multiple unicasts

abstract:
  We consider the problem of network coding across multiple unicasts. We give,
for wired and wireless networks, efficient polynomial time algorithms for
finding optimal network codes within the class of network codes restricted to
XOR coding between pairs of flows.


title: Approximation algorithms for wavelet transform coding of data streams

abstract:
  This paper addresses the problem of finding a B-term wavelet representation
of a given discrete function $f \in \real^n$ whose distance from f is
minimized. The problem is well understood when we seek to minimize the
Euclidean distance between f and its representation. The first known algorithms
for finding provably approximate representations minimizing general $\ell_p$
distances (including $\ell_\infty$) under a wide variety of compactly supported
wavelet bases are presented in this paper. For the Haar basis, a polynomial
time approximation scheme is demonstrated. These algorithms are applicable in
the one-pass sublinear-space data stream model of computation. They generalize
naturally to multiple dimensions and weighted norms. A universal representation
that provides a provable approximation guarantee under all p-norms
simultaneously; and the first approximation algorithms for bit-budget versions
of the problem, known as adaptive quantization, are also presented. Further, it
is shown that the algorithms presented here can be used to select a basis from
a tree-structured dictionary of bases and find a B-term representation of the
given function that provably approximates its best dictionary-basis
representation.


title:
Achievable Rates for the Multiple Access Channel with Feedback and
  Correlated Sources

abstract:
  In this paper, we investigate achievable rates on the multiple access channel
with feedback and correlated sources (MACFCS). The motivation for studying the
MACFCS stems from the fact that in a sensor network, sensors collect and
transmit correlated data to a common sink. We derive two achievable rate
regions for the three-node MACFCS.


title: Myopic Coding in Wireless Networks

abstract:
  We investigate the achievable rate of data transmission from sources to sinks
through a multiple-relay network. We study achievable rates for omniscient
coding, in which all nodes are considered in the coding design at each node. We
find that, when maximizing the achievable rate, not all nodes need to
``cooperate'' with all other nodes in terms of coding and decoding. This leads
us to suggest a constrained network, whereby each node only considers a few
neighboring nodes during encoding and decoding. We term this myopic coding and
calculate achievable rates for myopic coding. We show by examples that, when
nodes transmit at low SNR, these rates are close to that achievable by
omniscient coding, when the network is unconstrained . This suggests that a
myopic view of the network might be as good as a global view. In addition,
myopic coding has the practical advantage of being more robust to topology
changes. It also mitigates the high computational complexity and large
buffer/memory requirements of omniscient coding schemes.


title:
Protocols for Kak's Cubic Cipher and Diffie-Hellman Based Asymmetric
  Oblivious Key Exchange

abstract:
  This paper presents protocols for Kak's cubic transformation and proposes a
modification to Diffie-Hellman key exchange protocol in order to achieve
asymmetric oblivious exchange of keys.


title:
Fast computation of power series solutions of systems of differential
  equations

abstract:
  We propose new algorithms for the computation of the first N terms of a
vector (resp. a basis) of power series solutions of a linear system of
differential equations at an ordinary point, using a number of arithmetic
operations which is quasi-linear with respect to N. Similar results are also
given in the non-linear case. This extends previous results obtained by Brent
and Kung for scalar differential equations of order one and two.


title: HCI and Educational Metrics as Tools for VLE Evaluation

abstract:
  The general set of HCI and Educational principles are considered and a
classification system constructed. A frequency analysis of principles is used
to obtain the most significant set. Metrics are devised to provide objective
measures of these principles and a consistent testing regime devised. These
principles are used to analyse Blackboard and Moodle.


title: Further Evaluationh of VLEs using HCI and Educational Metrics

abstract:
  Under consideration are the general set of Human computer Interaction (HCI)
and Educational principles from prominent authors in the field and the
construction of a system for evaluating Virtual Learning Environments (VLEs)
with respect to the application of these HCI and Educational Principles. A
frequency analysis of principles is used to obtain the most significant set.
Metrics are devised to provide objective measures of these principles and a
consistent testing regime is introduced. These principles are used to analyse
the University VLE Blackboard. An open source VLE is also constructed with
similar content to Blackboard courses so that a systematic comparison can be
made. HCI and Educational metrics are determined for each VLE.


title:
On the Shannon Covers of Certain Irreducible Constrained Systems of
  Finite Type

abstract:
  A construction of Crochemore, Mignosi and Restivo in the automata theory
literature gives a presentation of a finite-type constrained system (FTCS) that
is deterministic and has a relatively small number of states. This construction
is thus a good starting point for determining the minimal deterministic
presentation, known as the Shannon cover, of an FTCS. We analyze in detail the
Crochemore-Mignosi-Restivo (CMR) construction in the case when the list of
forbidden words defining the FTCS is of size at most two. We show that if the
FTCS is irreducible, then an irreducible presentation for the system can be
easily obtained by deleting a prescribed few states from the CMR presentation.
By studying the follower sets of the states in this irreducible presentation,
we are able to explicitly determine the Shannon cover in some cases. In
particular, our results show that the CMR construction directly yields the
Shannon cover in the case of an irreducible FTCS with exactly one forbidden
word, but this is not in general the case for FTCS's with two forbidden words.


title:
Jumps: Enhancing hop-count positioning in sensor networks using multiple
  coordinates

abstract:
  Positioning systems in self-organizing networks generally rely on
measurements such as delay and received signal strength, which may be difficult
to obtain and often require dedicated equipment. An alternative to such
approaches is to use simple connectivity information, that is, the presence or
absence of a link between any pair of nodes, and to extend it to hop-counts, in
order to obtain an approximate coordinate system. Such an approximation is
sufficient for a large number of applications, such as routing. In this paper,
we propose Jumps, a positioning system for those self-organizing networks in
which other types of (exact) positioning systems cannot be used or are deemed
to be too costly. Jumps builds a multiple coordinate system based solely on
nodes neighborhood knowledge. Jumps is interesting in the context of wireless
sensor networks, as it neither requires additional embedded equipment nor
relies on any nodes capabilities. While other approaches use only three
hop-count measurements to infer the position of a node, Jumps uses an arbitrary
number. We observe that an increase in the number of measurements leads to an
improvement in the localization process, without requiring a high dense
environment. We show through simulations that Jumps, when compared with
existing approaches, reduces the number of nodes sharing the same coordinates,
which paves the way for functions such as position-based routing.


title: Bounded expected delay in arithmetic coding

abstract:
  We address the problem of delay in an arithmetic coding system. Due to the
nature of the arithmetic coding process, source sequences causing arbitrarily
large encoding or decoding delays exist. This phenomena raises the question of
just how large is the expected input to output delay in these systems, i.e.,
once a source sequence has been encoded, what is the expected number of source
letters that should be further encoded to allow full decoding of that sequence.
In this paper, we derive several new upper bounds on the expected delay for a
memoryless source, which improve upon a known bound due to Gallager. The bounds
provided are uniform in the sense of being independent of the sequence's
history. In addition, we give a sufficient condition for a source to admit a
bounded expected delay, which holds for a stationary ergodic Markov source of
any order.


title: Cognitive Radio: An Information-Theoretic Perspective

abstract:
  Cognitive radios have been proposed as a means to implement efficient reuse
of the licensed spectrum. The key feature of a cognitive radio is its ability
to recognize the primary (licensed) user and adapt its communication strategy
to minimize the interference that it generates. We consider a communication
scenario in which the primary and the cognitive user wish to communicate to
different receivers, subject to mutual interference. Modeling the cognitive
radio as a transmitter with side-information about the primary transmission, we
characterize the largest rate at which the cognitive radio can reliably
communicate under the constraint that (i) no interference is created for the
primary user, and (ii) the primary encoder-decoder pair is oblivious to the
presence of the cognitive radio.


title:
An Algebraic View of the Relation between Largest Common Subtrees and
  Smallest Common Supertrees

abstract:
  The relationship between two important problems in tree pattern matching, the
largest common subtree and the smallest common supertree problems, is
established by means of simple constructions, which allow one to obtain a
largest common subtree of two trees from a smallest common supertree of them,
and vice versa. These constructions are the same for isomorphic, homeomorphic,
topological, and minor embeddings, they take only time linear in the size of
the trees, and they turn out to have a clear algebraic meaning.


title: CMS Software Distribution on the LCG and OSG Grids

abstract:
  The efficient exploitation of worldwide distributed storage and computing
resources available in the grids require a robust, transparent and fast
deployment of experiment specific software. The approach followed by the CMS
experiment at CERN in order to enable Monte-Carlo simulations, data analysis
and software development in an international collaboration is presented. The
current status and future improvement plans are described.


title: Modeling and Mathematical Analysis of Swarms of Microscopic Robots

abstract:
  The biologically-inspired swarm paradigm is being used to design
self-organizing systems of locally interacting artificial agents. A major
difficulty in designing swarms with desired characteristics is understanding
the causal relation between individual agent and collective behaviors.
Mathematical analysis of swarm dynamics can address this difficulty to gain
insight into system design. This paper proposes a framework for mathematical
modeling of swarms of microscopic robots that may one day be useful in medical
applications. While such devices do not yet exist, the modeling approach can be
helpful in identifying various design trade-offs for the robots and be a useful
guide for their eventual fabrication. Specifically, we examine microscopic
robots that reside in a fluid, for example, a bloodstream, and are able to
detect and respond to different chemicals. We present the general mathematical
model of a scenario in which robots locate a chemical source. We solve the
scenario in one-dimension and show how results can be used to evaluate certain
design decisions.


title: Analysis of Dynamic Task Allocation in Multi-Robot Systems

abstract:
  Dynamic task allocation is an essential requirement for multi-robot systems
operating in unknown dynamic environments. It allows robots to change their
behavior in response to environmental changes or actions of other robots in
order to improve overall system performance. Emergent coordination algorithms
for task allocation that use only local sensing and no direct communication
between robots are attractive because they are robust and scalable. However, a
lack of formal analysis tools makes emergent coordination algorithms difficult
to design. In this paper we present a mathematical model of a general dynamic
task allocation mechanism. Robots using this mechanism have to choose between
two types of task, and the goal is to achieve a desired task division in the
absence of explicit communication and global knowledge. Robots estimate the
state of the environment from repeated local observations and decide which task
to choose based on these observations. We model the robots and observations as
stochastic processes and study the dynamics of the collective behavior.
Specifically, we analyze the effect that the number of observations and the
choice of the decision function have on the performance of the system. The
mathematical models are validated in a multi-robot multi-foraging scenario. The
model's predictions agree very closely with experimental results from
sensor-based simulations.


title: Designing a Multi-petabyte Database for LSST

abstract:
  The 3.2 giga-pixel LSST camera will produce approximately half a petabyte of
archive images every month. These data need to be reduced in under a minute to
produce real-time transient alerts, and then added to the cumulative catalog
for further analysis. The catalog is expected to grow about three hundred
terabytes per year. The data volume, the real-time transient alerting
requirements of the LSST, and its spatio-temporal aspects require innovative
techniques to build an efficient data access system at reasonable cost. As
currently envisioned, the system will rely on a database for catalogs and
metadata. Several database systems are being evaluated to understand how they
perform at these data rates, data volumes, and access patterns. This paper
describes the LSST requirements, the challenges they impose, the data access
philosophy, results to date from evaluating available database technologies
against LSST requirements, and the proposed database architecture to meet the
data challenges.


title: One-in-Two-Matching Problem is NP-complete

abstract:
  2-dimensional Matching Problem, which requires to find a matching of left- to
right-vertices in a balanced $2n$-vertex bipartite graph, is a well-known
polynomial problem, while various variants, like the 3-dimensional analogoue
(3DM, with triangles on a tripartite graph), or the Hamiltonian Circuit Problem
(HC, a restriction to ``unicyclic'' matchings) are among the main examples of
NP-hard problems, since the first Karp reduction series of 1972. The same holds
for the weighted variants of these problems, the Linear Assignment Problem
being polynomial, and the Numerical 3-Dimensional Matching and Travelling
Salesman Problem being NP-complete.
  In this paper we show that a small modification of the 2-dimensional Matching
and Assignment Problems in which for each $i \leq n/2$ it is required that
either $\pi(2i-1)=2i-1$ or $\pi(2i)=2i$, is a NP-complete problem. The proof is
by linear reduction from SAT (or NAE-SAT), with the size $n$ of the Matching
Problem being four times the number of edges in the factor graph representation
of the boolean problem. As a corollary, in combination with the simple linear
reduction of One-in-Two Matching to 3-Dimensional Matching, we show that SAT
can be linearly reduced to 3DM, while the original Karp reduction was only
cubic.


title:
On Multistage Successive Refinement for Wyner-Ziv Source Coding with
  Degraded Side Informations

abstract:
  We provide a complete characterization of the rate-distortion region for the
multistage successive refinement of the Wyner-Ziv source coding problem with
degraded side informations at the decoder. Necessary and sufficient conditions
for a source to be successively refinable along a distortion vector are
subsequently derived. A source-channel separation theorem is provided when the
descriptions are sent over independent channels for the multistage case.
Furthermore, we introduce the notion of generalized successive refinability
with multiple degraded side informations. This notion captures whether
progressive encoding to satisfy multiple distortion constraints for different
side informations is as good as encoding without progressive requirement.
Necessary and sufficient conditions for generalized successive refinability are
given. It is shown that the following two sources are generalized successively
refinable: (1) the Gaussian source with degraded Gaussian side informations,
(2) the doubly symmetric binary source when the worse side information is a
constant. Thus for both cases, the failure of being successively refinable is
only due to the inherent uncertainty on which side information will occur at
the decoder, but not the progressive encoding requirement.


title:
A Hybrid Quantum Encoding Algorithm of Vector Quantization for Image
  Compression

abstract:
  Many classical encoding algorithms of Vector Quantization (VQ) of image
compression that can obtain global optimal solution have computational
complexity O(N). A pure quantum VQ encoding algorithm with probability of
success near 100% has been proposed, that performs operations 45sqrt(N) times
approximately. In this paper, a hybrid quantum VQ encoding algorithm between
classical method and quantum algorithm is presented. The number of its
operations is less than sqrt(N) for most images, and it is more efficient than
the pure quantum algorithm.
  Key Words: Vector Quantization, Grover's Algorithm, Image Compression,
Quantum Algorithm


title: A New Cryptosystem Based On Hidden Order Groups

abstract:
  Let $G_1$ be a cyclic multiplicative group of order $n$. It is known that the
Diffie-Hellman problem is random self-reducible in $G_1$ with respect to a
fixed generator $g$ if $\phi(n)$ is known. That is, given $g, g^x\in G_1$ and
having oracle access to a `Diffie-Hellman Problem' solver with fixed generator
$g$, it is possible to compute $g^{1/x} \in G_1$ in polynomial time (see
theorem 3.2). On the other hand, it is not known if such a reduction exists
when $\phi(n)$ is unknown (see conjuncture 3.1). We exploit this ``gap'' to
construct a cryptosystem based on hidden order groups and present a practical
implementation of a novel cryptographic primitive called an \emph{Oracle Strong
Associative One-Way Function} (O-SAOWF). O-SAOWFs have applications in
multiparty protocols. We demonstrate this by presenting a key agreement
protocol for dynamic ad-hoc groups.


title: Novel Reversible Multiplier Architecture Using Reversible TSG Gate

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. Recently a 4 * 4 reversible gate called TSG is proposed. The
most significant aspect of the proposed gate is that it can work singly as a
reversible full adder, that is reversible full adder can now be implemented
with a single gate only. This paper proposes a NXN reversible multiplier using
TSG gate. It is based on two concepts. The partial products can be generated in
parallel with a delay of d using Fredkin gates and thereafter the addition can
be reduced to log2N steps by using reversible parallel adder designed from TSG
gates. Similar multiplier architecture in conventional arithmetic (using
conventional logic) has been reported in existing literature, but the proposed
one in this paper is totally based on reversible logic and reversible cells as
its building block. A 4x4 architecture of the proposed reversible multiplier is
also designed. It is demonstrated that the proposed multiplier architecture
using the TSG gate is much better and optimized, compared to its 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:
The Discrete Memoryless Multiple Access Channel with Confidential
  Messages

abstract:
  A multiple-access channel is considered in which messages from one encoder
are confidential. Confidential messages are to be transmitted with perfect
secrecy, as measured by equivocation at the other encoder. The upper bounds and
the achievable rates for this communication situation are determined.


title: An Information-Spectrum Approach to Multiterminal Rate-Distortion Theory

abstract:
  An information-spectrum approach is applied to solve the multiterminal source
coding problem for correlated general sources, where sources may be
nonstationary and/or nonergodic, and the distortion measure is arbitrary and
may be nonadditive. A general formula for the rate-distortion region of the
multiterminal source coding problem with the maximum distortion criterion under
fixed-length coding is shown in this correspondence.


title: Systematic Topology Analysis and Generation Using Degree Correlations

abstract:
  We present a new, systematic approach for analyzing network topologies. We
first introduce the dK-series of probability distributions specifying all
degree correlations within d-sized subgraphs of a given graph G. Increasing
values of d capture progressively more properties of G at the cost of more
complex representation of the probability distribution. Using this series, we
can quantitatively measure the distance between two graphs and construct random
graphs that accurately reproduce virtually all metrics proposed in the
literature. The nature of the dK-series implies that it will also capture any
future metrics that may be proposed. Using our approach, we construct graphs
for d=0,1,2,3 and demonstrate that these graphs reproduce, with increasing
accuracy, important properties of measured and modeled Internet topologies. We
find that the d=2 case is sufficient for most practical purposes, while d=3
essentially reconstructs the Internet AS- and router-level topologies exactly.
We hope that a systematic method to analyze and synthesize topologies offers a
significant improvement to the set of tools available to network topology and
protocol researchers.


title: The complexity of acyclic conjunctive queries revisited

abstract:
  In this paper, we consider first-order logic over unary functions and study
the complexity of the evaluation problem for conjunctive queries described by
such kind of formulas. A natural notion of query acyclicity for this language
is introduced and we study the complexity of a large number of variants or
generalizations of acyclic query problems in that context (Boolean or not
Boolean, with or without inequalities, comparisons, etc...). Our main results
show that all those problems are \textit{fixed-parameter linear} i.e. they can
be evaluated in time $f(|Q|).|\textbf{db}|.|Q(\textbf{db})|$ where $|Q|$ is the
size of the query $Q$, $|\textbf{db}|$ the database size, $|Q(\textbf{db})|$ is
the size of the output and $f$ is some function whose value depends on the
specific variant of the query problem (in some cases, $f$ is the identity
function). Our results have two kinds of consequences. First, they can be
easily translated in the relational (i.e., classical) setting. Previously known
bounds for some query problems are improved and new tractable cases are then
exhibited. Among others, as an immediate corollary, we improve a result of
\~\cite{PapadimitriouY-99} by showing that any (relational) acyclic conjunctive
query with inequalities can be evaluated in time
$f(|Q|).|\textbf{db}|.|Q(\textbf{db})|$. A second consequence of our method is
that it provides a very natural descriptive approach to the complexity of
well-known algorithmic problems. A number of examples (such as acyclic subgraph
problems, multidimensional matching, etc...) are considered for which new
insights of their complexity are given.


title: On the Foundations of Universal Sequence Prediction

abstract:
  Solomonoff completed the Bayesian framework by providing a rigorous, unique,
formal, and universal choice for the model class and the prior. We discuss in
breadth how and in which sense universal (non-i.i.d.) sequence prediction
solves various (philosophical) problems of traditional Bayesian sequence
prediction. We show that Solomonoff's model possesses many desirable
properties: Fast convergence and strong bounds, and in contrast to most
classical continuous prior densities has no zero p(oste)rior problem, i.e. can
confirm universal hypotheses, is reparametrization and regrouping invariant,
and avoids the old-evidence and updating problem. It even performs well
(actually better) in non-computable environments.


title: Complementary Set Matrices Satisfying a Column Correlation Constraint

abstract:
  Motivated by the problem of reducing the peak to average power ratio (PAPR)
of transmitted signals, we consider a design of complementary set matrices
whose column sequences satisfy a correlation constraint. The design algorithm
recursively builds a collection of $2^{t+1}$ mutually orthogonal (MO)
complementary set matrices starting from a companion pair of sequences. We
relate correlation properties of column sequences to that of the companion pair
and illustrate how to select an appropriate companion pair to ensure that a
given column correlation constraint is satisfied. For $t=0$, companion pair
properties directly determine matrix column correlation properties. For $t\geq
1$, reducing correlation merits of the companion pair may lead to improved
column correlation properties. However, further decrease of the maximum
out-off-phase aperiodic autocorrelation of column sequences is not possible
once the companion pair correlation merit is less than a threshold determined
by $t$. We also reveal a design of the companion pair which leads to
complementary set matrices with Golay column sequences. Exhaustive search for
companion pairs satisfying a column correlation constraint is infeasible for
medium and long sequences. We instead search for two shorter length sequences
by minimizing a cost function in terms of their autocorrelation and
crosscorrelation merits. Furthermore, an improved cost function which helps in
reducing the maximum out-off-phase column correlation is derived based on the
properties of the companion pair. By exploiting the well-known Welch bound,
sufficient conditions for the existence of companion pairs which satisfy a set
of column correlation constraints are also given.


title: A Characterization of the Degree Sequences of 2-Trees

abstract:
  A graph G is a 2-tree if G=K_3, or G has a vertex v of degree 2, whose
neighbours are adjacent, and G\v{i}s a 2-tree. A characterization of the degree
sequences of 2-trees is given. This characterization yields a linear-time
algorithm for recognizing and realizing degree sequences of 2-trees.


title: Perspective alignment in spatial language

abstract:
  It is well known that perspective alignment plays a major role in the
planning and interpretation of spatial language. In order to understand the
role of perspective alignment and the cognitive processes involved, we have
made precise complete cognitive models of situated embodied agents that
self-organise a communication system for dialoging about the position and
movement of real world objects in their immediate surroundings. We show in a
series of robotic experiments which cognitive mechanisms are necessary and
sufficient to achieve successful spatial language and why and how perspective
alignment can take place, either implicitly or based on explicit marking.


title: Geometric representation of graphs in low dimension

abstract:
  We give an efficient randomized algorithm to construct a box representation
of any graph G on n vertices in $1.5 (\Delta + 2) \ln n$ dimensions, where
$\Delta$ is the maximum degree of G. We also show that $\boxi(G) \le (\Delta +
2) \ln n$ for any graph G. Our bound is tight up to a factor of $\ln n$. We
also show that our randomized algorithm can be derandomized to get a polynomial
time deterministic algorithm. Though our general upper bound is in terms of
maximum degree $\Delta$, we show that for almost all graphs on n vertices, its
boxicity is upper bound by $c\cdot(d_{av} + 1) \ln n$ where d_{av} is the
average degree and c is a small constant. Also, we show that for any graph G,
$\boxi(G) \le \sqrt{8 n d_{av} \ln n}$, which is tight up to a factor of $b
\sqrt{\ln n}$ for a constant b.


title: Generalized Multiple Access Channels with Confidential Messages

abstract:
  A discrete memoryless generalized multiple access channel (GMAC) with
confidential messages is studied, where two users attempt to transmit common
information to a destination and each user also has private (confidential)
information intended for the destination. The two users are allowed to receive
channel outputs, and hence may obtain the confidential information sent by each
other from channel outputs they receive. However, each user views the other
user as a wire-tapper, and wishes to keep its confidential information as
secret as possible from the other user. The level of secrecy of the
confidential information is measured by the equivocation rate, i.e., the
entropy rate of the confidential information conditioned on channel outputs at
the wire-tapper. The performance measure of interest for the GMAC with
confidential messages is the rate-equivocation tuple that includes the common
rate, two private rates and two equivocation rates as components. The set that
includes all these achievable rate-equivocation tuples is referred to as the
capacity-equivocation region. The GMAC with one confidential message set is
first studied, where only one user (user 1) has private (confidential)
information for the destination. Inner and outer bounds on the
capacity-equivocation region are derived, and the capacity-equivocation are
established for some classes of channels including the Gaussian GMAC.
Furthermore, the secrecy capacity region is established, which is the set of
all achievable rates with user 2 being perfectly ignorant of confidential
messages of user 1. For the GMAC with two confidential message sets, where both
users have confidential messages for the destination, an inner bound on the
capacity-equivocation region is obtained.


title: Collaborative Tagging and Semiotic Dynamics

abstract:
  Collaborative tagging has been quickly gaining ground because of its ability
to recruit the activity of web users into effectively organizing and sharing
vast amounts of information. Here we collect data from a popular system and
investigate the statistical properties of tag co-occurrence. We introduce a
stochastic model of user behavior embodying two main aspects of collaborative
tagging: (i) a frequency-bias mechanism related to the idea that users are
exposed to each other's tagging activity; (ii) a notion of memory - or aging of
resources - in the form of a heavy-tailed access to the past state of the
system. Remarkably, our simple modeling is able to account quantitatively for
the observed experimental features, with a surprisingly high accuracy. This
points in the direction of a universal behavior of users, who - despite the
complexity of their own cognitive processes and the uncoordinated and selfish
nature of their tagging activity - appear to follow simple activity patterns.

categories: cs.CY cs.DL physics.data-an physics.soc-ph


title: Cooperative Relay Broadcast Channels

abstract:
  The capacity regions are investigated for two relay broadcast channels
(RBCs), where relay links are incorporated into standard two-user broadcast
channels to support user cooperation. In the first channel, the Partially
Cooperative Relay Broadcast Channel, only one user in the system can act as a
relay and transmit to the other user through a relay link. An achievable rate
region is derived based on the relay using the decode-and-forward scheme. An
outer bound on the capacity region is derived and is shown to be tighter than
the cut-set bound. For the special case where the Partially Cooperative RBC is
degraded, the achievable rate region is shown to be tight and provides the
capacity region. Gaussian Partially Cooperative RBCs and Partially Cooperative
RBCs with feedback are further studied. In the second channel model being
studied in the paper, the Fully Cooperative Relay Broadcast Channel, both users
can act as relay nodes and transmit to each other through relay links. This is
a more general model than the Partially Cooperative RBC. All the results for
Partially Cooperative RBCs are correspondingly generalized to the Fully
Cooperative RBCs. It is further shown that the AWGN Fully Cooperative RBC has a
larger achievable rate region than the AWGN Partially Cooperative RBC. The
results illustrate that relaying and user cooperation are powerful techniques
in improving the capacity of broadcast channels.


title:
Reasoning and Planning with Sensing Actions, Incomplete Information, and
  Static Causal Laws using Answer Set Programming

abstract:
  We extend the 0-approximation of sensing actions and incomplete information
in [Son and Baral 2000] to action theories with static causal laws and prove
its soundness with respect to the possible world semantics. We also show that
the conditional planning problem with respect to this approximation is
NP-complete. We then present an answer set programming based conditional
planner, called ASCP, that is capable of generating both conformant plans and
conditional plans in the presence of sensing actions, incomplete information
about the initial state, and static causal laws. We prove the correctness of
our implementation and argue that our planner is sound and complete with
respect to the proposed approximation. Finally, we present experimental results
comparing ASCP to other planners.


title:
Computational Modeling in Applied Problems: collected papers on
  econometrics, operations research, game theory and simulation

abstract:
  Computational models pervade all branches of the exact sciences and have in
recent times also started to prove to be of immense utility in some of the
traditionally 'soft' sciences like ecology, sociology and politics. This volume
is a collection of a few cutting-edge research papers on the application of
variety of computational models and tools in the analysis, interpretation and
solution of vexing real-world problems and issues in economics, management,
ecology and global politics by some prolific researchers in the field.


title: The Distribution of Patterns in Random Trees

abstract:
  Let $T\_n$ denote the set of unrooted labeled trees of size $n$ and let
$T\_n$ be a particular (finite, unlabeled) tree. Assuming that every tree of
$T\_n$ is equally likely, it is shown that the limiting distribution as $n$
goes to infinity of the number of occurrences of $M$ as an induced subtree is
asymptotically normal with mean value and variance asymptotically equivalent to
$\mu n$ and $\sigma^2n$, respectively, where the constants $\mu>0$ and
$\sigma\ge 0$ are computable.


title: Applied MVC Patterns. A pattern language

abstract:
  How to get advantages of MVC model without making applications unnecessarily
complex? The full-featured MVC implementation is on the top end of ladder of
complexity. The other end is meant for simple cases that do not call for such
complex designs, however still in need of the advantages of MVC patterns, such
as ability to change the look-and-feel. This paper presents patterns of MVC
implementation that help to benefit from the paradigm and keep the right
balance between flexibility and implementation complexity.


title: SAT Techniques for Lexicographic Path Orders

abstract:
  This seminar report is concerned with expressing LPO-termination of term
rewrite systems as a satisfiability problem in propositional logic. After
relevant algorithms are explained, experimental results are reported.


title: Toward a Collection-based Metadata Maintenance Model

abstract:
  In this paper, the authors identify key entities and relationships in the
operational management of metadata catalogs that describe digital collections,
and they draft a data model to support the administration of metadata
maintenance for collections. Further, they consider this proposed model in
light of other data schemes to which it relates and discuss the implications of
the model for library metadata maintenance operations.


title:
The Gaussian Multiple Access Wire-Tap Channel with Collective Secrecy
  Constraints

abstract:
  We consider the Gaussian Multiple Access Wire-Tap Channel (GMAC-WT). In this
scenario, multiple users communicate with an intended receiver in the presence
of an intelligent and informed wire-tapper who receives a degraded version of
the signal at the receiver. We define a suitable security measure for this
multi-access environment. We derive an outer bound for the rate region such
that secrecy to some pre-determined degree can be maintained. We also find,
using Gaussian codebooks, an achievable such secrecy region. Gaussian codewords
are shown to achieve the sum capacity outer bound, and the achievable region
concides with the outer bound for Gaussian codewords, giving the capacity
region when inputs are constrained to be Gaussian. We present numerical results
showing the new rate region and compare it with that of the Gaussian
Multiple-Access Channel (GMAC) with no secrecy constraints.


title: A Formal Measure of Machine Intelligence

abstract:
  A fundamental problem in artificial intelligence is that nobody really knows
what intelligence is. The problem is especially acute when we need to consider
artificial systems which are significantly different to humans. In this paper
we approach this problem in the following way: We take a number of well known
informal definitions of human intelligence that have been given by experts, and
extract their essential features. These are then mathematically formalised to
produce a general measure of intelligence for arbitrary machines. We believe
that this measure formally captures the concept of machine intelligence in the
broadest reasonable sense.


title:
Face Recognition using Principal Component Analysis and Log-Gabor
  Filters

abstract:
  In this article we propose a novel face recognition method based on Principal
Component Analysis (PCA) and Log-Gabor filters. The main advantages of the
proposed method are its simple implementation, training, and very high
recognition accuracy. For recognition experiments we used 5151 face images of
1311 persons from different sets of the FERET and AR databases that allow to
analyze how recognition accuracy is affected by the change of facial
expressions, illumination, and aging. Recognition experiments with the FERET
database (containing photographs of 1196 persons) showed that our method can
achieve maximal 97-98% first one recognition rate and 0.3-0.4% Equal Error
Rate. The experiments also showed that the accuracy of our method is less
affected by eye location errors and used image normalization method than of
traditional PCA -based recognition method.


title: Strongly Almost Periodic Sequences under Finite Automata Mappings

abstract:
  The notion of almost periodicity nontrivially generalizes the notion of
periodicity. Strongly almost periodic sequences (=uniformly recurrent infinite
words) first appeared in the field of symbolic dynamics, but then turned out to
be interesting in connection with computer science. The paper studies the class
of eventually strongly almost periodic sequences (i. e., becoming strongly
almost periodic after deleting some prefix). We prove that the property of
eventual strong almost periodicity is preserved under the mappings done by
finite automata and finite transducers. The class of almost periodic sequences
includes the class of eventually strongly almost periodic sequences. We prove
this inclusion to be strict.


title:
Recognition of expression variant faces using masked log-Gabor features
  and Principal Component Analysis

abstract:
  In this article we propose a method for the recognition of faces with
different facial expressions. For recognition we extract feature vectors by
using log-Gabor filters of multiple orientations and scales. Using sliding
window algorithm and variances -based masking these features are extracted at
image regions that are less affected by the changes of facial expressions.
Extracted features are passed to the Principal Component Analysis (PCA) -based
recognition method. The results of face recognition experiments using
expression variant faces showed that the proposed method could achieve higher
recognition accuracy than many other methods. For development and testing we
used facial images from the AR and FERET databases. Using facial photographs of
more than one thousand persons from the FERET database the proposed method
achieved 96.6-98.9% first one recognition rate and 0.2-0.6% Equal Error Rate
(EER).


title: The Gaussian Multiple Access Wire-Tap Channel

abstract:
  We consider the Gaussian Multiple Access Wire-Tap Channel (GMAC-WT). In this
scenario, multiple users communicate with an intended receiver in the presence
of an intelligent and informed wire-tapper who receives a degraded version of
the signal at the receiver. We define suitable security measures for this
multi-access environment. Using codebooks generated randomly according to a
Gaussian distribution, achievable secrecy rate regions are identified using
superposition coding and TDMA coding schemes. An upper bound for the secrecy
sum-rate is derived, and our coding schemes are shown to achieve the sum
capacity. Numerical results showing the new rate region are presented and
compared with the capacity region of the Gaussian Multiple-Access Channel
(GMAC) with no secrecy constraints, quantifying the price paid for secrecy.


title: Spanners for Geometric Intersection Graphs

abstract:
  Efficient algorithms are presented for constructing spanners in geometric
intersection graphs. For a unit ball graph in R^k, a (1+\epsilon)-spanner is
obtained using efficient partitioning of the space into hypercubes and solving
bichromatic closest pair problems. The spanner construction has almost
equivalent complexity to the construction of Euclidean minimum spanning trees.
The results are extended to arbitrary ball graphs with a sub-quadratic running
time.
  For unit ball graphs, the spanners have a small separator decomposition which
can be used to obtain efficient algorithms for approximating proximity problems
like diameter and distance queries. The results on compressed quadtrees,
geometric graph separators, and diameter approximation might be of independent
interest.


title: A Delay Analysis of Maximal Matching Switching with Speedup

abstract:
  In this paper we analyze the average queue backlog in a combined input-output
queued switch using a maximal size matching scheduling algorithm. We compare
this average backlog to the average backlog achieved by an optimal switch. We
model the cell arrival process as independent and identically distributed
between time slots and uniformly distributed among input and output ports. For
switches with many input and output ports, the backlog associated with maximal
size matching with speedup 3 is no more than 10/3 times the backlog associated
with an optimal switch. Moreover, this performance ratio rapidly approaches 2
as speedup increases.


title: On the Design of Agent-Based Systems using UML and Extensions

abstract:
  The Unified Software Development Process (USDP) and UML have been now
generally accepted as the standard methodology and modeling language for
developing Object-Oriented Systems. Although Agent-based Systems introduces new
issues, we consider that USDP and UML can be used in an extended manner for
modeling Agent-based Systems. The paper presents a methodology for designing
agent-based systems and the specific models expressed in an UML-based notation
corresponding to each phase of the software development process. UML was
extended using the provided mechanism: stereotypes. Therefore, this approach
can be managed with any CASE tool supporting UML. A Case Study, the development
of a specific agent-based Student Evaluation System (SAS), is presented.


title: A framework of reusable structures for mobile agent development

abstract:
  Mobile agents research is clearly aiming towards imposing agent based
development as the next generation of tools for writing software. This paper
comes with its own contribution to this global goal by introducing a novel
unifying framework meant to bring simplicity and interoperability to and among
agent platforms as we know them today. In addition to this, we also introduce a
set of agent behaviors which, although tailored for and from the area of
virtual learning environments, are none the less generic enough to be used for
rapid, simple, useful and reliable agent deployment. The paper also presents an
illustrative case study brought forward to prove the feasibility of our design.


title:
Mobile Agent Based Solutions for Knowledge Assessment in elearning
  Environments

abstract:
  E-learning is nowadays one of the most interesting of the "e- " domains
available through the Internet. The main problem to create a Web-based, virtual
environment is to model the traditional domain and to implement the model using
the most suitable technologies. We analyzed the distance learning domain and
investigated the possibility to implement some e-learning services using mobile
agent technologies. This paper presents a model of the Student Assessment
Service (SAS) and an agent-based framework developed to be used for
implementing specific applications. A specific Student Assessment application
that relies on the framework was developed.


title: Peer to Peer Networks for Defense Against Internet Worms

abstract:
  Internet worms, which spread in computer networks without human mediation,
pose a severe threat to computer systems today. The rate of propagation of
worms has been measured to be extremely high and they can infect a large
fraction of their potential hosts in a short time. We study two different
methods of patch dissemination to combat the spread of worms. We first show
that using a fixed number of patch servers performs woefully inadequately
against Internet worms. We then show that by exploiting the exponential data
dissemination capability of P2P systems, the spread of worms can be halted very
effectively. We compare the two methods by using fluid models to compute two
quantities of interest: the time taken to effectively combat the progress of
the worm and the maximum number of infected hosts. We validate our models using
Internet measurements and simulations.


title: Query Chains: Learning to Rank from Implicit Feedback

abstract:
  This paper presents a novel approach for using clickthrough data to learn
ranked retrieval functions for web search results. We observe that users
searching the web often perform a sequence, or chain, of queries with a similar
information need. Using query chains, we generate new types of preference
judgments from search engine logs, thus taking advantage of user intelligence
in reformulating queries. To validate our method we perform a controlled user
study comparing generated preference judgments to explicit relevance judgments.
We also implemented a real-world search engine to test our approach, using a
modified ranking SVM to learn an improved ranking function from preference
data. Our results demonstrate significant improvements in the ranking given by
the search engine. The learned rankings outperform both a static ranking
function, as well as one trained without considering query chains.


title: Evaluating the Robustness of Learning from Implicit Feedback

abstract:
  This paper evaluates the robustness of learning from implicit feedback in web
search. In particular, we create a model of user behavior by drawing upon user
studies in laboratory and real-world settings. The model is used to understand
the effect of user behavior on the performance of a learning algorithm for
ranked retrieval. We explore a wide range of possible user behaviors and find
that learning from implicit feedback can be surprisingly robust. This
complements previous results that demonstrated our algorithm's effectiveness in
a real-world search engine application.


title:
Minimally Invasive Randomization for Collecting Unbiased Preferences
  from Clickthrough Logs

abstract:
  Clickthrough data is a particularly inexpensive and plentiful resource to
obtain implicit relevance feedback for improving and personalizing search
engines. However, it is well known that the probability of a user clicking on a
result is strongly biased toward documents presented higher in the result set
irrespective of relevance. We introduce a simple method to modify the
presentation of search results that provably gives relevance judgments that are
unaffected by presentation bias under reasonable assumptions. We validate this
property of the training data in interactive real world experiments. Finally,
we show that using these unbiased relevance judgments learning methods can be
guaranteed to converge to an ideal ranking given sufficient data.


title: An Unfolding-Based Semantics for Logic Programming with Aggregates

abstract:
  The paper presents two equivalent definitions of answer sets for logic
programs with aggregates. These definitions build on the notion of unfolding of
aggregates, and they are aimed at creating methodologies to translate logic
programs with aggregates to normal logic programs or positive programs, whose
answer set semantics can be used to defined the semantics of the original
programs. The first definition provides an alternative view of the semantics
for logic programming with aggregates described by Pelov et al.
  The second definition is similar to the traditional answer set definition for
normal logic programs, in that, given a logic program with aggregates and an
interpretation, the unfolding process produces a positive program. The paper
shows how this definition can be extended to consider aggregates in the head of
the rules.
  The proposed views of logic programming with aggregates are simple and
coincide with the ultimate stable model semantics, and with other semantic
characterizations for large classes of program (e.g., programs with monotone
aggregates and programs that are aggregate-stratified).
  Moreover, it can be directly employed to support an implementation using
available answer set solvers. The paper describes a system, called ASP^A, that
is capable of computing answer sets of programs with arbitrary (e.g.,
recursively defined) aggregates.


title: Fast and Generalized Polynomial Time Memory Consistency Verification

abstract:
  The problem of verifying multi-threaded execution against the memory
consistency model of a processor is known to be an NP hard problem. However
polynomial time algorithms exist that detect almost all failures in such
execution. These are often used in practice for microprocessor verification. We
present a low complexity and fully parallelized algorithm to check program
execution against the processor consistency model. In addition our algorithm is
general enough to support a number of consistency models without any
degradation in performance. An implementation of this algorithm is currently
used in practice to verify processors in the post silicon stage for multiple
architectures.


title: General Discounting versus Average Reward

abstract:
  Consider an agent interacting with an environment in cycles. In every
interaction cycle the agent is rewarded for its performance. We compare the
average reward U from cycle 1 to m (average value) with the future discounted
reward V from cycle k to infinity (discounted value). We consider essentially
arbitrary (non-geometric) discount sequences and arbitrary reward sequences
(non-MDP environments). We show that asymptotically U for m->infinity and V for
k->infinity are equal, provided both limits exist. Further, if the effective
horizon grows linearly with k or faster, then existence of the limit of U
implies that the limit of V exists. Conversely, if the effective horizon grows
linearly with k or slower, then existence of the limit of V implies that the
limit of U exists.


title:
Asymptotically Optimal Multiple-access Communication via Distributed
  Rate Splitting

abstract:
  We consider the multiple-access communication problem in a distributed
setting for both the additive white Gaussian noise channel and the discrete
memoryless channel. We propose a scheme called Distributed Rate Splitting to
achieve the optimal rates allowed by information theory in a distributed
manner. In this scheme, each real user creates a number of virtual users via a
power/rate splitting mechanism in the M-user Gaussian channel or via a random
switching mechanism in the M-user discrete memoryless channel. At the receiver,
all virtual users are successively decoded. Compared with other multiple-access
techniques, Distributed Rate Splitting can be implemented with lower complexity
and less coordination. Furthermore, in a symmetric setting, we show that the
rate tuple achieved by this scheme converges to the maximum equal rate point
allowed by the information-theoretic bound as the number of virtual users per
real user tends to infinity. When the capacity regions are asymmetric, we show
that a point on the dominant face can be achieved asymptotically. Finally, when
there is an unequal number of virtual users per real user, we show that
differential user rate requirements can be accommodated in a distributed
fashion.


title: Throughput Optimal Distributed Control of Stochastic Wireless Networks

abstract:
  This paper has been withdrawn by the author due to the need for further
revision.


title: Continuations, proofs and tests

abstract:
  Continuation Passing Style (CPS) is one of the most important issues in the
field of functional programming languages, and the quest for a primitive notion
of types for continuation is still open. Starting from the notion of ``test''
proposed by Girard, we develop a notion of test for intuitionistic logic. We
give a complete deductive system for tests and we show that it is good to deal
with ``continuations''. In particular, in the proposed system it is possible to
work with Call by Value and Call by Name translations in a uniform way.


title: Linear Shift-Register Synthesis for Multiple Sequences of Varying Length

abstract:
  The problem of finding the shortest linear shift-register capable of
generating t finite length sequences over some field F is considered. A similar
problem was already addressed by Feng and Tzeng. They presented an iterative
algorithm for solving this multi-sequence shift-register synthesis problem,
which can be considered as generalization of the well known Berlekamp-Massey
algorithm. The Feng-Tzeng algorithm works indeed, if all t sequences have the
same length. This paper focuses on multi-sequence shift-register synthesis for
generating sequences of varying length. It is exposed, that the Feng-Tzeng
algorithm does not always give the correct solution in this case. A modified
algorithm is proposed and formally proved, which overcomes this problem.


title: On Orthogonalities in Matrices

abstract:
  In this paper we have discussed different possible orthogonalities in
matrices, namely orthogonal, quasi-orthogonal, semi-orthogonal and
non-orthogonal matrices including completely positive matrices, while giving
some of their constructions besides studying some of their properties.


title: Patterns of i.i.d. Sequences and Their Entropy - Part I: General Bounds

abstract:
  Tight bounds on the block entropy of patterns of sequences generated by
independent and identically distributed (i.i.d.) sources are derived. A pattern
of a sequence is a sequence of integer indices with each index representing the
order of first occurrence of the respective symbol in the original sequence.
Since a pattern is the result of data processing on the original sequence, its
entropy cannot be larger. Bounds derived here describe the pattern entropy as
function of the original i.i.d. source entropy, the alphabet size, the symbol
probabilities, and their arrangement in the probability space. Matching upper
and lower bounds derived provide a useful tool for very accurate approximations
of pattern block entropies for various distributions, and for assessing the
decrease of the pattern entropy from that of the original i.i.d. sequence.


title:
Generalized Entropy Power Inequalities and Monotonicity Properties of
  Information

abstract:
  New families of Fisher information and entropy power inequalities for sums of
independent random variables are presented. These inequalities relate the
information in the sum of $n$ independent random variables to the information
contained in sums over subsets of the random variables, for an arbitrary
collection of subsets. As a consequence, a simple proof of the monotonicity of
information in central limit theorems is obtained, both in the setting of
i.i.d. summands as well as in the more general setting of independent summands
with variance-standardized sums.


title:
On Learning Thresholds of Parities and Unions of Rectangles in Random
  Walk Models

abstract:
  In a recent breakthrough, [Bshouty et al., 2005] obtained the first
passive-learning algorithm for DNFs under the uniform distribution. They showed
that DNFs are learnable in the Random Walk and Noise Sensitivity models. We
extend their results in several directions. We first show that thresholds of
parities, a natural class encompassing DNFs, cannot be learned efficiently in
the Noise Sensitivity model using only statistical queries. In contrast, we
show that a cyclic version of the Random Walk model allows to learn efficiently
polynomially weighted thresholds of parities. We also extend the algorithm of
Bshouty et al. to the case of Unions of Rectangles, a natural generalization of
DNFs to $\{0,...,b-1\}^n$.


title: On fractionally linear functions over a finite field

abstract:
  Abstrct: In this note, by considering fractionally linear functions over a
finite field and consequently developing an abstract sequence, we study some of
its properties.


title: A Polynomial Time Nilpotence Test for Galois Groups and Related Results

abstract:
  We give a deterministic polynomial-time algorithm to check whether the Galois
group $\Gal{f}$ of an input polynomial $f(X) \in \Q[X]$ is nilpotent: the
running time is polynomial in $\size{f}$. Also, we generalize the Landau-Miller
solvability test to an algorithm that tests if $\Gal{f}$ is in $\Gamma_d$: this
algorithm runs in time polynomial in $\size{f}$ and $n^d$ and, moreover, if
$\Gal{f}\in\Gamma_d$ it computes all the prime factors of $# \Gal{f}$.


title: A General Method for Finding Low Error Rates of LDPC Codes

abstract:
  This paper outlines a three-step procedure for determining the low bit error
rate performance curve of a wide class of LDPC codes of moderate length. The
traditional method to estimate code performance in the higher SNR region is to
use a sum of the contributions of the most dominant error events to the
probability of error. These dominant error events will be both code and decoder
dependent, consisting of low-weight codewords as well as non-codeword events if
ML decoding is not used. For even moderate length codes, it is not feasible to
find all of these dominant error events with a brute force search. The proposed
method provides a convenient way to evaluate very low bit error rate
performance of an LDPC code without requiring knowledge of the complete error
event weight spectrum or resorting to a Monte Carlo simulation. This new method
can be applied to various types of decoding such as the full belief propagation
version of the message passing algorithm or the commonly used min-sum
approximation to belief propagation. The proposed method allows one to
efficiently see error performance at bit error rates that were previously out
of reach of Monte Carlo methods. This result will provide a solid foundation
for the analysis and design of LDPC codes and decoders that are required to
provide a guaranteed very low bit error rate performance at certain SNRs.


title:
Node-Based Optimal Power Control, Routing, and Congestion Control in
  Wireless Networks

abstract:
  We present a unified analytical framework within which power control, rate
allocation, routing, and congestion control for wireless networks can be
optimized in a coherent and integrated manner. We consider a multi-commodity
flow model with an interference-limited physical-layer scheme in which power
control and routing variables are chosen to minimize the sum of convex link
costs reflecting, for instance, queuing delay. Distributed network algorithms
where joint power control and routing are performed on a node-by-node basis are
presented. We show that with appropriately chosen parameters, these algorithms
iteratively converge to the global optimum from any initial point with finite
cost. Next, we study refinements of the algorithms for more accurate link
capacity models, and extend the results to wireless networks where the
physical-layer achievable rate region is given by an arbitrary convex set, and
the link costs are strictly quasiconvex. Finally, we demonstrate that
congestion control can be seamlessly incorporated into our framework, so that
algorithms developed for power control and routing can naturally be extended to
optimize user input rates.


title:
Gridscape II: A Customisable and Pluggable Grid Monitoring Portal and
  its Integration with Google Maps

abstract:
  Grid computing has emerged as an effective means of facilitating the sharing
of distributed heterogeneous resources, enabling collaboration in large scale
environments. However, the nature of Grid systems, coupled with the
overabundance and fragmentation of information, makes it difficult to monitor
resources, services, and computations in order to plan and make decisions. In
this paper we present Gridscape II, a customisable portal component that can be
used on its own or plugged in to compliment existing Grid portals. Gridscape II
manages the gathering of information from arbitrary, heterogeneous and
distributed sources and presents them together seamlessly within a single
interface. It also leverages the Google Maps API in order to provide a highly
interactive user interface. Gridscape II is simple and easy to use, providing a
solution to those users who do not wish to invest heavily in developing their
own monitoring portal from scratch, and also for those users who want something
that is easy to customise and extend for their specific needs.


title: From Proof Nets to the Free *-Autonomous Category

abstract:
  In the first part of this paper we present a theory of proof nets for full
multiplicative linear logic, including the two units. It naturally extends the
well-known theory of unit-free multiplicative proof nets. A linking is no
longer a set of axiom links but a tree in which the axiom links are subtrees.
These trees will be identified according to an equivalence relation based on a
simple form of graph rewriting. We show the standard results of
sequentialization and strong normalization of cut elimination. In the second
part of the paper we show that the identifications enforced on proofs are such
that the class of two-conclusion proof nets defines the free *-autonomous
category.


title:
Approximate Discrete Probability Distribution Representation using a
  Multi-Resolution Binary Tree

abstract:
  Computing and storing probabilities is a hard problem as soon as one has to
deal with complex distributions over multiple random variables. The problem of
efficient representation of probability distributions is central in term of
computational efficiency in the field of probabilistic reasoning. The main
problem arises when dealing with joint probability distributions over a set of
random variables: they are always represented using huge probability arrays. In
this paper, a new method based on binary-tree representation is introduced in
order to store efficiently very large joint distributions. Our approach
approximates any multidimensional joint distributions using an adaptive
discretization of the space. We make the assumption that the lower is the
probability mass of a particular region of feature space, the larger is the
discretization step. This assumption leads to a very optimized representation
in term of time and memory. The other advantages of our approach are the
ability to refine dynamically the distribution every time it is needed leading
to a more accurate representation of the probability distribution and to an
anytime representation of the distribution.


title: Utility Computing and Global Grids

abstract:
  This chapter focuses on the use of Grid technologies to achieve utility
computing. An overview of how Grids can support utility computing is first
presented through the architecture of Utility Grids. Then, utility-based
resource allocation is described in detail at each level of the architecture.
Finally, some industrial solutions for utility computing are discussed.


title:
SLA-Based Coordinated Superscheduling Scheme and Performance for
  Computational Grids

abstract:
  The Service Level Agreement~(SLA) based grid superscheduling approach
promotes coordinated resource sharing. Superscheduling is facilitated between
administratively and topologically distributed grid sites by grid schedulers
such as Resource brokers. In this work, we present a market-based SLA
coordination mechanism. We based our SLA model on a well known \emph{contract
net protocol}.
  The key advantages of our approach are that it allows:~(i) resource owners to
have finer degree of control over the resource allocation that was previously
not possible through traditional mechanism; and (ii) superschedulers to bid for
SLA contracts in the contract net with focus on completing the job within the
user specified deadline. In this work, we use simulation to show the
effectiveness of our proposed approach.


title: A Monadic, Functional Implementation of Real Numbers

abstract:
  Large scale real number computation is an essential ingredient in several
modern mathematical proofs. Because such lengthy computations cannot be
verified by hand, some mathematicians want to use software proof assistants to
verify the correctness of these proofs. This paper develops a new
implementation of the constructive real numbers and elementary functions for
such proofs by using the monad properties of the completion operation on metric
spaces. Bishop and Bridges's notion of regular sequences is generalized to,
what I call, regular functions which form the completion of any metric space.
Using the monad operations, continuous functions on length spaces (a common
subclass of metric spaces) are created by lifting continuous functions on the
original space. A prototype Haskell implementation has been created. I believe
that this approach yields a real number library that is reasonably efficient
for computation, and still simple enough to easily verify its correctness.


title: Ontological Representations of Software Patterns

abstract:
  This paper is based on and advocates the trend in software engineering of
extending the use of software patterns as means of structuring solutions to
software development problems (be they motivated by best practice or by company
interests and policies). The paper argues that, on the one hand, this
development requires tools for automatic organisation, retrieval and
explanation of software patterns. On the other hand, that the existence of such
tools itself will facilitate the further development and employment of patterns
in the software development process. The paper analyses existing pattern
representations and concludes that they are inadequate for the kind of
automation intended here. Adopting a standpoint similar to that taken in the
semantic web, the paper proposes that feasible solutions can be built on the
basis of ontological representations.


title:
A Case for Cooperative and Incentive-Based Coupling of Distributed
  Clusters

abstract:
  Research interest in Grid computing has grown significantly over the past
five years. Management of distributed resources is one of the key issues in
Grid computing. Central to management of resources is the effectiveness of
resource allocation as it determines the overall utility of the system. The
current approaches to superscheduling in a grid environment are non-coordinated
since application level schedulers or brokers make scheduling decisions
independently of the others in the system. Clearly, this can exacerbate the
load sharing and utilization problems of distributed resources due to
suboptimal schedules that are likely to occur. To overcome these limitations,
we propose a mechanism for coordinated sharing of distributed clusters based on
computational economy. The resulting environment, called
\emph{Grid-Federation}, allows the transparent use of resources from the
federation when local resources are insufficient to meet its users'
requirements. The use of computational economy methodology in coordinating
resource allocation not only facilitates the QoS based scheduling, but also
enhances utility delivered by resources.


title:
An Internet Framework to Bring Coherence between WAP and HTTP Ensuring
  Better Mobile Internet Security

abstract:
  To bring coherence between Wireless Access Protocol (WAP) and Hyper Text
Transfer Protocol (HTTP), in this paper, we have proposed an enhanced Internet
framework, which incorporates a new markup language and a browser compatible
with both of the access control protocols. This Markup Language and the browser
enables co-existence of both Hyper Text Markup Language (HTML) and Wireless
Markup Language (WML) contents in a single source file, whereas the browser
incorporates the ability to hold contents compliant with both HTTP and WAP. The
proposed framework also bridges the security gap that is present in the
existing mobile Internet framework.
  Keywords: WAP, WML, HTTP, HTML, browser, parser, wireless devices.


title: QoSIP: A QoS Aware IP Routing Ptotocol for Multimedia Data

abstract:
  Conventional IP routing protocols are not suitable for multimedia
applications which have very stringent Quality-of-Service (QoS) demands and
they require a connection oriented service. For multimedia applications it is
expected that the router should be able to forward the packet according to the
demand of the packet and it is necessary to find a path that satisfies the
specific demands of a particular application. In order to address these issues,
in this paper, we have presented a QoS aware IP routing protocol where a router
stores information about the QoS parameters and routes the packet accordingly.
  Keywords: IP Routing Protocol, Quality of Service (QoS) parameter, QoSIP,
Selective Flooding.


title:
An Electronic Payment System to Ensure Cost Effectiveness with Easy
  Security Incorporation for the Developing Countries

abstract:
  With the rapid growth of Information and Communication Technology, Electronic
commerce is now acting as a new means of carrying out business transactions
through electronic means such as Internet environment. To avoid the
complexities associated with the digital cash and electronic cash, consumers
and vendors are looking for credit card payments on the Internet as one
possible time-tested alternative. This gave rise of the on-line payment
processing using a third-party verification; which is not suitable for the
developing countries in most of the cases because of the excessive costs
associated with it for maintenance and establishment of an online third-party
processor. As a remedy of this problem, in this paper, we have proposed a
framework for easy security incorporation in credit card based electronic
payment system without the use of an on-line third- party processor; which
tends to be low cost and effective for the developing countries.


title: Modal Logics of Topological Relations

abstract:
  Logical formalisms for reasoning about relations between spatial regions play
a fundamental role in geographical information systems, spatial and constraint
databases, and spatial reasoning in AI. In analogy with Halpern and Shoham's
modal logic of time intervals based on the Allen relations, we introduce a
family of modal logics equipped with eight modal operators that are interpreted
by the Egenhofer-Franzosa (or RCC8) relations between regions in topological
spaces such as the real plane. We investigate the expressive power and
computational complexity of logics obtained in this way. It turns out that our
modal logics have the same expressive power as the two-variable fragment of
first-order logic, but are exponentially less succinct. The complexity ranges
from (undecidable and) recursively enumerable to highly undecidable, where the
recursively enumerable logics are obtained by considering substructures of
structures induced by topological spaces. As our undecidability results also
capture logics based on the real line, they improve upon undecidability results
for interval temporal logics by Halpern and Shoham. We also analyze modal
logics based on the five RCC5 relations, with similar results regarding the
expressive power, but weaker results regarding the complexity.


title: On the possible Computational Power of the Human Mind

abstract:
  The aim of this paper is to address the question: Can an artificial neural
network (ANN) model be used as a possible characterization of the power of the
human mind? We will discuss what might be the relationship between such a model
and its natural counterpart. A possible characterization of the different power
capabilities of the mind is suggested in terms of the information contained (in
its computational complexity) or achievable by it. Such characterization takes
advantage of recent results based on natural neural networks (NNN) and the
computational power of arbitrary artificial neural networks (ANN). The possible
acceptance of neural networks as the model of the human mind's operation makes
the aforementioned quite relevant.


title: A Chaotic Cipher Mmohocc and Its Randomness Evaluation

abstract:
  After a brief introduction to a new chaotic stream cipher Mmohocc which
utilizes the fundamental chaos characteristics of mixing, unpredictability, and
sensitivity to initial conditions, we conducted the randomness statistical
tests against the keystreams generated by the cipher. Two batteries of most
stringent randomness tests, namely the NIST Suite and the Diehard Suite, were
performed. The results showed that the keystreams have successfully passed all
the statistical tests. We conclude that Mmohocc can generate high-quality
pseudorandom numbers from a statistical point of view.


title: Efficient Operation of Coded Packet Networks

abstract:
  A fundamental problem faced in the design of almost all packet networks is
that of efficient operation--of reliably communicating given messages among
nodes at minimum cost in resource usage. We present a solution to the efficient
operation problem for coded packet networks, i.e., packet networks where the
contents of outgoing packets are arbitrary, causal functions of the contents of
received packets. Such networks are in contrast to conventional, routed packet
networks, where outgoing packets are restricted to being copies of received
packets and where reliability is provided by the use of retransmissions.
  This thesis introduces four considerations to coded packet networks: 1.
efficiency, 2. the lack of synchronization in packet networks, 3. the
possibility of broadcast links, and 4. packet loss. We take these
considerations and give a prescription for operation that is novel and general,
yet simple, useful, and extensible.


title: Low Complexity Algorithms for Linear Recurrences

abstract:
  We consider two kinds of problems: the computation of polynomial and rational
solutions of linear recurrences with coefficients that are polynomials with
integer coefficients; indefinite and definite summation of sequences that are
hypergeometric over the rational numbers. The algorithms for these tasks all
involve as an intermediate quantity an integer $N$ (dispersion or root of an
indicial polynomial) that is potentially exponential in the bit size of their
input. Previous algorithms have a bit complexity that is at least quadratic in
$N$. We revisit them and propose variants that exploit the structure of
solutions and avoid expanding polynomials of degree $N$. We give two
algorithms: a probabilistic one that detects the existence or absence of
nonzero polynomial and rational solutions in $O(\sqrt{N}\log^{2}N)$ bit
operations; a deterministic one that computes a compact representation of the
solution in $O(N\log^{3}N)$ bit operations. Similar speed-ups are obtained in
indefinite and definite hypergeometric summation. We describe the results of an
implementation.


title:
Parallel vs. Sequential Belief Propagation Decoding of LDPC Codes over
  GF(q) and Markov Sources

abstract:
  A sequential updating scheme (SUS) for belief propagation (BP) decoding of
LDPC codes over Galois fields, $GF(q)$, and correlated Markov sources is
proposed, and compared with the standard parallel updating scheme (PUS). A
thorough experimental study of various transmission settings indicates that the
convergence rate, in iterations, of the BP algorithm (and subsequently its
complexity) for the SUS is about one half of that for the PUS, independent of
the finite field size $q$. Moreover, this 1/2 factor appears regardless of the
correlations of the source and the channel's noise model, while the error
correction performance remains unchanged. These results may imply on the
'universality' of the one half convergence speed-up of SUS decoding.


title: Curve Shortening and the Rendezvous Problem for Mobile Autonomous Robots

abstract:
  If a smooth, closed, and embedded curve is deformed along its normal vector
field at a rate proportional to its curvature, it shrinks to a circular point.
This curve evolution is called Euclidean curve shortening and the result is
known as the Gage-Hamilton-Grayson Theorem. Motivated by the rendezvous problem
for mobile autonomous robots, we address the problem of creating a polygon
shortening flow. A linear scheme is proposed that exhibits several analogues to
Euclidean curve shortening: The polygon shrinks to an elliptical point, convex
polygons remain convex, and the perimeter of the polygon is monotonically
decreasing.


title: On the Capacity of Interference Channels with Degraded Message sets

abstract:
  This paper is motivated by a sensor network on a correlated field where
nearby sensors share information, and can thus assist rather than interfere
with one another. A special class of two-user Gaussian interference channels
(IFCs) is considered where one of the two transmitters knows both the messages
to be conveyed to the two receivers (called the IFC with degraded message
sets). Both achievability and converse arguments are provided for this scenario
for a class of discrete memoryless channels with weak interference. For the
case of the Gaussian weak interference channel with degraded message sets,
optimality of Gaussian inputs is also shown, resulting in the capacity region
of this channel.


title:
On the Capacity of Gaussian Weak Interference Channels with Degraded
  Message sets

abstract:
  This paper is motivated by a sensor network on a correlated field where
nearby sensors share information, and can thus assist rather than interfere
with one another. We consider a special class of two-user Gaussian interference
channels (IFCs) where one of the two transmitters knows both the messages to be
conveyed to the two receivers. Both achievability and converse arguments are
provided for a channel with Gaussian inputs and Gaussian noise when the
interference is weaker than the direct link (a so called weak IFC). In general,
this region serves as an outer bound on the capacity of weak IFCs with no
shared knowledge between transmitters.


title:
Analytic Properties and Covariance Functions of a New Class of
  Generalized Gibbs Random Fields

abstract:
  Spartan Spatial Random Fields (SSRFs) are generalized Gibbs random fields,
equipped with a coarse-graining kernel that acts as a low-pass filter for the
fluctuations. SSRFs are defined by means of physically motivated spatial
interactions and a small set of free parameters (interaction couplings). This
paper focuses on the FGC-SSRF model, which is defined on the Euclidean space
$\mathbb{R}^{d}$ by means of interactions proportional to the squares of the
field realizations, as well as their gradient and curvature. The permissibility
criteria of FGC-SSRFs are extended by considering the impact of a
finite-bandwidth kernel. It is proved that the FGC-SSRFs are almost surely
differentiable in the case of finite bandwidth. Asymptotic explicit expressions
for the Spartan covariance function are derived for $d=1$ and $d=3$; both known
and new covariance functions are obtained depending on the value of the
FGC-SSRF shape parameter. Nonlinear dependence of the covariance integral scale
on the FGC-SSRF characteristic length is established, and it is shown that the
relation becomes linear asymptotically. The results presented in this paper are
useful in random field parameter inference, as well as in spatial interpolation
of irregularly-spaced samples.


title: SAT Solving for Argument Filterings

abstract:
  This paper introduces a propositional encoding for lexicographic path orders
in connection with dependency pairs. This facilitates the application of SAT
solvers for termination analysis of term rewrite systems based on the
dependency pair method. We address two main inter-related issues and encode
them as satisfiability problems of propositional formulas that can be
efficiently handled by SAT solving: (1) the combined search for a lexicographic
path order together with an \emph{argument filtering} to orient a set of
inequalities; and (2) how the choice of the argument filtering influences the
set of inequalities that have to be oriented. We have implemented our
contributions in the termination prover AProVE. Extensive experiments show that
by our encoding and the application of SAT solvers one obtains speedups in
orders of magnitude as well as increased termination proving power.


title:
On the Capacity and Mutual Information of Memoryless Noncoherent
  Rayleigh-Fading Channels

abstract:
  The memoryless noncoherent single-input single-output (SISO) Rayleigh-fading
channel is considered. Closed-form expressions for the mutual information
between the output and the input of this channel when the input magnitude
distribution is discrete and restricted to having two mass points are derived,
and it is subsequently shown how these expressions can be used to obtain
closed-form expressions for the capacity of this channel for signal to noise
ratio (SNR) values of up to approximately 0 dB, and a tight capacity lower
bound for SNR values between 0 dB and 10 dB. The expressions for the channel
capacity and its lower bound are given as functions of a parameter which can be
obtained via numerical root-finding algorithms.


title: Numeration-automatic sequences

abstract:
  We present a base class of automata that induce a numeration system and we
give an algorithm to give the n-th word in the language of the automaton when
the expansion of n in the induced numeration system is feeded to the automaton.
Furthermore we give some algorithms for reverse reading of this expansion and a
way to combine automata to other automata having the same properties.