title:
Using the Modified Allan Variance for Accurate Estimation of the Hurst
  Parameter of Long-Range Dependent Traffic

abstract:
  Internet traffic exhibits self-similarity and long-range dependence (LRD) on
various time scales. A well studied issue is the estimation of statistical
parameters characterizing traffic self-similarity and LRD, such as the Hurst
parameter H. In this paper, we propose to adapt the Modified Allan Variance
(MAVAR), a time-domain quantity originally conceived to discriminate fractional
noise in frequency stability measurement, to estimate the Hurst parameter of
LRD traffic traces and, more generally, to identify fractional noise components
in network traffic. This novel method is validated by comparison to one of the
best techniques for analyzing self-similar and LRD traffic: the logscale
diagram based on wavelet analysis. Both methods are applied to pseudo-random
LRD data series, generated with assigned values of H. The superior spectral
sensitivity of MAVAR achieves outstanding accuracy in estimating H, even better
than the logscale method. The behaviour of MAVAR with most common deterministic
signals that yield nonstationarity in data under analysis is also studied.
Finally, both techniques are applied to a real IP traffic trace, providing a
sound example of the usefulness of MAVAR also in traffic characterization, to
complement other established techniques as the logscale method.


title:
Network Inference from TraceRoute Measurements: Internet Topology
  `Species'

abstract:
  Internet mapping projects generally consist in sampling the network from a
limited set of sources by using traceroute probes. This methodology, akin to
the merging of spanning trees from the different sources to a set of
destinations, leads necessarily to a partial, incomplete map of the Internet.
Accordingly, determination of Internet topology characteristics from such
sampled maps is in part a problem of statistical inference. Our contribution
begins with the observation that the inference of many of the most basic
topological quantities -- including network size and degree characteristics --
from traceroute measurements is in fact a version of the so-called `species
problem' in statistics. This observation has important implications, since
species problems are often quite challenging. We focus here on the most
fundamental example of a traceroute internet species: the number of nodes in a
network. Specifically, we characterize the difficulty of estimating this
quantity through a set of analytical arguments, we use statistical subsampling
principles to derive two proposed estimators, and we illustrate the performance
of these estimators on networks with various topological characteristics.

categories: cs.NI cond-mat.stat-mech math.ST physics.soc-ph stat.TH


title:
Accurate and robust image superresolution by neural processing of local
  image representations

abstract:
  Image superresolution involves the processing of an image sequence to
generate a still image with higher resolution. Classical approaches, such as
bayesian MAP methods, require iterative minimization procedures, with high
computational costs. Recently, the authors proposed a method to tackle this
problem, based on the use of a hybrid MLP-PNN architecture. In this paper, we
present a novel superresolution method, based on an evolution of this concept,
to incorporate the use of local image models. A neural processing stage
receives as input the value of model coefficients on local windows. The data
dimensionality is firstly reduced by application of PCA. An MLP, trained on
synthetic sequences with various amounts of noise, estimates the
high-resolution image data. The effect of varying the dimension of the network
input space is examined, showing a complex, structured behavior. Quantitative
results are presented showing the accuracy and robustness of the proposed
method.


title: Tree-Based Construction of LDPC Codes Having Good Pseudocodeword Weights

abstract:
  We present a tree-based construction of LDPC codes that have minimum
pseudocodeword weight equal to or almost equal to the minimum distance, and
perform well with iterative decoding. The construction involves enumerating a
$d$-regular tree for a fixed number of layers and employing a connection
algorithm based on permutations or mutually orthogonal Latin squares to close
the tree. Methods are presented for degrees $d=p^s$ and $d = p^s+1$, for $p$ a
prime. One class corresponds to the well-known finite-geometry and finite
generalized quadrangle LDPC codes; the other codes presented are new. We also
present some bounds on pseudocodeword weight for $p$-ary LDPC codes. Treating
these codes as $p$-ary LDPC codes rather than binary LDPC codes improves their
rates, minimum distances, and pseudocodeword weights, thereby giving a new
importance to the finite geometry LDPC codes where $p > 2$.


title: On the Expressiveness of the Ambient Logic

abstract:
  The Ambient Logic (AL) has been proposed for expressing properties of process
mobility in the calculus of Mobile Ambients (MA), and as a basis for query
languages on semistructured data. In this paper, we study the expressiveness of
AL. We define formulas for capabilities and for communication in MA. We also
derive some formulas that capture finitess of a term, name occurrences and
persistence. We study extensions of the calculus involving more complex forms
of communications, and we define characteristic formulas for the equivalence
induced by the logic on a subcalculus of MA. This subcalculus is defined by
imposing an image-finiteness condition on the reducts of a MA process.


title:
Diophantus' 20th Problem and Fermat's Last Theorem for n=4:
  Formalization of Fermat's Proofs in the Coq Proof Assistant

abstract:
  We present the proof of Diophantus' 20th problem (book VI of Diophantus'
Arithmetica), which consists in wondering if there exist right triangles whose
sides may be measured as integers and whose surface may be a square. This
problem was negatively solved by Fermat in the 17th century, who used the
"wonderful" method (ipse dixit Fermat) of infinite descent. This method, which
is, historically, the first use of induction, consists in producing smaller and
smaller non-negative integer solutions assuming that one exists; this naturally
leads to a reductio ad absurdum reasoning because we are bounded by zero. We
describe the formalization of this proof which has been carried out in the Coq
proof assistant. Moreover, as a direct and no less historical application, we
also provide the proof (by Fermat) of Fermat's last theorem for n=4, as well as
the corresponding formalization made in Coq.


title: On relating CTL to Datalog

abstract:
  CTL is the dominant temporal specification language in practice mainly due to
the fact that it admits model checking in linear time. Logic programming and
the database query language Datalog are often used as an implementation
platform for logic languages. In this paper we present the exact relation
between CTL and Datalog and moreover we build on this relation and known
efficient algorithms for CTL to obtain efficient algorithms for fragments of
stratified Datalog. The contributions of this paper are: a) We embed CTL into
STD which is a proper fragment of stratified Datalog. Moreover we show that STD
expresses exactly CTL -- we prove that by embedding STD into CTL. Both
embeddings are linear. b) CTL can also be embedded to fragments of Datalog
without negation. We define a fragment of Datalog with the successor build-in
predicate that we call TDS and we embed CTL into TDS in linear time. We build
on the above relations to answer open problems of stratified Datalog. We prove
that query evaluation is linear and that containment and satisfiability
problems are both decidable. The results presented in this paper are the first
for fragments of stratified Datalog that are more general than those containing
only unary EDBs.


title: Safe Data Sharing and Data Dissemination on Smart Devices

abstract:
  The erosion of trust put in traditional database servers, the growing
interest for different forms of data dissemination and the concern for
protecting children from suspicious Internet content are different factors that
lead to move the access control from servers to clients. Several encryption
schemes can be used to serve this purpose but all suffer from a static way of
sharing data. In a precedent paper, we devised smarter client-based access
control managers exploiting hardware security elements on client devices. The
goal pursued is being able to evaluate dynamic and personalized access control
rules on a ciphered XML input document, with the benefit of dissociating access
rights from encryption. In this demonstration, we validate our solution using a
real smart card platform and explain how we deal with the constraints usually
met on hardware security elements (small memory and low throughput). Finally,
we illustrate the generality of the approach and the easiness of its deployment
through two different applications: a collaborative application and a parental
control application on video streams.


title: Computing the Kalman form

abstract:
  We present two algorithms for the computation of the Kalman form of a linear
control system. The first one is based on the technique developed by
Keller-Gehrig for the computation of the characteristic polynomial. The cost is
a logarithmic number of matrix multiplications. To our knowledge, this improves
the best previously known algebraic complexity by an order of magnitude. Then
we also present a cubic algorithm proven to more efficient in practice.


title: Word sense disambiguation criteria: a systematic study

abstract:
  This article describes the results of a systematic in-depth study of the
criteria used for word sense disambiguation. Our study is based on 60 target
words: 20 nouns, 20 adjectives and 20 verbs. Our results are not always in line
with some practices in the field. For example, we show that omitting
non-content words decreases performance and that bigrams yield better results
than unigrams.


title: From finite-system entropy to entropy rate for a Hidden Markov Process

abstract:
  A recent result presented the expansion for the entropy rate of a Hidden
Markov Process (HMP) as a power series in the noise variable $\eps$. The
coefficients of the expansion around the noiseless ($\eps = 0$) limit were
calculated up to 11th order, using a conjecture that relates the entropy rate
of a HMP to the entropy of a process of finite length (which is calculated
analytically). In this communication we generalize and prove the validity of
the conjecture, and discuss the theoretical and practical consequences of our
new theorem.


title: Partial fillup and search time in LC tries

abstract:
  Andersson and Nilsson introduced in 1993 a level-compressed trie (in short:
LC trie) in which a full subtree of a node is compressed to a single node of
degree being the size of the subtree. Recent experimental results indicated a
'dramatic improvement' when full subtrees are replaced by partially filled
subtrees. In this paper, we provide a theoretical justification of these
experimental results showing, among others, a rather moderate improvement of
the search time over the original LC tries. For such an analysis, we assume
that n strings are generated independently by a binary memoryless source with p
denoting the probability of emitting a 1. We first prove that the so called
alpha-fillup level (i.e., the largest level in a trie with alpha fraction of
nodes present at this level) is concentrated on two values with high
probability. We give these values explicitly up to O(1), and observe that the
value of alpha (strictly between 0 and 1) does not affect the leading term.
  This result directly yields the typical depth (search time) in the alpha-LC
tries with p not equal to 1/2, which turns out to be C loglog n for an
explicitly given constant C (depending on p but not on alpha). This should be
compared with recently found typical depth in the original LC tries which is C'
loglog n for a larger constant C'. The search time in alpha-LC tries is thus
smaller but of the same order as in the original LC tries.


title:
Candidate One-Way Functions and One-Way Permutations Based on Quasigroup
  String Transformations

abstract:
  In this paper we propose a definition and construction of a new family of
