title: Bargaining over the interference channel

abstract:
  In this paper we analyze the interference channel as a conflict situation.
This viewpoint implies that certain points in the rate region are unreasonable
to one of the players. Therefore these points cannot be considered achievable
based on game theoretic considerations. We then propose to use Nash bargaining
solution as a tool that provides preferred points on the boundary of the game
theoretic rate region. We provide analysis for the 2x2 intereference channel
using the FDM achievable rate region. We also outline how to generalize our
results to other achievable rate regions for the interference channel as well
as the multiple access channel.
  Keywords: Spectrum optimization, distributed coordination, game theory,
interference channel, multiple access channel.


title:
Verification of Ptime reducibility for system F terms via Dual Light
  Affine Logic

abstract:
  In a previous work we introduced Dual Light Affine Logic (DLAL)
([BaillotTerui04]) as a variant of Light Linear Logic suitable for guaranteeing
complexity properties on lambda-calculus terms: all typable terms can be
evaluated in polynomial time and all Ptime functions can be represented. In the
present work we address the problem of typing lambda-terms in second-order
DLAL. For that we give a procedure which, starting with a term typed in system
F, finds all possible ways to decorate it into a DLAL typed term. We show that
our procedure can be run in time polynomial in the size of the original Church
typed system F term.


title:
A unifying framework for seed sensitivity and its application to subset
  seeds (Extended abstract)

abstract:
  We propose a general approach to compute the seed sensitivity, that can be
applied to different definitions of seeds. It treats separately three
components of the seed sensitivity problem - a set of target alignments, an
associated probability distribution, and a seed model - that are specified by
distinct finite automata. The approach is then applied to a new concept of
subset seeds for which we propose an efficient automaton construction.
Experimental results confirm that sensitive subset seeds can be efficiently
designed using our approach, and can then be used in similarity search
producing better results than ordinary spaced seeds.


title: Estimating seed sensitivity on homogeneous alignments

abstract:
  We address the problem of estimating the sensitivity of seed-based similarity
search algorithms. In contrast to approaches based on Markov models [18, 6, 3,
4, 10], we study the estimation based on homogeneous alignments. We describe an
algorithm for counting and random generation of those alignments and an
algorithm for exact computation of the sensitivity for a broad class of seed
strategies. We provide experimental results demonstrating a bias introduced by
ignoring the homogeneousness condition.


title: Towards an information-theoretically safe cryptographic protocol

abstract:
  We introduce what --if some kind of group action exists-- is a truly
(information theoretically) safe cryptographic communication system: a protocol
which provides \emph{zero} information to any passive adversary having full
access to the channel.


title: Minimizing Symmetric Set Functions Faster

abstract:
  We describe a combinatorial algorithm which, given a monotone and consistent
symmetric set function d on a finite set V in the sense of Rizzi, constructs a
non trivial set S minimizing d(S,V-S). This includes the possibility for the
minimization of symmetric submodular functions. The presented algorithm
requires at most as much time as the one described by Rizzi, but depending on
the function d, it may allow several improvements.


title: Encoding of Functions of Correlated Sources

abstract:
  This submission is being withdrawn due to serious errors in the achievability
proofs. The reviewers of the journal I had submitted to had found errors back
in 2006. I had forgotten about this paper until I saw the CFP for a JSAC issue
on in-network computation.
http://www.jsac.ucsd.edu/Calls/in-networkcomputationcfp.pdf.


title:
Asymptotic Learnability of Reinforcement Problems with Arbitrary
  Dependence

abstract:
  We address the problem of reinforcement learning in which observations may
exhibit an arbitrary form of stochastic dependence on past observations and
actions. The task for an agent is to attain the best possible asymptotic reward
where the true generating environment is unknown but belongs to a known
countable family of environments. We find some sufficient conditions on the
class of environments under which an agent exists which attains the best
asymptotic reward for any environment in the class. We analyze how tight these
conditions are and how they relate to different probabilistic assumptions known
in reinforcement learning and related fields, such as Markov Decision Processes
and mixing conditions.


title:
Remote-control and clustering of physical computations using the XML-RPC
  protocol and the open-Mosix system

abstract:
  The applications of the remote control of physical simulations performed in
clustered computers running under an open-Mosix system are presented. Results
from the simulation of a 2-dimensional ferromagnetic system of spins in the
Ising scheme are provided. Basic parameters of a simulated hysteresis loop like
coercivity and exchange bias due to pinning of ferromagnetic spins are given.
The paper describes in physicists terminology a cost effective solution which
utilizes an XML-RPC protocol (Extensible Markup Language - Remote Procedure
Calling) and standard C++ and Python languages.


title:
A General Framework for Scalability and Performance Analysis of DHT
  Routing Systems

abstract:
  In recent years, many DHT-based P2P systems have been proposed, analyzed, and
certain deployments have reached a global scale with nearly one million nodes.
One is thus faced with the question of which particular DHT system to choose,
and whether some are inherently more robust and scalable.
  Toward developing such a comparative framework, we present the reachable
component method (RCM) for analyzing the performance of different DHT routing
systems subject to random failures. We apply RCM to five DHT systems and obtain
analytical expressions that characterize their routability as a continuous
function of system size and node failure probability. An important consequence
is that in the large-network limit, the routability of certain DHT systems go
to zero for any non-zero probability of node failure. These DHT routing
algorithms are therefore unscalable, while some others, including Kademlia,
which powers the popular eDonkey P2P system, are found to be scalable.


title:
Mathematical Modeling of Aerodynamic Space -to - Surface Flight with
  Trajectory for Avoid Intercepting Process

abstract:
  Modeling has been created for a Space-to-Surface system defined for an
optimal trajectory for targeting in terminal phase with avoids an intercepting
process. The modeling includes models for simulation atmosphere, speed of
sound, aerodynamic flight and navigation by an infrared system. The modeling
and simulation includes statistical analysis of the modeling results.


title: Using SMART for Customized Monitoring of Windows Services

abstract:
  We focus on examining and working with an important category of computer
software called Services, which are provided as a part of newer Microsoft
Windows operating systems. A typical Windows user transparently utilizes many
of these services but is frequently unaware of their existence. Since some
services have the potential to create significant problems when they are
executing, it is important for a system administrator to identify which
services are running on the network, the types of processing done by each
service, and any interrelationships among the various services. This
information can then be used to improve the overall integrity of both the
individual computer where a questionable service is running and in aggregate an
entire network of computers.
  NCSA has developed an application called SMART (Services Monitoring And
Reporting Tool) that can be used to identify and display all services currently
running in the network. A commercial program called Hyena remotely monitors the
services on all computers attached to the network and exports this information
to SMART. SMART produces various outputs that the system administrator can
analyze and then determine appropriate actions to take. In particular, SMART
provides a color coordinated user interface to quickly identify and classify
both potentially hazardous services and also unknown services.


title: Implementation of float-float operators on graphics hardware

abstract:
  The Graphic Processing Unit (GPU) has evolved into a powerful and flexible
processor. The latest graphic processors provide fully programmable vertex and
pixel processing units that support vector operations up to single
floating-point precision. This computational power is now being used for
general-purpose computations. However, some applications require higher
precision than single precision. This paper describes the emulation of a 44-bit
floating-point number format and its corresponding operations. An
implementation is presented along with performance and accuracy results.


title: Fourier Analysis and Holographic Representations of 1D and 2D Signals

abstract:
  In this paper, we focus on Fourier analysis and holographic transforms for
signal representation. For instance, in the case of image processing, the
holographic representation has the property that an arbitrary portion of the
transformed image enables reconstruction of the whole image with details
missing. We focus on holographic representation defined through the Fourier
Transforms. Thus, We firstly review some results in Fourier transform and
Fourier series. Next, we review the Discrete Holographic Fourier Transform
(DHFT) for image representation. Then, we describe the contributions of our
work. We show a simple scheme for progressive transmission based on the DHFT.
Next, we propose the Continuous Holographic Fourier Transform (CHFT) and
discuss some theoretical aspects of it for 1D signals. Finally, some testes are
presented in the experimental results


title: Affine functions and series with co-inductive real numbers

abstract:
  We extend the work of A. Ciaffaglione and P. Di Gianantonio on mechanical
verification of algorithms for exact computation on real numbers, using
infinite streams of digits implemented as co-inductive types. Four aspects are
studied: the first aspect concerns the proof that digit streams can be related
to the axiomatized real numbers that are already axiomatized in the proof
system (axiomatized, but with no fixed representation). The second aspect
re-visits the definition of an addition function, looking at techniques to let
the proof search mechanism perform the effective construction of an algorithm
that is correct by construction. The third aspect concerns the definition of a
function to compute affine formulas with positive rational coefficients. This
should be understood as a testbed to describe a technique to combine
co-recursion and recursion to obtain a model for an algorithm that appears at
first sight to be outside the expressive power allowed by the proof system. The
fourth aspect concerns the definition of a function to compute series, with an
application on the series that is used to compute Euler's number e. All these
experiments should be reproducible in any proof system that supports
co-inductive types, co-recursion and general forms of terminating recursion,
but we performed with the Coq system [12, 3, 14].


title: Coq in a Hurry

abstract:
  These notes provide a quick introduction to the Coq system and show how it
can be used to define logical concepts and functions and reason about them. It
is designed as a tutorial, so that readers can quickly start their own
experiments, learning only a few of the capabilities of the system. A much more
comprehensive study is provided in [1], which also provides an extensive
collection of exercises to train on.


title: CoInduction in Coq

abstract:
  We describe the basic notions of co-induction as they are available in the
coq system. As an application, we describe arithmetic properties for simple
representations of real numbers.


title: Approximation Algorithms for K-Modes Clustering

abstract:
  In this paper, we study clustering with respect to the k-modes objective
