title:
Dense-Timed Petri Nets: Checking Zenoness, Token liveness and
  Boundedness

abstract:
  We consider Dense-Timed Petri Nets (TPN), an extension of Petri nets in which
each token is equipped with a real-valued clock and where the semantics is lazy
(i.e., enabled transitions need not fire; time can pass and disable
transitions). We consider the following verification problems for TPNs. (i)
Zenoness: whether there exists a zeno-computation from a given marking, i.e.,
an infinite computation which takes only a finite amount of time. We show
decidability of zenoness for TPNs, thus solving an open problem from [Escrig et
al.]. Furthermore, the related question if there exist arbitrarily fast
computations from a given marking is also decidable. On the other hand,
universal zenoness, i.e., the question if all infinite computations from a
given marking are zeno, is undecidable. (ii) Token liveness: whether a token is
alive in a marking, i.e., whether there is a computation from the marking which
eventually consumes the token. We show decidability of the problem by reducing
it to the coverability problem, which is decidable for TPNs. (iii) Boundedness:
whether the size of the reachable markings is bounded. We consider two versions
of the problem; namely semantic boundedness where only live tokens are taken
into consideration in the markings, and syntactic boundedness where also dead
tokens are considered. We show undecidability of semantic boundedness, while we
prove that syntactic boundedness is decidable through an extension of the
Karp-Miller algorithm.


title: On numerical stability of recursive present value computation method

abstract:
  We analyze numerical stability of a recursive computation scheme of present
value (PV) amd show that the absolute error increases exponentially for
positive discount rates. We show that reversing the direction of calculations
in the recurrence equation yields a robust PV computation routine.


title: HowTo Authenticate and Encrypt

abstract:
  Recently, various side-channel attacks on widely used encryption methods have
been discovered. Extensive research is currently undertaken to develop new
types of combined encryption and authentication mechanisms. Developers of
security systems ask whether to implement methods recommended by international
standards or to choose one of the new proposals. We explain the nature of the
attacks and how they can be avoided, and recommend a sound, provably secure
solution: the CCM standard.


title:
Numerical Simulation guided Lazy Abstraction Refinement for Nonlinear
  Hybrid Automata

abstract:
  This draft suggests a new counterexample guided abstraction refinement
(CEGAR) framework that uses the combination of numerical simulation for
nonlinear differential equations with linear programming for linear hybrid
automata (LHA) to perform reachability analysis on nonlinear hybrid automata. A
notion of $\epsilon-$ structural robustness is also introduced which allows the
algorithm to validate counterexamples using numerical simulations.
  Keywords: verification, model checking, hybrid systems, hybrid automata,
robustness, robust hybrid systems, numerical simulation, cegar, abstraction
refinement.


title:
On the Solution-Space Geometry of Random Constraint Satisfaction
  Problems

abstract:
  For a large number of random constraint satisfaction problems, such as random
k-SAT and random graph and hypergraph coloring, there are very good estimates
of the largest constraint density for which solutions exist. Yet, all known
polynomial-time algorithms for these problems fail to find solutions even at
much lower densities. To understand the origin of this gap we study how the
structure of the space of solutions evolves in such problems as constraints are
added. In particular, we prove that much before solutions disappear, they
organize into an exponential number of clusters, each of which is relatively
small and far apart from all other clusters. Moreover, inside each cluster most
variables are frozen, i.e., take only one value. The existence of such frozen
variables gives a satisfying intuitive explanation for the failure of the
polynomial-time algorithms analyzed so far. At the same time, our results
establish rigorously one of the two main hypotheses underlying Survey
Propagation, a heuristic introduced by physicists in recent years that appears
to perform extraordinarily well on random constraint satisfaction problems.


title: Capacity of a Class of Deterministic Relay Channels

abstract:
  The capacity of a class of deterministic relay channels with the transmitter
input X, the receiver output Y, the relay output Y_1 = f(X, Y), and a separate
communication link from the relay to the receiver with capacity R_0, is shown
to be
  C(R_0) = \max_{p(x)} \min \{I(X;Y)+R_0, I(X;Y, Y_1) \}.
  Thus every bit from the relay is worth exactly one bit to the receiver. Two
alternative coding schemes are presented that achieve this capacity. The first
scheme, ``hash-and-forward'', is based on a simple yet novel use of random
binning on the space of relay outputs, while the second scheme uses the usual
``compress-and-forward''. In fact, these two schemes can be combined together
to give a class of optimal coding schemes. As a corollary, this relay capacity
result confirms a conjecture by Ahlswede and Han on the capacity of a channel
with rate-limited state information at the decoder in the special case when the
channel state is recoverable from the channel input and the output.


title:
How Random is a Coin Toss? Bayesian Inference and the Symbolic Dynamics
  of Deterministic Chaos

abstract:
  Symbolic dynamics has proven to be an invaluable tool in analyzing the
mechanisms that lead to unpredictability and random behavior in nonlinear
dynamical systems. Surprisingly, a discrete partition of continuous state space
can produce a coarse-grained description of the behavior that accurately
describes the invariant properties of an underlying chaotic attractor. In
particular, measures of the rate of information production--the topological and
metric entropy rates--can be estimated from the outputs of Markov or generating
partitions. Here we develop Bayesian inference for k-th order Markov chains as
a method to finding generating partitions and estimating entropy rates from
finite samples of discretized data produced by coarse-grained dynamical
systems.


title:
A Low-Footprint Class Loading Mechanism for Embedded Java Virtual
  Machines

abstract:
  This paper shows that it is possible to dramatically reduce the memory
consumption of classes loaded in an embedded Java virtual machine without
reducing its functionalities. We describe how to pack the constant pool by
deleting entries which are only used during the class loading process. We
present some benchmarks which demonstrate the efficiency of this mechanism. We
finally suggest some additional optimizations which can be applied if some
restrictions to the functionalities of the virtual machine can be tolerated.


title:
Using Existing Network Simulators for Power-Aware Self-Organizing
  Wireless Sensor Network Protocols

abstract:
  In this document, we compare three existing simulation platforms (OPNET
Modeler, Network Simulator 2, Georgia Tech Sensor Network Simulator). Our
comparative study focuses on ease of use, scalability, ease of implementing
power consumption model and physical layer modeling accuracy, mainly.
Conclusions of this study are presented, and will help us decide which
simulating environment to use for evaluating power-aware self-organizing sensor
networks protocols.


title: Formalising Sylow's theorems in Coq

abstract:
  This report presents a formalisation of Sylow's theorems done in {\sc Coq}.
The formalisation has been done in a couple of weeks on top of Georges
Gonthier's {\sc ssreflect} \cite{ssreflect}. There were two ideas behind
formalising Sylow's theorems. The first one was to get familiar with Georges
way of doing proofs. The second one was to contribute to the collective effort
to formalise a large subset of group theory in {\sc Coq} with some non-trivial
proofs.}


title: Advances in Self Organising Maps

abstract:
  The Self-Organizing Map (SOM) with its related extensions is the most popular
artificial neural algorithm for use in unsupervised learning, clustering,
classification and data visualization. Over 5,000 publications have been
reported in the open literature, and many commercial projects employ the SOM as
a tool for solving hard real-world problems. Each two years, the "Workshop on
Self-Organizing Maps" (WSOM) covers the new developments in the field. The WSOM
series of conferences was initiated in 1997 by Prof. Teuvo Kohonen, and has
been successfully organized in 1997 and 1999 by the Helsinki University of
Technology, in 2001 by the University of Lincolnshire and Humberside, and in
2003 by the Kyushu Institute of Technology. The Universit\'{e} Paris I
Panth\'{e}on Sorbonne (SAMOS-MATISSE research centre) organized WSOM 2005 in
Paris on September 5-8, 2005.


title: Is the cyclic prefix necessary?

abstract:
  We show that one can do away with the cyclic prefix (CP) for SC-FDE and OFDM
at the cost of a moderate increase in the complexity of a DFT-based receiver.
Such an approach effectively deals with the decrease in the number of channel
uses due to the introduction of the CP. It is shown that the SINR for SC-FDE
remains the same asymptotically with the proposed receiver without CP as that
of the conventional receiver with CP. The results are shown for $N_t$ transmit
antennas and $N_r$ receive antennas where $N_r \geq N_t$.


title:
The effect of 'Open Access' upon citation impact: An analysis of ArXiv's
  Condensed Matter Section

abstract:
  This article statistically analyses how the citation impact of articles
deposited in the Condensed Matter section of the preprint server ArXiv (hosted
by Cornell University), and subsequently published in a scientific journal,
compares to that of articles in the same journal that were not deposited in
that archive. Its principal aim is to further illustrate and roughly estimate
the effect of two factors, 'early view' and 'quality bias', upon differences in
citation impact between these two sets of papers, using citation data from
Thomson Scientific's Web of Science. It presents estimates for a number of
journals in the field of condensed matter physics. In order to discriminate
between an 'open access' effect and an early view effect, longitudinal citation
data was analysed covering a time period as long as 7 years. Quality bias was
measured by calculating ArXiv citation impact differentials at the level of
individual authors publishing in a journal, taking into account co-authorship.
The analysis provided evidence of a strong quality bias and early view effect.
Correcting for these effects, there is in a sample of 6 condensed matter
physics journals studied in detail, no sign of a general 'open access
advantage' of papers deposited in ArXiv. The study does provide evidence that
ArXiv accelerates citation, due to the fact that that ArXiv makes papers
earlier available rather than that it makes papers freely available.


title: Multivariate Integral Perturbation Techniques - I (Theory)

abstract:
  We present a quasi-analytic perturbation expansion for multivariate
N-dimensional Gaussian integrals. The perturbation expansion is an infinite
series of lower-dimensional integrals (one-dimensional in the simplest
approximation). This perturbative idea can also be applied to multivariate
Student-t integrals. We evaluate the perturbation expansion explicitly through
2nd order, and discuss the convergence, including enhancement using Pade
approximants. Brief comments on potential applications in finance are given,
including options, models for credit risk and derivatives, and correlation
sensitivities.