one-way candidate functions ${\cal R}_N:Q^N \to Q^N$, where $Q=\{0,1,...,s-1\}$
is an alphabet with $s$ elements. Special instances of these functions can have
the additional property to be permutations (i.e. one-way permutations). These
one-way functions have the property that for achieving the security level of
$2^n$ computations in order to invert them, only $n$ bits of input are needed.
The construction is based on quasigroup string transformations. Since
quasigroups in general do not have algebraic properties such as associativity,
commutativity, neutral elements, inverting these functions seems to require
exponentially many readings from the lookup table that defines them (a Latin
Square) in order to check the satisfiability for the initial conditions, thus
making them natural candidates for one-way functions.


title: Entropy based Nearest Neighbor Search in High Dimensions

abstract:
  In this paper we study the problem of finding the approximate nearest
neighbor of a query point in the high dimensional space, focusing on the
Euclidean space. The earlier approaches use locality-preserving hash functions
(that tend to map nearby points to the same value) to construct several hash
tables to ensure that the query point hashes to the same bucket as its nearest
neighbor in at least one table. Our approach is different -- we use one (or a
few) hash table and hash several randomly chosen points in the neighborhood of
the query point showing that at least one of them will hash to the bucket
containing its nearest neighbor. We show that the number of randomly chosen
points in the neighborhood of the query point $q$ required depends on the
entropy of the hash value $h(p)$ of a random point $p$ at the same distance
from $q$ at its nearest neighbor, given $q$ and the locality preserving hash
function $h$ chosen randomly from the hash family. Precisely, we show that if
the entropy $I(h(p)|q,h) = M$ and $g$ is a bound on the probability that two
far-off points will hash to the same bucket, then we can find the approximate
nearest neighbor in $O(n^\rho)$ time and near linear $\tilde O(n)$ space where
$\rho = M/\log(1/g)$. Alternatively we can build a data structure of size
$\tilde O(n^{1/(1-\rho)})$ to answer queries in $\tilde O(d)$ time. By applying
this analysis to the locality preserving hash functions in and adjusting the
parameters we show that the $c$ nearest neighbor can be computed in time
$\tilde O(n^\rho)$ and near linear space where $\rho \approx 2.06/c$ as $c$
becomes large.


title: Sur le statut r\'{e}f\'{e}rentiel des entit\'{e}s nomm\'{e}es

abstract:
  We show in this paper that, on the one hand, named entities can be designated
using different denominations and that, on the second hand, names denoting
named entities are polysemous. The analysis cannot be limited to reference
resolution but should take into account naming strategies, which are mainly
based on two linguistic operations: synecdoche and metonymy. Lastly, we present
a model that explicitly represents the different denominations in discourse,
unifying the way to represent linguistic knowledge and world knowledge.


title:
A Unified Power Control Algorithm for Multiuser Detectors in Large
  Systems: Convergence and Performance

abstract:
  A unified approach to energy-efficient power control, applicable to a large
family of receivers including the matched filter, the decorrelator, the
(linear) minimum-mean-square-error detector (MMSE), and the individually and
jointly optimal multiuser detectors, has recently been proposed for
code-division-multiple-access (CDMA) networks. This unified power control (UPC)
algorithm exploits the linear relationship that has been shown to exist between
the transmit power and the output signal-to-interference-plus-noise ratio (SIR)
in large systems. Based on this principle and by computing the multiuser
efficiency, the UPC algorithm updates the users' transmit powers in an
iterative way to achieve the desired target SIR. In this paper, the convergence
of the UPC algorithm is proved for the matched filter, the decorrelator, and
the MMSE detector. In addition, the performance of the algorithm in finite-size
systems is studied and compared with that of existing power control schemes.
The UPC algorithm is particularly suitable for systems with randomly generated
long spreading sequences (i.e., sequences whose period is longer than one
symbol duration).


title: Cryptographic Authentication of Navigation Protocols

abstract:
  We examine the security of existing radio navigation protocols and attempt to
define secure, scalable replacements.


title: On the capacity of mobile ad hoc networks with delay constraints

abstract:
  Previous work on ad hoc network capacity has focused primarily on
source-destination throughput requirements for different models and
transmission scenarios, with an emphasis on delay tolerant applications. In
such problems, network capacity enhancement is achieved as a tradeoff with
transmission delay. In this paper, the capacity of ad hoc networks supporting
delay sensitive traffic is studied. First, a general framework is proposed for
characterizing the interactions between the physical and the network layer in
an ad hoc network. Then, CDMA ad hoc networks, in which advanced signal
processing techniques such as multiuser detection are relied upon to enhance
the user capacity, are analyzed. The network capacity is characterized using a
combination of geometric arguments and large scale analysis, for several
network scenarios employing matched filters, decorrelators and
minimum-mean-square-error receivers. Insight into the network performance for
finite systems is also provided by means of simulations. Both analysis and
simulations show a significant network capacity gain for ad hoc networks
employing multiuser detectors, compared with those using matched filter
receivers, as well as very good performance even under tight delay and
transmission power requirements.


title: Delta-confluent Drawings

abstract:
  We generalize the tree-confluent graphs to a broader class of graphs called
Delta-confluent graphs. This class of graphs and distance-hereditary graphs, a
well-known class of graphs, coincide. Some results about the visualization of
Delta-confluent graphs are also given.


title: Practical Semantic Analysis of Web Sites and Documents

abstract:
  As Web sites are now ordinary products, it is necessary to explicit the
notion of quality of a Web site. The quality of a site may be linked to the
easiness of accessibility and also to other criteria such as the fact that the
site is up to date and coherent. This last quality is difficult to insure
because sites may be updated very frequently, may have many authors, may be
partially generated and in this context proof-reading is very difficult. The
same piece of information may be found in different occurrences, but also in
data or meta-data, leading to the need for consistency checking. In this paper
we make a parallel between programs and Web sites. We present some examples of
semantic constraints that one would like to specify (constraints between the
meaning of categories and sub-categories in a thematic directory, consistency
between the organization chart and the rest of the site in an academic site).
We present quickly the Natural Semantics, a way to specify the semantics of
programming languages that inspires our works. Then we propose a specification
language for semantic constraints in Web sites that, in conjunction with the
well known ``make'' program, permits to generate some site verification tools
by compiling the specification into Prolog code. We apply our method to a large
XML document which is the scientific part of our institute activity report,
tracking errors or inconsistencies and also constructing some indicators that
can be used by the management of the institute.


title:
A decision support system for ship identification based on the curvature
  scale space representation

abstract:
  In this paper, a decision support system for ship identification is
presented. The system receives as input a silhouette of the vessel to be
identified, previously extracted from a side view of the object. This view
could have been acquired with imaging sensors operating at different spectral
ranges (CCD, FLIR, image intensifier). The input silhouette is preprocessed and
compared to those stored in a database, retrieving a small number of potential
matches ranked by their similarity to the target silhouette. This set of
potential matches is presented to the system operator, who makes the final ship
identification. This system makes use of an evolved version of the Curvature
Scale Space (CSS) representation. In the proposed approach, it is curvature
extrema, instead of zero crossings, that are tracked during silhouette
evolution, hence improving robustness and enabling to cope successfully with
cases where the standard CCS representation is found to be unstable. Also, the
use of local curvature was replaced with the more robust concept of lobe
concavity, with significant additional gains in performance. Experimental
results on actual operational imagery prove the excellent performance and
robustness of the developed method.


title: A Market Test for the Positivity of Arrow-Debreu Prices

abstract:
  We derive tractable necessary and sufficient conditions for the absence of
buy-and-hold arbitrage opportunities in a perfectly liquid, one period market.
We formulate the positivity of Arrow-Debreu prices as a generalized moment
problem to show that this no arbitrage condition is equivalent to the positive
semidefiniteness of matrices formed by the market price of tradeable securities
and their products. We apply this result to a market with multiple assets and
basket call options.


title:
Geo-aggregation permits low stretch and routing tables of logarithmical
  size

abstract:
  This article first addresses applicability of Euclidean models to the domain
of Internet routing. Those models are found (limitedly) applicable. Then a
simplistic model of routing is constructed for Euclidean plane densely covered
with points-routers. The model guarantees low stretch and logarithmical size of
routing tables at any node. The paper concludes with a discussion on
applicability of the model to real-world Internet routing.


title: Conditionally independent random variables

abstract:
  In this paper we investigate the notion of conditional independence and prove
several information inequalities for conditionally independent random
variables.


title:
A Near Maximum Likelihood Decoding Algorithm for MIMO Systems Based on
  Semi-Definite Programming

abstract:
  In Multi-Input Multi-Output (MIMO) systems, Maximum-Likelihood (ML) decoding
is equivalent to finding the closest lattice point in an N-dimensional complex
space. In general, this problem is known to be NP hard. In this paper, we
propose a quasi-maximum likelihood algorithm based on Semi-Definite Programming
(SDP). We introduce several SDP relaxation models for MIMO systems, with
increasing complexity. We use interior-point methods for solving the models and
obtain a near-ML performance with polynomial computational complexity. Lattice
basis reduction is applied to further reduce the computational complexity of
solving these models. The proposed relaxation models are also used for soft
output decoding in MIMO systems.


title: Computing Pure Nash Equilibria via Markov Random Fields

abstract:
  In this paper we present a novel generic mapping between Graphical Games and
Markov Random Fields so that pure Nash equilibria in the former can be found by
statistical inference on the latter. Thus, the problem of deciding whether a
graphical game has a pure Nash equilibrium, a well-known intractable problem,
can be attacked by well-established algorithms such as Belief Propagation,
Junction Trees, Markov Chain Monte Carlo and Simulated Annealing. Large classes
of graphical games become thus tractable, including all classes already known,
but also new classes such as the games with O(log n) treewidth.


title: Polar Polytopes and Recovery of Sparse Representations

abstract:
  Suppose we have a signal y which we wish to represent using a linear