function, a natural formulation of clustering for categorical data. One of the
main contributions of this paper is to establish the connection between k-modes
and k-median, i.e., the optimum of k-median is at most twice the optimum of
k-modes for the same categorical data clustering problem. Based on this
observation, we derive a deterministic algorithm that achieves an approximation
factor of 2. Furthermore, we prove that the distance measure in k-modes defines
a metric. Hence, we are able to extend existing approximation algorithms for
metric k-median to k-modes. Empirical results verify the superiority of our
method.


title:
minimUML: A Minimalist Approach to UML Diagraming for Early Computer
  Science Education

abstract:
  The Unified Modeling Language (UML) is commonly used in introductory Computer
Science to teach basic object-oriented design. However, there appears to be a
lack of suitable software to support this task. Many of the available programs
that support UML focus on developing code and not on enhancing learning. Those
that were designed for educational use sometimes have poor interfaces or are
missing common and important features, such as multiple selection and
undo/redo. There is a need for software that is tailored to an instructional
environment and has all the useful and needed functionality for that specific
task. This is the purpose of minimUML. minimUML provides a minimum amount of
UML, just what is commonly used in beginning programming classes, while
providing a simple, usable interface. In particular, minimUML was designed to
support abstract design while supplying features for exploratory learning and
error avoidance. In addition, it allows for the annotation of diagrams, through
text or freeform drawings, so students can receive feedback on their work.
minimUML was developed with the goal of supporting ease of use, supporting
novice students, and a requirement of no prior-training for its use.


title: Complexity of Monadic inf-datalog. Application to temporal logic

abstract:
  In [11] we defined Inf-Datalog and characterized the fragments of Monadic
inf-Datalog that have the same expressive power as Modal Logic (resp. $CTL$,
alternation-free Modal $\mu$-calculus and Modal $\mu$-calculus). We study here
the time and space complexity of evaluation of Monadic inf-Datalog programs on
finite models. We deduce a new unified proof that model checking has 1. linear
data and program complexities (both in time and space) for $CTL$ and
alternation-free Modal $\mu$-calculus, and 2. linear-space (data and program)
complexities, linear-time program complexity and polynomial-time data
complexity for $L\mu\_k$ (Modal $\mu$-calculus with fixed alternation-depth at
most $k$).}


title: Towards the Optimal Amplify-and-Forward Cooperative Diversity Scheme

abstract:
  In a slow fading channel, how to find a cooperative diversity scheme that
achieves the transmit diversity bound is still an open problem. In fact, all
previously proposed amplify-and-forward (AF) and decode-and-forward (DF)
schemes do not improve with the number of relays in terms of the diversity
multiplexing tradeoff (DMT) for multiplexing gains r higher than 0.5. In this
work, we study the class of slotted amplify-and-forward (SAF) schemes. We first
establish an upper bound on the DMT for any SAF scheme with an arbitrary number
of relays N and number of slots M. Then, we propose a sequential SAF scheme
that can exploit the potential diversity gain in the high multiplexing gain
regime. More precisely, in certain conditions, the sequential SAF scheme
achieves the proposed DMT upper bound which tends to the transmit diversity
bound when M goes to infinity. In particular, for the two-relay case, the
three-slot sequential SAF scheme achieves the proposed upper bound and
outperforms the two-relay non-orthorgonal amplify-and-forward (NAF) scheme of
Azarian et al. for multiplexing gains r < 2/3. Numerical results reveal a
significant gain of our scheme over the previously proposed AF schemes,
especially in high spectral efficiency and large network size regime.


title: Diversity-Multiplexing Tradeoff of Double Scattering MIMO Channels

abstract:
  It is well known that the presence of double scattering degrades the
performance of a MIMO channel, in terms of both the multiplexing gain and the
diversity gain. In this paper, a closed-form expression of the
diversity-multiplexing tradeoff (DMT) of double scattering MIMO channels is
obtained. It is shown that, for a channel with nT transmit antennas, nR receive
antennas and nS scatterers, the DMT only depends on the ordered version of the
triple (nT,nS,nR), for arbitrary nT, nS and nR. The condition under which the
double scattering channel has the same DMT as the single scattering channel is
also established.


title: If a tree casts a shadow is it telling the time?

abstract:
  Physical processes are computations only when we use them to externalize
thought. Computation is the performance of one or more fixed processes within a
contingent environment. We reformulate the Church-Turing thesis so that it
applies to programs rather than to computability. When suitably formulated
agent-based computing in an open, multi-scalar environment represents the
current consensus view of how we interact with the world. But we don't know how
to formulate multi-scalar environments.


title:
Open at the Top; Open at the Bottom; and Continually (but Slowly)
  Evolving

abstract:
  Systems of systems differ from traditional systems in that they are open at
the top, open at the bottom, and continually (but slowly) evolving. "Open at
the top" means that there is no pre-defined top level application. New
applications may be created at any time. "Open at the bottom" means that the
system primitives are defined functionally rather than concretely. This allows
the implementation of these primitives to be modified as technology changes.
"Continually (but slowly) evolving" means that the system's functionality is
stable enough to be useful but is understood to be subject to modification.
Systems with these properties tend to be environments within which other
systems operate--and hence are systems of systems. It is also important to
understand the larger environment within which a system of systems exists.


title: Complex Systems + Systems Engineering = Complex Systems Engineeri

abstract:
  One may define a complex system as a system in which phenomena emerge as a
consequence of multiscale interaction among the system's components and their
environments. The field of Complex Systems is the study of such
systems--usually naturally occurring, either bio-logical or social. Systems
Engineering may be understood to include the conceptualising and building of
systems that consist of a large number of concurrently operating and
interacting components--usually including both human and non-human elements. It
has become increasingly apparent that the kinds of systems that systems
engineers build have many of the same multiscale characteristics as those of
naturally occurring complex systems. In other words, systems engineering is the
engineering of complex systems. This paper and the associated panel will
explore some of the connections between the fields of complex systems and
systems engineering.


title: On Cosets of the Generalized First-Order Reed-Muller Code with Low PMEPR

abstract:
  Golay sequences are well suited for the use as codewords in orthogonal
frequency-division multiplexing (OFDM), since their peak-to-mean envelope power
ratio (PMEPR) in q-ary phase-shift keying (PSK) modulation is at most 2. It is
known that a family of polyphase Golay sequences of length 2^m organizes in
m!/2 cosets of a q-ary generalization of the first-order Reed-Muller code,
RM_q(1,m). In this paper a more general construction technique for cosets of
RM_q(1,m) with low PMEPR is established. These cosets contain so-called
near-complementary sequences. The application of this theory is then
illustrated by providing some construction examples. First, it is shown that
the m!/2 cosets of RM_q(1,m) comprised of Golay sequences just arise as a
special case. Second, further families of cosets of RM_q(1,m) with maximum
PMEPR between 2 and 4 are presented, showing that some previously unexplained
phenomena can now be understood within a unified framework. A lower bound on
the PMEPR of cosets of RM_q(1,m) is proved as well, and it is demonstrated that
the upper bound on the PMEPR is tight in many cases. Finally it is shown that
all upper bounds on the PMEPR of cosets of RM_q(1,m) also hold for the
peak-to-average power ratio (PAPR) under the Walsh-Hadamard transform.


title:
A Business Goal Driven Approach for Understanding and Specifying
  Information Security Requirements

abstract:
  In this paper we present an approach for specifying and prioritizing
information security requirements in organizations. It is important to
prioritize security requirements since hundred per cent security is not
achievable and the limited resources available should be directed to satisfy
the most important ones. We propose to link explicitly security requirements
with the organization's business vision, i.e. to provide business rationale for
security requirements. The rationale is then used as a basis for comparing the
importance of different security requirements. A conceptual framework is
presented, where the relationships between business vision, critical impact
factors and valuable assets (together with their security requirements) are
shown.


title: Digital watermarking in the singular vector domain

abstract:
  Many current watermarking algorithms insert data in the spatial or transform
domains like the discrete cosine, the discrete Fourier, and the discrete
wavelet transforms. In this paper, we present a data-hiding algorithm that
exploits the singular value decomposition (SVD) representation of the data. We
compute the SVD of the host image and the watermark and embed the watermark in
the singular vectors of the host image. The proposed method leads to an
imperceptible scheme for digital images, both in grey scale and color and is
quite robust against attacks like noise and JPEG compression.


title:
Error Rate Analysis for Coded Multicarrier Systems over Quasi-Static
  Fading Channels

abstract:
  This paper presents two methods for approximating the performance of coded
multicarrier systems operating over frequency-selective, quasi-static fading
channels with non-ideal interleaving. The first method is based on
approximating the performance of the system over each realization of the
channel, and is suitable for obtaining the outage performance of this type of
system. The second method is based on knowledge of the correlation matrix of
the frequency-domain channel gains and can be used to directly obtain the
average performance. Both of the methods are applicable for
convolutionally-coded interleaved systems employing Quadrature Amplitude
Modulation (QAM). As examples, both methods are used to study the performance
of the Multiband Orthogonal Frequency Division Multiplexing (OFDM) proposal for
high data-rate Ultra-Wideband (UWB) communication.


title: Graphics Turing Test

abstract:
  We define a Graphics Turing Test to measure graphics performance in a similar
manner to the definition of the traditional Turing Test. To pass the test one
needs to reach a computational scale, the Graphics Turing Scale, for which
Computer Generated Imagery becomes comparatively indistinguishable from real
images while also being interactive. We derive an estimate for this
computational scale which, although large, is within reach of todays
supercomputers. We consider advantages and disadvantages of various computer
systems designed to pass the Graphics Turing Test. Finally we discuss
commercial applications from the creation of such a system, in particular
Interactive Cinema.


title:
Theoretical Properties of Projection Based Multilayer Perceptrons with
  Functional Inputs

abstract:
  Many real world data are sampled functions. As shown by Functional Data