title: A framework for compositional verification of security protocols

abstract:
  Automatic security protocol analysis is currently feasible only for small
protocols. Since larger protocols quite often are composed of many small
protocols, compositional analysis is an attractive, but non-trivial approach.
  We have developed a framework for compositional analysis of a large class of
security protocols. The framework is intended to facilitate automatic as well
as manual verification of large structured security protocols. Our approach is
to verify properties of component protocols in a multi-protocol environment,
then deduce properties about the composed protocol. To reduce the complexity of
multi-protocol verification, we introduce a notion of protocol independence and
prove a number of theorems that enable analysis of independent component
protocols in isolation.
  To illustrate the applicability of our framework to real-world protocols, we
study a key establishment sequence in WiMax consisting of three subprotocols.
Except for a small amount of trivial reasoning, the analysis is done using
automatic tools.


title: Characterizing Optimal Adword Auctions

abstract:
  We present a number of models for the adword auctions used for pricing
advertising slots on search engines such as Google, Yahoo! etc. We begin with a
general problem formulation which allows the privately known valuation per
click to be a function of both the identity of the advertiser and the slot. We
present a compact characterization of the set of all deterministic incentive
compatible direct mechanisms for this model. This new characterization allows
us to conclude that there are incentive compatible mechanisms for this auction
with a multi-dimensional type-space that are {\em not} affine maximizers. Next,
we discuss two interesting special cases: slot independent valuation and slot
independent valuation up to a privately known slot and zero thereafter. For
both of these special cases, we characterize revenue maximizing and efficiency
maximizing mechanisms and show that these mechanisms can be computed with a
worst case computational complexity $O(n^2m^2)$ and $O(n^2m^3)$ respectively,
where $n$ is number of bidders and $m$ is number of slots. Next, we
characterize optimal rank based allocation rules and propose a new mechanism
that we call the customized rank based allocation. We report the results of a
numerical study that compare the revenue and efficiency of the proposed
mechanisms. The numerical results suggest that customized rank-based allocation
rule is significantly superior to the rank-based allocation rules.


title: Distributed Link Scheduling with Constant Overhead

abstract:
  This paper proposes a new class of simple, distributed algorithms for
scheduling in wireless networks. The algorithms generate new schedules in a
distributed manner via simple local changes to existing schedules. The class is
parameterized by integers $k\geq 1$. We show that algorithm $k$ of our class
achieves $k/(k+2)$ of the capacity region, for every $k\geq 1$. The algorithms
have small and constant worst-case overheads: in particular, algorithm $k$
generates a new schedule using {\em (a)} time less than $4k+2$ round-trip times
between neighboring nodes in the network, and {\em (b)} at most three control
transmissions by any given node, for any $k$. The control signals are
explicitly specified, and face the same interference effects as normal data
transmissions. Our class of distributed wireless scheduling algorithms are the
first ones guaranteed to achieve any fixed fraction of the capacity region
while using small and constant overheads that do not scale with network size.
The parameter $k$ explicitly captures the tradeoff between control overhead and
scheduler throughput performance and provides a tuning knob protocol designers
can use to harness this trade-off in practice.


title:
On the security of new key exchange protocols based on the triple
  decomposition problem

abstract:
  We show that two new key exchange protocols with security based on the triple
DP may have security based on the MSCSP.


title: A modular eballot system - V0.6

abstract:
  We consider a reasonably simple voting system which can be implemented for
web-based ballots. Simplicity, modularity and the requirement of compatibility
with current web browsers leads to a system which satisfies a set of security
requirements for a ballot system which is not complete but sufficient in many
cases. Due to weak-eligibility and vote-selling, this system cannot be used for
political or similar ballots.


title: Implementing the modular eballot system V0.6

abstract:
  We describe a practical implementation of the modular eballot system proposed
in ref.[1]


title: Wikipedia: organisation from a bottom-up approach

abstract:
  Wikipedia can be considered as an extreme form of a self-managing team, as a
means of labour division. One could expect that this bottom-up approach, with
the absense of top-down organisational control, would lead to a chaos, but our
analysis shows that this is not the case. In the Dutch Wikipedia, an integrated
and coherent data structure is created, while at the same time users succeed in
distributing roles by self-selection. Some users focus on an area of expertise,
while others edit over the whole encyclopedic range. This constitutes our
conclusion that Wikipedia, in general, is a successful example of a
self-managing team.


title: Scaling Construction Grammar up to Production Systems: the SCIM

abstract:
  While a great effort has concerned the development of fully integrated
modular understanding systems, few researches have focused on the problem of
unifying existing linguistic formalisms with cognitive processing models. The
Situated Constructional Interpretation Model is one of these attempts. In this
model, the notion of "construction" has been adapted in order to be able to
mimic the behavior of Production Systems. The Construction Grammar approach
establishes a model of the relations between linguistic forms and meaning, by
the mean of constructions. The latter can be considered as pairings from a
topologically structured space to an unstructured space, in some way a special
kind of production rules.


title:
Hierarchical Cooperation Achieves Optimal Capacity Scaling in Ad Hoc
  Networks

abstract:
  n source and destination pairs randomly located in an area want to
communicate with each other. Signals transmitted from one user to another at
distance r apart are subject to a power loss of r^{-alpha}, as well as a random
phase. We identify the scaling laws of the information theoretic capacity of
the network. In the case of dense networks, where the area is fixed and the
density of nodes increasing, we show that the total capacity of the network
scales linearly with n. This improves on the best known achievability result of
n^{2/3} of Aeron and Saligrama, 2006. In the case of extended networks, where
the density of nodes is fixed and the area increasing linearly with n, we show
that this capacity scales as n^{2-alpha/2} for 2<alpha<3 and sqrt{n} for
alpha>3. The best known earlier result (Xie and Kumar 2006) identified the
scaling law for alpha > 4. Thus, much better scaling than multihop can be
achieved in dense networks, as well as in extended networks with low
attenuation. The performance gain is achieved by intelligent node cooperation
and distributed MIMO communication. The key ingredient is a hierarchical and
digital architecture for nodal exchange of information for realizing the
cooperation.


title: Capabilities Engineering: Constructing Change-Tolerant Systems

abstract:
  We propose a Capabilities-based approach for building long-lived, complex
systems that have lengthy development cycles. User needs and technology evolve
during these extended development periods, and thereby, inhibit a fixed
requirements-oriented solution specification. In effect, for complex emergent
systems, the traditional approach of baselining requirements results in an
unsatisfactory system. Therefore, we present an alternative approach,
Capabilities Engineering, which mathematically exploits the structural
semantics of the Function Decomposition graph - a representation of user needs
- to formulate Capabilities. For any given software system, the set of derived
Capabilities embodies change-tolerant characteristics. More specifically, each
individual Capability is a functional abstraction constructed to be highly
cohesive and to be minimally coupled with its neighbors. Moreover, the
Capability set is chosen to accommodate an incremental development approach,
and to reflect the constraints of technology feasibility and implementation
schedules. We discuss our validation activities to empirically prove that the
Capabilities-based approach results in change-tolerant systems.


title:
Reconciling Synthesis and Decomposition: A Composite Approach to
  Capability Identification

abstract:
  Stakeholders' expectations and technology constantly evolve during the
lengthy development cycles of a large-scale computer based system.
Consequently, the traditional approach of baselining requirements results in an
unsatisfactory system because it is ill-equipped to accommodate such change. In
contrast, systems constructed on the basis of Capabilities are more
change-tolerant; Capabilities are functional abstractions that are neither as
amorphous as user needs nor as rigid as system requirements. Alternatively,
Capabilities are aggregates that capture desired functionality from the users'
needs, and are designed to exhibit desirable software engineering
characteristics of high cohesion, low coupling and optimum abstraction levels.
To formulate these functional abstractions we develop and investigate two
algorithms for Capability identification: Synthesis and Decomposition. The
synthesis algorithm aggregates detailed rudimentary elements of the system to
form Capabilities. In contrast, the decomposition algorithm determines
Capabilities by recursively partitioning the overall mission of the system into
more detailed entities. Empirical analysis on a small computer based library
system reveals that neither approach is sufficient by itself. However, a
composite algorithm based on a complementary approach reconciling the two polar
perspectives results in a more feasible set of Capabilities. In particular, the
composite algorithm formulates Capabilities using the cohesion and coupling
measures as defined by the decomposition algorithm and the abstraction level as
determined by the synthesis algorithm.


title: Prefix Codes for Power Laws with Countable Support

abstract:
  In prefix coding over an infinite alphabet, methods that consider specific
distributions generally consider those that decline more quickly than a power
law (e.g., Golomb coding). Particular power-law distributions, however, model
many random variables encountered in practice. For such random variables,
compression performance is judged via estimates of expected bits per input
symbol. This correspondence introduces a family of prefix codes with an eye
towards near-optimal coding of known distributions. Compression performance is
precisely estimated for well-known probability distributions using these codes
and using previously known prefix codes. One application of these near-optimal
codes is an improved representation of rational numbers.


title:
On "P = NP: Linear Programming Formulation of the Traveling Salesman
  Problem": A reply to Hofman's Claim of a "Counter-Example"

abstract:
  We show that Hofman's claim of a "counter-example" to Diaby's LP formulation
of the TSP is invalid.


title:
Proportional Fairness in Multi-channel Multi-rate Wireless Networks-Part
  I: The Case of Deterministic Channels

abstract:
  This is Part I of a two-part paper series that studies the use of the