combination of a number of basis atoms a_i, y=sum_i x_i a_i = Ax. The problem
of finding the minimum L0 norm representation for y is a hard problem. The
Basis Pursuit (BP) approach proposes to find the minimum L1 norm representation
instead, which corresponds to a linear program (LP) that can be solved using
modern LP techniques, and several recent authors have given conditions for the
BP (minimum L1 norm) and sparse (minimum L0 solutions) representations to be
identical. In this paper, we explore this sparse representation problem} using
the geometry of convex polytopes, as recently introduced into the field by
Donoho. By considering the dual LP we find that the so-called polar polytope P
of the centrally-symmetric polytope P whose vertices are the atom pairs +-a_i
is particularly helpful in providing us with geometrical insight into
optimality conditions given by Fuchs and Tropp for non-unit-norm atom sets. In
exploring this geometry we are able to tighten some of these earlier results,
showing for example that the Fuchs condition is both necessary and sufficient
for L1-unique-optimality, and that there are situations where Orthogonal
Matching Pursuit (OMP) can eventually find all L1-unique-optimal solutions with
m nonzeros even if ERC fails for m, if allowed to run for more than m steps.


title: Coding for the Optical Channel: the Ghost-Pulse Constraint

abstract:
  We consider a number of constrained coding techniques that can be used to
mitigate a nonlinear effect in the optical fiber channel that causes the
formation of spurious pulses, called ``ghost pulses.'' Specifically, if $b_1
b_2 ... b_{n}$ is a sequence of bits sent across an optical channel, such that
$b_k=b_l=b_m=1$ for some $k,l,m$ (not necessarily all distinct) but $b_{k+l-m}
= 0$, then the ghost-pulse effect causes $b_{k+l-m}$ to change to 1, thereby
creating an error. We design and analyze several coding schemes using binary
and ternary sequences constrained so as to avoid patterns that give rise to
ghost pulses. We also discuss the design of encoders and decoders for these
coding schemes.


title: COMODI: On the Graphical User Interface

abstract:
  We propose a series of features for the graphical user interface (GUI) of the
COmputational MOdule Integrator (COMODI) \cite{Synasc05a}\cite{COMODI}. In view
of the special requirements that a COMODI type of framework for scientific
computing imposes and inspiring from existing solutions that provide advanced
graphical visual programming environments, we identify those elements and
associated behaviors that will have to find their way into the first release of
COMODI.


title:
Design and Performance Analysis of a New Class of Rate Compatible Serial
  Concatenated Convolutional Codes

abstract:
  In this paper, we provide a performance analysis of a new class of serial
concatenated convolutional codes (SCCC) where the inner encoder can be
punctured beyond the unitary rate. The puncturing of the inner encoder is not
limited to inner coded bits, but extended to systematic bits. Moreover, it is
split into two different puncturings, in correspondence with inner code
systematic bits and parity bits. We derive the analytical upper bounds to the
error probability of this particular code structure and address suitable design
guidelines for the inner code puncturing patterns. We show that the percentile
of systematic and parity bits to be deleted strongly depends on the SNR region
of interest. In particular, to lower the error floor it is advantageous to put
more puncturing on inner systematic bits. Furthermore, we show that puncturing
of inner systematic bits should be interleaver dependent. Based on these
considerations, we derive design guidelines to obtain well-performing
rate-compatible SCCC families. Throughout the paper, the performance of the
proposed codes are compared with analytical bounds, and with the performance of
PCCC and SCCC proposed in the literature.


title: Semantic Optimization Techniques for Preference Queries

abstract:
  Preference queries are relational algebra or SQL queries that contain
