title: Capacity Theorems for Quantum Multiple Access Channels

abstract:
  We consider quantum channels with two senders and one receiver. For an
arbitrary such channel, we give multi-letter characterizations of two different
two-dimensional capacity regions. The first region characterizes the rates at
which it is possible for one sender to send classical information while the
other sends quantum information. The second region gives the rates at which
each sender can send quantum information. We give an example of a channel for
which each region has a single-letter description, concluding with a
characterization of the rates at which each user can simultaneously send
classical and quantum information.


title:
Polymorphic Self-* Agents for Stigmergic Fault Mitigation in Large-Scale
  Real-Time Embedded Systems

abstract:
  Organization and coordination of agents within large-scale, complex,
distributed environments is one of the primary challenges in the field of
multi-agent systems. A lot of interest has surfaced recently around self-*
(self-organizing, self-managing, self-optimizing, self-protecting) agents. This
paper presents polymorphic self-* agents that evolve a core set of roles and
behavior based on environmental cues. The agents adapt these roles based on the
changing demands of the environment, and are directly implementable in computer
systems applications. The design combines strategies from game theory,
stigmergy, and other biologically inspired models to address fault mitigation
in large-scale, real-time, distributed systems. The agents are embedded within
the individual digital signal processors of BTeV, a High Energy Physics
experiment consisting of 2500 such processors. Results obtained using a SWARM
simulation of the BTeV environment demonstrate the polymorphic character of the
agents, and show how this design exceeds performance and reliability metrics
obtained from comparable centralized, and even traditional decentralized
approaches.


title: Lessons from Three Views of the Internet Topology

abstract:
  Network topology plays a vital role in understanding the performance of
network applications and protocols. Thus, recently there has been tremendous
interest in generating realistic network topologies. Such work must begin with
an understanding of existing network topologies, which today typically consists
of a relatively small number of data sources. In this paper, we calculate an
extensive set of important characteristics of Internet AS-level topologies
extracted from the three data sources most frequently used by the research
community: traceroutes, BGP, and WHOIS. We find that traceroute and BGP
topologies are similar to one another but differ substantially from the WHOIS
topology. We discuss the interplay between the properties of the data sources
that result from specific data collection mechanisms and the resulting topology
views. We find that, among metrics widely considered, the joint degree
distribution appears to fundamentally characterize Internet AS-topologies: it
narrowly defines values for other important metrics. We also introduce an
evaluation criteria for the accuracy of topology generators and verify previous
observations that generators solely reproducing degree distributions cannot
capture the full spectrum of critical topological characteristics of any of the
three topologies. Finally, we release to the community the input topology
datasets, along with the scripts and output of our calculations. This
supplement should enable researchers to validate their models against real data
and to make more informed selection of topology data sources for their specific
needs.


title: Channel combining and splitting for cutoff rate improvement

abstract:
  The cutoff rate $R_0(W)$ of a discrete memoryless channel (DMC) $W$ is often
used as a figure of merit, alongside the channel capacity $C(W)$. Given a
channel $W$ consisting of two possibly correlated subchannels $W_1$, $W_2$, the
capacity function always satisfies $C(W_1)+C(W_2) \le C(W)$, while there are
examples for which $R_0(W_1)+R_0(W_2) > R_0(W)$. This fact that cutoff rate can
be ``created'' by channel splitting was noticed by Massey in his study of an
optical modulation system modeled as a $M$'ary erasure channel. This paper
demonstrates that similar gains in cutoff rate can be achieved for general
DMC's by methods of channel combining and splitting. Relation of the proposed
method to Pinsker's early work on cutoff rate improvement and to Imai-Hirakawa
multi-level coding are also discussed.


title: Codes for error detection, good or not good

abstract:
  Linear codes for error detection on a q-ary symmetric channel are studied. It
is shown that for given dimension k and minimum distance d, there exists a
value \mu(d,k) such that if C is a code of length n >= \mu(d,k), then neither C
nor its dual are good for error detection. For d >> k or k << d good
approximations for \mu(d,k) are given. A generalization to non-linear codes is
also given.