proportional fairness (PF) utility function as the basis for capacity
allocation and scheduling in multi-channel multi-rate wireless networks. The
contributions of Part I are threefold. (i) First, we lay down the theoretical
foundation for PF. Specifically, we present the fundamental properties and
physical/economic interpretation of PF. We show by general mathematical
arguments that PF leads to equal airtime allocation to users for the
single-channel case; and equal equivalent airtime allocation to users for the
multi-channel case, where the equivalent airtime enjoyed by a user is a
weighted sum of the airtimes enjoyed by the user on all channels, with the
weight of a channel being the price or value of that channel. We also establish
the Pareto efficiency of PF solutions. (ii) Second, we derive characteristics
of PF solutions that are useful for the construction of PF-optimization
algorithms. We present several PF-optimization algorithms, including a fast
algorithm that is amenable to parallel implementation. (iii) Third, we study
the use of PF utility for capacity allocation in large-scale WiFi networks
consisting of many adjacent wireless LANs. We find that the PF solution
simultaneously achieves higher system throughput, better fairness, and lower
outage probability with respect to the default solution given by today's 802.11
commercial products. Part II of this paper series extends our investigation to
the time-varying-channel case in which the data rates enjoyed by users over the
channels vary dynamically over time


title:
Proportional Fairness in Multi-channel Multi-rate Wireless Networks-Part
  II: The Case of Time-Varying Channels

abstract:
  This is Part II of a two-part paper series that studies the use of the
proportional fairness (PF) utility function as the basis for capacity
allocation and scheduling in multi-channel multi-rate wireless networks. The
contributions of Part II are twofold. (i) First, we extend the problem
formulation, theoretical results, and algorithms to the case of time-varying
channels, where opportunistic capacity allocation and scheduling can be
exploited to improve system performance. We lay down the theoretical foundation
for optimization that "couples" the time-varying characteristic of channels
with the requirements of the underlying applications into one consideration. In
particular, the extent to which opportunistic optimization is possible is not
just a function of how fast the channel characteristics vary, but also a
function of the elasticity of the underlying applications for delayed capacity
allocation. (ii) Second, building upon our theoretical framework and results,
we study subcarrier allocation and scheduling in orthogonal frequency division
multiplexing (OFDM) cellular wireless networks. We introduce the concept of a
W-normalized Doppler frequency to capture the extent to which opportunistic
scheduling can be exploited to achieve throughput-fairness performance gain. We
show that a "look-back PF" scheduling can strike a good balance between system
throughput and fairness while taking the underlying application requirements
into account.


title: Evolutionary Optimization in an Algorithmic Setting

abstract:
  Evolutionary processes proved very useful for solving optimization problems.
In this work, we build a formalization of the notion of cooperation and
competition of multiple systems working toward a common optimization goal of
the population using evolutionary computation techniques. It is justified that
evolutionary algorithms are more expressive than conventional recursive
algorithms. Three subclasses of evolutionary algorithms are proposed here:
bounded finite, unbounded finite and infinite types. Some results on
completeness, optimality and search decidability for the above classes are
presented. A natural extension of Evolutionary Turing Machine model developed
in this paper allows one to mathematically represent and study properties of
cooperation and competition in a population of optimized species.


title:
Safety Evaluation of Critical Applications Distributed on TDMA-Based
  Networks

abstract:
  Critical embedded systems have to provide a high level of dependability. In
automotive domain, for example, TDMA protocols are largely recommended because
of their deterministic behavior. Nevertheless, under the transient
environmental perturbations, the loss of communication cycles may occur with a
certain probability and, consequently, the system may fail. This paper analyzes
the impact of the transient perturbations (especially due to Electromagnetic
Interferences) on the dependability of systems distributed on TDMA-based
networks. The dependability of such system is modeled as that of
"consecutive-k-out-of-n:F" systems and we provide a efficient way for its
evaluation.


title: Managing network congestion with a Kohonen-based RED queue

abstract:
  The behaviour of the TCP AIMD algorithm is known to cause queue length
oscillations when congestion occurs at a router output link. Indeed, due to
these queueing variations, end-to-end applications experience large delay
jitter. Many studies have proposed efficient Active Queue Management (AQM)
mechanisms in order to reduce queue oscillations and stabilize the queue
length. These AQM are mostly improvements of the Random Early Detection (RED)
model. Unfortunately, these enhancements do not react in a similar manner for
various network conditions and are strongly sensitive to their initial setting
parameters. Although this paper proposes a solution to overcome the
difficulties of setting these parameters by using a Kohonen neural network
model, another goal of this study is to investigate whether cognitive
intelligence could be placed in the core network to solve such stability
problem. In our context, we use results from the neural network area to
demonstrate that our proposal, named Kohonen-RED (KRED), enables a stable queue
length without complex parameters setting and passive measurements.


title:
A Multi-server Scheduling Framework for Resource Allocation in Wireless
  Multi-carrier Networks

abstract:
  Multiuser resource allocation has recently been recognized as an effective
methodology for enhancing the power and spectrum efficiency in OFDM (orthogonal
frequency division multiplexing) systems. It is, however, not directly
applicable to current packet-switched networks, because (i) most existing
packet-scheduling schemes are based on a single-server model and do not serve
multiple users at the same time; and (ii) the conventional separate design of
MAC (medium access control) packet scheduling and PHY (physical) resource
allocation yields inefficient resource utilization. In this paper, we propose a
cross-layer resource allocation algorithm based on a novel multi-server
scheduling framework to achieve overall high system power efficiency in
packet-switched OFDM networks. Our contribution is four fold: (i) we propose
and analyze a MPGPS (multi-server packetized general processor sharing) service
discipline that serves multiple users at the same time and facilitates
multiuser resource allocation; (ii) we present a MPGPS-based joint MAC-PHY
resource allocation scheme that incorporates packet scheduling, subcarrier
allocation, and power allocation in an integrated framework; (iii) by
investigating the fundamental tradeoff between multiuser-diversity and queueing
performance, we present an A-MPGPS (adaptive MPGPS) service discipline that
strikes balance between power efficiency and queueing performance; and (iv) we
extend MPGPS to an O-MPGPS (opportunistic MPGPS) service discipline to further
enhance the resource utilization efficiency.


title:
The Importance of the Algorithmic Information Theory to Construct a
  Possible Example Where NP # P - II: An Irreducible Sentence

abstract:
  In this short communication it is discussed the relation between disentangled
states and algorithmic information theory aiming to construct an irreducible
sentence whose length increases in a non-polynomial way when the number of
qubits increases.


title: The Computational Complexity of the Traveling Salesman Problem

abstract:
  In this note, we show that the Traveling Salesman Problem cannot be solved in
polynomial-time on a classical computer.


title:
Environment of development of the programs of parametric creating of the
  drawings in CAD-system of renovation of the enterprises

abstract:
  The main ideas, data structures, structure and realization of operations with
them in environment of development of the programs of parametric creating of
the drawings are considered for the needs of the automated design engineering
system of renovation of the enterprises. The example of such program and
example of application of this environment for creating the drawing of the base
for equipment in CAD-system TechnoCAD GlassX are presented


title: Large Scale In Silico Screening on Grid Infrastructures

abstract:
  Large-scale grid infrastructures for in silico drug discovery open
opportunities of particular interest to neglected and emerging diseases. In
2005 and 2006, we have been able to deploy large scale in silico docking within
the framework of the WISDOM initiative against Malaria and Avian Flu requiring
about 105 years of CPU on the EGEE, Auvergrid and TWGrid infrastructures. These
achievements demonstrated the relevance of large-scale grid infrastructures for
the virtual screening by molecular docking. This also allowed evaluating the
performances of the grid infrastructures and to identify specific issues raised
by large-scale deployment.


title:
Fuzzy Logic Classification of Imaging Laser Desorption Fourier Transform
  Mass Spectrometry Data

abstract:
  A fuzzy logic based classification engine has been developed for classifying
mass spectra obtained with an imaging internal source Fourier transform mass
spectrometer (I^2LD-FTMS). Traditionally, an operator uses the relative
abundance of ions with specific mass-to-charge (m/z) ratios to categorize
spectra. An operator does this by comparing the spectrum of m/z versus
abundance of an unknown sample against a library of spectra from known samples.
Automated positioning and acquisition allow I^2LD-FTMS to acquire data from
very large grids, this would require classification of up to 3600 spectrum per
hour to keep pace with the acquisition. The tedious job of classifying numerous
spectra generated in an I^2LD-FTMS imaging application can be replaced by a
fuzzy rule base if the cues an operator uses can be encapsulated. We present
the translation of linguistic rules to a fuzzy classifier for mineral phases in
basalt. This paper also describes a method for gathering statistics on ions,
which are not currently used in the rule base, but which may be candidates for
making the rule base more accurate and complete or to form new rule bases based
on data obtained from known samples. A spatial method for classifying spectra
with low membership values, based on neighboring sample classifications, is
also presented.


title: Reliable Multi-Path Routing Schemes for Real-Time Streaming

abstract:
  In off-line streaming, packet level erasure resilient Forward Error
Correction (FEC) codes rely on the unrestricted buffering time at the receiver.
In real-time streaming, the extremely short playback buffering time makes FEC
inefficient for protecting a single path communication against long link
failures. It has been shown that one alternative path added to a single path
route makes packet level FEC applicable even when the buffering time is
limited. Further path diversity, however, increases the number of underlying
links increasing the total link failure rate, requiring from the sender
possibly more FEC packets. We introduce a scalar coefficient for rating a
multi-path routing topology of any complexity. It is called Redundancy Overall
Requirement (ROR) and is proportional to the total number of adaptive FEC
packets required for protection of the communication. With the capillary
routing algorithm, introduced in this paper we build thousands of multi-path
routing patterns. By computing their ROR coefficients, we show that contrary to
the expectations the overall requirement in FEC codes is reduced when the
further diversity of dual-path routing is achieved by the capillary routing
algorithm.


title:
A Combined LIFO-Priority Scheme for Overload Control of E-commerce Web
  Servers

abstract:
  E-commerce Web-servers often face overload conditions during which