occurrences of the winnow operator ("find the most preferred tuples in a given
relation"). Such queries are parameterized by specific preference relations.
Semantic optimization techniques make use of integrity constraints holding in
the database. In the context of semantic optimization of preference queries, we
identify two fundamental properties: containment of preference relations
relative to integrity constraints and satisfaction of order axioms relative to
integrity constraints. We show numerous applications of those notions to
preference query evaluation and optimization. As integrity constraints, we
consider constraint-generating dependencies, a class generalizing functional
dependencies. We demonstrate that the problems of containment and satisfaction
of order axioms can be captured as specific instances of constraint-generating
dependency entailment. This makes it possible to formulate necessary and
sufficient conditions for the applicability of our techniques as constraint
validity problems. We characterize the computational complexity of such
problems.


title: Hi\'{e}rarchisation des r\`{e}gles d'association en fouille de textes

abstract:
  Extraction of association rules is widely used as a data mining method.
However, one of the limit of this approach comes from the large number of
extracted rules and the difficulty for a human expert to deal with the totality
of these rules. We propose to solve this problem by structuring the set of
rules into hierarchy. The expert can then therefore explore the rules, access
from one rule to another one more general when we raise up in the hierarchy,
and in other hand, or a more specific rules. Rules are structured at two
levels. The global level aims at building a hierarchy from the set of rules
extracted. Thus we define a first type of rule-subsomption relying on Galois
lattices. The second level consists in a local and more detailed analysis of
each rule. It generate for a given rule a set of generalization rules
structured into a local hierarchy. This leads to the definition of a second
type of subsomption. This subsomption comes from inductive logic programming
and integrates a terminological model.


title: Learning Unions of $\omega(1)$-Dimensional Rectangles

abstract:
  We consider the problem of learning unions of rectangles over the domain
$[b]^n$, in the uniform distribution membership query learning setting, where
both b and n are "large". We obtain poly$(n, \log b)$-time algorithms for the
following classes:
  - poly$(n \log b)$-way Majority of $O(\frac{\log(n \log b)} {\log \log(n \log
b)})$-dimensional rectangles.
  - Union of poly$(\log(n \log b))$ many $O(\frac{\log^2 (n \log b)} {(\log
\log(n \log b) \log \log \log (n \log b))^2})$-dimensional rectangles.
  - poly$(n \log b)$-way Majority of poly$(n \log b)$-Or of disjoint
$O(\frac{\log(n \log b)} {\log \log(n \log b)})$-dimensional rectangles.
  Our main algorithmic tool is an extension of Jackson's boosting- and
Fourier-based Harmonic Sieve algorithm [Jackson 1997] to the domain $[b]^n$,
building on work of [Akavia, Goldwasser, Safra 2003]. Other ingredients used to
obtain the results stated above are techniques from exact learning [Beimel,
Kushilevitz 1998] and ideas from recent work on learning augmented $AC^{0}$
circuits [Jackson, Klivans, Servedio 2002] and on representing Boolean
functions as thresholds of parities [Klivans, Servedio 2001].


title:
DyNoC: A Dynamic Infrastructure for Communication in Dynamically
  Reconfigurable Devices

abstract:
  A new paradigm to support the communication among modules dynamically placed
on a reconfigurable device at run-time is presented. Based on the network on
chip (NoC) infrastructure, we developed a dynamic communication infrastructure
as well as routing methodologies capable to handle routing in a NoC with
obstacles created by dynamically placed components. We prove the unrestricted
reachability of components and pins, the deadlock-freeness and we finally show
the feasibility of our approach by means on real life example applications.


title: The "...system of constraints"

abstract:
  This paper proposes that the mathematical relationship between an entropy
distribution and its limit offers some new insight into system performance.
This relationship is used to quantify variation among the entities of a system,
where variation is defined as tolerance, option, specification or
implementation variation among the entities of a system. Variation has a
significnt and increasing impact on communications system performance. This
paper introduces means to identify, quantify and reduce such performance
variations.


title: Feynman graphs and related Hopf algebras

abstract:
  In a recent series of communications we have shown that the reordering
problem of bosons leads to certain combinatorial structures. These structures
may be associated with a certain graphical description. In this paper, we show
that there is a Hopf Algebra structure associated with this problem which is,
in a certain sense, unique.

categories: cs.SC cs.DM math-ph math.CO math.MP quant-ph


title: Secure and {\sl Practical} Identity-Based Encryption

abstract:
  In this paper, we present a variant of Waters' Identity-Based Encryption
scheme with a much smaller public-key size (only a few kilobytes). We show that
this variant is semantically secure against passive adversaries in the standard
model.\smallskip
  In essence, the new scheme divides Waters' public key size by a factor $\ell$
at the cost of (negligibly) reducing security by $\ell$ bits. Therefore, our
construction settles an open question asked by Waters and constitutes the first
fully secure {\sl practical} Identity-Based Encryption scheme


title: On Minimal Pseudo-Codewords of Tanner Graphs from Projective Planes

abstract:
  We would like to better understand the fundamental cone of Tanner graphs
derived from finite projective planes. Towards this goal, we discuss bounds on
the AWGNC and BSC pseudo-weight of minimal pseudo-codewords of such Tanner
graphs, on one hand, and study the structure of minimal pseudo-codewords, on
the other.


title: Belief Propagation Based Multi--User Detection

abstract:
  We apply belief propagation (BP) to multi--user detection in a spread
spectrum system, under the assumption of Gaussian symbols. We prove that BP is
both convergent and allows to estimate the correct conditional expectation of
the input symbols. It is therefore an optimal --minimum mean square error--
detection algorithm. This suggests the possibility of designing BP detection
algorithms for more general systems. As a byproduct we rederive the Tse-Hanly
formula for minimum mean square error without any recourse to random matrix
theory.


title: Why We Can Not Surpass Capacity: The Matching Condition

abstract:
  We show that iterative coding systems can not surpass capacity using only
quantities which naturally appear in density evolution. Although the result in
itself is trivial, the method which we apply shows that in order to achieve
capacity the various components in an iterative coding system have to be
perfectly matched. This generalizes the perfect matching condition which was
previously known for the case of transmission over the binary erasure channel
to the general class of binary-input memoryless output-symmetric channels.
Potential applications of this perfect matching condition are the construction
of capacity-achieving degree distributions and the determination of the number
required iterations as a function of the multiplicative gap to capacity.


title:
Defining a Comprehensive Threat Model for High Performance Computational
  Clusters

abstract:
  Over the past decade, high performance computational (HPC) clusters have
become mainstream in academic and industrial settings as accessible means of
computation. Throughout their proliferation, HPC security has been a secondary
concern to performance. It is evident, however, that ensuring HPC security
presents different challenges than the ones faced when dealing with traditional
networks. To design suitable security measures for high performance computing,
it is necessary to first realize the threats faced by such an environment. This
task can be accomplished by the means of constructing a comprehensive threat
model. To our knowledge, no such threat model exists with regards to Cluster
Computing. In this paper, we explore the unique challenges of securing HPCs and
propose a threat model based on the classical Confidentiality, Integrity and
Availability security principles.


title:
Geometrical relations between space time block code designs and
  complexity reduction

abstract:
  In this work, the geometric relation between space time block code design for
the coherent channel and its non-coherent counterpart is exploited to get an
analogue of the information theoretic inequality $I(X;S)\le I((X,H);S)$ in
terms of diversity. It provides a lower bound on the performance of
non-coherent codes when used in coherent scenarios. This leads in turn to a
code design decomposition result splitting coherent code design into two
complexity reduced sub tasks. Moreover a geometrical criterion for high
performance space time code design is derived.


title:
Deterministic boundary recognition and topology extraction for large
  sensor networks

abstract:
  We present a new framework for the crucial challenge of self-organization of
a large sensor network. The basic scenario can be described as follows: Given a
large swarm of immobile sensor nodes that have been scattered in a polygonal
region, such as a street network. Nodes have no knowledge of size or shape of
the environment or the position of other nodes. Moreover, they have no way of
measuring coordinates, geometric distances to other nodes, or their direction.
Their only way of interacting with other nodes is to send or to receive
messages from any node that is within communication range. The objective is to
develop algorithms and protocols that allow self-organization of the swarm into
large-scale structures that reflect the structure of the street network,
setting the stage for global routing, tracking and guiding algorithms.


title:
Bounds on the Pseudo-Weight of Minimal Pseudo-Codewords of Projective
  Geometry Codes

abstract:
  In this paper we focus our attention on a family of finite geometry codes,
called type-I projective geometry low-density parity-check (PG-LDPC) codes,
that are constructed based on the projective planes PG{2,q). In particular, we
study their minimal codewords and pseudo-codewords, as it is known that these
vectors characterize completely the code performance under maximum-likelihood
decoding and linear programming decoding, respectively. The main results of
this paper consist of upper and lower bounds on the pseudo-weight of the
minimal pseudo-codewords of type-I PG-LDPC codes.


title:
Integration of the DOLCE top-level ontology into the OntoSpec
  methodology

abstract:
  This report describes a new version of the OntoSpec methodology for ontology
building. Defined by the LaRIA Knowledge Engineering Team (University of
Picardie Jules Verne, Amiens, France), OntoSpec aims at helping builders to
model ontological knowledge (upstream of formal representation). The
methodology relies on a set of rigorously-defined modelling primitives and
principles. Its application leads to the elaboration of a semi-informal
ontology, which is independent of knowledge representation languages. We
recently enriched the OntoSpec methodology by endowing it with a new resource,
the DOLCE top-level ontology defined at the LOA (IST-CNR, Trento, Italy). The
goal of this integration is to provide modellers with additional help in
structuring application ontologies, while maintaining independence
vis-\`{a}-vis formal representation languages. In this report, we first provide
an overview of the OntoSpec methodology's general principles and then describe
the DOLCE re-engineering process. A complete version of DOLCE-OS (i.e. a
specification of DOLCE in the semi-informal OntoSpec language) is presented in
an appendix.


title: Numerical resolution of some BVP using Bernstein polynomials

abstract:
  In this work we present a method, based on the use of Bernstein polynomials,
for the numerical resolution of some boundary values problems. The computations
have not need of particular approximations of derivatives, such as finite
differences, or particular techniques, such as finite elements. Also, the
method doesn't require the use of matrices, as in resolution of linear
algebraic systems, nor the use of like-Newton algorithms, as in resolution of
non linear sets of equations. An initial equation is resolved only once, then
the method is based on iterated evaluations of appropriate polynomials.


title: Remarks on "Toward Compact Interdomain Routing"

abstract:
  This paper critically examines some propositions and arguments of
cs.NI/0508021 regarding applicability of hierarchical routing and perspectives
of compact routing. Arguments against the former are found to be inaccurate
while the latter is found to be equivalent to well-known deployed solutions.
Also, multiple (stacked) application of compact-routing solutions is found to
be equivalent to hierarchical routing.


title: A pair of trees without a simultaneous geometric embedding in the plane

abstract:
  Any planar graph has a crossing-free straight-line drawing in the plane. A
simultaneous geometric embedding of two n-vertex graphs is a straight-line
drawing of both graphs on a common set of n points, such that the edges withing
each individual graph do not cross. We consider simultaneous embeddings of two
labeled trees, with predescribed vertex correspondences, and present an
instance of such a pair that cannot be embedded. Further we provide an example
of a planar graph that cannot be embedded together with a path when vertex
correspondences are given.


title: The Nature of Novelty Detection

abstract:
  Sentence level novelty detection aims at reducing redundant sentences from a
sentence list. In the task, sentences appearing later in the list with no new
meanings are eliminated. Aiming at a better accuracy for detecting redundancy,
this paper reveals the nature of the novelty detection task currently
overlooked by the Novelty community $-$ Novelty as a combination of the partial
overlap (PO, two sentences sharing common facts) and complete overlap (CO, the
first sentence covers all the facts of the second sentence) relations. By
formalizing novelty detection as a combination of the two relations between
sentences, new viewpoints toward techniques dealing with Novelty are proposed.
Among the methods discussed, the similarity, overlap, pool and language
modeling approaches are commonly used. Furthermore, a novel approach, selected
pool method is provided, which is immediate following the nature of the task.
Experimental results obtained on all the three currently available novelty
datasets showed that selected pool is significantly better or no worse than the
current methods. Knowledge about the nature of the task also affects the
evaluation methodologies. We propose new evaluation measures for Novelty
according to the nature of the task, as well as possible directions for future
study.


title: Degrees of Freedom in Multiuser MIMO

abstract:
  We explore the available degrees of freedom for various multiuser MIMO
communication scenarios such as the multiple access, broadcast, interference,
relay, X and Z channels. For the two user MIMO interference channel, we find a
general inner bound and a genie-aided outer bound that give us the exact number
of degrees of freedom in many cases. We also study a share-and-transmit scheme
for transmitter cooperation. For the share-and-transmit scheme, we show how the
gains of transmitter cooperation are entirely offset by the cost of enabling
that cooperation so that the available degrees of freedom are not increased.


title: First-Order Modeling and Stability Analysis of Illusory Contours

abstract:
  In visual cognition, illusions help elucidate certain intriguing latent
perceptual functions of the human vision system, and their proper mathematical
modeling and computational simulation are therefore deeply beneficial to both
biological and computer vision. Inspired by existent prior works, the current
paper proposes a first-order energy-based model for analyzing and simulating
illusory contours. The lower complexity of the proposed model facilitates
rigorous mathematical analysis on the detailed geometric structures of illusory
contours. After being asymptotically approximated by classical active contours,
the proposed model is then robustly computed using the celebrated level-set
method of Osher and Sethian (J. Comput. Phys., 79:12-49, 1988) with a natural
supervising scheme. Potential cognitive implications of the mathematical
results are addressed, and generic computational examples are demonstrated and
discussed.


title: Towards a diagrammatic modeling of the LinBox C++ linear algebra library

abstract:
  We propose a new diagrammatic modeling language, DML. The paradigm used is
that of the category theory and in particular of the pushout tool. We show that
most of the object-oriented structures can be described with this tool and have
many examples in C++, ranging from virtual inheritance and polymorphism to
template genericity. With this powerful tool, we propose a quite simple
description of the C++ LinBox library. This library has been designed for
efficiency and genericity and therefore makes heavy usage of complex template
and polymorphic mecanism. Be reverse engineering, we are able to describe in a
simple manner the complex structure of archetypes in LinBox.


title: Precoding for 2x2 Doubly-Dispersive WSSUS Channels

abstract:
  Optimal link adaption to the scattering function of wide sense stationary
uncorrelated scattering (WSSUS) mobile communication channels is still an
unsolved problem despite its importance for next-generation system design. In
multicarrier transmission such link adaption is performed by pulse shaping
which in turn is equivalent to precoding with respect to the second order
channel statistics. In the present framework a translation of the precoder
optimization problem into an optimization problem over trace class operators is
used. This problem which is also well-known in the context of quantum
information theory is unsolved in general due to its non-convex nature. However
in very low dimension the problem formulation reveals an additional analytic
structure which again admits the solution to the optimal precoder and
multiplexing scheme. Hence, in this contribution the analytic solution of the
problem for the 2x2 doubly--dispersive WSSUS channel is presented.


title: Cybercars : Past, Present and Future of the Technology

abstract:
  Automobile has become the dominant transport mode in the world in the last
century. In order to meet a continuously growing demand for transport, one
solution is to change the control approach for vehicle to full driving
automation, which removes the driver from the control loop to improve
efficiency and reduce accidents. Recent work shows that there are several
realistic paths towards this deployment : driving assistance on passenger cars,
automated commercial vehicles on dedicated infrastructures, and new forms of
urban transport (car-sharing and cybercars). Cybercars have already been put
into operation in Europe, and it seems that this approach could lead the way
towards full automation on most urban, and later interurban infrastructures.
The European project CyberCars has brought many improvements in the technology
needed to operate cybercars over the last three years. A new, larger European
project is now being prepared to carry this work further in order to meet more
ambitious objectives in terms of safety and efficiency. This paper will present
past and present technologies and will focus on the future developments.


title: Optimal Transmit Covariance for Ergodic MIMO Channels

abstract:
  In this paper we consider the computation of channel capacity for ergodic
multiple-input multiple-output channels with additive white Gaussian noise. Two
scenarios are considered. Firstly, a time-varying channel is considered in
which both the transmitter and the receiver have knowledge of the channel
realization. The optimal transmission strategy is water-filling over space and
time. It is shown that this may be achieved in a causal, indeed instantaneous
fashion. In the second scenario, only the receiver has perfect knowledge of the
channel realization, while the transmitter has knowledge of the channel gain
probability law. In this case we determine an optimality condition on the input
covariance for ergodic Gaussian vector channels with arbitrary channel
distribution under the condition that the channel gains are independent of the
transmit signal. Using this optimality condition, we find an iterative
algorithm for numerical computation of optimal input covariance matrices.
Applications to correlated Rayleigh and Ricean channels are given.


title: Nonmonotonic Trust Management for P2P Applications

abstract:
  Community decisions about access control in virtual communities are
non-monotonic in nature. This means that they cannot be expressed in current,
monotonic trust management languages such as the family of Role Based Trust
Management languages (RT). To solve this problem we propose RT-, which adds a
restricted form of negation to the standard RT language, thus admitting a
controlled form of non-monotonicity. The semantics of RT- is discussed and
presented in terms of the well-founded semantics for Logic Programs. Finally we
discuss how chain discovery can be accomplished for RT-.


title:
Using Interval Particle Filtering for Marker less 3D Human Motion
  Capture

abstract:
  In this paper we present a new approach for marker less human motion capture
from conventional camera feeds. The aim of our study is to recover 3D positions
of key points of the body that can serve for gait analysis. Our approach is
based on foreground segmentation, an articulated body model and particle
filters. In order to be generic and simple no restrictive dynamic modelling was
used. A new modified particle filtering algorithm was introduced. It is used
efficiently to search the model configuration space. This new algorithm which
we call Interval Particle Filtering reorganizes the configurations search space
in an optimal deterministic way and proved to be efficient in tracking natural
human movement. Results for human motion capture from a single camera are
presented and compared to results obtained from a marker based system. The
system proved to be able to track motion successfully even in partial
occlusions.


title: Markerless Human Motion Capture for Gait Analysis

abstract:
  The aim of our study is to detect balance disorders and a tendency towards
the falls in the elderly, knowing gait parameters. In this paper we present a
new tool for gait analysis based on markerless human motion capture, from
camera feeds. The system introduced here, recovers the 3D positions of several
key points of the human body while walking. Foreground segmentation, an
articulated body model and particle filtering are basic elements of our
approach. No dynamic model is used thus this system can be described as generic
and simple to implement. A modified particle filtering algorithm, which we call
Interval Particle Filtering, is used to reorganise and search through the
model's configurations search space in a deterministic optimal way. This
algorithm was able to perform human movement tracking with success. Results
from the treatment of a single cam feeds are shown and compared to results
obtained using a marker based human motion capture system.


title: Acyclic orientations with path constraints

abstract:
  Many well-known combinatorial optimization problems can be stated over the
set of acyclic orientations of an undirected graph. For example, acyclic
orientations with certain diameter constraints are closely related to the
optimal solutions of the vertex coloring and frequency assignment problems. In
this paper we introduce a linear programming formulation of acyclic
orientations with path constraints, and discuss its use in the solution of the
vertex coloring problem and some versions of the frequency assignment problem.
A study of the polytope associated with the formulation is presented, including
proofs of which constraints of the formulation are facet-defining and the
introduction of new classes of valid inequalities.


title: A new authentication protocol for revocable anonymity in ad-hoc networks

abstract:
  This paper describes a new protocol for authentication in ad-hoc networks.
The protocol has been designed to meet specialized requirements of ad-hoc
networks, such as lack of direct communication between nodes or requirements
for revocable anonymity. At the same time, a ad-hoc authentication protocol
must be resistant to spoofing, eavesdropping and playback, and
man-in-the-middle attacks. The article analyzes existing authentication methods
based on the Public Key Infrastructure, and finds that they have several
drawbacks in ad-hoc networks. Therefore, a new authentication protocol, basing
on established cryptographic primitives (Merkle's puzzles and zero-knowledge
proofs) is proposed. The protocol is studied for a model ad-hoc chat
application that provides private conversations.


title:
The monadic second-order logic of graphs XVI : Canonical graph<br>
  decompositions

abstract:
  This article establishes that the split decomposition of graphs introduced by
Cunnigham, is definable in Monadic Second-Order Logic.This result is actually
an instance of a more general result covering canonical graph decompositions
like the modular decomposition and the Tutte decomposition of 2-connected
graphs into 3-connected components. As an application, we prove that the set of
graphs having the same cycle matroid as a given 2-connected graph can be
defined from this graph by Monadic Second-Order formulas.


title: On the Spread of Random Interleaver

abstract:
  For a given blocklength we determine the number of interleavers which have
spread equal to two. Using this, we find out the probability that a randomly
chosen interleaver has spread two. We show that as blocklength increases, this
probability increases but very quickly converges to the value $1-e^{-2} \approx
0.8647$. Subsequently, we determine a lower bound on the probability of an
interleaver having spread at least $s$. We show that this lower bound converges
to the value $e^{-2(s-2)^{2}}$, as the blocklength increases.


title: Ultra Wideband Impulse Radio Systems with Multiple Pulse Types

abstract:
  In an ultra wideband (UWB) impulse radio (IR) system, a number of pulses,
each transmitted in an interval called a "frame", is employed to represent one
information symbol. Conventionally, a single type of UWB pulse is used in all
frames of all users. In this paper, IR systems with multiple types of UWB
pulses are considered, where different types of pulses can be used in different
frames by different users. Both stored-reference (SR) and transmitted-reference
(TR) systems are considered. First, the spectral properties of a multi-pulse IR
system with polarity randomization is investigated. It is shown that the
average power spectral density is the average of the spectral contents of
different pulse shapes. Then, approximate closed-form expressions for the bit
error probability of a multi-pulse SR-IR system are derived for RAKE receivers
in asynchronous multiuser environments. The effects of both inter-frame
interference (IFI) and multiple-access interference (MAI) are analyzed. The
theoretical and simulation results indicate that SR-IR systems that are more
robust against IFI and MAI than a "conventional" SR-IR system can be designed
with multiple types of ultra-wideband pulses. Finally, extensions to
multi-pulse TR-IR systems are briefly described.


title: Comparing Computational Power

abstract:
  It is common practice to compare the computational power of different models
of computation. For example, the recursive functions are strictly more powerful
than the primitive recursive functions, because the latter are a proper subset
of the former (which includes Ackermann's function). Side-by-side with this
"containment" method of measuring power, it is standard to use an approach
based on "simulation". For example, one says that the (untyped) lambda calculus
is as powerful--computationally speaking--as the partial recursive functions,
because the lambda calculus can simulate all partial recursive functions by
encoding the natural numbers as Church numerals.
  The problem is that unbridled use of these two ways of comparing power allows
one to show that some computational models are strictly stronger than
themselves! We argue that a better definition is that model A is strictly
stronger than B if A can simulate B via some encoding, whereas B cannot
simulate A under any encoding. We then show that the recursive functions are
strictly stronger in this sense than the primitive recursive. We also prove
that the recursive functions, partial recursive functions, and Turing machines
are "complete", in the sense that no injective encoding can make them
equivalent to any "hypercomputational" model.


title: On Coding for Reliable Communication over Packet Networks

abstract:
  We present a capacity-achieving coding scheme for unicast or multicast over
lossy packet networks. In the scheme, intermediate nodes perform additional
coding yet do not decode nor even wait for a block of packets before sending
out coded packets. Rather, whenever they have a transmission opportunity, they
send out coded packets formed from random linear combinations of previously
received packets. All coding and decoding operations have polynomial
complexity.
  We show that the scheme is capacity-achieving as long as packets received on
a link arrive according to a process that has an average rate. Thus, packet
losses on a link may exhibit correlation in time or with losses on other links.
In the special case of Poisson traffic with i.i.d. losses, we give error
exponents that quantify the rate of decay of the probability of error with
coding delay. Our analysis of the scheme shows that it is not only
capacity-achieving, but that the propagation of packets carrying "innovative"
information follows the propagation of jobs through a queueing network, and
therefore fluid flow models yield good approximations. We consider networks
with both lossy point-to-point and broadcast links, allowing us to model both
wireline and wireless packet networks.


title: A Simple Cooperative Diversity Method Based on Network Path Selection

abstract:
  Cooperative diversity has been recently proposed as a way to form virtual
antenna arrays that provide dramatic gains in slow fading wireless
environments. However most of the proposed solutions require distributed
space-time coding algorithms, the careful design of which is left for future
investigation if there is more than one cooperative relay. We propose a novel
scheme, that alleviates these problems and provides diversity gains on the
order of the number of relays in the network. Our scheme first selects the best
relay from a set of M available relays and then uses this best relay for
cooperation between the source and the destination. We develop and analyze a
distributed method to select the best relay that requires no topology
information and is based on local measurements of the instantaneous channel
conditions. This method also requires no explicit communication among the
relays. The success (or failure) to select the best available path depends on
the statistics of the wireless channel, and a methodology to evaluate
performance for any kind of wireless channel statistics, is provided.
Information theoretic analysis of outage probability shows that our scheme
achieves the same diversity-multiplexing tradeoff as achieved by more complex
protocols, where coordination and distributed space-time coding for M nodes is
required, such as those proposed in [7]. The simplicity of the technique,
allows for immediate implementation in existing radio hardware and its adoption
could provide for improved flexibility, reliability and efficiency in future 4G
wireless systems.


title:
On Interleaving Techniques for MIMO Channels and Limitations of Bit
  Interleaved Coded Modulation

abstract:
  It is shown that while the mutual information curves for coded modulation
(CM) and bit interleaved coded modulation (BICM) overlap in the case of a
single input single output channel, the same is not true in multiple input
multiple output (MIMO) channels. A method for mitigating fading in the presence
of multiple transmit antennas, named coordinate interleaving (CI), is presented
as a generalization of component interleaving for a single transmit antenna.
The extent of any advantages of CI over BICM, relative to CM, is analyzed from
a mutual information perspective; the analysis is based on an equivalent
parallel channel model for CI. Several expressions for mutual information in
the presence of CI and multiple transmit and receive antennas are derived.
Results show that CI gives higher mutual information compared to that of BICM
if proper signal mappings are used. Effects like constellation rotation in the
presence of CI are also considered and illustrated; it is shown that
constellation rotation can increase the constrained capacity.


title: Semantic Embedding of Petri Nets into Event-B

abstract:
  We present an embedding of Petri nets into B abstract systems. The embedding
is achieved by translating both the static structure (modelling aspect) and the
evolution semantics of Petri nets. The static structure of a Petri-net is
captured within a B abstract system through a graph structure. This abstract
system is then included in another abstract system which captures the evolution
semantics of Petri-nets. The evolution semantics results in some B events
depending on the chosen policies: basic nets or high level Petri nets. The
current embedding enables one to use conjointly Petri nets and Event-B in the
same system development, but at different steps and for various analysis.


title:
Practical Datatype Specializations with Phantom Types and Recursion
  Schemes

abstract:
  Datatype specialization is a form of subtyping that captures program
invariants on data structures that are expressed using the convenient and
intuitive datatype notation. Of particular interest are structural invariants
such as well-formedness. We investigate the use of phantom types for describing
datatype specializations. We show that it is possible to express
statically-checked specializations within the type system of Standard ML. We
also show that this can be done in a way that does not lose useful programming
facilities such as pattern matching in case expressions.


title: On-Off Frequency-Shift-Keying for Wideband Fading Channels

abstract:
  M-ary On-Off Frequency-Shift-Keying (OOFSK) is a digital modulation format in
which M-ary FSK signaling is overlaid on On/Off keying. This paper investigates
the potential of this modulation format in the context of wideband fading
channels. First it is assumed that the receiver uses energy detection for the
reception of OOFSK signals. Capacity expressions are obtained for the cases in
which the receiver has perfect and imperfect fading side information. Power
efficiency is investigated when the transmitter is subject to a peak-to-average
power ratio (PAR) limitation or a peak power limitation. It is shown that under
a PAR limitation, it is extremely power inefficient to operate in the very low
SNR regime. On the other hand, if there is only a peak power limitation, it is
demonstrated that power efficiency improves as one operates with smaller SNR
and vanishing duty factor. Also studied are the capacity improvements that
accrue when the receiver can track phase shifts in the channel or if the
received signal has a specular component. To take advantage of those features,
the phase of the modulation is also allowed to carry information.


title: Applying Evolutionary Optimisation to Robot Obstacle Avoidance

abstract:
  This paper presents an artificial evolutionbased method for stereo image
analysis and its application to real-time obstacle detection and avoidance for
a mobile robot. It uses the Parisian approach, which consists here in splitting
the representation of the robot's environment into a large number of simple
primitives, the "flies", which are evolved following a biologically inspired
scheme and give a fast, low-cost solution to the obstacle detection problem in
mobile robotics.


title: Connection state overhead in a dynamic linear network

abstract:
  We consider a dynamical linear network where nearest neighbours communicate
via links whose states form binary (open/closed) valued independent and
identically distributed Markov processes. Our main result is the tight
information-theoretic lower bound on the network traffic required by the
connection state overhead, or the information required for all nodes to know
their connected neighbourhood. These results, and especially their possible
generalisations to more realistic network models, could give us valuable
understanding of the unavoidable protocol overheads in rapidly changing Ad hoc
and sensor networks.


title:
Vector Gaussian Multiple Description with Individual and Central
  Receivers

abstract:
  L multiple descriptions of a vector Gaussian source for individual and
central receivers are investigated. The sum rate of the descriptions with
covariance distortion measure constraints, in a positive semidefinite ordering,
is exactly characterized. For two descriptions, the entire rate region is
characterized. Jointly Gaussian descriptions are optimal in achieving the
limiting rates. The key component of the solution is a novel
information-theoretic inequality that is used to lower bound the achievable
multiple description rates.


title: Evidence with Uncertain Likelihoods

abstract:
  An agent often has a number of hypotheses, and must choose among them based
on observations, or outcomes of experiments. Each of these observations can be
viewed as providing evidence for or against various hypotheses. All the
attempts to formalize this intuition up to now have assumed that associated
with each hypothesis h there is a likelihood function \mu_h, which is a
probability measure that intuitively describes how likely each observation is,
conditional on h being the correct hypothesis. We consider an extension of this
framework where there is uncertainty as to which of a number of likelihood
functions is appropriate, and discuss how one formal approach to defining
evidence, which views evidence as a function from priors to posteriors, can be
generalized to accommodate this uncertainty.


title: When Ignorance is Bliss

abstract:
  It is commonly-accepted wisdom that more information is better, and that
information should never be ignored. Here we argue, using both a Bayesian and a
non-Bayesian analysis, that in some situations you are better off ignoring
information if your uncertainty is represented by a set of probability
measures. These include situations in which the information is relevant for the
prediction task at hand. In the non-Bayesian analysis, we show how ignoring
information avoids dilation, the phenomenon that additional pieces of
information sometimes lead to an increase in uncertainty. In the Bayesian
analysis, we show that for small sample sizes and certain prediction tasks, the
Bayesian posterior based on a noninformative prior yields worse predictions
than simply ignoring the given information.


title: Virtual Environments for multiphysics code validation on Computing Grids

abstract:
  We advocate in this paper the use of grid-based infrastructures that are
designed for seamless approaches to the numerical expert users, i.e., the
multiphysics applications designers. It relies on sophisticated computing
environments based on computing grids, connecting heterogeneous computing
resources: mainframes, PC-clusters and workstations running multiphysics codes
and utility software, e.g., visualization tools. The approach is based on
concepts defined by the HEAVEN* consortium. HEAVEN is a European scientific
consortium including industrial partners from the aerospace, telecommunication
and software industries, as well as academic research institutes. Currently,
the HEAVEN consortium works on a project that aims to create advanced services
platforms. It is intended to enable "virtual private grids" supporting various
environments for users manipulating a suitable high-level interface. This will
become the basis for future generalized services allowing the integration of
various services without the need to deploy specific grid infrastructures.


title:
Architectural Considerations for a Self-Configuring Routing Scheme for
  Spontaneous Networks

abstract:
  Decoupling the permanent identifier of a node from the node's
topology-dependent address is a promising approach toward completely scalable
self-organizing networks. A group of proposals that have adopted such an
approach use the same structure to: address nodes, perform routing, and
implement location service. In this way, the consistency of the routing
protocol relies on the coherent sharing of the addressing space among all nodes
in the network. Such proposals use a logical tree-like structure where routes
in this space correspond to routes in the physical level. The advantage of
tree-like spaces is that it allows for simple address assignment and
management. Nevertheless, it has low route selection flexibility, which results
in low routing performance and poor resilience to failures. In this paper, we
propose to increase the number of paths using incomplete hypercubes. The design
of more complex structures, like multi-dimensional Cartesian spaces, improves
the resilience and routing performance due to the flexibility in route
selection. We present a framework for using hypercubes to implement indirect
routing. This framework allows to give a solution adapted to the dynamics of
the network, providing a proactive and reactive routing protocols, our major
contributions. We show that, contrary to traditional approaches, our proposal
supports more dynamic networks and is more robust to node failures.


title:
Neuronal Spectral Analysis of EEG and Expert Knowledge Integration for
  Automatic Classification of Sleep Stages

abstract:
  Being able to analyze and interpret signal coming from electroencephalogram
(EEG) recording can be of high interest for many applications including medical
diagnosis and Brain-Computer Interfaces. Indeed, human experts are today able
to extract from this signal many hints related to physiological as well as
cognitive states of the recorded subject and it would be very interesting to
perform such task automatically but today no completely automatic system
exists. In previous studies, we have compared human expertise and automatic
processing tools, including artificial neural networks (ANN), to better
understand the competences of each and determine which are the difficult
aspects to integrate in a fully automatic system. In this paper, we bring more
elements to that study in reporting the main results of a practical experiment
which was carried out in an hospital for sleep pathology study. An EEG
recording was studied and labeled by a human expert and an ANN. We describe
here the characteristics of the experiment, both human and neuronal procedure
of analysis, compare their performances and point out the main limitations
which arise from this study.


title: R\'{e}flexions sur la question fr\'{e}quentielle en traitement du signal

abstract:
  New definitions are suggested for frequencies which may be instantaneous or
not. The Heisenberg-Gabor inequality and the Shannon sampling theorem are
briefly discussed.


title:
Canonical time-frequency, time-scale, and frequency-scale
  representations of time-varying channels

abstract:
  Mobile communication channels are often modeled as linear time-varying
filters or, equivalently, as time-frequency integral operators with finite
support in time and frequency. Such a characterization inherently assumes the
signals are narrowband and may not be appropriate for wideband signals. In this
paper time-scale characterizations are examined that are useful in wideband
time-varying channels, for which a time-scale integral operator is physically
justifiable. A review of these time-frequency and time-scale characterizations
is presented. Both the time-frequency and time-scale integral operators have a
two-dimensional discrete characterization which motivates the design of
time-frequency or time-scale rake receivers. These receivers have taps for both
time and frequency (or time and scale) shifts of the transmitted signal. A
general theory of these characterizations which generates, as specific cases,
the discrete time-frequency and time-scale models is presented here. The
interpretation of these models, namely, that they can be seen to arise from
processing assumptions on the transmit and receive waveforms is discussed. Out
of this discussion a third model arises: a frequency-scale continuous channel
model with an associated discrete frequency-scale characterization.


title: Balanced Allocation on Graphs

abstract:
  In this paper, we study the two choice balls and bins process when balls are
not allowed to choose any two random bins, but only bins that are connected by
an edge in an underlying graph. We show that for $n$ balls and $n$ bins, if the
graph is almost regular with degree $n^\epsilon$, where $\epsilon$ is not too
small, the previous bounds on the maximum load continue to hold. Precisely, the
maximum load is $\log \log n + O(1/\epsilon) + O(1)$. For general
$\Delta$-regular graphs, we show that the maximum load is $\log\log n +
O(\frac{\log n}{\log (\Delta/\log^4 n)}) + O(1)$ and also provide an almost
matching lower bound of $\log \log n + \frac{\log n}{\log (\Delta \log n)}$.
  V{\"o}cking [Voc99] showed that the maximum bin size with $d$ choice load
balancing can be further improved to $O(\log\log n /d)$ by breaking ties to the
left. This requires $d$ random bin choices. We show that such bounds can be
achieved by making only two random accesses and querying $d/2$ contiguous bins
in each access. By grouping a sequence of $n$ bins into $2n/d$ groups, each of
$d/2$ consecutive bins, if each ball chooses two groups at random and inserts
the new ball into the least-loaded bin in the lesser loaded group, then the
maximum load is $O(\log\log n/d)$ with high probability.


title: MathPSfrag: Creating Publication-Quality Labels in Mathematica Plots

abstract:
  This article introduces a Mathematica package providing a graphics export
function that automatically replaces Mathematica expressions in a graphic by
the corresponding LaTeX constructs and positions them correctly. It thus
facilitates the creation of publication-quality Enscapulated PostScript (EPS)
graphics.


title: Lower bounds on Locality Sensitive Hashing

abstract:
  Given a metric space $(X,d_X)$, $c\ge 1$, $r>0$, and $p,q\in [0,1]$, a
distribution over mappings $\h:X\to \mathbb N$ is called a
$(r,cr,p,q)$-sensitive hash family if any two points in $X$ at distance at most
$r$ are mapped by $\h$ to the same value with probability at least $p$, and any
two points at distance greater than $cr$ are mapped by $\h$ to the same value
with probability at most $q$. This notion was introduced by Indyk and Motwani
in 1998 as the basis for an efficient approximate nearest neighbor search
algorithm, and has since been used extensively for this purpose. The
performance of these algorithms is governed by the parameter
$\rho=\frac{\log(1/p)}{\log(1/q)}$, and constructing hash families with small
$\rho$ automatically yields improved nearest neighbor algorithms. Here we show
that for $X=\ell_1$ it is impossible to achieve $\rho\le \frac{1}{2c}$. This
almost matches the construction of Indyk and Motwani which achieves $\rho\le
\frac{1}{c}$.


title: Automata-based adaptive behavior for economic modeling using game theory

abstract:
  In this paper, we deal with some specific domains of applications to game
theory. This is one of the major class of models in the new approaches of
modelling in the economic domain. For that, we use genetic automata which allow
to buid adaptive strategies for the players. We explain how the automata-based
formalism proposed - matrix representation of automata with multiplicities -
allows to define a semi-distance between the strategy behaviors. With that
tools, we are able to generate an automatic processus to compute emergent
systems of entities whose behaviors are represented by these genetic automata.


title: A simple effective method for curvatures estimation on triangular meshes

abstract:
  To definite and compute differential invariants, like curvatures, for
triangular meshes (or polyhedral surfaces) is a key problem in CAGD and the
computer vision. The Gaussian curvature and the mean curvature are determined
by the differential of the Gauss map of the underlying surface. The Gauss map
assigns to each point in the surface the unit normal vector of the tangent
plane to the surface at this point. We follow the ideas developed in Chen and
Wu \cite{Chen2}(2004) and Wu, Chen and Chi\cite{Wu}(2005) to describe a new and
simple approach to estimate the differential of the Gauss map and curvatures
from the viewpoint of the gradient and the centroid weights. This will give us
a much better estimation of curvatures than Taubin's algorithm \cite{Taubin}
(1995).


title:
An efficient memetic, permutation-based evolutionary algorithm for
  real-world train timetabling

abstract:
  Train timetabling is a difficult and very tightly constrained combinatorial
problem that deals with the construction of train schedules. We focus on the
particular problem of local reconstruction of the schedule following a small
perturbation, seeking minimisation of the total accumulated delay by adapting
times of departure and arrival for each train and allocation of resources
(tracks, routing nodes, etc.). We describe a permutation-based evolutionary
algorithm that relies on a semi-greedy heuristic to gradually reconstruct the
schedule by inserting trains one after the other following the permutation.
This algorithm can be hybridised with ILOG commercial MIP programming tool
CPLEX in a coarse-grained manner: the evolutionary part is used to quickly
obtain a good but suboptimal solution and this intermediate solution is refined
using CPLEX. Experimental results are presented on a large real-world case
involving more than one million variables and 2 million constraints. Results
are surprisingly good as the evolutionary algorithm, alone or hybridised,
produces excellent solutions much faster than CPLEX alone.


title: Context Semantics, Linear Logic and Computational Complexity

abstract:
  We show that context semantics can be fruitfully applied to the quantitative
analysis of proof normalization in linear logic. In particular, context
semantics lets us define the weight of a proof-net as a measure of its inherent
complexity: it is both an upper bound to normalization time (modulo a
polynomial overhead, independently on the reduction strategy) and a lower bound
to the number of steps to normal form (for certain reduction strategies).
Weights are then exploited in proving strong soundness theorems for various
subsystems of linear logic, namely elementary linear logic, soft linear logic
and light linear logic.


title: ParFORM: recent development

abstract:
  We report on the status of our project of parallelization of the symbolic
manipulation program FORM. We have now parallel versions of FORM running on
Cluster- or SMP-architectures. These versions can be used to run arbitrary FORM
programs in parallel.


title:
Big Science with a Small Budget: Non-Embarrassingly Parallel
  Applications in a Non-Dedicated Network of Workstations

abstract:
  Many astronomers and astrophysicists require large computing resources for
their research, which are usually obtained via dedicated (and expensive)
parallel machines. Depending on the type of the problem to be solved, an
alternative solution can be provided by creating dynamically a computer cluster
out of non-dedicated workstations using the Condor High Throughput Computing
System and the Master-Worker (MW) framework. As an example of this we show in
this paper how a radiative transfer application previously coded with MPI is
solved using this solution without the need for dedicated machines.


title: Rate Region of the Quadratic Gaussian Two-Encoder Source-Coding Problem

abstract:
  We determine the rate region of the quadratic Gaussian two-encoder
source-coding problem. This rate region is achieved by a simple architecture
that separates the analog and digital aspects of the compression. Furthermore,
this architecture requires higher rates to send a Gaussian source than it does
to send any other source with the same covariance. Our techniques can also be
used to determine the sum rate of some generalizations of this classical
problem. Our approach involves coupling the problem to a quadratic Gaussian
``CEO problem.''


title: Capacity with Causal and Non-Causal Side Information - A Unified View

abstract:
  We identify the common underlying form of the capacity expression that is
applicable to both cases where causal or non-causal side information is made
available to the transmitter. Using this common form we find that for the
single user channel, the multiple access channel, the degraded broadcast
channel, and the degraded relay channel, the sum capacity with causal and
non-causal side information are identical when all the transmitter side
information is also made available to all the receivers. A genie-aided
outerbound is developed that states that when a genie provides $n$ bits of side
information to a receiver the resulting capacity improvement can not be more
than $n$ bits. Combining these two results we are able to bound the relative
capacity advantage of non-causal side information over causal side information
for both single user as well as various multiple user communication scenarios.
Applications of these capacity bounds are demonstrated through examples of
random access channels. Interestingly, the capacity results indicate that the
excessive MAC layer overheads common in present wireless systems may be avoided
through coding across multiple access blocks. It is also shown that even one
bit of side information at the transmitter can result in unbounded capacity
improvement. As a side, we obtain the sum capacity for a multiple access
channel when the side information available to the transmitter is causal and
possibly correlated to the side information available to the receiver.


title: Bibliographic Classification using the ADS Databases

abstract:
  We discuss two techniques used to characterize bibliographic records based on
their similarity to and relationship with the contents of the NASA Astrophysics
Data System (ADS) databases. The first method has been used to classify input
text as being relevant to one or more subject areas based on an analysis of the
frequency distribution of its individual words. The second method has been used
to classify existing records as being relevant to one or more databases based
on the distribution of the papers citing them. Both techniques have proven to
be valuable tools in assigning new and existing bibliographic records to
different disciplines within the ADS databases.


title: Optimal Prefix Codes for Infinite Alphabets with Nonlinear Costs

abstract:
  Let $P = \{p(i)\}$ be a measure of strictly positive probabilities on the set
of nonnegative integers. Although the countable number of inputs prevents usage
of the Huffman algorithm, there are nontrivial $P$ for which known methods find
a source code that is optimal in the sense of minimizing expected codeword
length. For some applications, however, a source code should instead minimize
one of a family of nonlinear objective functions, $\beta$-exponential means,
those of the form $\log_a \sum_i p(i) a^{n(i)}$, where $n(i)$ is the length of
the $i$th codeword and $a$ is a positive constant. Applications of such
minimizations include a novel problem of maximizing the chance of message
receipt in single-shot communications ($a<1$) and a previously known problem of
minimizing the chance of buffer overflow in a queueing system ($a>1$). This
paper introduces methods for finding codes optimal for such exponential means.
One method applies to geometric distributions, while another applies to
distributions with lighter tails. The latter algorithm is applied to Poisson
distributions and both are extended to alphabetic codes, as well as to
minimizing maximum pointwise redundancy. The aforementioned application of
minimizing the chance of buffer overflow is also considered.


title: Evolutionary Computing

abstract:
  Evolutionary computing (EC) is an exciting development in Computer Science.
It amounts to building, applying and studying algorithms based on the Darwinian
principles of natural selection. In this paper we briefly introduce the main
concepts behind evolutionary computing. We present the main components all
evolutionary algorithms (EA), sketch the differences between different types of
EAs and survey application areas ranging from optimization, modeling and
simulation to entertainment.


title: The egalitarian effect of search engines

abstract:
  Search engines have become key media for our scientific, economic, and social
activities by enabling people to access information on the Web in spite of its
size and complexity. On the down side, search engines bias the traffic of users
according to their page-ranking strategies, and some have argued that they
create a vicious cycle that amplifies the dominance of established and already
popular sites. We show that, contrary to these prior claims and our own
intuition, the use of search engines actually has an egalitarian effect. We
reconcile theoretical arguments with empirical evidence showing that the
combination of retrieval by search engines and search behavior by users
mitigates the attraction of popular pages, directing more traffic toward less
popular sites, even in comparison to what would be expected from users randomly
surfing the Web.


title: Logical Relations for Monadic Types

abstract:
  Logical relations and their generalizations are a fundamental tool in proving
properties of lambda-calculi, e.g., yielding sound principles for observational
equivalence. We propose a natural notion of logical relations able to deal with
the monadic types of Moggi's computational lambda-calculus. The treatment is
categorical, and is based on notions of subsconing, mono factorization systems,
and monad morphisms. Our approach has a number of interesting applications,
including cases for lambda-calculi with non-determinism (where being in logical
relation means being bisimilar), dynamic name creation, and probabilistic
systems.


title:
K-core decomposition of Internet graphs: hierarchies, self-similarity
  and measurement biases

abstract:
  We consider the $k$-core decomposition of network models and Internet graphs
at the autonomous system (AS) level. The $k$-core analysis allows to
characterize networks beyond the degree distribution and uncover structural
properties and hierarchies due to the specific architecture of the system. We
compare the $k$-core structure obtained for AS graphs with those of several
network models and discuss the differences and similarities with the real
Internet architecture. The presence of biases and the incompleteness of the
real maps are discussed and their effect on the $k$-core analysis is assessed
with numerical experiments simulating biased exploration on a wide range of
network models. We find that the $k$-core analysis provides an interesting
characterization of the fluctuations and incompleteness of maps as well as
information helping to discriminate the original underlying structure.


title:
Analysis of Stochastic Service Guarantees in Communication Networks: A
  Basic Calculus

abstract:
  A basic calculus is presented for stochastic service guarantee analysis in
communication networks. Central to the calculus are two definitions,
maximum-(virtual)-backlog-centric (m.b.c) stochastic arrival curve and
stochastic service curve, which respectively generalize arrival curve and
service curve in the deterministic network calculus framework. With m.b.c
stochastic arrival curve and stochastic service curve, various basic results
are derived under the (min, +) algebra for the general case analysis, which are
crucial to the development of stochastic network calculus. These results
include (i) superposition of flows, (ii) concatenation of servers, (iii) output
characterization, (iv) per-flow service under aggregation, and (v) stochastic
backlog and delay guarantees. In addition, to perform independent case
analysis, stochastic strict server is defined, which uses an ideal service
process and an impairment process to characterize a server. The concept of
stochastic strict server not only allows us to improve the basic results (i) --
(v) under the independent case, but also provides a convenient way to find the
stochastic service curve of a serve. Moreover, an approach is introduced to
find the m.b.c stochastic arrival curve of a flow and the stochastic service
curve of a server.


title:
Mismatched codebooks and the role of entropy-coding in lossy data
  compression

abstract:
  We introduce a universal quantization scheme based on random coding, and we
analyze its performance. This scheme consists of a source-independent random
codebook (typically_mismatched_ to the source distribution), followed by
optimal entropy-coding that is_matched_ to the quantized codeword distribution.
A single-letter formula is derived for the rate achieved by this scheme at a
given distortion, in the limit of large codebook dimension. The rate reduction
due to entropy-coding is quantified, and it is shown that it can be arbitrarily
large. In the special case of "almost uniform" codebooks (e.g., an i.i.d.
Gaussian codebook with large variance) and difference distortion measures, a
novel connection is drawn between the compression achieved by the present
scheme and the performance of "universal" entropy-coded dithered lattice
quantizers. This connection generalizes the "half-a-bit" bound on the
redundancy of dithered lattice quantizers. Moreover, it demonstrates a strong
notion of universality where a single "almost uniform" codebook is near-optimal
for_any_ source and_any_ difference distortion measure.


title:
A Survey of Virtualization Techniques Focusing on Secure On-Demand
  Cluster Computing

abstract:
  Virtualization, a technique once used to multiplex the resources of
high-priced mainframe hardware, is seeing a resurgence in applicability with
the increasing computing power of commodity computers. By inserting a layer of
software between the machine and traditional operating systems, this technology
allows access to a shared computing medium in a manner that is secure,
resource-controlled, and efficient. These properties are attractive in the
field of on-demand computing, where the fine-grained subdivision of resources
provided by virtualized systems allows potentially higher utilization of
computing resources.
  It this work, we survey a number of virtual machine systems with the goal of
finding an appropriate candidate to serve as the basis for the On-Demand Secure
Cluster Computing project at the National Center for Supercomputing
Applications. Contenders are reviewed on a number of desirable properties
including portability and security. We conclude with a comparison and
justification of our choice.


title: The Impact of Social Networks on Multi-Agent Recommender Systems

abstract:
  Awerbuch et al.'s approach to distributed recommender systems (DRSs) is to
have agents sample products at random while randomly querying one another for
the best item they have found; we improve upon this by adding a communication
network. Agents can only communicate with their immediate neighbors in the
network, but neighboring agents may or may not represent users with common
interests. We define two network structures: in the ``mailing-list model,''
agents representing similar users form cliques, while in the ``word-of-mouth
model'' the agents are distributed randomly in a scale-free network (SFN). In
both models, agents tell their neighbors about satisfactory products as they
are found. In the word-of-mouth model, knowledge of items propagates only
through interested agents, and the SFN parameters affect the system's
performance. We include a summary of our new results on the character and
parameters of random subgraphs of SFNs, in particular SFNs with power-law
degree distributions down to minimum degree 1. These networks are not as
resilient as Cohen et al. originally suggested. In the case of the widely-cited
``Internet resilience'' result, high failure rates actually lead to the
orphaning of half of the surviving nodes after 60% of the network has failed
and the complete disintegration of the network at 90%. We show that given an
appropriate network, the communication network reduces the number of sampled
items, the number of messages sent, and the amount of ``spam.'' We conclude
that in many cases DRSs will be useful for sharing information in a multi-agent
learning system.


title:
Parameters Affecting the Resilience of Scale-Free Networks to Random
  Failures

abstract:
  It is commonly believed that scale-free networks are robust to massive
numbers of random node deletions. For example, Cohen et al. study scale-free
networks including some which approximate the measured degree distribution of
the Internet. Their results suggest that if each node in this network failed
independently with probability 0.99, the remaining network would continue to
have a giant component. In this paper, we show that a large and important
subclass of scale-free networks are not robust to massive numbers of random
node deletions for practical purposes. In particular, we study finite
scale-free networks which have minimum node degree of 1 and a power-law degree
distribution beginning with nodes of degree 1 (power-law networks). We show
that, in a power-law network approximating the Internet's reported
distribution, when the probability of deletion of each node is 0.5 only about
25% of the surviving nodes in the network remain connected in a giant
component, and the giant component does not persist beyond a critical failure
rate of 0.9. The new result is partially due to improved analytical
accommodation of the large number of degree-0 nodes that result after node
deletions. Our results apply to finite power-law networks with a wide range of
power-law exponents, including Internet-like networks. We give both analytical
and empirical evidence that such networks are not generally robust to massive
random node deletions.


title:
K-ANMI: A Mutual Information Based Clustering Algorithm for Categorical
  Data

abstract:
  Clustering categorical data is an integral part of data mining and has
attracted much attention recently. In this paper, we present k-ANMI, a new
efficient algorithm for clustering categorical data. The k-ANMI algorithm works
in a way that is similar to the popular k-means algorithm, and the goodness of
clustering in each step is evaluated using a mutual information based criterion
(namely, Average Normalized Mutual Information-ANMI) borrowed from cluster
ensemble. Experimental results on real datasets show that k-ANMI algorithm is
competitive with those state-of-art categorical data clustering algorithms with
respect to clustering accuracy.


title:
Flat and One-Variable Clauses: Complexity of Verifying Cryptographic
  Protocols with Single Blind Copying

abstract:
  Cryptographic protocols with single blind copying were defined and modeled by
Comon and Cortier using the new class $\mathcal C$ of first order clauses. They
showed its satisfiability problem to be in 3-DEXPTIME. We improve this result
by showing that satisfiability for this class is NEXPTIME-complete, using new
resolution techniques. We show satisfiability to be DEXPTIME-complete if
clauses are Horn, which is what is required for modeling cryptographic
protocols. While translation to Horn clauses only gives a DEXPTIME upper bound
for the secrecy problem for these protocols, we further show that this secrecy
problem is actually DEXPTIME-complete.


title:
Towards a Hierarchical Model of Consciousness, Intelligence, Mind and
  Body

abstract: This article is taken out.


title: How to make the top ten: Approximating PageRank from in-degree

abstract:
  PageRank has become a key element in the success of search engines, allowing
to rank the most important hits in the top screen of results. One key aspect
that distinguishes PageRank from other prestige measures such as in-degree is
its global nature. From the information provider perspective, this makes it
difficult or impossible to predict how their pages will be ranked. Consequently
a market has emerged for the optimization of search engine results. Here we
study the accuracy with which PageRank can be approximated by in-degree, a
local measure made freely available by search engines. Theoretical and
empirical analyses lead to conclude that given the weak degree correlations in
the Web link graph, the approximation can be relatively accurate, giving
service and information providers an effective new marketing tool.


title: Short Quantum Games

abstract:
  In this thesis we introduce quantum refereed games, which are quantum
interactive proof systems with two competing provers. We focus on a restriction
of this model that we call "short quantum games" and we prove an upper bound
and a lower bound on the expressive power of these games.
  For the lower bound, we prove that every language having an ordinary quantum
interactive proof system also has a short quantum game. An important part of
this proof is the establishment of a quantum measurement that reliably
distinguishes between quantum states chosen from disjoint convex sets.
  For the upper bound, we show that certain types of quantum refereed games,
including short quantum games, are decidable in deterministic exponential time
by supplying a separation oracle for use with the ellipsoid method for convex
feasibility.