Analysis (FDA) methods, spectra, time series, images, gesture recognition data,
etc. can be processed more efficiently if their functional nature is taken into
account during the data analysis process. This is done by extending standard
data analysis methods so that they can apply to functional inputs. A general
way to achieve this goal is to compute projections of the functional data onto
a finite dimensional sub-space of the functional space. The coordinates of the
data on a basis of this sub-space provide standard vector representations of
the functions. The obtained vectors can be processed by any standard method. In
our previous work, this general approach has been used to define projection
based Multilayer Perceptrons (MLPs) with functional inputs. We study in this
paper important theoretical properties of the proposed model. We show in
particular that MLPs with functional inputs are universal approximators: they
can approximate to arbitrary accuracy any continuous mapping from a compact
sub-space of a functional space to R. Moreover, we provide a consistency result
that shows that any mapping from a functional space to R can be learned thanks
to examples by a projection based MLP: the generalization mean square error of
the MLP decreases to the smallest possible mean square error on the data when
the number of examples goes to infinity.


title:
Complexity of Consistent Query Answering in Databases under
  Cardinality-Based and Incremental Repair Semantics

abstract:
  Consistent Query Answering (CQA) is the problem of computing from a database
the answers to a query that are consistent with respect to certain integrity
constraints that the database, as a whole, may fail to satisfy. Consistent
answers have been characterized as those that are invariant under certain
minimal forms of restoration of the database consistency. We investigate
algorithmic and complexity theoretic issues of CQA under database repairs that
minimally depart -wrt the cardinality of the symmetric difference- from the
original database. We obtain first tight complexity bounds.
  We also address the problem of incremental complexity of CQA, that naturally
occurs when an originally consistent database becomes inconsistent after the
execution of a sequence of update operations. Tight bounds on incremental
complexity are provided for various semantics under denial constraints. Fixed
parameter tractability is also investigated in this dynamic context, where the
size of the update sequence becomes the relevant parameter.


title: Hypercomputing the Mandelbrot Set?

abstract:
  The Mandelbrot set is an extremely well-known mathematical object that can be
described in a quite simple way but has very interesting and non-trivial
properties. This paper surveys some results that are known concerning the
(non-)computability of the set. It considers two models of decidability over
the reals (which have been treated much more thoroughly and technically by
Hertling (2005), Blum, Shub and Smale, Brattka (2003) and Weihrauch (1999 and
2003) among others), two over the computable reals (the Russian school and
hypercomputation) and a model over the rationals.


title:
The Poincare conjecture for digital spaces. Properties of digital
  n-dimensional disks and spheres

abstract:
  Motivated by the Poincare conjecture, we study properties of digital
n-dimensional spheres and disks, which are digital models of their continuous
counterparts. We introduce homeomorphic transformations of digital manifolds,
which retain the connectedness, the dimension, the Euler characteristics and
the homology groups of manifolds. We find conditions where an n-dimensional
digital manifold is the n-dimensional digital sphere and discuss the link
between continuous closed n-manifolds and their digital models.


title:
Multiterminal Source Coding with Two Encoders--I: A Computable Outer
  Bound

abstract:
  In this first part, a computable outer bound is proved for the multiterminal
source coding problem, for a setup with two encoders, discrete memoryless
sources, and bounded distortion measures.


title: Sparse Matrix Implementation in Octave

abstract:
  There are many classes of mathematical problems which give rise to matrices,
where a large number of the elements are zero. In this case it makes sense to
have a special matrix type to handle this class of problems where only the
non-zero elements of the matrix are stored. Not only does this reduce the
amount of memory to store the matrix, but it also means that operations on this
type of matrix can take advantage of the a-priori knowledge of the positions of
the non-zero elements to accelerate their calculations. A matrix type that
stores only the non-zero elements is generally called sparse.
  Until recently Octave has lacked a full implementation of sparse matrices.
This article address the implementation of sparse matrices within Octave,
including their storage, creation, fundamental algorithms used, their
implementations and the basic operations and functions implemented for sparse
matrices. Mathematical issues such as the return types of sparse operations,
matrix fill-in and reordering for sparse matrix factorization is discussed in
the context of a real example.
  Benchmarking of Octave's implementation of sparse operations compared to
their equivalent in Matlab are given and their implications discussed. Results
are presented for multiplication and linear algebra operations for various
matrix orders and densities. Furthermore, the use of Octave's sparse matrix
implementation is demonstrated using a real example of a finite element model
(FEM) problem. Finally, the method of using sparse matrices with Octave's
oct-files is discussed. The means of creating, using and returning sparse
matrices within oct-files is discussed as well as the differences between
Octave's Sparse and Array classes.


title:
On the Complexity of Limit Sets of Cellular Automata Associated with
  Probability Measures

abstract:
  We study the notion of limit sets of cellular automata associated with
probability measures (mu-limit sets). This notion was introduced by P. Kurka
and A. Maass. It is a refinement of the classical notion of omega-limit sets
dealing with the typical long term behavior of cellular automata. It focuses on
the words whose probability of appearance does not tend to 0 as time tends to
infinity (the persistent words). In this paper, we give a characterisation of
the persistent language for non sensible cellular automata associated with
Bernouilli measures. We also study the computational complexity of these
languages. We show that the persistent language can be non-recursive. But our
main result is that the set of quasi-nilpotent cellular automata (those with a
single configuration in their mu-limit set) is neither recursively enumerable
nor co-recursively enumerable.


title: Minimum-Cost Coverage of Point Sets by Disks

abstract:
  We consider a class of geometric facility location problems in which the goal
is to determine a set X of disks given by their centers (t_j) and radii (r_j)
that cover a given set of demand points Y in the plane at the smallest possible
cost. We consider cost functions of the form sum_j f(r_j), where f(r)=r^alpha
is the cost of transmission to radius r. Special cases arise for alpha=1 (sum
of radii) and alpha=2 (total area); power consumption models in wireless
network design often use an exponent alpha>2. Different scenarios arise
according to possible restrictions on the transmission centers t_j, which may
be constrained to belong to a given discrete set or to lie on a line, etc. We
obtain several new results, including (a) exact and approximation algorithms
for selecting transmission points t_j on a given line in order to cover demand
points Y in the plane; (b) approximation algorithms (and an algebraic
intractability result) for selecting an optimal line on which to place
transmission points to cover Y; (c) a proof of NP-hardness for a discrete set
of transmission points in the plane and any fixed alpha>1; and (d) a
polynomial-time approximation scheme for the problem of computing a minimum
cost covering tour (MCCT), in which the total cost is a linear combination of
the transmission cost for the set of disks and the length of a tour/path that
connects the centers of the disks.


title: Can an Organism Adapt Itself to Unforeseen Circumstances?

abstract:
  A model of an organism as an autonomous intelligent system has been proposed.
This model was used to analyze learning of an organism in various environmental
conditions. Processes of learning were divided into two types: strong and weak
processes taking place in the absence and the presence of aprioristic
information about an object respectively. Weak learning is synonymous to
adaptation when aprioristic programs already available in a system (an
organism) are started. It was shown that strong learning is impossible for both
an organism and any autonomous intelligent system. It was shown also that the
knowledge base of an organism cannot be updated. Therefore, all behavior
programs of an organism are congenital. A model of a conditioned reflex as a
series of consecutive measurements of environmental parameters has been
advanced. Repeated measurements are necessary in this case to reduce the error
during decision making.


title: Nearly optimal exploration-exploitation decision thresholds

abstract:
  While in general trading off exploration and exploitation in reinforcement
learning is hard, under some formulations relatively simple solutions exist. In
this paper, we first derive upper bounds for the utility of selecting different
actions in the multi-armed bandit setting. Unlike the common statistical upper
confidence bounds, these explicitly link the planning horizon, uncertainty and
the need for exploration explicit. The resulting algorithm can be seen as a
generalisation of the classical Thompson sampling algorithm. We experimentally
test these algorithms, as well as $\epsilon$-greedy and the value of perfect
information heuristics. Finally, we also introduce the idea of bagging for
reinforcement learning. By employing a version of online bootstrapping, we can
efficiently sample from an approximate posterior distribution.


title: Semi-Supervised Learning -- A Statistical Physics Approach

abstract:
  We present a novel approach to semi-supervised learning which is based on
statistical physics. Most of the former work in the field of semi-supervised
learning classifies the points by minimizing a certain energy function, which
corresponds to a minimal k-way cut solution. In contrast to these methods, we
estimate the distribution of classifications, instead of the sole minimal k-way
cut, which yields more accurate and robust results. Our approach may be applied
to all energy functions used for semi-supervised learning. The method is based
on sampling using a Multicanonical Markov chain Monte-Carlo algorithm, and has
a straightforward probabilistic interpretation, which allows for soft
assignments of points to classes, and also to cope with yet unseen class types.
The suggested approach is demonstrated on a toy data set and on two real-life
data sets of gene expression.


title: The Aryabhata Algorithm Using Least Absolute Remainders

abstract:
  This paper presents an introduction to the Aryabhata algorithm for finding
multiplicative inverses and solving linear congruences, both of which have
applications in cryptography. We do so by the use of the least absolute
remainders. The exposition of the Aryabhata algorithm provided here can have
performance that could exceed what was described recently by Rao and Yang.


title: On Covering a Graph Optimally with Induced Subgraphs

abstract:
  We consider the problem of covering a graph with a given number of induced
subgraphs so that the maximum number of vertices in each subgraph is minimized.
We prove NP-completeness of the problem, prove lower bounds, and give
approximation algorithms for certain graph classes.


title: Towards Analog Reverse Time Computation

abstract:
  We report the consequences of a destabilization process on a simulated
General Purpose Analog Computer. This new technology overcomes problems linked
with serial ambiguity, and provides an analog bias to encode algorithms whose
complexity is over polynomial. We also implicitly demonstrate how
countermesures of the Stochastic Aperture Degeneracy could efficiently reach
higher computational classes, and would open a road towards Analog Reverse Time
Computation.


title: Revealing the Autonomous System Taxonomy: The Machine Learning Approach

abstract:
  Although the Internet AS-level topology has been extensively studied over the