revenue-generating requests may be dropped or abandoned due to an increase in
the browsing requests. In this paper we present a simple, yet effective,
mechanism for overload control of E-commerce Web-servers. We develop an
E-commerce workload model that separates the browsing requests from
revenue-generating transaction requests. During overload, we apply LIFO
discipline in the browsing queues and use a dynamic priority model to service
them. The transaction queues are given absolute priority over the browsing
queues. This is called the LIFO-Pri scheduling discipline. Experimental results
show that LIFO-Pri dramatically improves the overall Web-server throughput
while also increasing the completion rate of revenue-generating requests. The
Web-server was able to operate at nearly 60% of its maximum capacity even when
offered load was 1.5 times its capacity. Further, when compared to a single
queue FIFO system, there was a seven-fold increase in the number of completed
revenue-generating requests during overload.


title: T-Theory Applications to Online Algorithms for the Server Problem

abstract:
  Although largely unnoticed by the online algorithms community, T-theory, a
field of discrete mathematics, has contributed to the development of several
online algorithms for the k-server problem. A brief summary of the k-server
problem, and some important application concepts of T-theory, are given.
Additionally, a number of known k-server results are restated using the
established terminology of T-theory. Lastly, a previously unpublished
3-competitiveness proof, using T-theory, for the Harmonic algorithm for two
servers is presented.


title:
The Extraction and Complexity Limits of Graphical Models for Linear
  Codes

abstract:
  Two broad classes of graphical modeling problems for codes can be identified
in the literature: constructive and extractive problems. The former class of
problems concern the construction of a graphical model in order to define a new
code. The latter class of problems concern the extraction of a graphical model
for a (fixed) given code. The design of a new low-density parity-check code for
some given criteria (e.g. target block length and code rate) is an example of a
constructive problem. The determination of a graphical model for a classical
linear block code which implies a decoding algorithm with desired performance
and complexity characteristics is an example of an extractive problem. This
work focuses on extractive graphical model problems and aims to lay out some of
the foundations of the theory of such problems for linear codes.
  The primary focus of this work is a study of the space of all graphical
models for a (fixed) given code. The tradeoff between cyclic topology and
complexity in this space is characterized via the introduction of a new bound:
the tree-inducing cut-set bound. The proposed bound provides a more precise
characterization of this tradeoff than that which can be obtained using
existing tools (e.g. the Cut-Set Bound) and can be viewed as a generalization
of the square-root bound for tail-biting trellises to graphical models with
arbitrary cyclic topologies. Searching the space of graphical models for a
given code is then enabled by introducing a set of basic graphical model
transformation operations which are shown to span this space. Finally,
heuristics for extracting novel graphical models for linear block codes using
these transformations are investigated.


title:
Algebraic Soft-Decision Decoding of Reed-Solomon Codes Using Bit-level
  Soft Information

abstract:
  The performance of algebraic soft-decision decoding of Reed-Solomon codes
using bit-level soft information is investigated. Optimal multiplicity
assignment strategies of algebraic soft-decision decoding with infinite cost
are first studied over erasure channels and the binary symmetric channel. The
corresponding decoding radii are calculated in closed forms and tight bounds on
the error probability are derived. The multiplicity assignment strategy and the
corresponding performance analysis are then generalized to characterize the
decoding region of algebraic softdecision decoding over a mixed error and
bit-level erasure channel. The bit-level decoding region of the proposed
multiplicity assignment strategy is shown to be significantly larger than that
of conventional Berlekamp-Massey decoding. As an application, a bit-level
generalized minimum distance decoding algorithm is proposed. The proposed
decoding compares favorably with many other Reed-Solomon soft-decision decoding
algorithms over various channels. Moreover, owing to the simplicity of the
proposed bit-level generalized minimum distance decoding, its performance can
be tightly bounded using order statistics.


title:
Lossy Bulk Synchronous Parallel Processing Model for Very Large Scale
  Grids

abstract:
  The performance of a parallel algorithm in a very large scale grid is
significantly influenced by the underlying Internet protocols and
inter-connectivity. Many grid programming platforms use TCP due to its
reliability, usually with some optimizations to reduce its costs. However, TCP
does not perform well in a high bandwidth and high delay network environment.
On the other hand, UDP is the fastest protocol available because it omits
connection setup process, acknowledgments and retransmissions sacrificing
reliable transfer. Many new bulk data transfer schemes using UDP for data
transmission such as RBUDP, Tsunami, and SABUL have been introduced and shown
to have better performance compared to TCP. In this paper, we consider the use
of UDP and examine the relationship between packet loss and speedup with
respect to the number of grid nodes. Our measurement suggests that packet loss
rates between 5%-15% on average are not uncommon between PlanetLab nodes that
are widely distributed over the Internet. We show that transmitting multiple
copies of same packet produces higher speedup. We show the minimum number of
packet duplication required to maximize the possible speedup for a given number
of nodes using a BSP based model. Our work demonstrates that by using an
appropriate number of packet copies, we can increase performance of parallel
program.


title: Design approaches in technology enhanced learning

abstract:
  Design is a critical to the successful development of any interactive
learning environment (ILE). Moreover, in technology enhanced learning (TEL),
the design process requires input from many diverse areas of expertise. As
such, anyone undertaking tool development is required to directly address the
design challenge from multiple perspectives. We provide a motivation and
rationale for design approaches for learning technologies that draws upon
Simon's seminal proposition of Design Science (Simon, 1969). We then review the
application of Design Experiments (Brown, 1992) and Design Patterns (Alexander
et al., 1977) and argue that a patterns approach has the potential to address
many of the critical challenges faced by learning technologists.


title: Effectiveness of Garbage Collection in MIT/GNU Scheme

abstract:
  Scheme uses garbage collection for heap memory management. Ideally, garbage
collectors should be able to reclaim all dead objects, i.e. objects that will
not be used in future. However, garbage collectors collect only those dead
objects that are not reachable from any program variable. Dead objects that are
reachable from program variables are not reclaimed.
  In this paper we describe our experiments to measure the effectiveness of
garbage collection in MIT/GNU Scheme. We compute the drag time of objects, i.e.
the time for which an object remains in heap memory after its last use. The
number of dead objects and the drag time together indicate opportunities for
improving garbage collection. Our experiments reveal that up to 26% of dead
objects remain in memory. The average drag time is up to 37% of execution time.
Overall, we observe memory saving potential ranging from 9% to 65%.


title: Reducing Order Enforcement Cost in Complex Query Plans

abstract:
  Algorithms that exploit sort orders are widely used to implement joins,
grouping, duplicate elimination and other set operations. Query optimizers
traditionally deal with sort orders by using the notion of interesting orders.
The number of interesting orders is unfortunately factorial in the number of
participating attributes. Optimizer implementations use heuristics to prune the
number of interesting orders, but the quality of the heuristics is unclear.
Increasingly complex decision support queries and increasing use of covering
indices, which provide multiple alternative sort orders for relations, motivate
us to better address the problem of optimization with interesting orders.
  We show that even a simplified version of optimization with sort orders is
NP-hard and provide principled heuristics for choosing interesting orders. We
have implemented the proposed techniques in a Volcano-style cost-based
optimizer, and our performance study shows significant improvements in
estimated cost. We also executed our plans on a widely used commercial database
system, and on PostgreSQL, and found that actual execution times for our plans
were significantly better than for plans generated by those systems in several
cases.


title:
Dense Gaussian Sensor Networks: Minimum Achievable Distortion and the
  Order Optimality of Separation

abstract:
  We investigate the optimal performance of dense sensor networks by studying
the joint source-channel coding problem. The overall goal of the sensor network
is to take measurements from an underlying random process, code and transmit
those measurement samples to a collector node in a cooperative multiple access
channel with potential feedback, and reconstruct the entire random process at
the collector node. We provide lower and upper bounds for the minimum
achievable expected distortion when the underlying random process is Gaussian.
When the Gaussian random process satisfies some general conditions, we evaluate
the lower and upper bounds explicitly, and show that they are of the same order
for a wide range of power constraints. Thus, for these random processes, under
these power constraints, we express the minimum achievable expected distortion
as a function of the power constraint. Further, we show that the achievability
scheme that achieves the lower bound on the distortion is a separation-based
scheme that is composed of multi-terminal rate-distortion coding and
amplify-and-forward channel coding. Therefore, we conclude that separation is
order-optimal for the dense Gaussian sensor network scenario under
consideration, when the underlying random process satisfies some general
conditions.


title:
On the Rate Distortion Function of Certain Sources with a Proportional
  Mean-Square Error Distortion Measure

abstract:
  New bounds on the rate distortion function of certain non-Gaussian sources,
with a proportional-weighted mean-square error (MSE) distortion measure, are
given. The growth, g, of the rate distortion function, as a result of changing
from a non-weighted MSE distortion measure to a proportional-weighted
distortion criterion is analyzed. It is shown that for a small distortion, d,
the growth, g, and the difference between the rate distortion functions of a
Gaussian memoryless source and a source with memory, both with the same
marginal statistics and MSE distortion measure, share the same lower bound.
Several examples and applications are also given.


title:
Conditionally Cycle-Free Generalized Tanner Graphs: Theory and
  Application to High-Rate Serially Concatenated Codes

abstract:
  Generalized Tanner graphs have been implicitly studied by a number of authors
under the rubric of generalized parity-check matrices. This work considers the
conditioning of binary hidden variables in such models in order to break all
cycles and thus derive optimal soft-in soft-out (SISO) decoding algorithms.
Conditionally cycle-free generalized Tanner graphs are shown to imply optimal
SISO decoding algorithms for the first order Reed-Muller codes and their duals
- the extended Hamming codes - which are substantially less complex than
conventional bit-level trellis decoding. The study of low-complexity optimal
SISO decoding algorithms for the family of extended Hamming codes is
practically motivated. Specifically, it is shown that exended Hamming codes
offer an attractive alternative to high-rate convolutional codes in terms of
both performance and complexity for use in very high-rate, very low-floor,
serially concatenated coding schemes.


title:
Analysis of an Efficient Distributed Algorithm for Mutual Exclusion
  (Average-Case Analysis of Path Reversal)