title:
Exp\'{e}riences de classification d'une collection de documents XML de
  structure homog\`{e}ne

abstract:
  This paper presents some experiments in clustering homogeneous XMLdocuments
to validate an existing classification or more generally anorganisational
structure. Our approach integrates techniques for extracting knowledge from
documents with unsupervised classification (clustering) of documents. We focus
on the feature selection used for representing documents and its impact on the
emerging classification. We mix the selection of structured features with fine
textual selection based on syntactic characteristics.We illustrate and evaluate
this approach with a collection of Inria activity reports for the year 2003.
The objective is to cluster projects into larger groups (Themes), based on the
keywords or different chapters of these activity reports. We then compare the
results of clustering using different feature selections, with the official
theme structure used by Inria.


title: The Phase Transition in Exact Cover

abstract:
  We study EC3, a variant of Exact Cover which is equivalent to Positive 1-in-3
SAT. Random instances of EC3 were recently used as benchmarks for simulations
of an adiabatic quantum algorithm. Empirical results suggest that EC3 has a
phase transition from satisfiability to unsatisfiability when the number of
clauses per variable r exceeds some threshold r* ~= 0.62 +- 0.01. Using the
method of differential equations, we show that if r <= 0.546 w.h.p. a random
instance of EC3 is satisfiable. Combined with previous results this limits the
location of the threshold, if it exists, to the range 0.546 < r* < 0.644.


title: Quantum Algorithm Processor For Finding Exact Divisors

abstract:
  Wiring diagrams are given for a quantum algorithm processor in CMOS to
compute, in parallel, all divisors of an n-bit integer. Lines required in a
wiring diagram are proportional to n. Execution time is proportional to the
square of n.


title: Tight Bounds on the Redundancy of Huffman Codes

abstract:
  In this paper we study the redundancy of Huffman codes. In particular, we
consider sources for which the probability of one of the source symbols is
known. We prove a conjecture of Ye and Yeung regarding the upper bound on the
redundancy of such Huffman codes, which yields in a tight upper bound. We also
derive a tight lower bound for the redundancy under the same assumption.
  We further apply the method introduced in this paper to other related
problems. It is shown that several other previously known bounds with different
constraints follow immediately from our results.


title: Bounds on the Capacity of the Blockwise Noncoherent APSK-AWGN Channels

abstract:
  Capacity of M-ary Amplitude and Phase-Shift Keying(M-APSK) over an Additive
White Gaussian Noise(AWGN) channel that also introduces an unknown carrier
phase rotation is considered. The phase remains constant over a block of L
symbols and it is independent from block to block. Aiming to design codes with
equally probable symbols, uniformly distributed channel inputs are assumed.
Based on results of Peleg and Shamai for M-ary Phase Shift Keying(M-PSK)
modulation, easily computable upper and lower bounds on the effective M-APSK
capacity are derived. For moderate M and L and a broad range of Signal-to-Noise
Ratios(SNR's), the bounds come close together. As in the case of M-PSK
modulation, for large L the coherent capacity is approached.


title: OpenVanilla - A Non-Intrusive Plug-In Framework of Text Services

abstract:
  Input method (IM) is a sine qua non for text entry of many Asian languages,
but its potential applications on other languages remain under-explored. This
paper proposes a philosophy of input method design by seeing it as a
nonintrusive plug-in text service framework. Such design allows new
functionalities of text processing to be attached onto a running application
without any tweaking of code. We also introduce OpenVanilla, a cross-platform
framework that is designed with the above-mentioned model in mind. Frameworks
like OpenVanilla have shown that an input method can be more than just a text
entry tool: it offers a convenient way for developing various text service and
language tools.


abstract:
  This paper has been withdrawn by the author, because it was merged into
cs.HC/0508041


title: Sequential Predictions based on Algorithmic Complexity

abstract:
  This paper studies sequence prediction based on the monotone Kolmogorov
complexity Km=-log m, i.e. based on universal deterministic/one-part MDL. m is
extremely close to Solomonoff's universal prior M, the latter being an
excellent predictor in deterministic as well as probabilistic environments,
where performance is measured in terms of convergence of posteriors or losses.
Despite this closeness to M, it is difficult to assess the prediction quality
of m, since little is known about the closeness of their posteriors, which are
the important quantities for prediction. We show that for deterministic
computable environments, the "posterior" and losses of m converge, but rapid
convergence could only be shown on-sequence; the off-sequence convergence can
be slow. In probabilistic environments, neither the posterior nor the losses
converge, in general.


title:
Deciding Quantifier-Free Presburger Formulas Using Parameterized
  Solution Bounds

abstract:
  Given a formula in quantifier-free Presburger arithmetic, if it has a
satisfying solution, there is one whose size, measured in bits, is polynomially
bounded in the size of the formula. In this paper, we consider a special class
of quantifier-free Presburger formulas in which most linear constraints are
difference (separation) constraints, and the non-difference constraints are
sparse. This class has been observed to commonly occur in software
verification. We derive a new solution bound in terms of parameters
characterizing the sparseness of linear constraints and the number of
non-difference constraints, in addition to traditional measures of formula
size. In particular, we show that the number of bits needed per integer
variable is linear in the number of non-difference constraints and logarithmic
in the number and size of non-zero coefficients in them, but is otherwise
independent of the total number of linear constraints in the formula. The
derived bound can be used in a decision procedure based on instantiating
integer variables over a finite domain and translating the input
quantifier-free Presburger formula to an equi-satisfiable Boolean formula,
which is then checked using a Boolean satisfiability solver. In addition to our
main theoretical result, we discuss several optimizations for deriving tighter
bounds in practice. Empirical evidence indicates that our decision procedure
can greatly outperform other decision procedures.


title: Multicommodity Flow Algorithms for Buffered Global Routing

abstract:
  In this paper we describe a new algorithm for buffered global routing
according to a prescribed buffer site map. Specifically, we describe a provably
good multi-commodity flow based algorithm that finds a global routing
minimizing buffer and wire congestion subject to given constraints on routing
area (wirelength and number of buffers) and sink delays. Our algorithm allows
computing the tradeoff curve between routing area and wire/buffer congestion
under any combination of delay and capacity constraints, and simultaneously
performs buffer/wire sizing, as well as layer and pin assignment. Experimental
results show that near-optimal results are obtained with a practical runtime.


title: Relaxation Bounds on the Minimum Pseudo-Weight of Linear Block Codes

abstract:
  Just as the Hamming weight spectrum of a linear block code sheds light on the
performance of a maximum likelihood decoder, the pseudo-weight spectrum
provides insight into the performance of a linear programming decoder. Using
properties of polyhedral cones, we find the pseudo-weight spectrum of some
short codes. We also present two general lower bounds on the minimum
pseudo-weight. The first bound is based on the column weight of the
parity-check matrix. The second bound is computed by solving an optimization
problem. In some cases, this bound is more tractable to compute than previously
known bounds and thus can be applied to longer codes.


title:
Further Results on Coding for Reliable Communication over Packet
  Networks

abstract:
  In "On Coding for Reliable Communication over Packet Networks" (Lun, Medard,
and Effros, Proc. 42nd Annu. Allerton Conf. Communication, Control, and
Computing, 2004), a capacity-achieving coding scheme for unicast or multicast
over lossy wireline or wireless packet networks is presented. We extend that
paper's results in two ways: First, we extend the network model to allow
packets received on a link to arrive according to any process with an average
rate, as opposed to the assumption of Poisson traffic with i.i.d. losses that
was previously made. Second, in the case of Poisson traffic with i.i.d. losses,
we derive error exponents that quantify the rate at which the probability of
error decays with coding delay.


title:
An Operational Foundation for Delimited Continuations in

  the

 CPS

 Hierarchy

abstract:
  We present an abstract machine and a reduction semantics for the
lambda-calculus extended with control operators that give access to delimited
continuations in the CPS hierarchy. The abstract machine is derived from an
evaluator in continuation-passing style (CPS); the reduction semantics (i.e., a
small-step operational semantics with an explicit representation of evaluation
contexts) is constructed from the abstract machine; and the control operators
are the shift and reset family. We also present new applications of delimited
continuations in the CPS hierarchy: finding list prefixes and normalization by
evaluation for a hierarchical language of units and products.


title: Characterizations of Pseudo-Codewords of LDPC Codes

abstract:
  An important property of high-performance, low complexity codes is the
existence of highly efficient algorithms for their decoding. Many of the most
efficient, recent graph-based algorithms, e.g. message passing algorithms and
decoding based on linear programming, crucially depend on the efficient
representation of a code in a graphical model. In order to understand the
performance of these algorithms, we argue for the characterization of codes in
terms of a so called fundamental cone in Euclidean space which is a function of
a given parity check matrix of a code, rather than of the code itself. We give
a number of properties of this fundamental cone derived from its connection to
unramified covers of the graphical models on which the decoding algorithms
operate. For the class of cycle codes, these developments naturally lead to a
characterization of the fundamental polytope as the Newton polytope of the
Hashimoto edge zeta function of the underlying graph.


title:
Duality between channel capacity and rate distortion with two-sided
  state information

abstract:
  We show that the duality between channel capacity and data compression is
retained when state information is available to the sender, to the receiver, to
both, or to neither. We present a unified theory for eight special cases of
channel capacity and rate distortion with state information, which also extends
existing results to arbitrary pairs of independent and identically distributed
(i.i.d.) correlated state information available at the sender and at the
receiver, respectively. In particular, the resulting general formula for
channel capacity assumes the same form as the generalized Wyner Ziv rate
distortion function.


title: Trellis-Based Equalization for Sparse ISI Channels Revisited

abstract:
  Sparse intersymbol-interference (ISI) channels are encountered in a variety
of high-data-rate communication systems. Such channels have a large channel
memory length, but only a small number of significant channel coefficients. In
this paper, trellis-based equalization of sparse ISI channels is revisited. Due
to the large channel memory length, the complexity of maximum-likelihood
detection, e.g., by means of the Viterbi algorithm (VA), is normally
prohibitive. In the first part of the paper, a unified framework based on
factor graphs is presented for complexity reduction without loss of optimality.
In this new context, two known reduced-complexity algorithms for sparse ISI
channels are recapitulated: The multi-trellis VA (M-VA) and the
parallel-trellis VA (P-VA). It is shown that the M-VA, although claimed, does
not lead to a reduced computational complexity. The P-VA, on the other hand,
leads to a significant complexity reduction, but can only be applied for a
certain class of sparse channels. In the second part of the paper, a unified
approach is investigated to tackle general sparse channels: It is shown that
the use of a linear filter at the receiver renders the application of standard
reduced-state trellis-based equalizer algorithms feasible, without significant
loss of optimality. Numerical results verify the efficiency of the proposed
receiver structure.


title: Energy Optimal Data Propagation in Wireless Sensor Networks

abstract:
  We propose an algorithm which produces a randomized strategy reaching optimal
data propagation in wireless sensor networks (WSN).In [6] and [8], an energy
balanced solution is sought using an approximation algorithm. Our algorithm
improves by (a) when an energy-balanced solution does not exist, it still finds
an optimal solution (whereas previous algorithms did not consider this case and
provide no useful solution) (b) instead of being an approximation algorithm, it
finds the exact solution in one pass. We also provide a rigorous proof of the
optimality of our solution.


title: Measuring Semantic Similarity by Latent Relational Analysis

abstract:
  This paper introduces Latent Relational Analysis (LRA), a method for
measuring semantic similarity. LRA measures similarity in the semantic
relations between two pairs of words. When two pairs have a high degree of
relational similarity, they are analogous. For example, the pair cat:meow is
analogous to the pair dog:bark. There is evidence from cognitive science that
relational similarity is fundamental to many cognitive and linguistic tasks
(e.g., analogical reasoning). In the Vector Space Model (VSM) approach to
measuring relational similarity, the similarity between two pairs is calculated
by the cosine of the angle between the vectors that represent the two pairs.
The elements in the vectors are based on the frequencies of manually
constructed patterns in a large corpus. LRA extends the VSM approach in three
ways: (1) patterns are derived automatically from the corpus, (2) Singular
Value Decomposition is used to smooth the frequency data, and (3) synonyms are
used to reformulate word pairs. This paper describes the LRA algorithm and
experimentally compares LRA to VSM on two tasks, answering college-level
multiple-choice word analogy questions and classifying semantic relations in
noun-modifier expressions. LRA achieves state-of-the-art results, reaching
human-level performance on the analogy questions and significantly exceeding
VSM performance on both tasks.


title: Sensing Capacity for Markov Random Fields

abstract:
  This paper computes the sensing capacity of a sensor network, with sensors of
limited range, sensing a two-dimensional Markov random field, by modeling the
sensing operation as an encoder. Sensor observations are dependent across
sensors, and the sensor network output across different states of the
environment is neither identically nor independently distributed. Using a
random coding argument, based on the theory of types, we prove a lower bound on
the sensing capacity of the network, which characterizes the ability of the
sensor network to distinguish among environments with Markov structure, to
within a desired accuracy.


title: DNA Codes that Avoid Secondary Structures

abstract:
  In this paper, we consider the problem of designing DNA sequences (codewords)
for DNA storage systems and DNA computing that are unlikely to fold back onto
themselves to form undesirable secondary structures. The paper addresses both
the issue of enumerating the sequences with such properties and the problem of
practical code construction.


title: Very Simple Chaitin Machines for Concrete AIT

abstract:
  In 1975, Chaitin introduced his celebrated Omega number, the halting
probability of a universal Chaitin machine, a universal Turing machine with a
prefix-free domain. The Omega number's bits are {\em algorithmically
random}--there is no reason the bits should be the way they are, if we define
``reason'' to be a computable explanation smaller than the data itself. Since
that time, only {\em two} explicit universal Chaitin machines have been
proposed, both by Chaitin himself.
  Concrete algorithmic information theory involves the study of particular
universal Turing machines, about which one can state theorems with specific
numerical bounds, rather than include terms like O(1). We present several new
tiny Chaitin machines (those with a prefix-free domain) suitable for the study
of concrete algorithmic information theory. One of the machines, which we call
Keraia, is a binary encoding of lambda calculus based on a curried lambda
operator. Source code is included in the appendices.
  We also give an algorithm for restricting the domain of blank-endmarker
machines to a prefix-free domain over an alphabet that does not include the
endmarker; this allows one to take many universal Turing machines and construct
universal Chaitin machines from them.


title: On the Performance of Turbo Codes in Quasi-Static Fading Channels

abstract:
  In this paper, we investigate in detail the performance of turbo codes in
quasi-static fading channels both with and without antenna diversity. First, we
develop a simple and accurate analytic technique to evaluate the performance of
turbo codes in quasi-static fading channels. The proposed analytic technique
relates the frame error rate of a turbo code to the iterative decoder
convergence threshold, rather than to the turbo code distance spectrum.
Subsequently, we compare the performance of various turbo codes in quasi-static
fading channels. We show that, in contrast to the situation in the AWGN
channel, turbo codes with different interleaver sizes or turbo codes based on
RSC codes with different constraint lengths and generator polynomials exhibit
identical performance. Moreover, we also compare the performance of turbo codes
and convolutional codes in quasi-static fading channels under the condition of
identical decoding complexity. In particular, we show that turbo codes do not
outperform convolutional codes in quasi-static fading channels with no antenna
diversity; and that turbo codes only outperform convolutional codes in
quasi-static fading channels with antenna diversity.


title: Entropy coding with Variable Length Re-writing Systems

abstract:
  This paper describes a new set of block source codes well suited for data
compression. These codes are defined by sets of productions rules of the form
a.l->b, where a in A represents a value from the source alphabet A and l, b are
-small- sequences of bits. These codes naturally encompass other Variable
Length Codes (VLCs) such as Huffman codes. It is shown that these codes may
have a similar or even a shorter mean description length than Huffman codes for
the same encoding and decoding complexity. A first code design method allowing
to preserve the lexicographic order in the bit domain is described. The
corresponding codes have the same mean description length (mdl) as Huffman
codes from which they are constructed. Therefore, they outperform from a
compression point of view the Hu-Tucker codes designed to offer the
lexicographic property in the bit domain. A second construction method allows
to obtain codes such that the marginal bit probability converges to 0.5 as the
sequence length increases and this is achieved even if the probability
distribution function is not known by the encoder.


title: Honesty can be the best policy within quantum mechanics

abstract:
  Honesty has never been scientifically proved to be the best policy in any
case. It is pointed out that only honest person can prevent his dishonest
partner to bias the outcome of quantum coin tossing.


title: Algorithms for Discrete Denoising Under Channel Uncertainty

abstract:
  The goal of a denoising algorithm is to reconstruct a signal from its
noise-corrupted observations. Perfect reconstruction is seldom possible and
performance is measured under a given fidelity criterion. In a recent work, the
authors addressed the problem of denoising unknown discrete signals corrupted
by a discrete memoryless channel when the channel, rather than being completely
known, is only known to lie in some uncertainty set of possible channels. A
sequence of denoisers was derived for this case and shown to be asymptotically
optimal with respect to a worst-case criterion argued most relevant to this
setting. In the present work we address the implementation and complexity of
this denoiser for channels parametrized by a scalar, establishing its
practicality. We show that for symmetric channels, the problem can be mapped
into a convex optimization problem, which can be solved efficiently. We also
present empirical results suggesting the potential of these schemes to do well
in practice. A key component of our schemes is an estimator of the subset of
channels in the uncertainty set that are feasible in the sense of being able to
give rise to the noise-corrupted signal statistics for some channel input
distribution. We establish the efficiency of this estimator, both
algorithmically and experimentally. We also present a modification of the
recently developed discrete universal denoiser (DUDE) that assumes a channel
based on the said estimator, and show that, in practice, the resulting scheme
performs well. For concreteness, we focus on the binary alphabet case and
binary symmetric channels, but also discuss the extensions of the algorithms to
general finite alphabets and to general channels parameterized by a scalar.


title: SciBlog : A Tool for Scientific Collaboration

abstract:
  I describe a newly developed online scientific web-log (SciBlog). The online
facility consists of several moduls needed in a common and conventional
research activity. I show that this enables scientists around the world to
perform an online collaboration over the net.


title: Decoding of Expander Codes at Rates Close to Capacity

abstract:
  The decoding error probability of codes is studied as a function of their
block length. It is shown that the existence of codes with a polynomially small
decoding error probability implies the existence of codes with an exponentially
small decoding error probability. Specifically, it is assumed that there exists
a family of codes of length N and rate R=(1-\epsilon)C (C is a capacity of a
binary symmetric channel), whose decoding probability decreases polynomially in
1/N. It is shown that if the decoding probability decreases sufficiently fast,
but still only polynomially fast in 1/N, then there exists another such family
of codes whose decoding error probability decreases exponentially fast in N.
Moreover, if the decoding time complexity of the assumed family of codes is
polynomial in N and 1/\epsilon, then the decoding time complexity of the
presented family is linear in N and polynomial in 1/\epsilon. These codes are
compared to the recently presented codes of Barg and Zemor, ``Error Exponents
of Expander Codes,'' IEEE Trans. Inform. Theory, 2002, and ``Concatenated
Codes: Serial and Parallel,'' IEEE Trans. Inform. Theory, 2005. It is shown
that the latter families can not be tuned to have exponentially decaying (in N)
error probability, and at the same time to have decoding time complexity linear
in N and polynomial in 1/\epsilon.


title:
Disks, Partitions, Volumes and RAID Performance with the Linux Operating
  System

abstract:
  Block devices in computer operating systems typically correspond to disks or
disk partitions, and are used to store files in a filesystem. Disks are not the
only real or virtual device which adhere to the block accessible stream of
bytes block device model. Files, remote devices, or even RAM may be used as a
virtual disks. This article examines several common combinations of block
device layers used as virtual disks in the Linux operating system: disk
partitions, loopback files, software RAID, Logical Volume Manager, and Network
Block Devices. It measures their relative performance using different
filesystems: Ext2, Ext3, ReiserFS, JFS, XFS,NFS.


title:
Layered Orthogonal Lattice Detector for Two Transmit Antenna
  Communications

abstract:
  A novel detector for multiple-input multiple-output (MIMO) communications is
presented. The algorithm belongs to the class of the lattice detectors, i.e. it
finds a reduced complexity solution to the problem of finding the closest
vector to the received observations. The algorithm achieves optimal
maximum-likelihood (ML) performance in case of two transmit antennas, at the
same time keeping a complexity much lower than the exhaustive search-based ML
detection technique. Also, differently from the state-of-art lattice detector
(namely sphere decoder), the proposed algorithm is suitable for a highly
parallel hardware architecture and for a reliable bit soft-output information
generation, thus making it a promising option for real-time high-data rate
transmission.


title: Representing Digital Assets using MPEG-21 Digital Item Declaration

abstract:
  Various XML-based approaches aimed at representing compound digital assets
have emerged over the last several years. Approaches that are of specific
relevance to the digital library community include the Metadata Encoding and
Transmission Standard (METS), the IMS Content Packaging XML Binding, and the
XML Formatted Data Units (XFDU) developed by CCSDS Panel 2. The MPEG-21 Digital
Item Declaration (MPEG-21 DID) is another standard specifying the
representation of digital assets in XML that, so far, has received little
attention in the digital library community. This article gives a brief insight
into the MPEG-21 standardization effort, highlights the major characteristics
of the MPEG-21 DID Abstract Model, and describes the MPEG-21 Digital Item
Declaration Language (MPEG-21 DIDL), an XML syntax for the representation of
digital assets based on the MPEG-21 DID Abstract Model. Also, it briefly
demonstrates the potential relevance of MPEG-21 DID to the digital library
community by describing its use in the aDORe repository environment at the
Research Library of the Los Alamos National Laboratory (LANL) for the
representation of digital assets.


title:
Can Small Museums Develop Compelling, Educational and Accessible Web
  Resources? The Case of Accademia Carrara

abstract:
  Due to the lack of budget, competence, personnel and time, small museums are
often unable to develop compelling, educational and accessible web resources
for their permanent collections or temporary exhibitions. In an attempt to
prove that investing in these types of resources can be very fruitful even for
small institutions, we will illustrate the case of Accademia Carrara, a museum
in Bergamo, northern Italy, which, for a current temporary exhibition on
Cezanne and Renoir's masterpieces from the Paul Guillaume collection, developed
a series of multimedia applications, including an accessible website, rich in
content and educational material [www.cezannerenoir.it].


title: Copyright and Promotion: Oxymoron or Opportunity?

abstract:
  Copyright in the cultural sphere can act as a barrier to the dissemination of
high-quality information. On the other hand it protects works of art that might
not be made available otherwise. This dichotomy makes the area of copyright
difficult, especially when it applies to the digital arena of the web where
copying is so easy and natural. Here we present a snapshot of the issues for
online copyright, with particular emphasis on the relevance to cultural
institutions. We concentrate on Europe and the US; as an example we include a
special section dedicated to the situation in Italy.


title:
Lossy source encoding via message-passing and decimation over
  generalized codewords of LDGM codes

abstract:
  We describe message-passing and decimation approaches for lossy source coding
using low-density generator matrix (LDGM) codes. In particular, this paper
addresses the problem of encoding a Bernoulli(0.5) source: for randomly
generated LDGM codes with suitably irregular degree distributions, our methods
yield performance very close to the rate distortion limit over a range of
rates. Our approach is inspired by the survey propagation (SP) algorithm,
originally developed by Mezard et al. for solving random satisfiability
problems. Previous work by Maneva et al. shows how SP can be understood as
belief propagation (BP) for an alternative representation of satisfiability
problems. In analogy to this connection, our approach is to define a family of
Markov random fields over generalized codewords, from which local
message-passing rules can be derived in the standard way. The overall source
encoding method is based on message-passing, setting a subset of bits to their
preferred values (decimation), and reducing the code.


title: Real Hypercomputation and Continuity

abstract:
  By the sometimes so-called 'Main Theorem' of Recursive Analysis, every
computable real function is necessarily continuous. We wonder whether and which
kinds of HYPERcomputation allow for the effective evaluation of also
discontinuous f:R->R. More precisely the present work considers the following
three super-Turing notions of real function computability:
  * relativized computation; specifically given oracle access to the Halting
Problem 0' or its jump 0'';
  * encoding real input x and/or output y=f(x) in weaker ways also related to
the Arithmetic Hierarchy;
  * non-deterministic computation.
  It turns out that any f:R->R computable in the first or second sense is still
necessarily continuous whereas the third type of hypercomputation does provide
the required power to evaluate for instance the discontinuous sign function.


title:
MAP estimation via agreement on (hyper)trees: Message-passing and linear
  programming

abstract:
  We develop and analyze methods for computing provably optimal {\em maximum a
posteriori} (MAP) configurations for a subclass of Markov random fields defined
on graphs with cycles. By decomposing the original distribution into a convex
combination of tree-structured distributions, we obtain an upper bound on the
optimal value of the original problem (i.e., the log probability of the MAP
assignment) in terms of the combined optimal values of the tree problems. We
prove that this upper bound is tight if and only if all the tree distributions
share an optimal configuration in common. An important implication is that any
such shared configuration must also be a MAP configuration for the original
distribution. Next we develop two approaches to attempting to obtain tight
upper bounds: (a) a {\em tree-relaxed linear program} (LP), which is derived
from the Lagrangian dual of the upper bounds; and (b) a {\em tree-reweighted
max-product message-passing algorithm} that is related to but distinct from the
max-product algorithm. In this way, we establish a connection between a certain
LP relaxation of the mode-finding problem, and a reweighted form of the
max-product (min-sum) message-passing algorithm.


title: Every decision tree has an influential variable

abstract:
  We prove that for any decision tree calculating a boolean function
$f:\{-1,1\}^n\to\{-1,1\}$, \[ \Var[f] \le \sum_{i=1}^n \delta_i \Inf_i(f), \]
where $\delta_i$ is the probability that the $i$th input variable is read and
$\Inf_i(f)$ is the influence of the $i$th variable on $f$. The variance,
influence and probability are taken with respect to an arbitrary product
measure on $\{-1,1\}^n$. It follows that the minimum depth of a decision tree
calculating a given balanced function is at least the reciprocal of the largest
influence of any input variable. Likewise, any balanced boolean function with a
decision tree of depth $d$ has a variable with influence at least
$\frac{1}{d}$. The only previous nontrivial lower bound known was $\Omega(d
2^{-d})$. Our inequality has many generalizations, allowing us to prove
influence lower bounds for randomized decision trees, decision trees on
arbitrary product probability spaces, and decision trees with non-boolean
outputs. As an application of our results we give a very easy proof that the
randomized query complexity of nontrivial monotone graph properties is at least
$\Omega(v^{4/3}/p^{1/3})$, where $v$ is the number of vertices and $p \leq
\half$ is the critical threshold probability. This supersedes the milestone
$\Omega(v^{4/3})$ bound of Hajnal and is sometimes superior to the best known
lower bounds of Chakrabarti-Khot and Friedgut-Kahn-Wigderson.


title:
On Achievable Rates and Complexity of LDPC Codes for Parallel Channels
  with Application to Puncturing

abstract:
  This paper considers the achievable rates and decoding complexity of
low-density parity-check (LDPC) codes over statistically independent parallel
channels. The paper starts with the derivation of bounds on the conditional
entropy of the transmitted codeword given the received sequence at the output
of the parallel channels; the component channels are considered to be
memoryless, binary-input, and output-symmetric (MBIOS). These results serve for
the derivation of an upper bound on the achievable rates of ensembles of LDPC
codes under optimal maximum-likelihood (ML) decoding when their transmission
takes place over parallel MBIOS channels. The paper relies on the latter bound
for obtaining upper bounds on the achievable rates of ensembles of randomly and
intentionally punctured LDPC codes over MBIOS channels. The paper also provides
a lower bound on the decoding complexity (per iteration) of ensembles of LDPC
codes under message-passing iterative decoding over parallel MBIOS channels;
the bound is given in terms of the gap between the rate of these codes for
which reliable communication is achievable and the channel capacity. The paper
presents a diagram which shows interconnections between the theorems introduced
in this paper and some other previously reported results. The setting which
serves for the derivation of the bounds on the achievable rates and decoding
complexity is general, and the bounds can be applied to other scenarios which
can be treated as different forms of communication over parallel channels.


title: Universal Learning of Repeated Matrix Games

abstract:
  We study and compare the learning dynamics of two universal learning
algorithms, one based on Bayesian learning and the other on prediction with
expert advice. Both approaches have strong asymptotic performance guarantees.
When confronted with the task of finding good long-term strategies in repeated
2x2 matrix games, they behave quite differently.


title:
Throughput and Delay in Random Wireless Networks with Restricted
  Mobility

abstract:
  Grossglauser and Tse (2001) introduced a mobile random network model where
each node moves independently on a unit disk according to a stationary uniform
distribution and showed that a throughput of $\Theta(1)$ is achievable. El
Gamal, Mammen, Prabhakar and Shah (2004) showed that the delay associated with
this throughput scales as $\Theta(n\log n)$, when each node moves according to
an independent random walk. In a later work, Diggavi, Grossglauser and Tse
(2002) considered a random network on a sphere with a restricted mobility
model, where each node moves along a randomly chosen great circle on the unit
sphere. They showed that even with this one-dimensional restriction on
mobility, constant throughput scaling is achievable. Thus, this particular
mobility restriction does not affect the throughput scaling. This raises the
question whether this mobility restriction affects the delay scaling.
  This paper studies the delay scaling at $\Theta(1)$ throughput for a random
network with restricted mobility. First, a variant of the scheme presented by
Diggavi, Grossglauser and Tse (2002) is presented and it is shown to achieve
$\Theta(1)$ throughput using different (and perhaps simpler) techniques. The
exact order of delay scaling for this scheme is determined, somewhat
surprisingly, to be of $\Theta(n\log n)$, which is the same as that without the
mobility restriction. Thus, this particular mobility restriction \emph{does
not} affect either the maximal throughput scaling or the corresponding delay
scaling of the network. This happens because under this 1-D restriction, each
node is in the proximity of every other node in essentially the same manner as
without this restriction.


title: Complexity of Networks

abstract:
  Network or graph structures are ubiquitous in the study of complex systems.
Often, we are interested in complexity trends of these system as it evolves
under some dynamic. An example might be looking at the complexity of a food web
as species enter an ecosystem via migration or speciation, and leave via
extinction.
  In this paper, a complexity measure of networks is proposed based on the {\em
complexity is information content} paradigm. To apply this paradigm to any
object, one must fix two things: a representation language, in which strings of
symbols from some alphabet describe, or stand for the objects being considered;
and a means of determining when two such descriptions refer to the same object.
With these two things set, the information content of an object can be computed
in principle from the number of equivalent descriptions describing a particular
object.
  I propose a simple representation language for undirected graphs that can be
encoded as a bitstring, and equivalence is a topological equivalence. I also
present an algorithm for computing the complexity of an arbitrary undirected
network.


title: Myopic Coding in Multiple Relay Channels

abstract:
  In this paper, we investigate achievable rates for data transmission from
sources to sinks through multiple relay networks. We consider myopic coding, a
constrained communication strategy in which each node has only a local view of
the network, meaning that nodes can only transmit to and decode from
neighboring nodes. We compare this with omniscient coding, in which every node
has a global view of the network and all nodes can cooperate. Using Gaussian
channels as examples, we find that when the nodes transmit at low power, the
rates achievable with two-hop myopic coding are as large as that under
omniscient coding in a five-node multiple relay channel and close to that under
omniscient coding in a six-node multiple relay channel. These results suggest
that we may do local coding and cooperation without compromising much on the
transmission rate. Practically, myopic coding schemes are more robust to
topology changes because encoding and decoding at a node are not affected when
there are changes at remote nodes. Furthermore, myopic coding mitigates the
high computational complexity and large buffer/memory requirements of
omniscient coding.


title: Families of unitary matrices achieving full diversity

abstract:
  This paper presents an algebraic construction of families of unitary matrices
that achieve full diversity. They are obtained as subsets of cyclic division
algebras.


title:
Proceedings of the 15th Workshop on Logic-based methods in Programming
  Environments WLPE'05 -- October 5, 2005 -- Sitges (Barcelona), Spain

abstract:
  This volume contains papers presented at WLPE 2005, 15th International
Workshop on Logic-based methods in Programming Environments.
  The aim of the workshop is to provide an informal meeting for the researchers
working on logic-based tools for development and analysis of programs. This
year we emphasized two aspects: on one hand the presentation, pragmatics and
experiences of tools for logic programming environments; on the other one,
logic-based environmental tools for programming in general.
  The workshop took place in Sitges (Barcelona), Spain as a satellite workshop
of the 21th International Conference on Logic Programming (ICLP 2005). This
workshop continues the series of successful international workshops on logic
programming environments held in Ohio, USA (1989), Eilat, Israel (1990), Paris,
France (1991), Washington, USA (1992), Vancouver, Canada (1993), Santa
Margherita Ligure, Italy (1994), Portland, USA (1995), Leuven, Belgium and Port
Jefferson, USA (1997), Las Cruces, USA (1999), Paphos, Cyprus (2001),
Copenhagen, Denmark (2002), Mumbai, India (2003) and Saint Malo, France (2004).
  We have received eight submissions (2 from France, 2 Spain-US cooperations,
one Spain-Argentina cooperation, one from Japan, one from the United Kingdom
and one Sweden-France cooperation). Program committee has decided to accept
seven papers. This volume contains revised versions of the accepted papers.
  We are grateful to the authors of the papers, the reviewers and the members
of the Program Committee for the help and fruitful discussions.


title: Re-visiting the One-Time Pad

abstract:
  In 1949, Shannon proved the perfect secrecy of the Vernam cryptographic
system,also popularly known as the One-Time Pad (OTP). Since then, it has been
believed that the perfectly random and uncompressible OTP which is transmitted
needs to have a length equal to the message length for this result to be true.
In this paper, we prove that the length of the transmitted OTP which actually
contains useful information need not be compromised and could be less than the
message length without sacrificing perfect secrecy. We also provide a new
interpretation for the OTP encryption by treating the message bits as making
True/False statements about the pad, which we define as a private-object. We
introduce the paradigm of private-object cryptography where messages are
transmitted by verifying statements about a secret-object. We conclude by
suggesting the use of Formal Axiomatic Systems for investing N bits of secret.


title: A 3D RGB Axis-based Color-oriented Cryptography

abstract:
  In this document, a formal approach to encrypt, decrypt, transmit and receive
information using colors is explored. A piece of information consists of set of
symbols with a definite property imposed on the generating set. The symbols are
usually encoded using ascii scheme. A linear to 3d transformation is presented.
The change of axis from traditional xyz to rgb is highlighted and its effect
are studied. A point in this new axis is then represented as a unique color and
a vector or matrix is associated with it, making it amenable to standard vector
or matrix operations. A formal notion on hybrid cryptography is introduced as
the algorithm lies on the boundary of symmetric and asymmetric cryptography. No
discussion is complete, without mentioning reference to communication aspects
of secure information in a channel. Transmission scheme pertaining to light as
carrier is introduced and studied. Key-exchanges do not come under the scope of
current frame of document.


title: ZEUS - A Domain-Oriented Fact Comparison Based Authentication Protocol

abstract:
  In this paper, facts existing in different domains are explored, which are
comparable by their end result. Properties of various domains and the facts
that are part of such a unit are also presented, examples of comparison and
methods of usage as means of zero-knowledge protocols are given, finally a
zero-knowledge protocol based on afore-mentioned concept is given.


title: The Structure of Collaborative Tagging Systems

abstract:
  Collaborative tagging describes the process by which many users add metadata
in the form of keywords to shared content. Recently, collaborative tagging has
grown in popularity on the web, on sites that allow users to tag bookmarks,
photographs and other content. In this paper we analyze the structure of
collaborative tagging systems as well as their dynamical aspects. Specifically,
we discovered regularities in user activity, tag frequencies, kinds of tags
used, bursts of popularity in bookmarking and a remarkable stability in the
relative proportions of tags within a given url. We also present a dynamical
model of collaborative tagging that predicts these stable patterns and relates
them to imitation and shared knowledge.


title: A General Framework for Codes Involving Redundancy Minimization

abstract:
  A framework with two scalar parameters is introduced for various problems of
finding a prefix code minimizing a coding penalty function. The framework
encompasses problems previously proposed by Huffman, Campbell, Nath, and Drmota
and Szpankowski, shedding light on the relationships among these problems. In
particular, Nath's range of problems can be seen as bridging the minimum
average redundancy problem of Huffman with the minimum maximum pointwise
redundancy problem of Drmota and Szpankowski. Using this framework, two
linear-time Huffman-like algorithms are devised for the minimum maximum
pointwise redundancy problem, the only one in the framework not previously
solved with a Huffman-like algorithm. Both algorithms provide solutions common
to this problem and a subrange of Nath's problems, the second algorithm being
distinguished by its ability to find the minimum variance solution among all
solutions common to the minimum maximum pointwise redundancy and Nath problems.
Simple redundancy bounds are also presented.


title: Source Coding for Quasiarithmetic Penalties

abstract:
  Huffman coding finds a prefix code that minimizes mean codeword length for a
given probability distribution over a finite number of items. Campbell
generalized the Huffman problem to a family of problems in which the goal is to
minimize not mean codeword length but rather a generalized mean known as a
quasiarithmetic or quasilinear mean. Such generalized means have a number of
diverse applications, including applications in queueing. Several
quasiarithmetic-mean problems have novel simple redundancy bounds in terms of a
generalized entropy. A related property involves the existence of optimal
codes: For ``well-behaved'' cost functions, optimal codes always exist for
(possibly infinite-alphabet) sources having finite generalized entropy. Solving
finite instances of such problems is done by generalizing an algorithm for
finding length-limited binary codes to a new algorithm for finding optimal
binary codes for any quasiarithmetic mean with a convex cost function. This
algorithm can be performed using quadratic time and linear space, and can be
extended to other penalty functions, some of which are solvable with similar
space and time complexity, and others of which are solvable with slightly
greater complexity. This reduces the computational complexity of a problem
involving minimum delay in a queue, allows combinations of previously
considered problems to be optimized, and greatly expands the space of problems
solvable in quadratic time and linear space. The algorithm can be extended for
purposes such as breaking ties among possibly different optimal codes, as with
bottom-merge Huffman coding.


title: On the Asymptotic Performance of Iterative Decoders for Product Codes

abstract:
  We consider hard-decision iterative decoders for product codes over the
erasure channel, which employ repeated rounds of decoding rows and columns
alternatingly. We derive the exact asymptotic probability of decoding failure
as a function of the error-correction capabilities of the row and column codes,
the number of decoding rounds, and the channel erasure probability. We examine
both the case of codes capable of correcting a constant amount of errors, and
the case of codes capable of correcting a constant fraction of their length.


title: High-performance BWT-based Encoders

abstract:
  In 1994, Burrows and Wheeler developed a data compression algorithm which
performs significantly better than Lempel-Ziv based algorithms. Since then, a
lot of work has been done in order to improve their algorithm, which is based
on a reversible transformation of the input string, called BWT (the
Burrows-Wheeler transformation). In this paper, we propose a compression scheme
based on BWT, MTF (move-to-front coding), and a version of the algorithms
presented in [Dragos Trinca, ITCC-2004].


title: Modelling the Eulerian Path Problem using a String Matching Framework

abstract:
  The well-known Eulerian path problem can be solved in polynomial time (more
exactly, there exists a linear time algorithm for this problem). In this paper,
we model the problem using a string matching framework, and then initiate an
algorithmic study on a variant of this problem, called the (2,1)-STRING-MATCH
problem (which is actually a generalization of the Eulerian path problem).
Then, we present a polynomial-time algorithm for the (2,1)-STRING-MATCH
problem, which is the most important result of this paper. Specifically, we get
a lower bound of Omega(n), and an upper bound of O(n^{2}).


title: Special Cases of Encodings by Generalized Adaptive Codes

abstract:
  Adaptive (variable-length) codes associate variable-length codewords to
symbols being encoded depending on the previous symbols in the input data
string. This class of codes has been presented in [Dragos Trinca,
cs.DS/0505007] as a new class of non-standard variable-length codes.
Generalized adaptive codes (GA codes, for short) have been also presented in
[Dragos Trinca, cs.DS/0505007] not only as a new class of non-standard
variable-length codes, but also as a natural generalization of adaptive codes
of any order. This paper is intended to continue developing the theory of
variable-length codes by establishing several interesting connections between
adaptive codes and other classes of codes. The connections are discussed not
only from a theoretical point of view (by proving new results), but also from
an applicative one (by proposing several applications). First, we prove that
adaptive Huffman encodings and Lempel-Ziv encodings are particular cases of
encodings by GA codes. Second, we show that any (n,1,m) convolutional code
satisfying certain conditions can be modelled as an adaptive code of order m.
Third, we describe a cryptographic scheme based on the connection between
adaptive codes and convolutional codes, and present an insightful analysis of
this scheme. Finally, we conclude by generalizing adaptive codes to
(p,q)-adaptive codes, and discussing connections between adaptive codes and
time-varying codes.


title: Modelling the EAH Data Compression Algorithm using Graph Theory

abstract:
  Adaptive codes associate variable-length codewords to symbols being encoded
depending on the previous symbols in the input data string. This class of codes
has been introduced in [Dragos Trinca, cs.DS/0505007] as a new class of
non-standard variable-length codes. New algorithms for data compression, based
on adaptive codes of order one, have been presented in [Dragos Trinca,
ITCC-2004], where we have behaviorally shown that for a large class of input
data strings, these algorithms substantially outperform the Lempel-Ziv
universal data compression algorithm. EAH has been introduced in [Dragos
Trinca, cs.DS/0505061], as an improved generalization of these algorithms. In
this paper, we present a translation of the EAH algorithm into the graph
theory.


title: Translating the EAH Data Compression Algorithm into Automata Theory

abstract:
  Adaptive codes have been introduced in [Dragos Trinca, cs.DS/0505007] as a
new class of non-standard variable-length codes. These codes associate
variable-length codewords to symbols being encoded depending on the previous
symbols in the input data string. A new data compression algorithm, called EAH,
has been introduced in [Dragos Trinca, cs.DS/0505061], where we have
behaviorally shown that for a large class of input data strings, this algorithm
substantially outperforms the well-known Lempel-Ziv universal data compression
algorithm. In this paper, we translate the EAH encoder into automata theory.


title: Extending Prolog with Incomplete Fuzzy Information

abstract:
  Incomplete information is a problem in many aspects of actual environments.
Furthermore, in many sceneries the knowledge is not represented in a crisp way.
It is common to find fuzzy concepts or problems with some level of uncertainty.
There are not many practical systems which handle fuzziness and uncertainty and
the few examples that we can find are used by a minority. To extend a popular
system (which many programmers are using) with the ability of combining crisp
and fuzzy knowledge representations seems to be an interesting issue.
  Our first work (Fuzzy Prolog) was a language that models
$\mathcal{B}([0,1])$-valued Fuzzy Logic. In the Borel algebra,
$\mathcal{B}([0,1])$, truth value is represented using unions of intervals of
real numbers. This work was more general in truth value representation and
propagation than previous works.
  An interpreter for this language using Constraint Logic Programming over Real
numbers (CLP(${\cal R}$)) was implemented and is available in the Ciao system.
  Now, we enhance our former approach by using default knowledge to represent
incomplete information in Logic Programming. We also provide the implementation
of this new framework. This new release of Fuzzy Prolog handles incomplete
information, it has a complete semantics (the previous one was incomplete as
Prolog) and moreover it is able to combine crisp and fuzzy logic in Prolog
programs. Therefore, new Fuzzy Prolog is more expressive to represent real
world.
  Fuzzy Prolog inherited from Prolog its incompleteness. The incorporation of
default reasoning to Fuzzy Prolog removes this problem and requires a richer
semantics which we discuss.


title: Summarizing Reports on Evolving Events; Part I: Linear Evolution

abstract:
  We present an approach for summarization from multiple documents which report
on events that evolve through time, taking into account the different document
sources. We distinguish the evolution of an event into linear and non-linear.
According to our approach, each document is represented by a collection of
messages which are then used in order to instantiate the cross-document
relations that determine the summary content. The paper presents the
summarization system that implements this approach through a case study on
linear evolution.


title:
Performance of PPM Multipath Synchronization in the Limit of Large
  Bandwidth

abstract:
  The acquisition, or synchronization, of the multipath profile for an
ultrawideband pulse position modulation (PPM) communication systems is
considered. Synchronization is critical for the proper operation of PPM based
For the multipath channel, it is assumed that channel gains are known, but path
delays are unknown. In the limit of large bandwidth, W, it is assumed that the
number of paths, L, grows. The delay spread of the channel, M, is proportional
to the bandwidth. The rate of growth of L versus M determines whether
synchronization can occur. It is shown that if L/sqrt(M) --> 0, then the
maximum likelihood synchronizer cannot acquire any of the paths and
alternatively if L/M --> 0, the maximum likelihood synchronizer is guaranteed
to miss at least one path.


title:
Conference Key Agreement and Quantum Sharing of Classical Secrets with
  Noisy GHZ States

abstract:
  We propose a wide class of distillation schemes for multi-partite entangled
states that are CSS-states. Our proposal provides not only superior efficiency,
but also new insights on the connection between CSS-states and bipartite graph
states. We then consider the applications of our distillation schemes for two
cryptographic tasks--namely, (a) conference key agreement and (b) quantum
sharing of classical secrets. In particular, we construct
``prepare-and-measure'' protocols. Also we study the yield of those protocols
and the threshold value of the fidelity above which the protocols can function
securely. Surprisingly, our protocols will function securely even when the
initial state does not violate the standard Bell-inequalities for GHZ states.
Experimental realization involving only bi-partite entanglement is also
suggested.


title: Capacity of Ultra Wide Band Wireless Ad Hoc Networks

abstract:
  Throughput capacity is a critical parameter for the design and evaluation of
ad-hoc wireless networks. Consider n identical randomly located nodes, on a
unit area, forming an ad-hoc wireless network. Assuming a fixed per node
transmission capability of T bits per second at a fixed range, it has been
shown that the uniform throughput capacity per node r(n) is Theta((T)/(sqrt{n
log n})), a decreasing function of node density n.
  However an alternate communication model may also be considered, with each
node constrained to a maximum transmit power P_0 and capable of utilizing W Hz
of bandwidth. Under the limiting case W rightarrow infinity, such as in Ultra
Wide Band (UWB) networks, the uniform throughput per node is O ((n log
n)^{(alpha-1}/2}) (upper bound) and Omega((n^{(alpha-1)/2})/((log n)^{(alpha
+1)/2})) (achievable lower bound).
  These bounds demonstrate that throughput increases with node density $n$, in
contrast to previously published results. This is the result of the large
bandwidth, and the assumed power and rate adaptation, which alleviate
interference. Thus, the effect of physical layer properties on the capacity of
ad hoc wireless networks is demonstrated. Further, the promise of UWB as a
physical layer technology for ad-hoc networks is justified.


title:
On Multiple User Channels with Causal State Information at the
  Transmitters

abstract:
  We extend Shannon's result on the capacity of channels with state information
to multiple user channels. More specifically, we characterize the capacity
(region) of degraded broadcast channels and physically degraded relay channels
where the channel state information is causally available at the transmitters.
We also obtain inner and outer bounds on the capacity region for multiple
access channels with causal state information at the transmitters.


title: Tightness of LP via Max-product Belief Propagation

abstract:
  We investigate the question of tightness of linear programming (LP)
relaxation for finding a maximum weight independent set (MWIS) in sparse random
weighted graphs. We show that an edge-based LP relaxation is asymptotically
tight for Erdos-Renyi graph $G(n,c/n)$ for $c \leq 2e$ and random regular graph
$G(n,r)$ for $r\leq 4$ when node weights are i.i.d. with exponential
distribution of mean 1. We establish these results, through a precise relation
between the tightness of LP relaxation and convergence of the max-product
belief propagation algorithm. We believe that this novel method of
understanding structural properties of combinatorial problems through
properties of iterative procedure such as the max-product should be of interest
in its own right.


title: An Explicit Construction of Universally Decodable Matrices

abstract:
  Universally decodable matrices can be used for coding purposes when
transmitting over slow fading channels. These matrices are parameterized by
positive integers $L$ and $n$ and a prime power $q$. Based on Pascal's triangle
we give an explicit construction of universally decodable matrices for any
non-zero integers $L$ and $n$ and any prime power $q$ where $L \leq q+1$. This
is the largest set of possible parameter values since for any list of
universally decodable matrices the value $L$ is upper bounded by $q+1$, except
for the trivial case $n = 1$. For the proof of our construction we use
properties of Hasse derivatives, and it turns out that our construction has
connections to Reed-Solomon codes, Reed-Muller codes, and so-called
repeated-root cyclic codes. Additionally, we show how universally decodable
matrices can be modified so that they remain universally decodable matrices.


title: Search Process and Probabilistic Bifix Approach

abstract:
  An analytical approach to a search process is a mathematical prerequisite for
digital synchronization acquisition analysis and optimization. A search is
performed for an arbitrary set of sequences within random but not equiprobable
L-ary data. This paper derives in detail an expression for probability
distribution function, from which other statistical parameters - expected value
and variance - can be obtained. The probabilistic nature of (cross-) bifix
indicators is shown and application examples are outlined, ranging beyond the
usual telecommunication field.


title: A primer on Answer Set Programming

abstract:
  A introduction to the syntax and Semantics of Answer Set Programming intended
as an handout to [under]graduate students taking Artificial Intlligence or
Logic Programming classes.


title: Maximum Weight Matching via Max-Product Belief Propagation

abstract:
  Max-product "belief propagation" is an iterative, local, message-passing
algorithm for finding the maximum a posteriori (MAP) assignment of a discrete
probability distribution specified by a graphical model. Despite the
spectacular success of the algorithm in many application areas such as
iterative decoding, computer vision and combinatorial optimization which
involve graphs with many cycles, theoretical results about both correctness and
convergence of the algorithm are known in few cases (Weiss-Freeman Wainwright,
Yeddidia-Weiss-Freeman, Richardson-Urbanke}.
  In this paper we consider the problem of finding the Maximum Weight Matching
(MWM) in a weighted complete bipartite graph. We define a probability
distribution on the bipartite graph whose MAP assignment corresponds to the
MWM. We use the max-product algorithm for finding the MAP of this distribution
or equivalently, the MWM on the bipartite graph. Even though the underlying
bipartite graph has many short cycles, we find that surprisingly, the
max-product algorithm always converges to the correct MAP assignment as long as
the MAP assignment is unique. We provide a bound on the number of iterations
required by the algorithm and evaluate the computational cost of the algorithm.
We find that for a graph of size $n$, the computational cost of the algorithm
scales as $O(n^3)$, which is the same as the computational cost of the best
known algorithm. Finally, we establish the precise relation between the
max-product algorithm and the celebrated {\em auction} algorithm proposed by
Bertsekas. This suggests possible connections between dual algorithm and
max-product algorithm for discrete optimization problems.


title: Investigations of Process Damping Forces in Metal Cutting

abstract:
  Using finite element software developed for metal cutting by Third Wave
Systems we investigate the forces involved in chatter, a self-sustained
oscillation of the cutting tool. The phenomena is decomposed into a vibrating
tool cutting a flat surface work piece, and motionless tool cutting a work
piece with a wavy surface. While cutting the wavy surface, the shearplane was
seen to oscillate in advance of the oscillation of the depth of cut, as were
the cutting, thrust, and shear plane forces. The vibrating tool was used to
investigate process damping through the interaction of the relief face of the
tool and the workpiece. Crushing forces are isolated and compared to the
contact length between the tool and workpiece. We found that the wavelength
dependence of the forces depended on the relative size of the wavelength to the
length of the relief face of the tool. The results indicate that the damping
force from crushing will be proportional to the cutting speed for short tools,
and inversely proportional for long tools.


title: Corpus-based Learning of Analogies and Semantic Relations

abstract:
  We present an algorithm for learning from unlabeled text, based on the Vector
Space Model (VSM) of information retrieval, that can solve verbal analogy
questions of the kind found in the SAT college entrance exam. A verbal analogy
has the form A:B::C:D, meaning "A is to B as C is to D"; for example,
mason:stone::carpenter:wood. SAT analogy questions provide a word pair, A:B,
and the problem is to select the most analogous word pair, C:D, from a set of
five choices. The VSM algorithm correctly answers 47% of a collection of 374
college-level analogy questions (random guessing would yield 20% correct; the
average college-bound senior high school student answers about 57% correctly).
We motivate this research by applying it to a difficult problem in natural
language processing, determining semantic relations in noun-modifier pairs. The
problem is to classify a noun-modifier pair, such as "laser printer", according
to the semantic relation between the noun (printer) and the modifier (laser).
We use a supervised nearest-neighbour algorithm that assigns a class to a given
noun-modifier pair by finding the most analogous noun-modifier pair in the
training data. With 30 classes of semantic relations, on a collection of 600
labeled noun-modifier pairs, the learning algorithm attains an F value of 26.5%
(random guessing: 3.3%). With 5 classes of semantic relations, the F value is
43.2% (random: 20%). The performance is state-of-the-art for both verbal
analogies and noun-modifier relations.


title: A Generalised Hadamard Transform

abstract:
  A Generalised Hadamard Transform for multi-phase or multilevel signals is
introduced, which includes the Fourier, Generalised, Discrete Fourier,
Walsh-Hadamard and Reverse Jacket Transforms. The jacket construction is
formalised and shown to admit a tensor product decomposition. Primary matrices
under this decomposition are identified. New examples of primary jacket
matrices of orders 8 and 12 are presented.


title:
A Tracer Driver for Versatile Dynamic Analyses of Constraint Logic
  Programs

abstract:
  Programs with constraints are hard to debug. In this paper, we describe a
general architecture to help develop new debugging tools for constraint
programming. The possible tools are fed by a single general-purpose tracer. A
tracer-driver is used to adapt the actual content of the trace, according to
the needs of the tool. This enables the tools and the tracer to communicate in
a client-server scheme. Each tool describes its needs of execution data thanks
to event patterns. The tracer driver scrutinizes the execution according to
these event patterns and sends only the data that are relevant to the connected
tools. Experimental measures show that this approach leads to good performance
in the context of constraint logic programming, where a large variety of tools
exists and the trace is potentially huge.


title:
An Improved Non-Termination Criterion for Binary Constraint Logic
  Programs

abstract:
  On one hand, termination analysis of logic programs is now a fairly
established research topic within the logic programming community. On the other
hand, non-termination analysis seems to remain a much less attractive subject.
If we divide this line of research into two kinds of approaches: dynamic versus
static analysis, this paper belongs to the latter. It proposes a criterion for
detecting non-terminating atomic queries with respect to binary CLP clauses,
which strictly generalizes our previous works on this subject. We give a
generic operational definition and a logical form of this criterion. Then we
show that the logical form is correct and complete with respect to the
operational definition.


title: New Upper Bounds on A(n,d)

abstract:
  Upper bounds on the maximum number of codewords in a binary code of a given
length and minimum Hamming distance are considered. New bounds are derived by a
combination of linear programming and counting arguments. Some of these bounds
improve on the best known analytic bounds. Several new record bounds are
obtained for codes with small lengths.


title: Proving or Disproving likely Invariants with Constraint Reasoning

abstract:
  A program invariant is a property that holds for every execution of the
program. Recent work suggest to infer likely-only invariants, via dynamic
analysis. A likely invariant is a property that holds for some executions but
is not guaranteed to hold for all executions. In this paper, we present work in
progress addressing the challenging problem of automatically verifying that
likely invariants are actual invariants. We propose a constraint-based
reasoning approach that is able, unlike other approaches, to both prove or
disprove likely invariants. In the latter case, our approach provides
counter-examples. We illustrate the approach on a motivating example where
automatically generated likely invariants are verified.


title: Enhancing the Alloy Analyzer with Patterns of Analysis

abstract:
  Formal techniques have been shown to be useful in the development of correct
software. But the level of expertise required of practitioners of these
techniques prohibits their widespread adoption. Formal techniques need to be
tailored to the commercial software developer. Alloy is a lightweight
specification language supported by the Alloy Analyzer (AA), a tool based on
off-the-shelf SAT technology. The tool allows a user to check interactively
whether given properties are consistent or valid with respect to a high-level
specification, providing an environment in which the correctness of such a
specification may be established. However, Alloy is not particularly suited to
expressing program specifications and the feedback provided by AA can be
misleading where the specification under analysis or the property being checked
contains inconsistencies. In this paper, we address these two shortcomings.
Firstly, we present a lightweight language called "Loy", tailored to the
specification of object-oriented programs. An encoding of Loy into Alloy is
provided so that AA can be used for automated analysis of Loy program
specifications. Secondly, we present some "patterns of analysis" that guide a
developer through the analysis of a Loy specification in order to establish its
correctness before implementation.


title:
Relations between semantic security and indistinguishability against
  cpa, non-adaptive cca and adaptive cca in comparison based framework

abstract:
  In this paper we try to unify the frameworks of definitions of semantic
security, indistinguishability and non-malleability by defining semantic
security in comparison based framework. This facilitates the study of relations
among these goals against different attack models and makes the proof of the
equivalence of semantic security and indistinguishability easier and more
understandable. Besides, our proof of the equivalence of semantic security and
indistinguishability does not need any intermediate goals such as non
devidability to change the definition framework.


title:
A Generic Framework for the Analysis and Specialization of Logic
  Programs

abstract:
  The relationship between abstract interpretation and partial deduction has
received considerable attention and (partial) integrations have been proposed
starting from both the partial deduction and abstract interpretation
perspectives. In this work we present what we argue is the first fully
described generic algorithm for efficient and precise integration of abstract
interpretation and partial deduction. Taking as starting point state-of-the-art
algorithms for context-sensitive, polyvariant abstract interpretation and
(abstract) partial deduction, we present an algorithm which combines the best
of both worlds. Key ingredients include the accurate success propagation
inherent to abstract interpretation and the powerful program transformations
achievable by partial deduction. In our algorithm, the calls which appear in
the analysis graph are not analyzed w.r.t. the original definition of the
procedure but w.r.t. specialized definitions of these procedures. Such
specialized definitions are obtained by applying both unfolding and abstract
executability. Our framework is parametric w.r.t. different control strategies
and abstract domains. Different combinations of such parameters correspond to
existing algorithms for program analysis and specialization. Simultaneously,
our approach opens the door to the efficient computation of strictly more
precise results than those achievable by each of the individual techniques. The
algorithm is now one of the key components of the CiaoPP analysis and
specialization system.


title: A study of set-sharing analysis via cliques

abstract:
  We study the problem of efficient, scalable set-sharing analysis of logic
programs. We use the idea of representing sharing information as a pair of
abstract substitutions, one of which is a worst-case sharing representation
called a clique set, which was previously proposed for the case of inferring
pair-sharing. We use the clique-set representation for (1) inferring actual
set-sharing information, and (2) analysis within a top-down framework. In
particular, we define the abstract functions required by standard top-down
analyses, both for sharing alone and also for the case of including freeness in
addition to sharing. Our experimental evaluation supports the conclusion that,
for inferring set-sharing, as it was the case for inferring pair-sharing,
precision losses are limited, while useful efficiency gains are obtained. At
the limit, the clique-set representation allowed analyzing some programs that
exceeded memory capacity using classical sharing representations.


title:
Asymptotically fast polynomial matrix algorithms for multivariable
  systems

abstract:
  We present the asymptotically fastest known algorithms for some basic
problems on univariate polynomial matrices: rank, nullspace, determinant,
generic inverse, reduced form. We show that they essentially can be reduced to
two computer algebra techniques, minimal basis computations and matrix fraction
expansion/reconstruction, and to polynomial matrix multiplication. Such
reductions eventually imply that all these problems can be solved in about the
same amount of time as polynomial matrix multiplication.


title:
A Family of Binary Sequences with Optimal Correlation Property and Large
  Linear Span

abstract:
  A family of binary sequences is presented and proved to have optimal
correlation property and large linear span. It includes the small set of Kasami
sequences, No sequence set and TN sequence set as special cases. An explicit
lower bound expression on the linear span of sequences in the family is given.
With suitable choices of parameters, it is proved that the family has
exponentially larger linear spans than both No sequences and TN sequences. A
class of ideal autocorrelation sequences is also constructed and proved to have
large linear span.


title: New Sequence Sets with Zero-Correlation Zone

abstract:
  A method for constructing sets of sequences with zero-correlation zone (ZCZ
sequences) and sequence sets with low cross correlation is proposed. The method
is to use families of short sequences and complete orthogonal sequence sets to
derive families of long sequences with desired correlation properties. It is a
unification of works of Matsufuji and Torii \emph{et al.}, and there are more
choices of parameters of sets for our method. In particular, ZCZ sequence sets
generated by the method can achieve a related ZCZ bound. Furthermore, the
proposed method can be utilized to derive new ZCZ sets with both longer ZCZ and
larger set size from known ZCZ sets. These sequence sets are applicable in
broadband satellite IP networks.


title: Quantum Algorithm Processors to Reveal Hamiltonian Cycles

abstract:
  Quantum computer versus quantum algorithm processor in CMOS are compared to
find (in parallel) all Hamiltonian cycles in a graph with m edges and n
vertices, each represented by k bits. A quantum computer uses quantum states
analogous to CMOS registers. With efficient initialization, number of CMOS
registers is proportional to (n-1)! Number of qubits in a quantum computer is
approximately proportional to kn+2mn in the approach below. Using CMOS, the
bits per register is about proportional to kn, which is less since bits can be
irreversibly reset. In either concept, number of gates, or operations to
identify Hamiltonian cycles is proportional to kmn. However, a quantum computer
needs an additional exponentially large number of operations to accomplish a
probabilistic readout. In contrast, CMOS is deterministic and readout is
comparable to ordinary memory.


title:
Long-term neuronal behavior caused by two synaptic modification
  mechanisms

abstract:
  We report the first results of simulating the coupling of neuronal,
astrocyte, and cerebrovascular activity. It is suggested that the dynamics of
the system is different from systems that only include neurons. In the
neuron-vascular coupling, distribution of synapse strengths affects neuronal
behavior and thus balance of the blood flow; oscillations are induced in the
neuron-to-astrocyte coupling.


title: Unified Theory of Source Coding: Part I -- Two Terminal Problems

abstract:
  Since the publication of Shannon's theory of one terminal source coding, a
number of interesting extensions have been derived by researchers such as
Slepian-Wolf, Wyner, Ahlswede-K\"{o}rner, Wyner-Ziv and Berger-Yeung.
Specifically, the achievable rate or rate-distortion region has been described
by a first order information-theoretic functional of the source statistics in
each of the above cases. At the same time several problems have also remained
unsolved. Notable two terminal examples include the joint distortion problem,
where both sources are reconstructed under a combined distortion criterion, as
well as the partial side information problem, where one source is reconstructed
under a distortion criterion using information about the other (side
information) available at a certain rate (partially). In this paper we solve
both of these open problems. Specifically, we give an infinite order
description of the achievable rate-distortion region in each case. In our
analysis we set the above problems in a general framework and formulate a
unified methodology that solves not only the problems at hand but any two
terminal problem with noncooperative encoding. The key to such unification is
held by a fundamental source coding principle which we derive by extending the
typicality arguments of Shannon and Wyner-Ziv. Finally, we demonstrate the
expansive scope of our technique by re-deriving known coding theorems. We shall
observe that our infinite order descriptions simplify to the expected first
order in the known special cases.


title: Unified Theory of Source Coding: Part II -- Multiterminal Problems

abstract:
  In the first paper of this two part communication, we solved in a unified
framework a variety of two terminal source coding problems with noncooperative
encoders, thereby consolidating works of Shannon, Slepian-Wolf, Wyner,
Ahlswede-K\"{o}rner, Wyner-Ziv, Berger {\em et al.} and Berger-Yeung. To
achieve such unification we made use of a fundamental principle that
dissociates bulk of the analysis from the distortion criterion at hand (if any)
and extends the typicality arguments of Shannon and Wyner-Ziv. In this second
paper, we generalize the fundamental principle for any number of sources and on
its basis exhaustively solve all multiterminal source coding problems with
noncooperative encoders and one decoder. The distortion criteria, when
applicable, are required to apply to single letters and be bounded. Our
analysis includes cases where side information is, respectively, partially
available, completely available and altogether unavailable at the decoder. As
seen in our first paper, the achievable regions permit infinite order
information-theoretic descriptions. We also show that the entropy-constrained
multiterminal estimation problem can be solved as a special case of our theory.


title:
Iterative Algorithm for Finding Frequent Patterns in Transactional
  Databases

abstract:
  A high-performance algorithm for searching for frequent patterns (FPs) in
transactional databases is presented. The search for FPs is carried out by
using an iterative sieve algorithm by computing the set of enclosed cycles. In
each inner cycle of level FPs composed of elements are generated. The assigned
number of enclosed cycles (the parameter of the problem) defines the maximum
length of the desired FPs. The efficiency of the algorithm is produced by (i)
the extremely simple logical searching scheme, (ii) the avoidance of recursive
procedures, and (iii) the usage of only one-dimensional arrays of integers.


title:
How Good is Phase-Shift Keying for Peak-Limited Rayleigh Fading Channels
  in the Low-SNR Regime?

abstract:
  This paper investigates the achievable information rate of phase-shift keying
(PSK) over frequency non-selective Rayleigh fading channels without channel
state information (CSI). The fading process exhibits general temporal
correlation characterized by its spectral density function. We consider both
discrete-time and continuous-time channels, and find their asymptotics at low
signal-to-noise ratio (SNR). Compared to known capacity upper bounds under peak
constraints, these asymptotics usually lead to negligible rate loss in the
low-SNR regime for slowly time-varying fading channels. We further specialize
to case studies of Gauss-Markov and Clarke's fading models.


title:
Streaming and Sublinear Approximation of Entropy and Information
  Distances

abstract:
  In many problems in data mining and machine learning, data items that need to
be clustered or classified are not points in a high-dimensional space, but are
distributions (points on a high dimensional simplex). For distributions,
natural measures of distance are not the $\ell_p$ norms and variants, but
information-theoretic measures like the Kullback-Leibler distance, the
Hellinger distance, and others. Efficient estimation of these distances is a
key component in algorithms for manipulating distributions. Thus, sublinear
resource constraints, either in time (property testing) or space (streaming)
are crucial.
  We start by resolving two open questions regarding property testing of
distributions. Firstly, we show a tight bound for estimating bounded, symmetric
f-divergences between distributions in a general property testing (sublinear
time) framework (the so-called combined oracle model). This yields optimal
algorithms for estimating such well known distances as the Jensen-Shannon
divergence and the Hellinger distance. Secondly, we close a $(\log n)/H$ gap
between upper and lower bounds for estimating entropy $H$ in this model. In a
stream setting (sublinear space), we give the first algorithm for estimating
the entropy of a distribution. Our algorithm runs in polylogarithmic space and
yields an asymptotic constant factor approximation scheme. We also provide
other results along the space/time/approximation tradeoff curve.


title: On Algorithms and Complexity for Sets with Cardinality Constraints

abstract:
  Typestate systems ensure many desirable properties of imperative programs,
including initialization of object fields and correct use of stateful library
interfaces. Abstract sets with cardinality constraints naturally generalize
typestate properties: relationships between the typestates of objects can be
expressed as subset and disjointness relations on sets, and elements of sets
can be represented as sets of cardinality one. Motivated by these applications,
this paper presents new algorithms and new complexity results for constraints
on sets and their cardinalities. We study several classes of constraints and
demonstrate a trade-off between their expressive power and their complexity.
  Our first result concerns a quantifier-free fragment of Boolean Algebra with
Presburger Arithmetic. We give a nondeterministic polynomial-time algorithm for
reducing the satisfiability of sets with symbolic cardinalities to constraints
on constant cardinalities, and give a polynomial-space algorithm for the
resulting problem.
  In a quest for more efficient fragments, we identify several subclasses of
sets with cardinality constraints whose satisfiability is NP-hard. Finally, we
identify a class of constraints that has polynomial-time satisfiability and
entailment problems and can serve as a foundation for efficient program
analysis.


title: Coding Schemes for Line Networks

abstract:
  We consider a simple network, where a source and destination node are
connected with a line of erasure channels. It is well known that in order to
achieve the min-cut capacity, the intermediate nodes are required to process
the information. We propose coding schemes for this setting, and discuss each
scheme in terms of complexity, delay, achievable rate, memory requirement, and
adaptability to unknown channel parameters. We also briefly discuss how these
schemes can be extended to more general networks.


title: A Sorting Algorithm Based on Calculation

abstract:
  This article introduces an adaptive sorting algorithm that can relocate
elements accurately by substituting their values into a function which we name
it the guessing function. We focus on building this function which is the
mapping relationship between record values and their corresponding sorted
locations essentially. The time complexity of this algorithm O(n),when records
distributed uniformly. Additionally, similar approach can be used in the
searching algorithm.


title: A Closed-Form Solution for the Finite Length Constant Modulus Receiver

abstract:
  In this paper, a closed-form solution minimizing the Godard or Constant
Modulus (CM) cost function under the practical conditions of finite SNR and
finite equalizer length is derived. While previous work has been reported by
Zeng et al., IEEE Trans. Information Theory. 1998, to establish the link
between the constant modulus and Wiener receivers, we show that under the
Gaussian approximation of intersymbol interference at the output of the
equalizer, the CM finite-length receiver is equivalent to the nonblind MMSE
equalizer up to a complex gain factor. Some simulation results are provided to
support the Gaussian approximation assumption.


title: On context-tree prediction of individual sequences

abstract:
  Motivated by the evident success of context-tree based methods in lossless
data compression, we explore, in this paper, methods of the same spirit in
universal prediction of individual sequences. By context-tree prediction, we
refer to a family of prediction schemes, where at each time instant $t$, after
having observed all outcomes of the data sequence $x_1,...,x_{t-1}$, but not
yet $x_t$, the prediction is based on a ``context'' (or a state) that consists
of the $k$ most recent past outcomes $x_{t-k},...,x_{t-1}$, where the choice of
$k$ may depend on the contents of a possibly longer, though limited, portion of
the observed past, $x_{t-k_{\max}},...x_{t-1}$. This is different from the
study reported in [1], where general finite-state predictors as well as
``Markov'' (finite-memory) predictors of fixed order, were studied in the
regime of individual sequences.
  Another important difference between this study and [1] is the asymptotic
regime. While in [1], the resources of the predictor (i.e., the number of
states or the memory size) were kept fixed regardless of the length $N$ of the
data sequence, here we investigate situations where the number of contexts or
states is allowed to grow concurrently with $N$. We are primarily interested in
the following fundamental question: What is the critical growth rate of the
number of contexts, below which the performance of the best context-tree
predictor is still universally achievable, but above which it is not? We show
that this critical growth rate is linear in $N$. In particular, we propose a
universal context-tree algorithm that essentially achieves optimum performance
as long as the growth rate is sublinear, and show that, on the other hand, this
is impossible in the linear case.


title: Mapping DEVS Models onto UML Models

abstract:
  Discrete event simulation specification (DEVS) is a formalism designed to
describe both discrete state and continuous state systems. It is a powerful
abstract mathematical notation. However, until recently it lacked proper
graphical representation, which made computer simulation of DEVS models a
challenging issue. Unified modeling language (UML) is a multipurpose graphical
modeling language, a de-facto industrial modeling standard. There exist several
commercial and open-source UML editors and code generators. Most of them can
save UML models in XML-based XMI files ready for further automated processing.
In this paper, we propose a mapping of DEVS models onto UML state and component
diagrams. This mapping may lead to an eventual unification of the two modeling
formalisms, combining the abstractness of DEVS and expressive power and
``computer friendliness'' of the UML.


title: Temporal Phylogenetic Networks and Logic Programming

abstract:
  The concept of a temporal phylogenetic network is a mathematical model of
evolution of a family of natural languages. It takes into account the fact that
languages can trade their characteristics with each other when linguistic
communities are in contact, and also that a contact is only possible when the
languages are spoken at the same time. We show how computational methods of
answer set programming and constraint logic programming can be used to generate
plausible conjectures about contacts between prehistoric linguistic
communities, and illustrate our approach by applying it to the evolutionary
history of Indo-European languages.
  To appear in Theory and Practice of Logic Programming (TPLP).


title: A Fresh Look at the Reliability of Long-term Digital Storage

abstract:
  Many emerging Web services, such as email, photo sharing, and web site
archives, need to preserve large amounts of quickly-accessible data
indefinitely into the future. In this paper, we make the case that these
applications' demands on large scale storage systems over long time horizons
require us to re-evaluate traditional storage system designs. We examine
threats to long-lived data from an end-to-end perspective, taking into account
not just hardware and software faults but also faults due to humans and
organizations. We present a simple model of long-term storage failures that
helps us reason about the various strategies for addressing these threats in a
cost-effective manner. Using this model we show that the most important
strategies for increasing the reliability of long-term storage are detecting
latent faults quickly, automating fault repair to make it faster and cheaper,
and increasing the independence of data replicas.


title: Point Process Models of 1/f Noise and Internet Traffic

abstract:
  We present a simple model reproducing the long-range autocorrelations and the
power spectrum of the web traffic. The model assumes the traffic as Poisson
flow of files with size distributed according to the power-law. In this model
the long-range autocorrelations are independent of the network properties as
well as of inter-packet time distribution.


title: Planning with Preferences using Logic Programming

abstract:
  We present a declarative language, PP, for the high-level specification of
preferences between possible solutions (or trajectories) of a planning problem.
This novel language allows users to elegantly express non-trivial,
multi-dimensional preferences and priorities over such preferences. The
semantics of PP allows the identification of most preferred trajectories for a
given goal. We also provide an answer set programming implementation of
planning problems with PP preferences.


title:
Decompositions of graphs of functions and efficient iterations of lookup
  tables

abstract:
  We show that every function f implemented as a lookup table can be
implemented such that the computational complexity of evaluating f^m(x) is
small, independently of m and x. The implementation only increases the storage
space by a small_constant_ factor.


title: Asymptotic Behavior of Error Exponents in the Wideband Regime

abstract:
  In this paper, we complement Verd\'{u}'s work on spectral efficiency in the
wideband regime by investigating the fundamental tradeoff between rate and
bandwidth when a constraint is imposed on the error exponent. Specifically, we
consider both AWGN and Rayleigh-fading channels. For the AWGN channel model,
the optimal values of $R_z(0)$ and $\dot{R_z}(0)$ are calculated, where
$R_z(1/B)$ is the maximum rate at which information can be transmitted over a
channel with bandwidth $B/2$ when the error-exponent is constrained to be
greater than or equal to $z.$ Based on this calculation, we say that a sequence
of input distributions is near optimal if both $R_z(0)$ and $\dot{R_z}(0)$ are
achieved. We show that QPSK, a widely-used signaling scheme, is near-optimal
within a large class of input distributions for the AWGN channel. Similar
results are also established for a fading channel where full CSI is available
at the receiver.


title: Component Based Programming in Scientific Computing: The Viable Approach

abstract:
  Computational scientists are facing a new era where the old ways of
developing and reusing code have to be left behind and a few daring steps are
to be made towards new horizons. The present work analyzes the needs that drive
this change, the factors that contribute to the inertia of the community and
slow the transition, the status and perspective of present attempts, the
principle, practical and technical problems that are to be addressed in the
short and long run.


title: COMODI: Architecture for a Component-Based Scientific Computing System

abstract:
  The COmputational MODule Integrator (COMODI) is an initiative aiming at a
component based framework, component developer tool and component repository
for scientific computing. We identify the main ingredients to a solution that
would be sufficiently appealing to scientists and engineers to consider
alternatives to their deeply rooted programming traditions. The overall
structure of the complete solution is sketched with special emphasis on the
Component Developer Tool standing at the basis of COMODI.