past few years, little is known about the details of the AS taxonomy. An AS
"node" can represent a wide variety of organizations, e.g., large ISP, or small
private business, university, with vastly different network characteristics,
external connectivity patterns, network growth tendencies, and other properties
that we can hardly neglect while working on veracious Internet representations
in simulation environments. In this paper, we introduce a radically new
approach based on machine learning techniques to map all the ASes in the
Internet into a natural AS taxonomy. We successfully classify 95.3% of ASes
with expected accuracy of 78.1%. We release to the community the AS-level
topology dataset augmented with: 1) the AS taxonomy information and 2) the set
of AS attributes we used to classify ASes. We believe that this dataset will
serve as an invaluable addition to further understanding of the structure and
evolution of the Internet.


title: On Conditional Branches in Optimal Search Trees

abstract:
  Algorithms for efficiently finding optimal alphabetic decision trees -- such
as the Hu-Tucker algorithm -- are well established and commonly used. However,
such algorithms generally assume that the cost per decision is uniform and thus
independent of the outcome of the decision. The few algorithms without this
assumption instead use one cost if the decision outcome is ``less than'' and
another cost otherwise. In practice, neither assumption is accurate for
software optimized for today's microprocessors. Such software generally has one
cost for the more likely decision outcome and a greater cost -- often far
greater -- for the less likely decision outcome. This problem and
generalizations thereof are thus applicable to hard coding static decision tree
instances in software, e.g., for optimizing program bottlenecks or for
compiling switch statements. An O(n^3)-time O(n^2)-space dynamic programming
algorithm can solve this optimal binary decision tree problem, and this
approach has many generalizations that optimize for the behavior of processors
with predictive branch capabilities, both static and dynamic. Solutions to this
formulation are often faster in practice than ``optimal'' decision trees as
formulated in the literature. Different search paradigms can sometimes yield
even better performance.


title: AS Relationships: Inference and Validation

abstract:
  Research on performance, robustness, and evolution of the global Internet is
fundamentally handicapped without accurate and thorough knowledge of the nature
and structure of the contractual relationships between Autonomous Systems
(ASs). In this work we introduce novel heuristics for inferring AS
relationships. Our heuristics improve upon previous works in several technical
aspects, which we outline in detail and demonstrate with several examples.
Seeking to increase the value and reliability of our inference results, we then
focus on validation of inferred AS relationships. We perform a survey with ASs'
network administrators to collect information on the actual connectivity and
policies of the surveyed ASs. Based on the survey results, we find that our new
AS relationship inference techniques achieve high levels of accuracy: we
correctly infer 96.5% customer to provider (c2p), 82.8% peer to peer (p2p), and
90.3% sibling to sibling (s2s) relationships. We then cross-compare the
reported AS connectivity with the AS connectivity data contained in BGP tables.
We find that BGP tables miss up to 86.2% of the true adjacencies of the
surveyed ASs. The majority of the missing links are of the p2p type, which
highlights the limitations of present measuring techniques to capture links of
this type. Finally, to make our results easily accessible and practically
useful for the community, we open an AS relationship repository where we
archive, on a weekly basis, and make publicly available the complete Internet
AS-level topology annotated with AS relationship information for every pair of
AS neighbors.


title: Cryptographic Pseudo-Random Sequences from the Chaotic Henon Map

abstract:
  A scheme for pseudo-random binary sequence generation based on the
two-dimensional discrete-time Henon map is proposed. Properties of the proposed
sequences pertaining to linear complexity, linear complexity profile,
correlation and auto-correlation are investigated. All these properties of the
sequences suggest a strong resemblance to random sequences. Results of
statistical testing of the sequences are found encouraging. An attempt is made
to estimate the keyspace size if the proposed scheme is used for cryptographic
applications. The keyspace size is found to be large and is dependent on the
precision of the computing platform used.


title:
The Case for Modeling Security, Privacy, Usability and Reliability
  (SPUR) in Automotive Software

abstract:
  Over the past five years, there has been considerable growth and established
value in the practice of modeling automotive software requirements. Much of
this growth has been centered on requirements of software associated with the
established functional areas of an automobile, such as those associated with
powertrain, chassis, body, safety and infotainment. This paper makes a case for
modeling four additional attributes that are increasingly important as vehicles
become information conduits: security, privacy, usability, and reliability.
These four attributes are important in creating specifications for embedded
in-vehicle automotive software.


title:
Approximation Algorithms for Restricted Cycle Covers Based on Cycle
  Decompositions

abstract:
  A cycle cover of a graph is a set of cycles such that every vertex is part of
exactly one cycle. An L-cycle cover is a cycle cover in which the length of
every cycle is in the set L. The weight of a cycle cover of an edge-weighted
graph is the sum of the weights of its edges.
  We come close to settling the complexity and approximability of computing
L-cycle covers. On the one hand, we show that for almost all L, computing
L-cycle covers of maximum weight in directed and undirected graphs is APX-hard
and NP-hard. Most of our hardness results hold even if the edge weights are
restricted to zero and one.
  On the other hand, we show that the problem of computing L-cycle covers of
maximum weight can be approximated within a factor of 2 for undirected graphs
and within a factor of 8/3 in the case of directed graphs. This holds for
arbitrary sets L.


title:
Low Latency Wireless Ad-Hoc Networking: Power and Bandwidth Challenges
  and a Hierarchical Solution

abstract:
  This paper is concerned with the scaling of the number of hops in a large
scale wireless ad-hoc network (WANET), a quantity we call network latency. A
large network latency affects all aspects of data communication in a WANET,
including an increase in delay, packet loss, required processing power and
memory. We consider network management and data routing challenges in WANETs
with scalable network latency. On the physical side, reducing network latency
imposes a significantly higher power and bandwidth demand on nodes, as is
reflected in a set of new bounds. On the protocol front, designing distributed
routing protocols that can guarantee the delivery of data packets within
scalable number of hops is a challenging task. To solve this, we introduce
multi-resolution randomized hierarchy (MRRH), a novel power and bandwidth
efficient WANET protocol with scalable network latency. MRRH uses a randomized
algorithm for building and maintaining a random hierarchical network topology,
which together with the proposed routing algorithm can guarantee efficient
delivery of data packets in the wireless network. For a network of size $N$,
MRRH can provide an average latency of only $O(\log^{3} N)$. The power and
bandwidth consumption of MRRH are shown to be \emph{nearly} optimal for the
latency it provides. Therefore, MRRH, is a provably efficient candidate for
truly large scale wireless ad-hoc networking.


title: Locked and Unlocked Chains of Planar Shapes

abstract:
  We extend linkage unfolding results from the well-studied case of polygonal
linkages to the more general case of linkages of polygons. More precisely, we
consider chains of nonoverlapping rigid planar shapes (Jordan regions) that are
hinged together sequentially at rotatable joints. Our goal is to characterize
the families of planar shapes that admit locked chains, where some
configurations cannot be reached by continuous reconfiguration without
self-intersection, and which families of planar shapes guarantee universal
foldability, where every chain is guaranteed to have a connected configuration
space. Previously, only obtuse triangles were known to admit locked shapes, and
only line segments were known to guarantee universal foldability. We show that
a surprisingly general family of planar shapes, called slender adornments,
guarantees universal foldability: roughly, the distance from each edge along
the path along the boundary of the slender adornment to each hinge should be
monotone. In contrast, we show that isosceles triangles with any desired apex
angle less than 90 degrees admit locked chains, which is precisely the
threshold beyond which the inward-normal property no longer holds.


title: Communication Bottlenecks in Scale-Free Networks

abstract:
  We consider the effects of network topology on the optimality of packet
routing quantified by $\gamma_c$, the rate of packet insertion beyond which
congestion and queue growth occurs. The key result of this paper is to show
that for any network, there exists an absolute upper bound, expressed in terms
of vertex separators, for the scaling of $\gamma_c$ with network size $N$,
irrespective of the routing algorithm used. We then derive an estimate to this
upper bound for scale-free networks, and introduce a novel static routing
protocol which is superior to shortest path routing under intense packet
insertion rates.


title:
Cohomology in Grothendieck Topologies and Lower Bounds in Boolean
  Complexity II: A Simple Example

abstract:
  In a previous paper we have suggested a number of ideas to attack circuit
size complexity with cohomology. As a simple example, we take circuits that can
only compute the AND of two inputs, which essentially reduces to SET COVER. We
show a very special case of the cohomological approach (one particular free
category, using injective and superskyscraper sheaves) gives the linear
programming bound coming from the relaxation of the standard integer
programming reformulation of SET COVER.


title:
An Extremal Inequality Motivated by Multiterminal Information Theoretic
  Problems

abstract:
  We prove a new extremal inequality, motivated by the vector Gaussian
broadcast channel and the distributed source coding with a single quadratic
distortion constraint problems. As a corollary, this inequality yields a
generalization of the classical entropy-power inequality (EPI). As another
corollary, this inequality sheds insight into maximizing the differential
entropy of the sum of two dependent random variables.


title: APHRODITE: an Anomaly-based Architecture for False Positive Reduction

abstract:
  We present APHRODITE, an architecture designed to reduce false positives in
network intrusion detection systems. APHRODITE works by detecting anomalies in
the output traffic, and by correlating them with the alerts raised by the NIDS
working on the input traffic. Benchmarks show a substantial reduction of false
positives and that APHRODITE is effective also after a "quick setup", i.e. in
the realistic case in which it has not been "trained" and set up optimally


title:
Unification of multi-lingual scientific terminological resources using
  the ISO 16642 standard. The TermSciences initiative

abstract:
  This paper presents the TermSciences portal, which deals with the
implementation of a conceptual model that uses the recent ISO 16642 standard
(Terminological Markup Framework). This standard turns out to be suitable for
concept modeling since it allowed for organizing the original resources by
concepts and to associate the various terms for a given concept. Additional
structuring is produced by sharing conceptual relationships, that is,
cross-linking of resource results through the introduction of semantic
relations which may have initially be missing.


title:
Two Proofs of the Fisher Information Inequality via Data Processing
  Arguments

abstract:
  Two new proofs of the Fisher information inequality (FII) using data