abstract:
  The algorithm analysed by Na\"{i}mi, Trehe and Arnold was the very first
distributed algorithm to solve the mutual exclusion problem in complete
networks by using a dynamic logical tree structure as its basic distributed
data structure, viz. a path reversal transformation in rooted n-node trees;
besides, it was also the first one to achieve a logarithmic average-case
message complexity. The present paper proposes a direct and general approach to
compute the moments of the cost of path reversal. It basically uses one-one
correspondences between combinatorial structures and the associated probability
generating functions: the expected cost of path reversal is thus proved to be
exactly $H_{n-1}$. Moreover, time and message complexity of the algorithm as
well as randomized bounds on its worst-case message complexity in arbitrary
networks are also given. The average-case analysis of path reversal and the
analysis of this distributed algorithm for mutual exclusion are thus fully
completed in the paper. The general techniques used should also prove available
and fruitful when adapted to the most efficient recent tree-based distributed
algorithms for mutual exclusion which require powerful tools, particularly for
average-case analyses.


title: On the space complexity of one-pass compression

abstract:
  We study how much memory one-pass compression algorithms need to compete with
the best multi-pass algorithms. We call a one-pass algorithm an (f (n,
\ell))-footprint compressor if, given $n$, $\ell$ and an $n$-ary string $S$, it
stores $S$ in ((\rule{0ex}{2ex} O (H_\ell (S)) + o (\log n)) |S| + O (n^{\ell +
1} \log n)) bits -- where (H_\ell (S)) is the $\ell$th-order empirical entropy
of $S$ -- while using at most (f (n, \ell)) bits of memory. We prove that, for
any (\epsilon > 0) and some (f (n, \ell) \in O (n^{\ell + \epsilon} \log n)),
there is an (f (n, \ell))-footprint compressor; on the other hand, there is no
(f (n, \ell))-footprint compressor for (f (n, \ell) \in o (n^\ell \log n)).


title: Model Theory of Ultrafinitism I: Fuzzy Initial Segments of Arithmetics

abstract:
  This article is the first of an intended series of works on the model theory
of Ultrafinitism. It is roughly divided into two parts. The first one addresses
some of the issues related to ultrafinitistic programs, as well as some of the
core ideas proposed thus far. The second part of the paper presents a model of
ultrafinitistic arithmetics based on the notion of fuzzy initial segments of
the standard natural numbers series. We also introduce a proof theory and a
semantics for ultrafinitism through which feasibly consistent theories can be
treated on the same footing as their classically consistent counterparts. We
conclude with a brief sketch of a foundational program, that aims at
reproducing the transfinite within the finite realm.


title: Fourier meets M\"{o}bius: fast subset convolution

abstract:
  We present a fast algorithm for the subset convolution problem: given
functions f and g defined on the lattice of subsets of an n-element set N,
compute their subset convolution f*g, defined for all S\subseteq N by (f *
g)(S) = \sum_{T \subseteq S}f(T) g(S\setminus T), where addition and
multiplication is carried out in an arbitrary ring. Via M\"{o}bius transform
and inversion, our algorithm evaluates the subset convolution in O(n^2 2^n)
additions and multiplications, substantially improving upon the straightforward
O(3^n) algorithm. Specifically, if the input functions have an integer range
{-M,-M+1,...,M}, their subset convolution over the ordinary sum-product ring
can be computed in O^*(2^n log M) time; the notation O^* suppresses
polylogarithmic factors. Furthermore, using a standard embedding technique we
can compute the subset convolution over the max-sum or min-sum semiring in
O^*(2^n M) time. To demonstrate the applicability of fast subset convolution,
we present the first O^*(2^k n^2 + n m) algorithm for the minimum Steiner tree
problem in graphs with n vertices, k terminals, and m edges with bounded
integer weights, improving upon the O^*(3^k n + 2^k n^2 + n m) time bound of
the classical Dreyfus-Wagner algorithm. We also discuss extensions to recent
O^*(2^n)-time algorithms for covering and partitioning problems (Bj\"{o}rklund
and Husfeldt, FOCS 2006; Koivisto, FOCS 2006).


title: Extending the Trusted Path in Client-Server Interaction

abstract:
  We present a method to secure the complete path between a server and the
local human user at a network node. This is useful for scenarios like internet
banking, electronic signatures, or online voting. Protection of input
authenticity and output integrity and authenticity is accomplished by a
combination of traditional and novel technologies, e.g., SSL, ActiveX, and
DirectX. Our approach does not require administrative privileges to deploy and
is hence suitable for consumer applications. Results are based on the
implementation of a proof-of-concept application for the Windows platform.


title:
Barriers and local minima in energy landscapes of stochastic local
  search

abstract:
  A local search algorithm operating on an instance of a Boolean constraint
satisfaction problem (in particular, k-SAT) can be viewed as a stochastic
process traversing successive adjacent states in an ``energy landscape''
defined by the problem instance on the n-dimensional Boolean hypercube. We
investigate analytically the worst-case topography of such landscapes in the
context of satisfiable k-SAT via a random ensemble of satisfiable ``k-regular''
linear equations modulo 2.
  We show that for each fixed k=3,4,..., the typical k-SAT energy landscape
induced by an instance drawn from the ensemble has a set of 2^{\Omega(n)} local
energy minima, each separated by an unconditional \Omega(n) energy barrier from
each of the O(1) ground states, that is, solution states with zero energy. The
main technical aspect of the analysis is that a random k-regular 0/1 matrix
constitutes a strong boundary expander with almost full GF(2)-linear rank, a
property which also enables us to prove a 2^{\Omega(n)} lower bound for the
expected number of steps required by the focused random walk heuristic to solve
typical instances drawn from the ensemble. These results paint a grim picture
of the worst-case topography of k-SAT for local search, and constitute
apparently the first rigorous analysis of the growth of energy barriers in a
random ensemble of k-SAT landscapes as the number of variables n is increased.


title:
Learning and discrimination through STDP in a top-down modulated
  associative memory

abstract:
  This article underlines the learning and discrimination capabilities of a
model of associative memory based on artificial networks of spiking neurons.
Inspired from neuropsychology and neurobiology, the model implements top-down
modulations, as in neocortical layer V pyramidal neurons, with a learning rule
based on synaptic plasticity (STDP), for performing a multimodal association
learning task. A temporal correlation method of analysis proves the ability of
the model to associate specific activity patterns to different samples of
stimulation. Even in the absence of initial learning and with continuously
varying weights, the activity patterns become stable enough for discrimination.


title: Clustering and Sharing Incentives in BitTorrent Systems

abstract:
  Peer-to-peer protocols play an increasingly instrumental role in Internet
content distribution. Consequently, it is important to gain a full
understanding of how these protocols behave in practice and how their
parameters impact overall performance. We present the first experimental
investigation of the peer selection strategy of the popular BitTorrent protocol
in an instrumented private torrent. By observing the decisions of more than 40
nodes, we validate three BitTorrent properties that, though widely believed to
hold, have not been demonstrated experimentally. These include the clustering
of similar-bandwidth peers, the effectiveness of BitTorrent's sharing
incentives, and the peers' high average upload utilization. In addition, our
results show that BitTorrent's new choking algorithm in seed state provides
uniform service to all peers, and that an underprovisioned initial seed leads
to the absence of peer clustering and less effective sharing incentives. Based
on our observations, we provide guidelines for seed provisioning by content
providers, and discuss a tracker protocol extension that addresses an
identified limitation of the protocol.


title:
Mixing and non-mixing local minima of the entropy contrast for blind
  source separation

abstract:
  In this paper, both non-mixing and mixing local minima of the entropy are
analyzed from the viewpoint of blind source separation (BSS); they correspond
respectively to acceptable and spurious solutions of the BSS problem. The
contribution of this work is twofold. First, a Taylor development is used to
show that the \textit{exact} output entropy cost function has a non-mixing
minimum when this output is proportional to \textit{any} of the non-Gaussian
sources, and not only when the output is proportional to the lowest entropic
source. Second, in order to prove that mixing entropy minima exist when the
source densities are strongly multimodal, an entropy approximator is proposed.
The latter has the major advantage that an error bound can be provided. Even if
this approximator (and the associated bound) is used here in the BSS context,
it can be applied for estimating the entropy of any random variable with
multimodal density.


title: Rectangular Layouts and Contact Graphs

abstract:
  Contact graphs of isothetic rectangles unify many concepts from applications
including VLSI and architectural design, computational geometry, and GIS.
Minimizing the area of their corresponding {\em rectangular layouts} is a key
problem. We study the area-optimization problem and show that it is NP-hard to
find a minimum-area rectangular layout of a given contact graph. We present
O(n)-time algorithms that construct $O(n^2)$-area rectangular layouts for
general contact graphs and $O(n\log n)$-area rectangular layouts for trees.
(For trees, this is an $O(\log n)$-approximation algorithm.) We also present an
infinite family of graphs (rsp., trees) that require $\Omega(n^2)$ (rsp.,
$\Omega(n\log n)$) area.
  We derive these results by presenting a new characterization of graphs that
admit rectangular layouts using the related concept of {\em rectangular duals}.
A corollary to our results relates the class of graphs that admit rectangular
layouts to {\em rectangle of influence drawings}.


title: On the Complexity of Processing Massive, Unordered, Distributed Data

abstract:
  An existing approach for dealing with massive data sets is to stream over the
input in few passes and perform computations with sublinear resources. This
method does not work for truly massive data where even making a single pass
over the data with a processor is prohibitive. Successful log processing
systems in practice such as Google's MapReduce and Apache's Hadoop use multiple
machines. They efficiently perform a certain class of highly distributable
computations defined by local computations that can be applied in any order to
the input.
  Motivated by the success of these systems, we introduce a simple algorithmic