processing inequalities for mutual information and conditional variance are
presented.


title:
Order-Optimal Data Aggregation in Wireless Sensor Networks - Part I:
  Regular Networks

abstract:
  The predominate traffic patterns in a wireless sensor network are many-to-one
and one-to-many communication. Hence, the performance of wireless sensor
networks is characterized by the rate at which data can be disseminated from or
aggregated to a data sink. In this paper, we consider the data aggregation
problem. We demonstrate that a data aggregation rate of O(log(n)/n) is optimal
and that this rate can be achieved in wireless sensor networks using a
generalization of cooperative beamforming called cooperative time-reversal
communication.


title:
The Influence of Adaptive Multicoding on Mutual Information and Channel
  Capacity for Uncertain Wideband CDMA Rayleigh Fading Channels

abstract:
  We consider the problem of adaptive modulation for wideband DS-CDMA Rayleigh
fading channels with imperfect channel state information (CSI). We assume a
multidimensional signal subspace spanned by a collection of random spreading
codes (multicoding) and study the effects of both the subspace dimension and
the probability distribution of the transmitted symbols on the mutual
information between the channel input and output in the presence of uncertainty
regarding the true state of the channel. We develop approximations for the
mutual information as well as both upper and lower bounds on the mutual
information that are stated explicitly in terms of the dimension of the signal
constellation, the number of resolvable fading paths on the channel, the
current estimate of channel state, and the mean-squared-error of the channel
estimate. We analyze these approximations and bounds in order to quantify the
impact of signal dimension and symbol distribution on system performance.


title:
On the Low SNR Capacity of Peak-Limited Non-Coherent Fading Channels
  with Memory

abstract:
  The capacity of non-coherent stationary Gaussian fading channels with memory
under a peak-power constraint is studied in the asymptotic weak-signal regime.
It is assumed that the fading law is known to both transmitter and receiver but
that neither is cognizant of the fading realization. A connection is
demonstrated between the asymptotic behavior of channel capacity in this regime
and the asymptotic behavior of the prediction error incurred in predicting the
fading process from very noisy observations of its past. This connection can be
viewed as the low signal-to-noise ratio (SNR) analog of recent results by
Lapidoth & Moser and by Lapidoth demonstrating connections between the high SNR
capacity growth and the noiseless or almost-noiseless prediction error. We
distinguish between two families of fading laws: the ``slowly forgetting'' and
the ``quickly forgetting''. For channels in the former category the low SNR
capacity is achieved by IID inputs, whereas in the latter such inputs are
typically sub-optimal. Instead, the asymptotic capacity can be approached by
inputs with IID phase but block-constant magnitude.


title:
Real Computational Universality: The Word Problem for a class of groups
  with infinite presentation

abstract:
  The word problem for discrete groups is well-known to be undecidable by a
Turing Machine; more precisely, it is reducible both to and from and thus
equivalent to the discrete Halting Problem.
  The present work introduces and studies a real extension of the word problem
for a certain class of groups which are presented as quotient groups of a free
group and a normal subgroup. Most important, the free group will be generated
by an uncountable set of generators with index running over certain sets of
real numbers. This allows to include many mathematically important groups which
are not captured in the framework of the classical word problem.
  Our contribution extends computational group theory from the discrete to the
Blum-Shub-Smale (BSS) model of real number computation. We believe this to be
an interesting step towards applying BSS theory, in addition to semi-algebraic
geometry, also to further areas of mathematics.
  The main result establishes the word problem for such groups to be not only
semi-decidable (and thus reducible FROM) but also reducible TO the Halting
Problem for such machines. It thus provides the first non-trivial example of a
problem COMPLETE, that is, computationally universal for this model.


title:
Statistical Properties of Eigen-Modes and Instantaneous Mutual
  Information in MIMO Time-Varying Rayleigh Channels

abstract:
  In this paper, we study two important metrics in multiple-input
multiple-output (MIMO) time-varying Rayleigh flat fading channels. One is the
eigen-mode, and the other is the instantaneous mutual information (IMI). Their
second-order statistics, such as the correlation coefficient, level crossing
rate (LCR), and average fade/outage duration, are investigated, assuming a
general nonisotropic scattering environment. Exact closed-form expressions are
derived and Monte Carlo simulations are provided to verify the accuracy of the
analytical results. For the eigen-modes, we found they tend to be
spatio-temporally uncorrelated in large MIMO systems. For the IMI, the results
show that its correlation coefficient can be well approximated by the squared
amplitude of the correlation coefficient of the channel, under certain
conditions. Moreover, we also found the LCR of IMI is much more sensitive to
the scattering environment than that of each eigen-mode.


title:
Squarepants in a Tree: Sum of Subtree Clustering and Hyperbolic Pants
  Decomposition

abstract:
  We provide efficient constant factor approximation algorithms for the
problems of finding a hierarchical clustering of a point set in any metric
space, minimizing the sum of minimimum spanning tree lengths within each
cluster, and in the hyperbolic or Euclidean planes, minimizing the sum of
cluster perimeters. Our algorithms for the hyperbolic and Euclidean planes can
also be used to provide a pants decomposition, that is, a set of disjoint
simple closed curves partitioning the plane minus the input points into subsets
with exactly three boundary components, with approximately minimum total
length. In the Euclidean case, these curves are squares; in the hyperbolic
case, they combine our Euclidean square pants decomposition with our tree
clustering method for general metric spaces.


title: Certain new M-matrices and their properties and applications

abstract:
  The Mn-matrix was defined by Mohan [20] in which he has shown a method of
constructing (1,-1)-matrices and studied some of their properties. The
(1,-1)-matrices were constructed and studied by Cohn [5],Wang [33], Ehrlich [8]
and Ehrlich and Zeller[9]. But in this paper, while giving some resemblances of
this matrix with Hadamard matrix, and by naming it as M-matrix, we show how to
construct partially balanced incomplete block (PBIB) designs and some regular
bipartite graphs by it. We have considered two types of these M- matrices. Also
we will make a mention of certain applications of these M-matrices in signal
and communication processing, and network systems and end with some open
problems.


title: Collaborative thesaurus tagging the Wikipedia way

abstract:
  This paper explores the system of categories that is used to classify
articles in Wikipedia. It is compared to collaborative tagging systems like
del.icio.us and to hierarchical classification like the Dewey Decimal
Classification (DDC). Specifics and commonalitiess of these systems of subject
indexing are exposed. Analysis of structural and statistical properties
(descriptors per record, records per descriptor, descriptor levels) shows that
the category system of Wikimedia is a thesaurus that combines collaborative
tagging and hierarchical subject indexing in a special way.


title: An O(n^3)-Time Algorithm for Tree Edit Distance

abstract:
  The {\em edit distance} between two ordered trees with vertex labels is the
minimum cost of transforming one tree into the other by a sequence of
elementary operations consisting of deleting and relabeling existing nodes, as
well as inserting new nodes. In this paper, we present a worst-case
$O(n^3)$-time algorithm for this problem, improving the previous best
$O(n^3\log n)$-time algorithm~\cite{Klein}. Our result requires a novel
adaptive strategy for deciding how a dynamic program divides into subproblems
(which is interesting in its own right), together with a deeper understanding
of the previous algorithms for the problem. We also prove the optimality of our
algorithm among the family of \emph{decomposition strategy} algorithms--which
also includes the previous fastest algorithms--by tightening the known lower
bound of $\Omega(n^2\log^2 n)$~\cite{Touzet} to $\Omega(n^3)$, matching our
algorithm's running time. Furthermore, we obtain matching upper and lower
bounds of $\Theta(n m^2 (1 + \log \frac{n}{m}))$ when the two trees have
different sizes $m$ and~$n$, where $m < n$.


title: UniCalc.LIN: a linear constraint solver for the UniCalc system

abstract:
  In this short paper we present a linear constraint solver for the UniCalc
system, an environment for reliable solution of mathematical modeling problems.


title: A Fixed-Point Type for Octave

abstract:
  This paper announces the availability of a fixed point toolbox for the Matlab
compatible software package Octave. This toolbox is released under the GNU
Public License, and can be used to model the losses in algorithms implemented
in hardware. Furthermore, this paper presents as an example of the use of this
toolbox, the effects of a fixed point implementation on the precision of an
OFDM modulator.


title:
Optimal Distortion-Power Tradeoffs in Sensor Networks: Gauss-Markov
  Random Processes

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 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 stationary and
Gaussian. In the case where the random process is also Markovian, we evaluate
the lower and upper bounds explicitly and show that they are of the same order
for a wide range of sum power constraints. Thus, for a Gauss-Markov random
process, under these sum power constraints, we determine the achievability
scheme that is order-optimal, and express the minimum achievable expected
distortion as a function of the sum power constraint.


title: On Orthogonality of Latin Squares

abstract:
  An arrangement of s elements in s rows and s columns, such that no element
repeats more than once in each row and each column is called a Latin square of
order s. If two Latin squares of the same order superimposed one on the other
and in the resultant array if each ordered pair occurs once and only once then
they are called othogonal Latin Squares. A frequency square is an nxn matrix,
such that each element from the list of n elements, occurs t times in each row
and in each column. These two concepts lead to a new third concept called as t
orthogonal latin squares, where from a set of m orthogonal Latin squares, if t
orthogonal Latin squares are superimposed and each ordered t tuple in the
resultant array occurs once and only once then it is t othogonal Latin square.
In this paper it is proposed to construct such t othogonal latin squares


title:
Adaptative combination rule and proportional conflict redistribution
  rule for information fusion

abstract:
  This paper presents two new promising rules of combination for the fusion of
uncertain and potentially highly conflicting sources of evidences in the
framework of the theory of belief functions in order to palliate the well-know
limitations of Dempster's rule and to work beyond the limits of applicability
of the Dempster-Shafer theory. We present both a new class of adaptive
combination rules (ACR) and a new efficient Proportional Conflict
Redistribution (PCR) rule allowing to deal with highly conflicting sources for
static and dynamic fusion applications.


title: Demand-driven Inlining in a Region-based Optimizer for ILP Architectures

abstract:
  Region-based compilation repartitions a program into more desirable
compilation units using profiling information and procedure inlining to enable
region formation analysis. Heuristics play a key role in determining when it is
most beneficial to inline procedures during region formation. An ILP optimizing
compiler using a region-based approach restructures a program to better reflect
dynamic behavior and increase interprocedural optimization and scheduling
opportunities. This paper presents an interprocedural compilation technique
which performs procedure inlining on-demand, rather than as a separate phase,
to improve the ability of a region-based optimizer to control code growth,
compilation time and memory usage while improving performance. The
interprocedural region formation algorithm utilizes a demand-driven,
heuristics-guided approach to inlining, restructuring an input program into
interprocedural regions. Experimental results are presented to demonstrate the
impact of the algorithm and several inlining heuristics upon a number of
traditional and novel compilation characteristics within a region-based ILP
compiler and simulator.


title: A new M-matrix of Type III, its properties and applications

abstract:
  Some binary matrices like (1,-1) and (1,0) were studied by many authors like
Cohn, Wang, Ehlich and Ehlich and Zeller, and Mohan, Kageyama, Lee, and Gao. In
this recent paper by Mohan et al considered the M-matrices of Type I and II by
studying some of their properties and applications. In the present paper they
discussed the M-matrices of Type III, and studied their properties and
applications. They gave some constructions of SPBIB designs and some
corresponding M-graphs, which are being constructed by it. This is the
continuation of our earlier research work in this direction, and these papers
establish the importance of non-orthogonal matrices as well.


title: An exact algorithm for higher-dimensional orthogonal packing

abstract:
  Higher-dimensional orthogonal packing problems have a wide range of practical
applications, including packing, cutting, and scheduling. Combining the use of
our data structure for characterizing feasible packings with our new classes of
lower bounds, and other heuristics, we develop a two-level tree search
algorithm for solving higher-dimensional packing problems to optimality.
Computational results are reported, including optimal solutions for all
two--dimensional test problems from recent literature.
  This is the third in a series of articles describing new approaches to
higher-dimensional packing; see cs.DS/0310032 and cs.DS/0402044.


title:
Concerning the differentiability of the energy function in vector
  quantization algorithms

abstract:
  The adaptation rule for Vector Quantization algorithms, and consequently the
convergence of the generated sequence, depends on the existence and properties
of a function called the energy function, defined on a topological manifold.
Our aim is to investigate the conditions of existence of such a function for a
class of algorithms examplified by the initial ''K-means'' and Kohonen
algorithms. The results presented here supplement previous studies and show
that the energy function is not always a potential but at least the uniform
limit of a series of potential functions which we call a pseudo-potential. Our
work also shows that a large number of existing vector quantization algorithms
developped by the Artificial Neural Networks community fall into this category.
The framework we define opens the way to study the convergence of all the
corresponding adaptation rules at once, and a theorem gives promising insights
in that direction. We also demonstrate that the ''K-means'' energy function is
a pseudo-potential but not a potential in general. Consequently, the energy
function associated to the ''Neural-Gas'' is not a potential in general.


title:
Efficient algorithms for deciding the type of growth of products of
  integer matrices

abstract:
  For a given finite set $\Sigma$ of matrices with nonnegative integer entries
we study the growth of $$ \max_t(\Sigma) = \max\{\|A_{1}... A_{t}\|: A_i \in
\Sigma\}.$$ We show how to determine in polynomial time whether the growth with
$t$ is bounded, polynomial, or exponential, and we characterize precisely all
possible behaviors.


title:
Will the Butterfly Cipher keep your Network Data secure? Developments in
  Computer Encryption

abstract:
  This paper explains the recent developments in security and encryption. The
Butterfly cipher and quantum cryptography are reviewed and compared. Examples
of their relative uses are discussed and suggestions for future developments
considered. In addition application to network security together with a
substantial review of classification of encryption systems and a summary of
security weaknesses are considered.


title:
Low SNR Capacity of Fading Channels with Peak and Average Power
  Constraints

abstract:
  Flat-fading channels that are correlated in time are considered under peak
and average power constraints. For discrete-time channels, a new upper bound on
the capacity per unit time is derived. A low SNR analysis of a full-scattering
vector channel is used to derive a complimentary lower bound. Together, these
bounds allow us to identify the exact scaling of channel capacity for a fixed
peak to average ratio, as the average power converges to zero. The upper bound
is also asymptotically tight as the average power converges to zero for a fixed
peak power.
  For a continuous time infinite bandwidth channel, Viterbi identified the
capacity for M-FSK modulation. Recently, Zhang and Laneman showed that the
capacity can be achieved with non-bursty signaling (QPSK). An additional
contribution of this paper is to obtain similar results under peak and average
power constraints.


title: On Hadamard Conjecture

abstract:
  In this note, while giving an overview of the state of art of the well known
Hadamard conjecture, which is more than a century old and now it has been
established by using the methods given in the two papers by Mohan et al [6,7].


title: Structural Alignments of pseudo-knotted RNA-molecules in polynomial time

abstract:
  An RNA molecule is structured on several layers. The primary and most obvious
structure is its sequence of bases, i.e. a word over the alphabet {A,C,G,U}.
The higher structure is a set of one-to-one base-pairings resulting in a
two-dimensional folding of the one-dimensional sequence. One speaks of a
secondary structure if these pairings do not cross and of a tertiary structure
otherwise.
  Since the folding of the molecule is important for its function, the search
for related RNA molecules should not only be restricted to the primary
structure. It seems sensible to incorporate the higher structures in the
search. Based on this assumption and certain edit-operations a distance between
two arbitrary structures can be defined. It is known that the general
calculation of this measure is NP-complete \cite{zhang02similarity}. But for
some special cases polynomial algorithms are known. Using a new formal
description of secondary and tertiary structures, we extend the class of
structures for which the distance can be calculated in polynomial time. In
addition the presented algorithm may be used to approximate the edit-distance
between two arbitrary structures with a constant ratio.


title:
Extension of the functionality of the symbolic program FORM by external
  software

abstract:
  We describe the implementation of facilities for the communication with
external resources in the Symbolic Manipulation System FORM. This is done
according to the POSIX standards defined for the UNIX operating system. We
present a number of examples that illustrate the increased power due to these
new capabilities.


title:
Survivable Routing in IP-over-WDM Networks in the Presence of Multiple
  Failures

abstract:
  Failure restoration at the IP layer in IP-over-WDM networks requires to map
the IP topology on the WDM topology in such a way that a failure at the WDM
layer leaves the IP topology connected. Such a mapping is called $survivable$.
As finding a survivable mapping is known to be NP-complete, in practice it
requires a heuristic approach. We have introduced in [1] a novel algorithm
called ``SMART'', that is more effective and scalable than the heuristics known
to date. Moreover, the formal analysis of SMART [2] has led to new
applications: the formal verification of the existence of a survivable mapping,
and a tool tracing and repairing the vulnerable areas of the network. In this
paper we extend the theoretical analysis in [2] by considering $multiple
failures$.


title: New results on rewrite-based satisfiability procedures

abstract:
  Program analysis and verification require decision procedures to reason on
theories of data structures. Many problems can be reduced to the satisfiability
of sets of ground literals in theory T. If a sound and complete inference
system for first-order logic is guaranteed to terminate on T-satisfiability
problems, any theorem-proving strategy with that system and a fair search plan
is a T-satisfiability procedure. We prove termination of a rewrite-based
first-order engine on the theories of records, integer offsets, integer offsets
modulo and lists. We give a modularity theorem stating sufficient conditions
for termination on a combinations of theories, given termination on each. The
above theories, as well as others, satisfy these conditions. We introduce
several sets of benchmarks on these theories and their combinations, including
both parametric synthetic benchmarks to test scalability, and real-world
problems to test performances on huge sets of literals. We compare the
rewrite-based theorem prover E with the validity checkers CVC and CVC Lite.
Contrary to the folklore that a general-purpose prover cannot compete with
reasoners with built-in theories, the experiments are overall favorable to the
theorem prover, showing that not only the rewriting approach is elegant and
conceptually simple, but has important practical implications.


title:
Beyond Hirsch Conjecture: walks on random polytopes and smoothed
  complexity of the simplex method

abstract:
  The smoothed analysis of algorithms is concerned with the expected running
time of an algorithm under slight random perturbations of arbitrary inputs.
Spielman and Teng proved that the shadow-vertex simplex method has polynomial
smoothed complexity. On a slight random perturbation of an arbitrary linear
program, the simplex method finds the solution after a walk on polytope(s) with
expected length polynomial in the number of constraints n, the number of
variables d and the inverse standard deviation of the perturbation 1/sigma.
  We show that the length of walk in the simplex method is actually
polylogarithmic in the number of constraints n. Spielman-Teng's bound on the
walk was O(n^{86} d^{55} sigma^{-30}), up to logarithmic factors. We improve
this to O(log^7 n (d^9 + d^3 \s^{-4})). This shows that the tight Hirsch
conjecture n-d on the length of walk on polytopes is not a limitation for the
smoothed Linear Programming. Random perturbations create short paths between
vertices.
  We propose a randomized phase-I for solving arbitrary linear programs, which
is of independent interest. Instead of finding a vertex of a feasible set, we
add a vertex at random to the feasible set. This does not affect the solution
of the linear program with constant probability. This overcomes one of the
major difficulties of smoothed analysis of the simplex method -- one can now
statistically decouple the walk from the smoothed linear program. This yields a
much better reduction of the smoothed complexity to a geometric quantity -- the
size of planar sections of random polytopes. We also improve upon the known
estimates for that size, showing that it is polylogarithmic in the number of
vertices.


title: A Short Note on The Volume of Hypersphere

abstract:
  In this note, a new method for deriving the volume of hypersphere is proposed