model for massive, unordered, distributed (mud) computation. We initiate the
study of understanding its computational complexity. Our main result is a
positive one: any unordered function that can be computed by a streaming
algorithm can also be computed with a mud algorithm, with comparable space and
communication complexity. We extend this result to some useful classes of
approximate and randomized streaming algorithms. We also give negative results,
using communication complexity arguments to prove that extensions to private
randomness, promise problems and indeterminate functions are impossible.
  We believe that the line of research we introduce in this paper has the
potential for tremendous impact. The distributed systems that motivate our work
successfully process data at an unprecedented scale, distributed over hundreds
or even thousands of machines, and perform hundreds of such analyses each day.
The mud model (and its generalizations) inspire a set of complexity-theoretic
questions that lie at their heart.


title: An approach to RAID-6 based on cyclic groups of a prime order

abstract:
  As the size of data storing arrays of disks grows, it becomes vital to
protect data against double disk failures. A popular method of protection is
via the Reed-Solomon (RS) code with two parity words. In the present paper we
construct alternative examples of linear block codes protecting against two
erasures. Our construction is based on an abstract notion of cone. Concrete
cones are constructed via matrix representations of cyclic groups of prime
order. In particular, this construction produces EVENODD code. Interesting
conditions on the prime number arise in our analysis of these codes. At the
end, we analyse an assembly implementation of the corresponding system on a
general purpose processor and compare its write and recovery speed with the
standard DP-RAID system.


title:
The Implications of Network-Centric Software Systems on Software
  Architecture: A Critical Evaluation

abstract:
  The purpose of this paper is to evaluate the impact of emerging
network-centric software systems on the field of software architecture. We
first develop an insight concerning the term "network-centric" by presenting
its origin and its implications within the context of software architecture. On
the basis of this insight, we present our definition of a network-centric
framework and its distinguishing characteristics. We then enumerate the
challenges that face the field of software architecture as software development
shifts from a platform-centric to a network-centric model. In order to face
these challenges, we propose a formal approach embodied in a new architectural
style that supports overcoming these challenges at the architectural level.
Finally, we conclude by presenting an illustrative example to demonstrate the
usefulness of the concepts of network centricity, summarizing our
contributions, and linking our approach to future work that needs to be done in
this area.


title: Distributed Control of Microscopic Robots in Biomedical Applications

abstract:
  Current developments in molecular electronics, motors and chemical sensors
could enable constructing large numbers of devices able to sense, compute and
act in micron-scale environments. Such microscopic machines, of sizes
comparable to bacteria, could simultaneously monitor entire populations of
cells individually in vivo. This paper reviews plausible capabilities for
microscopic robots and the physical constraints due to operation in fluids at
low Reynolds number, diffusion-limited sensing and thermal noise from Brownian
motion. Simple distributed controls are then presented in the context of
prototypical biomedical tasks, which require control decisions on millisecond
time scales. The resulting behaviors illustrate trade-offs among speed,
accuracy and resource use. A specific example is monitoring for patterns of
chemicals in a flowing fluid released at chemically distinctive sites.
Information collected from a large number of such devices allows estimating
properties of cell-sized chemical sources in a macroscopic volume. The
microscopic devices moving with the fluid flow in small blood vessels can
detect chemicals released by tissues in response to localized injury or
infection. We find the devices can readily discriminate a single cell-sized
chemical source from the background chemical concentration, providing
high-resolution sensing in both time and space. By contrast, such a source
would be difficult to distinguish from background when diluted throughout the
blood volume as obtained with a blood sample.


title: Channel Coding: The Road to Channel Capacity

abstract:
  Starting from Shannon's celebrated 1948 channel coding theorem, we trace the
evolution of channel coding from Hamming codes to capacity-approaching codes.
We focus on the contributions that have led to the most significant
improvements in performance vs. complexity for practical applications,
particularly on the additive white Gaussian noise (AWGN) channel. We discuss
algebraic block codes, and why they did not prove to be the way to get to the
Shannon limit. We trace the antecedents of today's capacity-approaching codes:
convolutional codes, concatenated codes, and other probabilistic coding
schemes. Finally, we sketch some of the practical applications of these codes.


title:
An Anthological Review of Research Utilizing MontyLingua, a Python-Based
  End-to-End Text Processor

abstract:
  MontyLingua, an integral part of ConceptNet which is currently the largest
commonsense knowledge base, is an English text processor developed using Python
programming language in MIT Media Lab. The main feature of MontyLingua is the
coverage for all aspects of English text processing from raw input text to
semantic meanings and summary generation, yet each component in MontyLingua is
loosely-coupled to each other at the architectural and code level, which
enabled individual components to be used independently or substituted. However,
there has been no review exploring the role of MontyLingua in recent research
work utilizing it. This paper aims to review the use of and roles played by
MontyLingua and its components in research work published in 19 articles
between October 2004 and August 2006. We had observed a diversified use of
MontyLingua in many different areas, both generic and domain-specific. Although
the use of text summarizing component had not been observe, we are optimistic
that it will have a crucial role in managing the current trend of information
overload in future research.


title:
Very Sparse Stable Random Projections, Estimators and Tail Bounds for
  Stable Random Projections

abstract:
  This paper will focus on three different aspects in improving the current
practice of stable random projections.
  Firstly, we propose {\em very sparse stable random projections} to
significantly reduce the processing and storage cost, by replacing the
$\alpha$-stable distribution with a mixture of a symmetric $\alpha$-Pareto
distribution (with probability $\beta$, $0<\beta\leq1$) and a point mass at the
origin (with a probability $1-\beta$). This leads to a significant
$\frac{1}{\beta}$-fold speedup for small $\beta$.
  Secondly, we provide an improved estimator for recovering the original
$l_\alpha$ norms from the projected data. The standard estimator is based on
the (absolute) sample median, while we suggest using the geometric mean. The
geometric mean estimator we propose is strictly unbiased and is easier to
study. Moreover, the geometric mean estimator is more accurate, especially
non-asymptotically.
  Thirdly, we provide an adequate answer to the basic question of how many
projections (samples) are needed for achieving some pre-specified level of
accuracy. \cite{Proc:Indyk_FOCS00,Article:Indyk_TKDE03} did not provide a
criterion that can be used in practice. The geometric mean estimator we propose
allows us to derive sharp tail bounds which can be expressed in exponential
forms with constants explicitly given.