by using probability theory. The explicit expression of the multiple times
convolution of the probability density functions we should use is very
complicated. But in here, we don't need its whole explicit expression. We just
need the only a part of information and this fact make it possible to derive
the general expression of the voulume of hypersphere. We also comments about
the paradox in the hypersphere which was introduced by R.W.Hamming.


title: A New Fault-Tolerant M-network and its Analysis

abstract:
  This paper introduces a new class of efficient inter connection networks
called as M-graphs for large multi-processor systems.The concept of M-matrix
and M-graph is an extension of Mn-matrices and Mn-graphs.We analyze these
M-graphs regarding their suitability for large multi-processor systems. An(p,N)
M-graph consists of N nodes, where p is the degree of each node.The topology is
found to be having many attractive features prominent among them is the
capability of maximal fault-tolerance, high density and constant diameter.It is
found that these combinatorial structures exibit some properties like
symmetry,and an inter-relation with the nodes, and degree of the concerned
graph, which can be utilized for the purposes of inter connected networks.But
many of the properties of these mathematical and graphical structures still
remained unexplored and the present aim of the paper is to study and analyze
some of the properties of these M-graphs and explore their application in
networks and multi-processor systems.


title: Solving Classical String Problems on Compressed Texts

abstract:
  Here we study the complexity of string problems as a function of the size of
a program that generates input. We consider straight-line programs (SLP), since
all algorithms on SLP-generated strings could be applied to processing
LZ-compressed texts.
  The main result is a new algorithm for pattern matching when both a text T
and a pattern P are presented by SLPs (so-called fully compressed pattern
matching problem). We show how to find a first occurrence, count all
occurrences, check whether any given position is an occurrence or not in time
O(n^2m). Here m,n are the sizes of straight-line programs generating
correspondingly P and T.
  Then we present polynomial algorithms for computing fingerprint table and
compressed representation of all covers (for the first time) and for finding
periods of a given compressed string (our algorithm is faster than previously
known). On the other hand, we show that computing the Hamming distance between
two SLP-generated strings is NP- and coNP-hard.


title:
Inner and Outer Rounding of Boolean Operations on Lattice Polygonal
  Regions

abstract:
  Robustness problems due to the substitution of the exact computation on real
numbers by the rounded floating point arithmetic are often an obstacle to
obtain practical implementation of geometric algorithms. If the adoption of the
--exact computation paradigm--[Yap et Dube] gives a satisfactory solution to
this kind of problems for purely combinatorial algorithms, this solution does
not allow to solve in practice the case of algorithms that cascade the
construction of new geometric objects. In this report, we consider the problem
of rounding the intersection of two polygonal regions onto the integer lattice
with inclusion properties. Namely, given two polygonal regions A and B having
their vertices on the integer lattice, the inner and outer rounding modes
construct two polygonal regions with integer vertices which respectively is
included and contains the true intersection. We also prove interesting results
on the Hausdorff distance, the size and the convexity of these polygonal
regions.


title:
Polynomial Time Nondimensionalisation of Ordinary Differential Equations
  via their Lie Point Symmetries

abstract:
  Lie group theory states that knowledge of a $m$-parameters solvable group of
symmetries of a system of ordinary differential equations allows to reduce by
$m$ the number of equation. We apply this principle by finding dilatations and
translations that are Lie point symmetries of considered ordinary differential
system. By rewriting original problem in an invariant coordinates set for these
symmetries, one can reduce the involved number of parameters. This process is
classically call nondimensionalisation in dimensional analysis. We present an
algorithm based on this standpoint and show that its arithmetic complexity is
polynomial in input's size.


title: Effect of E-printing on Citation Rates in Astronomy and Physics

abstract:
  In this report we examine the change in citation behavior since the
introduction of the arXiv e-print repository (Ginsparg, 2001). It has been
observed that papers that initially appear as arXiv e-prints get cited more
than papers that do not (Lawrence, 2001; Brody et al., 2004; Schwarz &
Kennicutt, 2004; Kurtz et al., 2005a, Metcalfe, 2005). Using the citation
statistics from the NASA-Smithsonian Astrophysics Data System (ADS; Kurtz et
al., 1993, 2000), we confirm the findings from other studies, we examine the
average citation rate to e-printed papers in the Astrophysical Journal, and we
show that for a number of major astronomy and physics journals the most
important papers are submitted to the arXiv e-print repository first.


title:
Biologically Inspired Hierarchical Model for Feature Extraction and
  Localization

abstract:
  Feature extraction and matching are among central problems of computer
vision. It is inefficent to search features over all locations and scales.
Neurophysiological evidence shows that to locate objects in a digital image the
human visual system employs visual attention to a specific object while
ignoring others. The brain also has a mechanism to search from coarse to fine.
In this paper, we present a feature extractor and an associated hierarchical
searching model to simulate such processes. With the hierarchical
representation of the object, coarse scanning is done through the matching of
the larger scale and precise localization is conducted through the matching of
the smaller scale. Experimental results justify the proposed model in its
effectiveness and efficiency to localize features.


title: Golden Space-Time Trellis Coded Modulation

abstract:
  In this paper, we present a concatenated coding scheme for a high rate
$2\times 2$ multiple-input multiple-output (MIMO) system over slow fading
channels. The inner code is the Golden code \cite{Golden05} and the outer code
is a trellis code. Set partitioning of the Golden code is designed specifically
to increase the minimum determinant. The branches of the outer trellis code are
labeled with these partitions. Viterbi algorithm is applied for trellis
decoding. In order to compute the branch metrics a lattice sphere decoder is
used. The general framework for code optimization is given. The performance of
the proposed concatenated scheme is evaluated by simulation. It is shown that
the proposed scheme achieves significant performance gains over uncoded Golden
code.


title: Quantum Fuzzy Sets: Blending Fuzzy Set Theory and Quantum Computation

abstract:
  In this article we investigate a way in which quantum computing can be used
to extend the class of fuzzy sets. The core idea is to see states of a quantum
register as characteristic functions of quantum fuzzy subsets of a given set.
As the real unit interval is embedded in the Bloch sphere, every fuzzy set is
automatically a quantum fuzzy set. However, a generic quantum fuzzy set can be
seen as a (possibly entangled) superposition of many fuzzy sets at once,
offering new opportunities for modeling uncertainty. After introducing the main
framework of quantum fuzzy set theory, we analyze the standard operations of
fuzzification and defuzzification from our viewpoint. We conclude this
preliminary paper with a list of possible applications of quantum fuzzy sets to
pattern recognition, as well as future directions of pure research in quantum
fuzzy set theory.


title: Unifying two Graph Decompositions with Modular Decomposition

abstract:
  We introduces the umodules, a generalisation of the notion of graph module.
The theory we develop captures among others undirected graphs, tournaments,
digraphs, and $2-$structures. We show that, under some axioms, a unique
decomposition tree exists for umodules. Polynomial-time algorithms are provided
for: non-trivial umodule test, maximal umodule computation, and decomposition
tree computation when the tree exists. Our results unify many known
decomposition like modular and bi-join decomposition of graphs, and a new
decomposition of tournaments.


title: Univariate polynomial real root isolation: Continued Fractions revisited

abstract:
  We present algorithmic, complexity and implementation results concerning real
root isolation of integer univariate polynomials using the continued fraction
expansion of real algebraic numbers. One motivation is to explain the method's
good performance in practice. We improve the previously known bound by a factor
of $d \tau$, where $d$ is the polynomial degree and $\tau$ bounds the
coefficient bitsize, thus matching the current record complexity for real root
isolation by exact methods. Namely, the complexity bound is $\sOB(d^4 \tau^2)$
using the standard bound on the expected bitsize of the integers in the
continued fraction expansion. We show how to compute the multiplicities within
the same complexity and extend the algorithm to non square-free polynomials.
Finally, we present an efficient open-source \texttt{C++} implementation in the
algebraic library \synaps, and illustrate its efficiency as compared to other
available software. We use polynomials with coefficient bitsize up to 8000 and
degree up to 1000.


title: Certain t-partite graphs

abstract:
  By making use of the generalized concept of orthogonality in Latin squares,
certain t-partite graphs have been constructed and a suggestion for a net work
system and some applications have been made.


title: Unbiased Matrix Rounding

abstract:
  We show several ways to round a real matrix to an integer one such that the
rounding errors in all rows and columns as well as the whole matrix are less
than one. This is a classical problem with applications in many fields, in
particular, statistics.
  We improve earlier solutions of different authors in two ways. For rounding