title:
A higher-order active contour model of a `gas of circles' and its
  application to tree crown extraction

abstract:
  Many image processing problems involve identifying the region in the image
domain occupied by a given entity in the scene. Automatic solution of these
problems requires models that incorporate significant prior knowledge about the
shape of the region. Many methods for including such knowledge run into
difficulties when the topology of the region is unknown a priori, for example
when the entity is composed of an unknown number of similar objects.
Higher-order active contours (HOACs) represent one method for the modelling of
non-trivial prior knowledge about shape without necessarily constraining region
topology, via the inclusion of non-local interactions between region boundary
points in the energy defining the model. The case of an unknown number of
circular objects arises in a number of domains, e.g. medical, biological,
nanotechnological, and remote sensing imagery. Regions composed of an a priori
unknown number of circles may be referred to as a `gas of circles'. In this
report, we present a HOAC model of a `gas of circles'. In order to guarantee
stable circles, we conduct a stability analysis via a functional Taylor
expansion of the HOAC energy around a circular shape. This analysis fixes one
of the model parameters in terms of the others and constrains the rest. In
conjunction with a suitable likelihood energy, we apply the model to the
extraction of tree crowns from aerial imagery, and show that the new model
outperforms other techniques.


title: Discovering Network Topology in the Presence of Byzantine Faults

abstract:
  We study the problem of Byzantine-robust topology discovery in an arbitrary
asynchronous network. We formally state the weak and strong versions of the
problem. The weak version requires that either each node discovers the topology
of the network or at least one node detects the presence of a faulty node. The
strong version requires that each node discovers the topology regardless of
faults. We focus on non-cryptographic solutions to these problems. We explore
their bounds. We prove that the weak topology discovery problem is solvable
only if the connectivity of the network exceeds the number of faults in the
system. Similarly, we show that the strong version of the problem is solvable
only if the network connectivity is more than twice the number of faults. We
present solutions to both versions of the problem. The presented algorithms
match the established graph connectivity bounds. The algorithms do not require
the individual nodes to know either the diameter or the size of the network.
The message complexity of both programs is low polynomial with respect to the
network size. We describe how our solutions can be extended to add the property
of termination, handle topology changes and perform neighborhood discovery.


title: 2FACE: Bi-Directional Face Traversal for Efficient Geometric Routing

abstract:
  We propose bi-directional face traversal algorithm $2FACE$ to shorten the
path the message takes to reach the destination in geometric routing. Our
algorithm combines the practicality of the best single-direction traversal
algorithms with the worst case message complexity of $O(|E|)$, where $E$ is the
number of network edges. We apply $2FACE$ to a variety of geometric routing
algorithms. Our simulation results indicate that bi-directional face traversal
decreases the latency of message delivery two to three times compared to single
direction face traversal. The thus selected path approaches the shortest
possible route. This gain in speed comes with a similar message overhead
increase. We describe an algorithm which compensates for this message overhead
by recording the preferable face traversal direction. Thus, if a source has
several messages to send to the destination, the subsequent messages follow the
shortest route. Our simulation results show that with most geometric routing
algorithms the message overhead of finding the short route by bi-directional
face traversal is compensated within two to four repeat messages.


title: A Neutrosophic Description Logic

abstract:
  Description Logics (DLs) are appropriate, widely used, logics for managing
structured knowledge. They allow reasoning about individuals and concepts, i.e.
set of individuals with common properties. Typically, DLs are limited to
dealing with crisp, well defined concepts. That is, concepts for which the
problem whether an individual is an instance of it is yes/no question. More
often than not, the concepts encountered in the real world do not have a
precisely defined criteria of membership: we may say that an individual is an
instance of a concept only to a certain degree, depending on the individual's
properties. The DLs that deal with such fuzzy concepts are called fuzzy DLs. In
order to deal with fuzzy, incomplete, indeterminate and inconsistent concepts,
we need to extend the fuzzy DLs, combining the neutrosophic logic with a
classical DL. In particular, concepts become neutrosophic (here neutrosophic
means fuzzy, incomplete, indeterminate, and inconsistent), thus reasoning about
neutrosophic concepts is supported. We'll define its syntax, its semantics, and
describe its properties.


title: Expressiveness of Metric modalities for continuous time

abstract:
  We prove a conjecture by A. Pnueli and strengthen it showing a sequence of
"counting modalities" none of which is expressible in the temporal logic
generated by the previous modalities, over the real line, or over the positive
reals. Moreover, there is no finite temporal logic that can express all of them
over the real line, so that no finite metric temporal logic is expressively
complete.


title: Wireless Information-Theoretic Security - Part I: Theoretical Aspects

abstract:
  In this two-part paper, we consider the transmission of confidential data
over wireless wiretap channels. The first part presents an
information-theoretic problem formulation in which two legitimate partners
communicate over a quasi-static fading channel and an eavesdropper observes
their transmissions through another independent quasi-static fading channel. We
define the secrecy capacity in terms of outage probability and provide a
complete characterization of the maximum transmission rate at which the
eavesdropper is unable to decode any information. In sharp contrast with known
results for Gaussian wiretap channels (without feedback), our contribution
shows that in the presence of fading information-theoretic security is
achievable even when the eavesdropper has a better average signal-to-noise
ratio (SNR) than the legitimate receiver - fading thus turns out to be a friend
and not a foe. The issue of imperfect channel state information is also
addressed. Practical schemes for wireless information-theoretic security are
presented in Part II, which in some cases comes close to the secrecy capacity
limits given in this paper.


title:
Wireless Information-Theoretic Security - Part II: Practical
  Implementation

abstract:
  In Part I of this two-part paper on confidential communication over wireless
channels, we studied the fundamental security limits of quasi-static fading
channels from the point of view of outage secrecy capacity with perfect and
imperfect channel state information. In Part II, we develop a practical secret
key agreement protocol for Gaussian and quasi-static fading wiretap channels.
The protocol uses a four-step procedure to secure communications: establish
common randomness via an opportunistic transmission, perform message
reconciliation, establish a common key via privacy amplification, and use of
the key. We introduce a new reconciliation procedure that uses multilevel
coding and optimized low density parity check codes which in some cases comes
close to achieving the secrecy capacity limits established in Part I. Finally,
we develop new metrics for assessing average secure key generation rates and
show that our protocol is effective in secure key renewal.


title: Knowledge Representation Concepts for Automated SLA Management

abstract:
  Outsourcing of complex IT infrastructure to IT service providers has
increased substantially during the past years. IT service providers must be
able to fulfil their service-quality commitments based upon predefined Service
Level Agreements (SLAs) with the service customer. They need to manage, execute
and maintain thousands of SLAs for different customers and different types of
services, which needs new levels of flexibility and automation not available
with the current technology. The complexity of contractual logic in SLAs
requires new forms of knowledge representation to automatically draw inferences
and execute contractual agreements. A logic-based approach provides several
advantages including automated rule chaining allowing for compact knowledge
representation as well as flexibility to adapt to rapidly changing business
requirements. We suggest adequate logical formalisms for representation and
enforcement of SLA rules and describe a proof-of-concept implementation. The
article describes selected formalisms of the ContractLog KR and their adequacy
for automated SLA management and presents results of experiments to demonstrate
flexibility and scalability of the approach.


title: Functional Bregman Divergence and Bayesian Estimation of Distributions

abstract:
  A class of distortions termed functional Bregman divergences is defined,
which includes squared error and relative entropy. A functional Bregman
divergence acts on functions or distributions, and generalizes the standard
Bregman divergence for vectors and a previous pointwise Bregman divergence that
was defined for functions. A recently published result showed that the mean
minimizes the expected Bregman divergence. The new functional definition
enables the extension of this result to the continuous case to show that the
mean minimizes the expected functional Bregman divergence over a set of
functions or distributions. It is shown how this theorem applies to the
Bayesian estimation of distributions. Estimation of the uniform distribution
from independent and identically drawn samples is used as a case study.


title: Low-rank matrix factorization with attributes

abstract:
  We develop a new collaborative filtering (CF) method that combines both
previously known users' preferences, i.e. standard CF, as well as product/user
attributes, i.e. classical function approximation, to predict a given user's
interest in a particular product. Our method is a generalized low rank matrix
completion problem, where we learn a function whose inputs are pairs of vectors
-- the standard low rank matrix completion problem being a special case where
the inputs to the function are the row and column indices of the matrix. We
solve this generalized matrix completion problem using tensor product kernels
for which we also formally generalize standard kernel properties. Benchmark
experiments on movie ratings show the advantages of our generalized matrix
completion method over the standard matrix completion one with no information
about movies or people, as well as over standard multi-task or single task
learning methods.


title: Relay Channels with Confidential Messages

abstract:
  We consider a relay channel where a relay helps the transmission of messages
from one sender to one receiver. The relay is considered not only as a sender
that helps the message transmission but as a wire-tapper who can obtain some
knowledge about the transmitted messages. In this paper we study the coding
problem of the relay channel under the situation that some of transmitted
messages are confidential to the relay. A security of such confidential
messages is measured by the conditional entropy. The rate region is defined by
the set of transmission rates for which messages are reliably transmitted and
the security of confidential messages is larger than a prescribed level. In
this paper we give two definition of the rate region. We first define the rate
region in the case of deterministic encoder and call it the deterministic rate
region. Next, we define the rate region in the case of stochastic encoder and
call it the stochastic rate region. We derive explicit inner and outer bounds
for the above two rate regions and present a class of relay channels where two
bounds match. Furthermore, we show that stochastic encoder can enlarge the rate
region. We also evaluate the deterministic rate region of the Gaussian relay
channel with confidential messages.


title: Hereditary Discrepancies in Different Numbers of Colors II

abstract:
  We bound the hereditary discrepancy of a hypergraph $\HH$ in two colors in
terms of its hereditary discrepancy in $c$ colors. We show that
$\herdisc(\HH,2) \le K c \herdisc(\HH,c)$, where $K$ is some absolute constant.
This bound is sharp.


title: Coupling Methodology within the Software Platform Alliances

abstract:
  CEA, ANDRA and EDF are jointly developing the software platform ALLIANCES
which aim is to produce a tool for the simulation of nuclear waste storage and
disposal repository. This type of simulations deals with highly coupled
thermo-hydro-mechanical and chemical (T-H-M-C) processes. A key objective of
Alliances is to give the capability for coupling algorithms development between
existing codes. The aim of this paper is to present coupling methodology use in
the context of this software platform.


title:
Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured
  Peer-to-Peer Networks

abstract:
  In unstructured peer-to-peer (P2P) networks, the overlay topology (or
connectivity graph) among peers is a crucial component in addition to the
peer/data organization and search. Topological characteristics have profound
impact on the efficiency of search on such unstructured P2P networks as well as
other networks. It has been well-known that search on small-world topologies of
N nodes can be as efficient as O(ln N), while scale-free (power-law) topologies
offer even better search efficiencies like as good as O(lnln N) for a range of
degree distribution exponents. However, generation and maintenance of such
scale-free topologies are hard to realize in a distributed and potentially
uncooperative environments as in the P2P networks. A key limitation of
scale-free topologies is the high load (i.e. high degree) on very few number of
hub nodes. In a typical unstructured P2P network, peers are not willing to
maintain high degrees/loads as they may not want to store large number of
entries for construction of the overlay topology. So, to achieve fairness and
practicality among all peers, hard cutoffs on the number of entries are imposed
by the individual peers, which limits scale-freeness of the overall topology.
Thus, efficiency of the flooding search reduces as the size of the hard cutoff
does. We investigate construction of scale-free topologies with hard cutoffs
(i.e. there are not any major hubs) and effect of these hard cutoffs on the
search efficiency. Interestingly, we observe that the efficiency of normalized
flooding and random walk search algorithms increases as the hard cutoff
decreases.


title:
Shannon's secrecy system with informed receivers and its application to
  systematic coding for wiretapped channels

abstract:
  Shannon's secrecy system is studied in a setting, where both the legitimate
decoder and the wiretapper have access to side information sequences correlated
to the source, but the wiretapper receives both the coded information and the
side information via channels that are more noisy than the respective channels
of the legitmate decoder, which in turn, also shares a secret key with the
encoder. A single--letter characterization is provided for the achievable
region in the space of five figures of merit: the equivocation at the
wiretapper, the key rate, the distortion of the source reconstruction at the
legitimate receiver, the bandwidth expansion factor of the coded channels, and
the average transmission cost (generalized power). Beyond the fact that this is
an extension of earlier studies, it also provides a framework for studying
fundamental performance limits of systematic codes in the presence of a wiretap
channel. The best achievable performance of systematic codes is then compared
to that of a general code in several respects, and a few examples are given.


title: Quantitative Analysis of the Publishing Landscape in High-Energy Physics

abstract:
  World-wide collaboration in high-energy physics (HEP) is a tradition which
dates back several decades, with scientific publications mostly coauthored by
scientists from different countries. This coauthorship phenomenon makes it
difficult to identify precisely the ``share'' of each country in HEP scientific
production. One year's worth of HEP scientific articles published in
peer-reviewed journals is analysed and their authors are uniquely assigned to
countries. This method allows the first correct estimation on a ``pro rata''
basis of the share of HEP scientific publishing among several countries and
institutions. The results provide an interesting insight into the geographical
collaborative patterns of the HEP community. The HEP publishing landscape is
further analysed to provide information on the journals favoured by the HEP
community and on the geographical variation of their author bases. These
results provide quantitative input to the ongoing debate on the possible
transition of HEP publishing to an Open Access model.


title:
Scatter Networks: A New Approach for Analyzing Information Scatter on
  the Web

abstract:
  Information on any given topic is often scattered across the web. Previously
this scatter has been characterized through the distribution of a set of facts
(i.e. pieces of information) across web pages, showing that typically a few
pages contain many facts on the topic, while many pages contain just a few.
While such approaches have revealed important scatter phenomena, they are lossy
in that they conceal how specific facts (e.g. rare facts) occur in specific
types of pages (e.g. fact-rich pages). To reveal such regularities, we
construct bi-partite networks, consisting of two types of vertices: the facts
contained in webpages and the webpages themselves. Such a representation
enables the application of a series of network analysis techniques, revealing
structural features such as connectivity, robustness, and clustering. We
discuss the implications of each of these features to the users' ability to
find comprehensive information online. Finally, we compare the bipartite graph
structure of webpages and facts with the hyperlink structure between the
webpages.


title:
The specifications making in complex CAD-system of renovation of the
  enterprises on the basis of modules in the drawing and electronic catalogues

abstract:
  The experience of automation of the specifications making of the projects of
renovation of the industrial enterprises is described, being based on the
special modules in the drawing containing the visible image and additional
parameters, and electronic catalogues


title:
The modelling of the automation schemes of technological processes in
  CAD-system of renovation of the enterprises

abstract:
  According to the requirements of the Russian standards, the automation
schemes are necessary practically in each project of renovation of industrial
buildings and facilities, in which any technological processes are realized.
The model representations of the automation schemes in CAD-system TechnoCAD
GlassX are described. The models follow a principle "to exclude a repeated
input operations"


title: Hard Disk Drive as a Magnetomechanical Logic Device

abstract:
  We consider the conditions how two binary numbers can be superimposed on the
same track with the use of different recording magnetic fields. As a result the
average magnetization of longitudinal medium along the track can have three
states: -M, 0 and +M. Possibility to perform logic operations with these states
is considered. We demonstrate OR, AND, XOR and NOT operations and discuss a
modification of a recording device.


title:
Genetic Programming for Kernel-based Learning with Co-evolving Subsets
  Selection

abstract:
  Support Vector Machines (SVMs) are well-established Machine Learning (ML)
algorithms. They rely on the fact that i) linear learning can be formalized as
a well-posed optimization problem; ii) non-linear learning can be brought into
linear learning thanks to the kernel trick and the mapping of the initial
search space onto a high dimensional feature space. The kernel is designed by
the ML expert and it governs the efficiency of the SVM approach. In this paper,
a new approach for the automatic design of kernels by Genetic Programming,
called the Evolutionary Kernel Machine (EKM), is presented. EKM combines a
well-founded fitness function inspired from the margin criterion, and a
co-evolution framework ensuring the computational scalability of the approach.
Empirical validation on standard ML benchmark demonstrates that EKM is
competitive using state-of-the-art SVMs with tuned hyper-parameters.


title: Neural Computation with Rings of Quasiperiodic Oscillators

abstract:
  We describe the use of quasiperiodic oscillators for computation and control
of robots. We also describe their relationship to central pattern generators in
simple organisms and develop a group theory for describing the dynamics of
these systems.


title: Rhythms of social interaction: messaging within a massive online network

abstract:
  We have analyzed the fully-anonymized headers of 362 million messages
exchanged by 4.2 million users of Facebook, an online social network of college
students, during a 26 month interval. The data reveal a number of strong daily
and weekly regularities which provide insights into the time use of college
students and their social lives, including seasonal variations. We also
examined how factors such as school affiliation and informal online friend
lists affect the observed behavior and temporal patterns. Finally, we show that
Facebook users appear to be clustered by school with respect to their temporal
messaging patterns.


title:
Functional Brain Imaging with Multi-Objective Multi-Modal Evolutionary
  Optimization

abstract:
  Functional brain imaging is a source of spatio-temporal data mining problems.
A new framework hybridizing multi-objective and multi-modal optimization is
proposed to formalize these data mining problems, and addressed through
Evolutionary Computation (EC). The merits of EC for spatio-temporal data mining
are demonstrated as the approach facilitates the modelling of the experts'
requirements, and flexibly accommodates their changing goals.


title:
Static Safety for an Actor Dedicated Process Calculus by Abstract
  Interpretation

abstract:
  The actor model eases the definition of concurrent programs with non uniform
behaviors. Static analysis of such a model was previously done in a data-flow
oriented way, with type systems. This approach was based on constraint set
resolution and was not able to deal with precise properties for communications
of behaviors. We present here a new approach, control-flow oriented, based on
the abstract interpretation framework, able to deal with communication of
behaviors. Within our new analyses, we are able to verify most of the previous
properties we observed as well as new ones, principally based on occurrence
counting.


title: On the Benefits of Inoculation, an Example in Train Scheduling

abstract:
  The local reconstruction of a railway schedule following a small perturbation
of the traffic, seeking minimization of the total accumulated delay, is a very
difficult and tightly constrained combinatorial problem. Notoriously enough,
the railway company's public image degrades proportionally to the amount of
daily delays, and the same goes for its profit! This paper describes an
inoculation procedure which greatly enhances an evolutionary algorithm for
train re-scheduling. The procedure consists in building the initial population
around a pre-computed solution based on problem-related information available
beforehand. The optimization is performed by adapting times of departure and
arrival, as well as allocation of tracks, for each train at each station. This
is achieved by a permutation-based evolutionary algorithm that relies on a
semi-greedy heuristic scheduler to gradually reconstruct the schedule by
inserting trains one after another. Experimental results are presented on
various instances of a large real-world case involving around 500 trains and
more than 1 million constraints. In terms of competition with commercial math
ematical programming tool ILOG CPLEX, it appears that within a large class of
instances, excluding trivial instances as well as too difficult ones, and with
very few exceptions, a clever initialization turns an encouraging failure into
a clear-cut success auguring of substantial financial savings.


title: A Generic Global Constraint based on MDDs

abstract:
  The paper suggests the use of Multi-Valued Decision Diagrams (MDDs) as the
supporting data structure for a generic global constraint. We give an algorithm
for maintaining generalized arc consistency (GAC) on this constraint that
amortizes the cost of the GAC computation over a root-to-terminal path in the
search tree. The technique used is an extension of the GAC algorithm for the
regular language constraint on finite length input. Our approach adds support
for skipped variables, maintains the reduced property of the MDD dynamically
and provides domain entailment detection. Finally we also show how to adapt the
approach to constraint types that are closely related to MDDs, such as AOMDDs
and Case DAGs.


title: A Symbolic Intruder Model for Hash-Collision Attacks

abstract:
  In the recent years, several practical methods have been published to compute
collisions on some commonly used hash functions. In this paper we present a
method to take into account, at the symbolic level, that an intruder actively
attacking a protocol execution may use these collision algorithms in reasonable
time during the attack. Our decision procedure relies on the reduction of
constraint solving for an intruder exploiting the collision properties of hush
functions to constraint solving for an intruder operating on words.


title:
An informational approach to the global optimization of
  expensive-to-evaluate functions

abstract:
  In many global optimization problems motivated by engineering applications,
the number of function evaluations is severely limited by time or cost. To
ensure that each evaluation contributes to the localization of good candidates
for the role of global minimizer, a sequential choice of evaluation points is
usually carried out. In particular, when Kriging is used to interpolate past
evaluations, the uncertainty associated with the lack of information on the
function can be expressed and used to compute a number of criteria accounting
for the interest of an additional evaluation at any given point. This paper
introduces minimizer entropy as a new Kriging-based criterion for the
sequential choice of points at which the function should be evaluated. Based on
\emph{stepwise uncertainty reduction}, it accounts for the informational gain
on the minimizer expected from a new evaluation. The criterion is approximated
using conditional simulations of the Gaussian process model behind Kriging, and
then inserted into an algorithm similar in spirit to the \emph{Efficient Global
Optimization} (EGO) algorithm. An empirical comparison is carried out between
our criterion and \emph{expected improvement}, one of the reference criteria in
the literature. Experimental results indicate major evaluation savings over
EGO. Finally, the method, which we call IAGO (for Informational Approach to
Global Optimization) is extended to robust optimization problems, where both
the factors to be tuned and the function evaluations are corrupted by noise.


title:
Coding Improves the Optimal Delay-Throughput Trade-offs in Mobile Ad-Hoc
  Networks: Two-Dimensional I.I.D. Mobility Models

abstract:
  In this paper, we investigate the delay-throughput trade-offs in mobile
ad-hoc networks under two-dimensional i.i.d. mobility models. We consider two
mobility time-scales: (i) Fast mobility where node mobility is at the same
time-scale as data transmissions; (ii) Slow mobility where node mobility is
assumed to occur at a much slower time-scale than data transmissions. Given a
delay constraint $D,$ the main results are as follows: (1) For the
two-dimensional i.i.d. mobility model with fast mobiles, the maximum throughput
per source-destination (S-D) pair is shown to be $O(\sqrt{D/n}),$ where $n$ is
the number of mobiles. (2) For the two-dimensional i.i.d. mobility model with
slow mobiles, the maximum throughput per S-D pair is shown to be
$O(\sqrt[3]{D/n}).$ (3) For each case, we propose a joint coding-scheduling
algorithm to achieve the optimal delay-throughput trade-offs.


title:
A Unified View of TD Algorithms; Introducing Full-Gradient TD and
  Equi-Gradient Descent TD

abstract:
  This paper addresses the issue of policy evaluation in Markov Decision
Processes, using linear function approximation. It provides a unified view of
algorithms such as TD(lambda), LSTD(lambda), iLSTD, residual-gradient TD. It is
asserted that they all consist in minimizing a gradient function and differ by
the form of this function and their means of minimizing it. Two new schemes are
introduced in that framework: Full-gradient TD which uses a generalization of
the principle introduced in iLSTD, and EGD TD, which reduces the gradient by
successive equi-gradient descents. These three algorithms form a new
intermediate family with the interesting property of making much better use of
the samples than TD while keeping a gradient descent scheme, which is useful
for complexity issues and optimistic policy iteration.