matrices of size $m \times n$, we reduce the runtime from $O((m n)^2 Second,
our roundings also have a rounding error of less than one in all initial
intervals of rows and columns. Consequently, arbitrary intervals have an error
of at most two. This is particularly useful in the statistics application of
controlled rounding.
  The same result can be obtained via (dependent) randomized rounding. This has
the additional advantage that the rounding is unbiased, that is, for all
entries $y_{ij}$ of our rounding, we have $E(y_{ij}) = x_{ij}$, where $x_{ij}$
is the corresponding entry of the input matrix.


title: Universal decoding with an erasure option

abstract:
  Motivated by applications of rateless coding, decision feedback, and ARQ, we
study the problem of universal decoding for unknown channels, in the presence
of an erasure option. Specifically, we harness the competitive minimax
methodology developed in earlier studies, in order to derive a universal
version of Forney's classical erasure/list decoder, which in the erasure case,
optimally trades off between the probability of erasure and the probability of
undetected error. The proposed universal erasure decoder guarantees universal
achievability of a certain fraction $\xi$ of the optimum error exponents of
these probabilities (in a sense to be made precise in the sequel). A
single--letter expression for $\xi$, which depends solely on the coding rate
and the threshold, is provided. The example of the binary symmetric channel is
studied in full detail, and some conclusions are drawn.


title: Retraction and Generalized Extension of Computing with Words

abstract:
  Fuzzy automata, whose input alphabet is a set of numbers or symbols, are a
formal model of computing with values. Motivated by Zadeh's paradigm of
computing with words rather than numbers, Ying proposed a kind of fuzzy
automata, whose input alphabet consists of all fuzzy subsets of a set of
symbols, as a formal model of computing with all words. In this paper, we
introduce a somewhat general formal model of computing with (some special)
words. The new features of the model are that the input alphabet only comprises
some (not necessarily all) fuzzy subsets of a set of symbols and the fuzzy
transition function can be specified arbitrarily. By employing the methodology
of fuzzy control, we establish a retraction principle from computing with words
to computing with values for handling crisp inputs and a generalized extension
principle from computing with words to computing with all words for handling
fuzzy inputs. These principles show that computing with values and computing
with all words can be respectively implemented by computing with words. Some
algebraic properties of retractions and generalized extensions are addressed as
well.


title: Distributed Metadata with the AMGA Metadata Catalog

abstract:
  Catalog Services play a vital role on Data Grids by allowing users and
applications to discover and locate the data needed. On large Data Grids, with
hundreds of geographically distributed sites, centralized Catalog Services do
not provide the required scalability, performance or fault-tolerance. In this
article, we start by presenting and discussing the general requirements on Grid
Catalogs of applications being developed by the EGEE user community. This
provides the motivation for the second part of the article, where we present
the replication and distribution mechanisms we have designed and implemented
into the AMGA Metadata Catalog, which is part of the gLite software stack being
developed for the EGEE project. Implementing these mechanisms in the catalog
itself has the advantages of not requiring any special support from the
relational database back-end, of being database independent, and of allowing
tailoring the mechanisms to the specific requirements and characteristics of
Metadata Catalogs.


title: Complexity and Philosophy

abstract:
  The science of complexity is based on a new way of thinking that stands in
sharp contrast to the philosophy underlying Newtonian science, which is based
on reductionism, determinism, and objective knowledge. This paper reviews the
historical development of this new world view, focusing on its philosophical
foundations. Determinism was challenged by quantum mechanics and chaos theory.
Systems theory replaced reductionism by a scientifically based holism.
Cybernetics and postmodern social science showed that knowledge is
intrinsically subjective. These developments are being integrated under the
header of "complexity science". Its central paradigm is the multi-agent system.
Agents are intrinsically subjective and uncertain about their environment and
future, but out of their local interactions, a global organization emerges.
Although different philosophers, and in particular the postmodernists, have
voiced similar ideas, the paradigm of complexity still needs to be fully
assimilated by philosophy. This will throw a new light on old philosophical
issues such as relativism, ethics and the role of the subject.


title: Octave-GTK: A GTK binding for GNU Octave

abstract:
  This paper discusses the problems faced with interoperability between two
programming languages, with respect to GNU Octave, and GTK API written in C, to
provide the GTK API on Octave.Octave-GTK is the fusion of two different API's:
one exported by GNU Octave [scientific computing tool] and the other GTK [GUI
toolkit]; this enables one to use GTK primitives within GNU Octave, to build
graphical front ends,at the same time using octave engine for number crunching
power. This paper illustrates our implementation of binding logic, and shows
results extended to various other libraries using the same base code generator.
Also shown, are methods of code generation, binding automation, and the niche
we plan to fill in the absence of GUI in Octave. Canonical discussion of
advantages, feasibility and problems faced in the process are elucidated.


title:
Information and multiaccess interference in a complexity-constrained
  vector channel

abstract:
  Rodrigo de Miguel et al 2007 J. Phys. A: Math. Theor. 40 5241-5260: A noisy
vector channel operating under a strict complexity constraint at the receiver
is introduced. According to this constraint, detected bits, obtained by
performing hard decisions directly on the channel's matched filter output, must
be the same as the transmitted binary inputs. An asymptotic analysis is carried
out using mathematical tools imported from the study of neural networks, and it
is shown that, under a bounded noise assumption, such complexity-constrained
channel exhibits a non-trivial Shannon-theoretic capacity. It is found that
performance relies on rigorous interference-based multiuser cooperation at the
transmitter and that this cooperation is best served when all transmitters use
the same amplitude.


title: Naming Games in Spatially-Embedded Random Networks

abstract:
  We investigate a prototypical agent-based model, the Naming Game, on random
geometric networks. The Naming Game is a minimal model, employing local
communications that captures the emergence of shared communication schemes
(languages) in a population of autonomous semiotic agents. Implementing the
Naming Games on random geometric graphs, local communications being local
broadcasts, serves as a model for agreement dynamics in large-scale,
autonomously operating wireless sensor networks. Further, it captures essential
features of the scaling properties of the agreement process for
spatially-embedded autonomous agents. We also present results for the case when
a small density of long-range communication links are added on top of the
random geometric graph, resulting in a "small-world"-like network and yielding
a significantly reduced time to reach global agreement.


title: Semantically Correct Query Answers in the Presence of Null Values

abstract:
  For several reasons a database may not satisfy a given set of integrity
constraints(ICs), but most likely most of the information in it is still
consistent with those ICs; and could be retrieved when queries are answered.
Consistent answers to queries wrt a set of ICs have been characterized as
answers that can be obtained from every possible minimally repaired consistent
version of the original database. In this paper we consider databases that
contain null values and are also repaired, if necessary, using null values. For
this purpose, we propose first a precise semantics for IC satisfaction in a
database with null values that is compatible with the way null values are
treated in commercial database management systems. Next, a precise notion of
repair is introduced that privileges the introduction of null values when
repairing foreign key constraints, in such a way that these new values do not
create an infinite cycle of new inconsistencies. Finally, we analyze how to
specify this kind of repairs of a database that contains null values using
disjunctive logic programs with stable model semantics.


title:
Successive Wyner-Ziv Coding Scheme and its Application to the Quadratic
  Gaussian CEO Problem

abstract:
  We introduce a distributed source coding scheme called successive Wyner-Ziv
coding. We show that any point in the rate region of the quadratic Gaussian CEO
problem can be achieved via the successive Wyner-Ziv coding. The concept of
successive refinement in the single source coding is generalized to the
distributed source coding scenario, which we refer to as distributed successive
refinement. For the quadratic Gaussian CEO problem, we establish a necessary
and sufficient condition for distributed successive refinement, where the
successive Wyner-Ziv coding scheme plays an important role.


title:
The emergence of knowledge exchange: an agent-based model of a software
  market

abstract:
  We investigate knowledge exchange among commercial organisations, the
rationale behind it and its effects on the market. Knowledge exchange is known
to be beneficial for industry, but in order to explain it, authors have used
high level concepts like network effects, reputation and trust. We attempt to
formalise a plausible and elegant explanation of how and why companies adopt
information exchange and why it benefits the market as a whole when this
happens. This explanation is based on a multi-agent model that simulates a
market of software providers. Even though the model does not include any
high-level concepts, information exchange naturally emerges during simulations
as a successful profitable behaviour. The conclusions reached by this
agent-based analysis are twofold: (1) A straightforward set of assumptions is
enough to give rise to exchange in a software market. (2) Knowledge exchange is
shown to increase the efficiency of the market.


title:
Polynomial Constraint Satisfaction, Graph Bisection, and the Ising
  Partition Function

abstract:
  We introduce a problem class we call Polynomial Constraint Satisfaction
Problems, or PCSP. Where the usual CSPs from computer science and optimization
have real-valued score functions, and partition functions from physics have
monomials, PCSP has scores that are arbitrary multivariate formal polynomials,
or indeed take values in an arbitrary ring.
  Although PCSP is much more general than CSP, remarkably, all (exact,
exponential-time) algorithms we know of for 2-CSP (where each score depends on
at most 2 variables) extend to 2-PCSP, at the expense of just a polynomial
factor in running time. Specifically, we extend the reduction-based algorithm
of Scott and Sorkin; the specialization of that approach to sparse random
instances, where the algorithm runs in polynomial expected time;
dynamic-programming algorithms based on tree decompositions; and the
split-and-list matrix-multiplication algorithm of Williams.
  This gives the first polynomial-space exact algorithm more efficient than
exhaustive enumeration for the well-studied problems of finding a minimum
bisection of a graph, and calculating the partition function of an Ising model,
and the most efficient algorithm known for certain instances of Maximum
Independent Set. Furthermore, PCSP solves both optimization and counting
versions of a wide range of problems, including all CSPs, and thus enables
samplers including uniform sampling of optimal solutions and Gibbs sampling of
all solutions.


title:
Linear-programming design and analysis of fast algorithms for Max 2-Sat
  and Max 2-CSP

abstract:
  The class $(r,2)$-CSP, or simply Max 2-CSP, consists of constraint
satisfaction problems with at most two $r$-valued variables per clause. For
instances with $n$ variables and $m$ binary clauses, we present an $O(n
r^{5+19m/100})$-time algorithm which is the fastest polynomial-space algorithm
for many problems in the class, including Max Cut. The method also proves a
treewidth bound $\tw(G) \leq (13/75+o(1))m$, which gives a faster Max 2-CSP
algorithm that uses exponential space: running in time
$\Ostar{2^{(13/75+o(1))m}}$, this is fastest for most problems in Max 2-CSP.
Parametrizing in terms of $n$ rather than $m$, for graphs of average degree $d$
we show a simple algorithm running time $\Ostar{2^{(1-\frac{2}{d+1})n}}$, the
fastest polynomial-space algorithm known.
  In combination with ``Polynomial CSPs'' introduced in a companion paper,
these algorithms also allow (with an additional polynomial-factor overhead in
space and time) counting and sampling, and the solution of problems like Max
Bisection that escape the usual CSP framework.
  Linear programming is key to the design as well as the analysis of the
algorithms.


title: Event Systems and Access Control

abstract:
  We consider the interpretations of notions of access control (permissions,
interdictions, obligations, and user rights) as run-time properties of
information systems specified as event systems with fairness. We give proof
rules for verifying that an access control policy is enforced in a system, and
consider preservation of access control by refinement of event systems. In
particular, refinement of user rights is non-trivial; we propose to combine
low-level user rights and system obligations to implement high-level user
rights.