title: Finding Community Structure in Mega-scale Social Networks

abstract:
  Community analysis algorithm proposed by Clauset, Newman, and Moore (CNM
algorithm) finds community structure in social networks. Unfortunately, CNM
algorithm does not scale well and its use is practically limited to networks
whose sizes are up to 500,000 nodes. The paper identifies that this
inefficiency is caused from merging communities in unbalanced manner. The paper
introduces three kinds of metrics (consolidation ratio) to control the process
of community analysis trying to balance the sizes of the communities being
merged. Three flavors of CNM algorithms are built incorporating those metrics.
The proposed techniques are tested using data sets obtained from existing
social networking service that hosts 5.5 million users. All the methods exhibit
dramatic improvement of execution efficiency in comparison with the original
CNM algorithm and shows high scalability. The fastest method processes a
network with 1 million nodes in 5 minutes and a network with 4 million nodes in
35 minutes, respectively. Another one processes a network with 500,000 nodes in
50 minutes (7 times faster than the original algorithm), finds community
structures that has improved modularity, and scales to a network with 5.5
million.


title: Parameterized Algorithms for Directed Maximum Leaf Problems

abstract:
  We prove that finding a rooted subtree with at least $k$ leaves in a digraph
is a fixed parameter tractable problem. A similar result holds for finding
rooted spanning trees with many leaves in digraphs from a wide family $\cal L$
that includes all strong and acyclic digraphs. This settles completely an open
question of Fellows and solves another one for digraphs in $\cal L$. Our
algorithms are based on the following combinatorial result which can be viewed
as a generalization of many results for a `spanning tree with many leaves' in
the undirected case, and which is interesting on its own: If a digraph $D\in
\cal L$ of order $n$ with minimum in-degree at least 3 contains a rooted
spanning tree, then $D$ contains one with at least $(n/2)^{1/5}-1$ leaves.


title:
Permutation Decoding and the Stopping Redundancy Hierarchy of Linear
  Block Codes

abstract:
  We investigate the stopping redundancy hierarchy of linear block codes and
its connection to permutation decoding techniques. An element in the ordered
list of stopping redundancy values represents the smallest number of possibly
linearly dependent rows in any parity-check matrix of a code that avoids
stopping sets of a given size. Redundant parity-check equations can be shown to
have a similar effect on decoding performance as permuting the coordinates of
the received codeword according to a selected set of automorphisms of the code.
Based on this finding we develop new decoding strategies for data transmission
over the binary erasure channel that combine iterative message passing and
permutation decoding in order to avoid errors confined to stopping sets. We
also introduce the notion of s-SAD sets, containing the smallest number of
automorphisms of a code with the property that they move any set of not more
than s erasures into positions that do not correspond to stopping sets within a
judiciously chosen parity-check matrix.


title:
The Gaussian multiple access wire-tap channel: wireless secrecy and
  cooperative jamming

abstract:
  We consider the General Gaussian Multiple Access Wire-Tap Channel (GGMAC-WT).
In this scenario, multiple users communicate with an intended receiver in the
presence of an intelligent and informed eavesdropper. We define two suitable
secrecy measures, termed individual and collective, to reflect the confidence
in the system for this multi-access environment. We determine achievable rates
such that secrecy to some pre-determined degree can be maintained, using
Gaussian codebooks. We also find outer bounds for the case when the
eavesdropper receives a degraded version of the intended receiver's signal. In
the degraded case, Gaussian codewords are shown to achieve the sum capacity for
collective constraints. In addition, a TDMA scheme is shown to also achieve sum
capacity for both sets of constraints. Numerical results showing the new rate
region are presented and compared with the capacity region of the Gaussian
Multiple-Access Channel (GMAC) with no secrecy constraints. We then find the
secrecy sum-rate maximizing power allocations for the transmitters, and show
that a cooperative jamming scheme can be used to increase achievable rates in
this scenario.


title: On Random Network Coding for Multicast

abstract:
  Random linear network coding is a particularly decentralized approach to the
multicast problem. Use of random network codes introduces a non-zero
probability however that some sinks will not be able to successfully decode the
required sources. One of the main theoretical motivations for random network
codes stems from the lower bound on the probability of successful decoding
reported by Ho et. al. (2003). This result demonstrates that all sinks in a
linearly solvable network can successfully decode all sources provided that the
random code field size is large enough. This paper develops a new bound on the
probability of successful decoding.


title: The DFAs of Finitely Different Languages

abstract:
  Two languages are "finitely different" if their symmetric difference is
finite. We consider the DFAs of finitely different regular languages and find
major structural similarities. We proceed to consider the smallest DFAs that
recognize a language finitely different from some given DFA. Such "f-minimal"
DFAs are not unique, and this non-uniqueness is characterized. Finally, we
offer a solution to the minimization problem of finding such f-minimal DFAs.


title: Nash equilibria in Voronoi games on graphs

abstract:
  In this paper we study a game where every player is to choose a vertex
(facility) in a given undirected graph. All vertices (customers) are then
assigned to closest facilities and a player's payoff is the number of customers
assigned to it. We show that deciding the existence of a Nash equilibrium for a
given graph is NP-hard which to our knowledge is the first result of this kind
for a zero-sum game. We also introduce a new measure, the social cost
discrepancy, defined as the ratio of the costs between the worst and the best
Nash equilibria. We show that the social cost discrepancy in our game is
Omega(sqrt(n/k)) and O(sqrt(kn)), where n is the number of vertices and k the
number of players.


title:
On the possibility of making the complete computer model of a human
  brain

abstract:
  The development of the algorithm of a neural network building by the
corresponding parts of a DNA code is discussed.


title: A probabilistic analysis of a leader election algorithm

abstract:
  A {\em leader election} algorithm is an elimination process that divides
recursively into tow subgroups an initial group of n items, eliminates one
subgroup and continues the procedure until a subgroup is of size 1. In this
paper the biased case is analyzed. We are interested in the {\em cost} of the
algorithm, i.e. the number of operations needed until the algorithm stops.
Using a probabilistic approach, the asymptotic behavior of the algorithm is
shown to be related to the behavior of a hitting time of two random sequences
on [0,1].


title:
An Efficient Algorithm to Recognize Locally Equivalent Graphs in
  Non-Binary Case

abstract:
  Let $v$ be a vertex of a graph $G$. By the local complementation of $G$ at
$v$ we mean to complement the subgraph induced by the neighbors of $v$. This
operator can be generalized as follows. Assume that, each edge of $G$ has a
label in the finite field $\mathbf{F}_q$. Let $(g_{ij})$ be set of labels
($g_{ij}$ is the label of edge $ij$). We define two types of operators. For the
first one, let $v$ be a vertex of $G$ and $a\in \mathbf{F}_q$, and obtain the
graph with labels $g'_{ij}=g_{ij}+ag_{vi}g_{vj}$. For the second, if $0\neq
b\in \mathbf{F}_q$ the resulted graph is a graph with labels $g''_{vi}=bg_{vi}$
and $g''_{ij}=g_{ij}$, for $i,j$ unequal to $v$. It is clear that if the field
is binary, the operators are just local complementations that we described.
  The problem of whether two graphs are equivalent under local complementations
has been studied, \cite{bouchalg}. Here we consider the general case and
assuming that $q$ is odd, present the first known efficient algorithm to verify
whether two graphs are locally equivalent or not.


title: Exploring k-Colorability

abstract: An introductory paper to the graph k-colorability problem.


title: Redundancy-Related Bounds on Generalized Huffman Codes

abstract:
  This paper presents new lower and upper bounds for the compression rate of
binary prefix codes optimized over memoryless sources according to various
nonlinear codeword length objectives. Like the most well-known redundancy
bounds for minimum average redundancy coding - Huffman coding - these are in
terms of a form of entropy and/or the probability of an input symbol, often the
most probable one. The bounds here, some of which are tight, improve on known
bounds of the form L in [H,H+1), where H is some form of entropy in bits (or,
in the case of redundancy objectives, 0) and L is the length objective, also in
bits. The objectives explored here include exponential-average length, maximum
pointwise redundancy, and exponential-average pointwise redundancy (also called
dth exponential redundancy). The first of these relates to various problems
involving queueing, uncertainty, and lossless communications; the second
relates to problems involving Shannon coding and universal modeling. For these
two objectives we also explore the related problem of the necessary and
sufficient conditions for the shortest codeword of a code being a specific
length.


title: A local balance property of episturmian words

abstract:
  We prove that episturmian words and Arnoux-Rauzy sequences can be
characterized using a local balance property. We also give a new
characterization of epistandard words and show that the set of finite words
that are not factors of an episturmian word is not context-free.


title: Sudo-Lyndon

abstract:
  Based on Lyndon words, a new Sudoku-like puzzle is presented and some
relative theoretical questions are proposed.


title: Noise Limited Computational Speed

abstract:
  In modern transistor based logic gates, the impact of noise on computation
has become increasingly relevant since the voltage scaling strategy, aimed at
decreasing the dissipated power, has increased the probability of error due to
the reduced switching threshold voltages. In this paper we discuss the role of
noise in a two state model that mimic the dynamics of standard logic gates and
show that the presence of the noise sets a fundamental limit to the computing
speed. An optimal idle time interval that minimizes the error probability, is
derived.


title: Entropy vectors and network codes

abstract:
  We consider a network multicast example that relates the solvability of the
multicast problem with the existence of an entropy function. As a result, we
provide an alternative approach to the proving of the insufficiency of linear
(and abelian) network codes and demonstrate the utility of non-Shannon
inequalities to tighten outer bounds on network coding capacity regions.


title: Group characterizable entropy functions

abstract:
  This paper studies properties of entropy functions that are induced by groups
and subgroups. We showed that many information theoretic properties of those
group induced entropy functions also have corresponding group theoretic
interpretations. Then we propose an extension method to find outer bound for
these group induced entropy functions.


title: Towards a New ODE Solver Based on Cartan's Equivalence Method

abstract:
  The aim of the present paper is to propose an algorithm for a new ODE--solver
which should improve the abilities of current solvers to handle second order
differential equations. The paper provides also a theoretical result revealing
the relationship between the change of coordinates, that maps the generic
equation to a given target equation, and the symmetry $\D$-groupoid of this
target.


title:
Comments on "Design and performance evaluation of load distribution
  strategies for multiple loads on heterogeneous linear daisy chain networks''

abstract:
  Min, Veeravalli, and Barlas proposed strategies to minimize the overall
execution time of one or several divisible loads on a heterogeneous linear
network, using one or more installments. We show on a very simple example that
the proposed approach does not always produce a solution and that, when it
does, the solution is often suboptimal. We also show how to find an optimal
scheduling for any instance, once the number of installments per load is given.
Finally, we formally prove that under a linear cost model, as in the original
paper, an optimal schedule has an infinite number of installments. Such a cost
model can therefore not be sed to design practical multi-installment
strategies.


title: The Haar Wavelet Transform of a Dendrogram: Additional Notes

abstract:
  We consider the wavelet transform of a finite, rooted, node-ranked, $p$-way
tree, focusing on the case of binary ($p = 2$) trees. We study a Haar wavelet
transform on this tree. Wavelet transforms allow for multiresolution analysis
through translation and dilation of a wavelet function. We explore how this
works in our tree context.


title:
Distributed Decision Through Self-Synchronizing Sensor Networks in the
  Presence of Propagation Delays and Nonreciprocal Channels

abstract:
  In this paper we propose and analyze a distributed algorithm for achieving
globally optimal decisions, either estimation or detection, through a
self-synchronization mechanism among linearly coupled integrators initialized
with local measurements. We model the interaction among the nodes as a directed
graph with weights dependent on the radio interface and we pose special
attention to the effect of the propagation delays occurring in the exchange of
data among sensors, as a function of the network geometry. We derive necessary
and sufficient conditions for the proposed system to reach a consensus on
globally optimal decision statistics. One of the major results proved in this
work is that a consensus is achieved for any bounded delay condition if and
only if the directed graph is quasi-strongly connected. We also provide a
closed form expression for the global consensus, showing that the effect of
delays is, in general, to introduce a bias in the final decision. The closed
form expression is also useful to modify the consensus mechanism in order to
get rid of the bias with minimum extra complexity.


title: Feasible reactivity in a synchronous pi-calculus

abstract:
  Reactivity is an essential property of a synchronous program. Informally, it
guarantees that at each instant the program fed with an input will `react'
producing an output. In the present work, we consider a refined property that
we call ` feasible reactivity'. Beyond reactivity, this property guarantees
that at each instant both the size of the program and its reaction time are
bounded by a polynomial in the size of the parameters at the beginning of the
computation and the size of the largest input. We propose a method to annotate
programs and we develop related static analysis techniques that guarantee
feasible reactivity for programs expressed in the S-pi-calculus. The latter is
a synchronous version of the pi-calculus based on the SL synchronous
programming model.


title: A Practical Approach to Lossy Joint Source-Channel Coding

abstract:
  This work is devoted to practical joint source channel coding. Although the
proposed approach has more general scope, for the sake of clarity we focus on a
specific application example, namely, the transmission of digital images over
noisy binary-input output-symmetric channels. The basic building blocks of most
state-of the art source coders are: 1) a linear transformation; 2) scalar
quantization of the transform coefficients; 3) probability modeling of the
sequence of quantization indices; 4) an entropy coding stage. We identify the
weakness of the conventional separated source-channel coding approach in the
catastrophic behavior of the entropy coding stage. Hence, we replace this stage
with linear coding, that maps directly the sequence of redundant quantizer
output symbols into a channel codeword. We show that this approach does not
entail any loss of optimality in the asymptotic regime of large block length.
However, in the practical regime of finite block length and low decoding
complexity our approach yields very significant improvements. Furthermore, our
scheme allows to retain the transform, quantization and probability modeling of
current state-of the art source coders, that are carefully matched to the
features of specific classes of sources. In our working example, we make use of
``bit-planes'' and ``contexts'' model defined by the JPEG2000 standard and we
re-interpret the underlying probability model as a sequence of conditionally
Markov sources. The Markov structure allows to derive a simple successive
coding and decoding scheme, where the latter is based on iterative Belief
Propagation. We provide a construction example of the proposed scheme based on
punctured Turbo Codes and we demonstrate the gain over a conventional separated
scheme by running extensive numerical experiments on test images.


title: What is needed to exploit knowledge of primary transmissions?

abstract:
  Recently, Tarokh and others have raised the possibility that a cognitive
radio might know the interference signal being transmitted by a strong primary
user in a non-causal way, and use this knowledge to increase its data rates.
However, there is a subtle difference between knowing the signal transmitted by
the primary and the actual interference at our receiver since there is a
wireless channel between these two points. We show that even an unknown phase
results in a substantial decrease in the data rates that can be achieved, and
thus there is a need to feedback interference channel estimates to the
cognitive transmitter. We then consider the case of fading channels. We derive
an upper bound on the rate for given outage error probability for faded dirt.
We give a scheme that uses appropriate "training" to obtain such estimates and
quantify this scheme's required overhead as a function of the relevant
coherence time and interference power.


title: Logic Programming with Satisfiability

abstract:
  This paper presents a Prolog interface to the MiniSat satisfiability solver.
Logic program- ming with satisfiability combines the strengths of the two
paradigms: logic programming for encoding search problems into satisfiability
on the one hand and efficient SAT solving on the other. This synergy between
these two exposes a programming paradigm which we propose here as a logic
programming pearl. To illustrate logic programming with SAT solving we give an
example Prolog program which solves instances of Partial MAXSAT.


title: Tradeoff between decoding complexity and rate for codes on graphs

abstract:
  We consider transmission over a general memoryless channel, with bounded
decoding complexity per bit under message passing decoding. We show that the
achievable rate is bounded below capacity if there is a finite success in the
decoding in a specified number of operations per bit at the decoder for some
codes on graphs. These codes include LDPC and LDGM codes. Good performance with
low decoding complexity suggests strong local structures in the graphs of these
codes, which are detrimental to the code rate asymptotically. The proof method
leads to an interesting necessary condition on the code structures which could
achieve capacity with bounded decoding complexity. We also show that if a code
sequence achieves a rate epsilon close to the channel capacity, the decoding
complexity scales at least as O(log(1/epsilon).


title: Dynamic Random Geometric Graphs

abstract:
  In this work we introduce Dynamic Random Geometric Graphs as a basic rough
model for mobile wireless sensor networks, where communication distances are
set to the known threshold for connectivity of static random geometric graphs.
We provide precise asymptotic results for the expected length of the
connectivity and disconnectivity periods of the network. We believe the formal
tools developed in this work could be of use in future studies in more concrete
settings. In addition, for static random geometric graphs at the threshold for
connectivity, we provide asymptotic expressions on the probability of existence
of components according to their sizes.


title: Firebird Database Backup by Serialized Database Table Dump

abstract:
  This paper presents a simple data dump and load utility for Firebird
databases which mimics mysqldump in MySQL. This utility, fb_dump and fb_load,
for dumping and loading respectively, retrieves each database table using
kinterbasdb and serializes the data using marshal module. This utility has two
advantages over the standard Firebird database backup utility, gbak. Firstly,
it is able to backup and restore single database tables which might help to
recover corrupted databases. Secondly, the output is in text-coded format (from
marshal module) making it more resilient than a compressed text backup, as in
the case of using gbak.


title: A First Step Towards Automatically Building Network Representations

abstract:
  To fully harness Grids, users or middlewares must have some knowledge on the
topology of the platform interconnection network. As such knowledge is usually
not available, one must uses tools which automatically build a topological
network model through some measurements. In this article, we define a
methodology to assess the quality of these network model building tools, and we
apply this methodology to representatives of the main classes of model builders
and to two new algorithms. We show that none of the main existing techniques
build models that enable to accurately predict the running time of simple
application kernels for actual platforms. However some of the new algorithms we
propose give excellent results in a wide range of situations.


title: Properties of Rank Metric Codes

abstract:
  This paper investigates general properties of codes with the rank metric. We
first investigate asymptotic packing properties of rank metric codes. Then, we
study sphere covering properties of rank metric codes, derive bounds on their
parameters, and investigate their asymptotic covering properties. Finally, we
establish several identities that relate the rank weight distribution of a
linear code to that of its dual code. One of our identities is the counterpart
of the MacWilliams identity for the Hamming metric, and it has a different form
from the identity by Delsarte.


title: A Local Algorithm for Finding Dense Subgraphs

abstract:
  We present a local algorithm for finding dense subgraphs of bipartite graphs,
according to the definition of density proposed by Kannan and Vinay. Our
algorithm takes as input a bipartite graph with a specified starting vertex,
and attempts to find a dense subgraph near that vertex. We prove that for any
subgraph S with k vertices and density theta, there are a significant number of
starting vertices within S for which our algorithm produces a subgraph S' with
density theta / O(log n) on at most O(D k^2) vertices, where D is the maximum
degree. The running time of the algorithm is O(D k^2), independent of the
number of vertices in the graph.


title: The Hadwiger Number of Jordan Regions is Unbounded

abstract:
  We show that for every n > 0 there is a planar topological disk A_0 and n
translates A_1, A_2, ..., A_n of A_0 such that the interiors of A_0, ... A_n
are pairwise disjoint, but with each A_i touching A_0 for 1 <= i <= n.


title: Sparse geometric graphs with small dilation

abstract:
  Given a set S of n points in R^D, and an integer k such that 0 <= k < n, we
show that a geometric graph with vertex set S, at most n - 1 + k edges, maximum
degree five, and dilation O(n / (k+1)) can be computed in time O(n log n). For
any k, we also construct planar n-point sets for which any geometric graph with
n-1+k edges has dilation Omega(n/(k+1)); a slightly weaker statement holds if
the points of S are required to be in convex position.


title: Random Sentences from a Generalized Phrase-Structure Grammar Interpreter

abstract:
  In numerous domains in cognitive science it is often useful to have a source
for randomly generated corpora. These corpora may serve as a foundation for
artificial stimuli in a learning experiment (e.g., Ellefson & Christiansen,
2000), or as input into computational models (e.g., Christiansen & Dale, 2001).
The following compact and general C program interprets a phrase-structure
grammar specified in a text file. It follows parameters set at a Unix or
Unix-based command-line and generates a corpus of random sentences from that
grammar.


title:
Invariant template matching in systems with spatiotemporal coding: a
  vote for instability

abstract:
  We consider the design of a pattern recognition that matches templates to
images, both of which are spatially sampled and encoded as temporal sequences.
The image is subject to a combination of various perturbations. These include
ones that can be modeled as parameterized uncertainties such as image blur,
luminance, translation, and rotation as well as unmodeled ones. Biological and
neural systems require that these perturbations be processed through a minimal
number of channels by simple adaptation mechanisms. We found that the most
suitable mathematical framework to meet this requirement is that of weakly
attracting sets. This framework provides us with a normative and unifying
solution to the pattern recognition problem. We analyze the consequences of its
explicit implementation in neural systems. Several properties inherent to the
systems designed in accordance with our normative mathematical argument
coincide with known empirical facts. This is illustrated in mental rotation,
visual search and blur/intensity adaptation. We demonstrate how our results can
be applied to a range of practical problems in template matching and pattern
recognition.


title: Improving Prolog programs: Refactoring for Prolog

abstract:
  Refactoring is an established technique from the object-oriented (OO)
programming community to restructure code: it aims at improving software
readability, maintainability and extensibility. Although refactoring is not
tied to the OO-paradigm in particular, its ideas have not been applied to Logic
Programming until now.
  This paper applies the ideas of refactoring to Prolog programs. A catalogue
is presented listing refactorings classified according to scope. Some of the
refactorings have been adapted from the OO-paradigm, while others have been
specifically designed for Prolog. The discrepancy between intended and
operational semantics in Prolog is also addressed by some of the refactorings.
  In addition, ViPReSS, a semi-automatic refactoring browser, is discussed and
the experience with applying ViPReSS to a large Prolog legacy system is
reported. The main conclusion is that refactoring is both a viable technique in
Prolog and a rather desirable one.


title:
Performance of Ultra-Wideband Impulse Radio in Presence of Impulsive
  Interference

abstract:
  We analyze the performance of coherent impulsive-radio (IR) ultra-wideband
(UWB) channel in presence of the interference generated by concurrent
transmissions of the systems with the same impulsive radio. We derive a novel
algorithm, using Monte-Carlo method, to calculate a lower bound on the rate
that can be achieved using maximum-likelihood estimator. Using this bound we
show that such a channel is very robust to interference, in contrast to the
nearest-neighbor detector.


title:
Social Behaviours Applied to P2P Systems: An efficient Algorithm for
  Resource Organisation

abstract:
  P2P systems are a great solution to the problem of distributing resources.
The main issue of P2P networks is that searching and retrieving resources
shared by peers is usually expensive and does not take into account
similarities among peers. In this paper we present preliminary simulations of
PROSA, a novel algorithm for P2P network structuring, inspired by social
behaviours. Peers in PROSA self--organise in social groups of similar peers,
called ``semantic--groups'', depending on the resources they are sharing. Such
a network smoothly evolves to a small--world graph, where queries for resources
are efficiently and effectively routed.


title: Protection of DVB Systems by Trusted Computing

abstract:
  We describe a concept to employ Trusted Computing technology to secure
Conditional Access Systems (CAS) for DVB. Central is the embedding of a trusted
platform module (TPM) into the set-top-box or residential home gateway. Various
deployment scenarios exhibit possibilities of charging co-operation with mobile
network operators (MNO), or other payment providers.


title: An Upper Bound on the Average Size of Silhouettes

abstract:
  It is a widely observed phenomenon in computer graphics that the size of the
silhouette of a polyhedron is much smaller than the size of the whole
polyhedron. This paper provides, for the first time, theoretical evidence
supporting this for a large class of objects, namely for polyhedra that
approximate surfaces in some reasonable way; the surfaces may be non-convex and
non-differentiable and they may have boundaries. We prove that such polyhedra
have silhouettes of expected size $O(\sqrt{n})$ where the average is taken over
all points of view and n is the complexity of the polyhedron.


title:
Paths Beyond Local Search: A Nearly Tight Bound for Randomized
  Fixed-Point Computation

abstract:
  In 1983, Aldous proved that randomization can speedup local search. For
example, it reduces the query complexity of local search over [1:n]^d from
Theta (n^{d-1}) to O (d^{1/2}n^{d/2}). It remains open whether randomization
helps fixed-point computation. Inspired by this open problem and recent
advances on equilibrium computation, we have been fascinated by the following
question:
  Is a fixed-point or an equilibrium fundamentally harder to find than a local
optimum? In this paper, we give a nearly-tight bound of Omega(n)^{d-1} on the
randomized query complexity for computing a fixed point of a discrete Brouwer
function over [1:n]^d. Since the randomized query complexity of global
optimization over [1:n]^d is Theta (n^{d}), the randomized query model over
[1:n]^d strictly separates these three important search problems: Global
optimization is harder than fixed-point computation, and fixed-point
computation is harder than local search. Our result indeed demonstrates that
randomization does not help much in fixed-point computation in the query model;
the deterministic complexity of this problem is Theta (n^{d-1}).


title:
Mapping the Object-Role Modeling language ORM2 into Description Logic
  language DLRifd

abstract:
  In recent years, several efforts have been made to enhance conceptual data
modelling with automated reasoning to improve the model's quality and derive
implicit information. One approach to achieve this in implementations, is to
constrain the language. Advances in Description Logics can help choosing the
right language to have greatest expressiveness yet to remain within the
decidable fragment of first order logic to realise a workable implementation
with good performance using DL reasoners. The best fit DL language appears to
be the ExpTime-complete DLRifd. To illustrate trade-offs and highlight features
of the modelling languages, we present a precise transformation of the mappable
features of the very expressive (undecidable) ORM/ORM2 conceptual data
modelling languages to exactly DLRifd. Although not all ORM2 features can be
mapped, this is an interesting fragment because it has been shown that DLRifd
can also encode UML Class Diagrams and EER, and therefore can foster
interoperation between conceptual data models and research into ontological
aspects of the modelling languages.


title: Aperture-Angle and Hausdorff-Approximation of Convex Figures

abstract:
  The aperture angle alpha(x, Q) of a point x not in Q in the plane with
respect to a convex polygon Q is the angle of the smallest cone with apex x
that contains Q. The aperture angle approximation error of a compact convex set
C in the plane with respect to an inscribed convex polygon Q of C is the
minimum aperture angle of any x in C Q with respect to Q. We show that for any
compact convex set C in the plane and any k > 2, there is an inscribed convex
k-gon Q of C with aperture angle approximation error (1 - 2/(k+1)) pi. This
bound is optimal, and settles a conjecture by Fekete from the early 1990s. The
same proof technique can be used to prove a conjecture by Brass: If a polygon P
admits no approximation by a sub-k-gon (the convex hull of k vertices of P)
with Hausdorff distance sigma, but all subpolygons of P (the convex hull of
some vertices of P) admit such an approximation, then P is a (k+1)-gon. This
implies the following result: For any k > 2 and any convex polygon P of
perimeter at most 1 there is a sub-k-gon Q of P such that the
Hausdorff-distance of P and Q is at most 1/(k+1) * sin(pi/(k+1)).


title: Observable Graphs

abstract:
  An edge-colored directed graph is \emph{observable} if an agent that moves
along its edges is able to determine his position in the graph after a
sufficiently long observation of the edge colors. When the agent is able to
determine his position only from time to time, the graph is said to be
\emph{partly observable}. Observability in graphs is desirable in situations
where autonomous agents are moving on a network and one wants to localize them
(or the agent wants to localize himself) with limited information. In this
paper, we completely characterize observable and partly observable graphs and
show how these concepts relate to observable discrete event systems and to
local automata. Based on these characterizations, we provide polynomial time
algorithms to decide observability, to decide partial observability, and to
compute the minimal number of observations necessary for finding the position
of an agent. In particular we prove that in the worst case this minimal number
of observations increases quadratically with the number of nodes in the graph.
  From this it follows that it may be necessary for an agent to pass through
the same node several times before he is finally able to determine his position
in the graph. We then consider the more difficult question of assigning colors
to a graph so as to make it observable and we prove that two different versions
of this problem are NP-complete.


title:
A Note on the Periodicity and the Output Rate of Bit Search Type
  Generators

abstract:
  We investigate the bit-search type irregular decimation algorithms that are
used within LFSR-based stream ciphers. In particular, we concentrate on BSG and
ABSG, and consider two different setups for the analysis. In the first case,
the input is assumed to be a m-sequence; we show that all possible output
sequences can be classified into two sets, each of which is characterized by
the equivalence of their elements up to shifts. Furthermore, we prove that the
cardinality of each of these sets is equal to the period of one of its elements
and subsequently derive the first known bounds on the expected output period
(assuming that no subperiods exist). In the second setup, we work in a
probabilistic framework and assume that the input sequence is evenly
distributed (i.e., independent identically distributed Bernoulli process with
probability 1/2). Under these assumptions, we derive closed-form expressions
for the distribution of the output length and the output rate, which is shown
to be asymptotically Gaussian-distributed and concentrated around the mean with
exponential tightness.


title: Secure Broadcasting

abstract:
  Wyner's wiretap channel is extended to parallel broadcast channels and fading
channels with multiple receivers. In the first part of the paper, we consider
the setup of parallel broadcast channels with one sender, multiple intended
receivers, and one eavesdropper. We study the situations where the sender
broadcasts either a common message or independent messages to the intended
receivers. We derive upper and lower bounds on the common-message-secrecy
capacity, which coincide when the users are reversely degraded. For the case of
independent messages we establish the secrecy sum-capacity when the users are
reversely degraded.
  In the second part of the paper we apply our results to fading channels:
perfect channel state information of all intended receivers is known globally,
whereas the eavesdropper channel is known only to her. For the common message
case, a somewhat surprising result is proven: a positive rate can be achieved
independently of the number of intended receivers. For independent messages, an
opportunistic transmission scheme is presented that achieves the secrecy
sum-capacity in the limit of large number of receivers. Our results are stated
for a fast fading channel model. Extensions to the block fading model are also
discussed.


title: Authentication via wireless networks

abstract:
  Personal authentication is an important process we encounter almost every
day; when we are logging on a computer, entering a company where we work, or a
restricted area, when we are using our plastic credit cards to pay for a
service or to complete some other financial transaction, etc. In each of these
processes of personal authentication some kind of magnetic or optical token is
required. But by using novel technologies like mobile computing and wireless
networking, it is possible to avoid carrying multitude of ID cards or
remembering a number of PIN codes. Article shows how to efficiently
authenticate users via Personal Area Networks (PAN) like Bluetooth or IrDA
using commonplace AES (Rijndel) or MD5 encryption. This method can be
implemented on many types of mobile devices like Pocket PC PDA with Windows CE
(Windows Mobile 2003) real-time operating system, or any other customized OS,
so we will explain all components and key features of such basic system.


title: A note on using finite non-abelian $p$-groups in the MOR cryptosystem

abstract:
  The MOR cryptosystem is a natural generalization of the El-Gamal cryptosystem
to non-abelian groups. Using a $p$-group, a cryptosystem was built by this
author in 'A simple generalization of El-Gamal cryptosystem to non-abelian
groups'. It seems reasonable to assume the cryptosystem is as secure as the
El-Gamal cryptosystem over finite fields. A natural question arises can one
make a better cryptosystem using $p$-groups? In this paper we show that the
answer is no.


title:
Overcoming Hierarchical Difficulty by Hill-Climbing the Building Block
  Structure

abstract:
  The Building Block Hypothesis suggests that Genetic Algorithms (GAs) are
well-suited for hierarchical problems, where efficient solving requires proper
problem decomposition and assembly of solution from sub-solution with strong
non-linear interdependencies. The paper proposes a hill-climber operating over
the building block (BB) space that can efficiently address hierarchical
problems. The new Building Block Hill-Climber (BBHC) uses past hill-climb
experience to extract BB information and adapts its neighborhood structure
accordingly. The perpetual adaptation of the neighborhood structure allows the
method to climb the hierarchical structure solving successively the
hierarchical levels. It is expected that for fully non deceptive hierarchical
BB structures the BBHC can solve hierarchical problems in linearithmic time.
Empirical results confirm that the proposed method scales almost linearly with
the problem size thus clearly outperforms population based recombinative
methods.


title: Avoiding bias in cards cryptography

abstract:
  We outline the need for stricter requirements for unconditionally secure
cryptographic protocols inspired by the Russian Cards problem. A new
requirement CA4 is proposed that checks for bias in single card occurrence in
announcements consisting of alternatives for players' holdings of cards. This
requirement CA4 is shown to be equivalent to an alternative requirement CA5.
All announcements found to satisfy CA4 are 2-designs. We also show that all
binary designs are 3-designs. Instead of avoiding bias in announcements
produced by such protocols, one may as well apply unbiased protocols such that
patterns in announcements become meaningless. We gave two examples of such
protocols for card deal parameters (3,3,1), i.e. two of the players hold three
cards, and the remaining player, playing the role of eavesdropper, holds a
single card.


title: A Sum-Product Model as a Physical Basis for Shadow Fading

abstract:
  Shadow fading (slow fading) effects play a central role in mobile
communication system design and analysis. Experimental evidence indicates that
shadow fading exhibits log-normal power distribution almost universally, and
yet it is still not well understood what causes this. In this paper, we propose
a versatile sum-product signal model as a physical basis for shadow fading.
Simulation results imply that the proposed model results in log-normally
distributed local mean power regardless of the distributions of the
interactions in the radio channel, and hence it is capable of explaining the
log-normality in a wide variety of propagation scenarios. The sum-product model
also includes as its special cases the conventional product model as well as
the recently proposed sum model, and improves upon these by: a) being
applicable in both global and local distance scales; b) being more plausible
from physical point of view; c) providing better goodness-of-fit to log-normal
distribution than either of these models.


title:
Discrete Memoryless Interference and Broadcast Channels with
  Confidential Messages: Secrecy Rate Regions

abstract:
  We study information-theoretic security for discrete memoryless interference
and broadcast channels with independent confidential messages sent to two
receivers. Confidential messages are transmitted to their respective receivers
with information-theoretic secrecy. That is, each receiver is kept in total
ignorance with respect to the message intended for the other receiver. The
secrecy level is measured by the equivocation rate at the eavesdropping
receiver. In this paper, we present inner and outer bounds on secrecy capacity
regions for these two communication systems. The derived outer bounds have an
identical mutual information expression that applies to both channel models.
The difference is in the input distributions over which the expression is
optimized. The inner bound rate regions are achieved by random binning
techniques. For the broadcast channel, a double-binning coding scheme allows
for both joint encoding and preserving of confidentiality. Furthermore, we show
that, for a special case of the interference channel, referred to as the switch
channel, the two bound bounds meet. Finally, we describe several transmission
schemes for Gaussian interference channels and derive their achievable rate
regions while ensuring mutual information-theoretic secrecy. An encoding scheme
in which transmitters dedicate some of their power to create artificial noise
is proposed and shown to outperform both time-sharing and simple multiplexed
transmission of the confidential messages.


title: A Class of Multi-Channel Cosine Modulated IIR Filter Banks

abstract:
  This paper presents a class of multi-channel cosine-modulated filter banks
satisfying the perfect reconstruction (PR) property using an IIR prototype
filter. By imposing a suitable structure on the polyphase filter coefficients,
we show that it is possible to greatly simplify the PR condition, while
preserving the causality and stability of the system. We derive closed-form
expressions for the synthesis filters and also study the numerical stability of
the filter bank using frame theoretic bounds. Further, we show that it is
possible to implement this filter bank with much lower number of arithmetic
operations when compared to FIR filter banks with comparable performance. The
filter bank's modular structure also lends itself to efficient VLSI
implementation.


title:
An identity of Chernoff bounds with an interpretation in statistical
  physics and applications in information theory

abstract:
  An identity between two versions of the Chernoff bound on the probability a
certain large deviations event, is established. This identity has an
interpretation in statistical physics, namely, an isothermal equilibrium of a
composite system that consists of multiple subsystems of particles. Several
information--theoretic application examples, where the analysis of this large
deviations probability naturally arises, are then described from the viewpoint
of this statistical mechanical interpretation. This results in several
relationships between information theory and statistical physics, which we
hope, the reader will find insightful.


title:
Paging and Registration in Cellular Networks: Jointly Optimal Policies
  and an Iterative Algorithm

abstract:
  This paper explores optimization of paging and registration policies in
cellular networks. Motion is modeled as a discrete-time Markov process, and
minimization of the discounted, infinite-horizon average cost is addressed. The
structure of jointly optimal paging and registration policies is investigated
through the use of dynamic programming for partially observed Markov processes.
It is shown that there exist policies with a certain simple form that are
jointly optimal, though the dynamic programming approach does not directly
provide an efficient method to find the policies.
  An iterative algorithm for policies with the simple form is proposed and
investigated. The algorithm alternates between paging policy optimization and
registration policy optimization. It finds a pair of individually optimal
policies, but an example is given showing that the policies need not be jointly
optimal. Majorization theory and Riesz's rearrangement inequality are used to
show that jointly optimal paging and registration policies are given for
symmetric or Gaussian random walk models by the nearest-location-first paging
policy and distance threshold registration policies.


title: Exploring the academic invisible web

abstract:
  Purpose: To provide a critical review of Bergman's 2001 study on the Deep
Web. In addition, we bring a new concept into the discussion, the Academic
Invisible Web (AIW). We define the Academic Invisible Web as consisting of all
databases and collections relevant to academia but not searchable by the
general-purpose internet search engines. Indexing this part of the Invisible
Web is central to scientific search engines. We provide an overview of
approaches followed thus far. Design/methodology/approach: Discussion of
measures and calculations, estimation based on informetric laws. Literature
review on approaches for uncovering information from the Invisible Web.
Findings: Bergman's size estimate of the Invisible Web is highly questionable.
We demonstrate some major errors in the conceptual design of the Bergman paper.
A new (raw) size estimate is given. Research limitations/implications: The
precision of our estimate is limited due to a small sample size and lack of
reliable data. Practical implications: We can show that no single library alone
will be able to index the Academic Invisible Web. We suggest collaboration to
accomplish this task. Originality/value: Provides library managers and those
interested in developing academic search engines with data on the size and
attributes of the Academic Invisible Web.


title:
A Union Bound Approximation for Rapid Performance Evaluation of
  Punctured Turbo Codes

abstract:
  In this paper, we present a simple technique to approximate the performance
union bound of a punctured turbo code. The bound approximation exploits only
those terms of the transfer function that have a major impact on the overall
performance. We revisit the structure of the constituent convolutional encoder
and we develop a rapid method to calculate the most significant terms of the
transfer function of a turbo encoder. We demonstrate that, for a large
interleaver size, this approximation is very accurate. Furthermore, we apply
our proposed method to a family of punctured turbo codes, which we call
pseudo-randomly punctured codes. We conclude by emphasizing the benefits of our
approach compared to those employed previously. We also highlight the
advantages of pseudo-random puncturing over other puncturing schemes.


title: The Simplest Solution to an Underdetermined System of Linear Equations

abstract:
  Consider a d*n matrix A, with d<n. The problem of solving for x in y=Ax is
underdetermined, and has infinitely many solutions (if there are any). Given y,
the minimum Kolmogorov complexity solution (MKCS) of the input x is defined to
be an input z (out of many) with minimum Kolmogorov-complexity that satisfies
y=Az. One expects that if the actual input is simple enough, then MKCS will
recover the input exactly. This paper presents a preliminary study of the
existence and value of the complexity level up to which such a complexity-based
recovery is possible. It is shown that for the set of all d*n binary matrices
(with entries 0 or 1 and d<n), MKCS exactly recovers the input for an
overwhelming fraction of the matrices provided the Kolmogorov complexity of the
input is O(d). A weak converse that is loose by a log n factor is also
established for this case. Finally, we investigate the difficulty of finding a
matrix that has the property of recovering inputs with complexity of O(d) using
MKCS.


title: Wild, Wild Wikis: A way forward

abstract:
  Wikis can be considered as public domain knowledge sharing system. They
provide opportunity for those who may not have the privilege to publish their
thoughts through the traditional methods. They are one of the fastest growing
systems of online encyclopaedia. In this study, we consider the importance of
wikis as a way of creating, sharing and improving public knowledge. We identify
some of the problems associated with wikis to include, (a) identification of
the identities of information and its creator (b) accuracy of information (c)
justification of the credibility of authors (d) vandalism of quality of
information (e) weak control over the contents. A solution to some of these
problems is sought through the use of an annotation model. The model assumes
that contributions in wikis can be seen as annotation to the initial document.
It proposed a systematic control of contributors and contributions to the
initiative and the keeping of records of what existed and what was done to
initial documents. We believe that with this model, analysis can be done on the
progress of wiki initiatives. We assumed that using this model, wikis can be
better used for creation and sharing of knowledge for public use.


title:
AMIEDoT: An annotation model for document tracking and recommendation
  service

abstract:
  The primary objective of document annotation in whatever form, manual or
electronic is to allow those who may not have control to original document to
provide personal view on information source. Beyond providing personal
assessment to original information sources, we are looking at a situation where
annotation made can be used as additional source of information for document
tracking and recommendation service. Most of the annotation tools existing
today were conceived for their independent use with no reference to the creator
of the annotation. We propose AMIEDoT (Annotation Model for Information
Exchange and Document Tracking) an annotation model that can assist in document
tracking and recommendation service. The model is based on three parameters in
the acts of annotation. We believe that introducing document parameters, time
and the parameters of the creator of annotation into an annotation process can
be a dependable source to know, who used a document, when a document was used
and for what a document was used for. Beyond document tracking, our model can
be used in not only for selective dissemination of information but for
recommendation services. AMIEDoT can also be used for information sharing and
information reuse.


title: Orthogonal Codes for Robust Low-Cost Communication

abstract:
  Orthogonal coding schemes, known to asymptotically achieve the capacity per
unit cost (CPUC) for single-user ergodic memoryless channels with a zero-cost
input symbol, are investigated for single-user compound memoryless channels,
which exhibit uncertainties in their input-output statistical relationships. A
minimax formulation is adopted to attain robustness. First, a class of
achievable rates per unit cost (ARPUC) is derived, and its utility is
demonstrated through several representative case studies. Second, when the
uncertainty set of channel transition statistics satisfies a convexity
property, optimization is performed over the class of ARPUC through utilizing
results of minimax robustness. The resulting CPUC lower bound indicates the
ultimate performance of the orthogonal coding scheme, and coincides with the
CPUC under certain restrictive conditions. Finally, still under the convexity
property, it is shown that the CPUC can generally be achieved, through
utilizing a so-called mixed strategy in which an orthogonal code contains an
appropriate composition of different nonzero-cost input symbols.


title: AMIE: An annotation model for information research

abstract:
  The objective of most users for consulting any information database,
information warehouse or the internet is to resolve one problem or the other.
Available online or offline annotation tools were not conceived with the
objective of assisting users in their bid to resolve a decisional problem.
Apart from the objective and usage of annotation tools, how these tools are
conceived and classified has implication on their usage. Several criteria have
been used to categorize annotation concepts. Typically annotation are conceived
based on how it affect the organization of document been considered for
annotation or the organization of the resulting annotation. Our approach is
annotation that will assist in information research for decision making.
Annotation model for information exchange (AMIE) was conceived with the
objective of information sharing and reuse.


title:
Security Implications of Converged Networks and Protecting Them, without
  Compromising Efficiency

abstract:
  This dissertation has extensively looked into all aspects of VoIP
commu-nications technology, and information presented in preceding chapters,
which build up a solid framework to discuss the conceptual design model, and
investigate features that could be incorporated for actual Pro-jects, with
parameters that are tested on field values. The dissertation follows a
five-course model, for answering different questions, both tech-nical and
businesslike, around central issues, that have been crucial to explanation of
the topic; starting with a general overview of VoIP tech-nology, analyzing
current VoIP encryption methods, identifying security threats, designing a
robust VoIP system based on particulars discussed in preceding chapters, and
finally, a VoIP simulation.


title:
Informed Dynamic Scheduling for Belief-Propagation Decoding of LDPC
  Codes

abstract:
  Low-Density Parity-Check (LDPC) codes are usually decoded by running an
iterative belief-propagation, or message-passing, algorithm over the factor
graph of the code. The traditional message-passing schedule consists of
updating all the variable nodes in the graph, using the same pre-update
information, followed by updating all the check nodes of the graph, again,
using the same pre-update information. Recently several studies show that
sequential scheduling, in which messages are generated using the latest
available information, significantly improves the convergence speed in terms of
number of iterations. Sequential scheduling raises the problem of finding the
best sequence of message updates. This paper presents practical scheduling
strategies that use the value of the messages in the graph to find the next
message to be updated. Simulation results show that these informed update
sequences require significantly fewer iterations than standard sequential
schedules. Furthermore, the paper shows that informed scheduling solves some
standard trapping set errors. Therefore, it also outperforms traditional
scheduling for a large numbers of iterations. Complexity and implementability
issues are also addressed.


title:
The General Gaussian Multiple Access and Two-Way Wire-Tap Channels:
  Achievable Rates and Cooperative Jamming

abstract:
  The General Gaussian Multiple Access Wire-Tap Channel (GGMAC-WT) and the
Gaussian Two-Way Wire-Tap Channel (GTW-WT) are considered. In the GGMAC-WT,
multiple users communicate with an intended receiver in the presence of an
eavesdropper who receives their signals through another GMAC. In the GTW-WT,
two users communicate with each other over a common Gaussian channel, with an
eavesdropper listening through a GMAC. A secrecy measure that is suitable for
this multi-terminal environment is defined, and achievable secrecy rate regions
are found for both channels. For both cases, the power allocations maximizing
the achievable secrecy sum-rate are determined. It is seen that the optimum
policy may prevent some terminals from transmission in order to preserve the
secrecy of the system. Inspired by this construct, a new scheme,
\ital{cooperative jamming}, is proposed, where users who are prevented from
transmitting according to the secrecy sum-rate maximizing power allocation
policy "jam" the eavesdropper, thereby helping the remaining users. This scheme
is shown to increase the achievable secrecy sum-rate. Overall, our results show
that in multiple-access scenarios, users can help each other to collectively
achieve positive secrecy rates. In other words, cooperation among users can be
invaluable for achieving secrecy for the system.


title: Fast Computation of Small Cuts via Cycle Space Sampling

abstract:
  We describe a new sampling-based method to determine cuts in an undirected
graph. For a graph (V, E), its cycle space is the family of all subsets of E
that have even degree at each vertex. We prove that with high probability,
sampling the cycle space identifies the cuts of a graph. This leads to simple
new linear-time sequential algorithms for finding all cut edges and cut pairs
(a set of 2 edges that form a cut) of a graph.
  In the model of distributed computing in a graph G=(V, E) with O(log V)-bit
messages, our approach yields faster algorithms for several problems. The
diameter of G is denoted by Diam, and the maximum degree by Delta. We obtain
simple O(Diam)-time distributed algorithms to find all cut edges,
2-edge-connected components, and cut pairs, matching or improving upon previous
time bounds. Under natural conditions these new algorithms are universally
optimal --- i.e. a Omega(Diam)-time lower bound holds on every graph. We obtain
a O(Diam+Delta/log V)-time distributed algorithm for finding cut vertices; this
is faster than the best previous algorithm when Delta, Diam = O(sqrt(V)). A
simple extension of our work yields the first distributed algorithm with
sub-linear time for 3-edge-connected components. The basic distributed
algorithms are Monte Carlo, but they can be made Las Vegas without increasing
the asymptotic complexity.
  In the model of parallel computing on the EREW PRAM our approach yields a
simple algorithm with optimal time complexity O(log V) for finding cut pairs
and 3-edge-connected components.


title: Nearest Neighbor Network Traversal

abstract:
  A mobile agent in a network wants to visit every node of an n-node network,
using a small number of steps. We investigate the performance of the following
``nearest neighbor'' heuristic: always go to the nearest unvisited node. If the
network graph never changes, then from (Rosenkrantz, Stearns and Lewis, 1977)
and (Hurkens and Woeginger, 2004) it follows that Theta(n log n) steps are
necessary and sufficient in the worst case. We give a simpler proof of the
upper bound and an example that improves the best known lower bound.
  We investigate how the performance of this heuristic changes when it is
distributively implemented in a network. Even if network edges are allow to
fail over time, we show that the nearest neighbor strategy never runs for more
than O(n^2) iterations. We also show that any strategy can be forced to take at
least n(n-1)/2 steps before all nodes are visited, if the edges of the network
are deleted in an adversarial way.


title: Guessing based on length functions

abstract:
  A guessing wiretapper's performance on a Shannon cipher system is analyzed
for a source with memory. Close relationships between guessing functions and
length functions are first established. Subsequently, asymptotically optimal
encryption and attack strategies are identified and their performances analyzed
for sources with memory. The performance metrics are exponents of guessing
moments and probability of large deviations. The metrics are then characterized
for unifilar sources. Universal asymptotically optimal encryption and attack
strategies are also identified for unifilar sources. Guessing in the increasing
order of Lempel-Ziv coding lengths is proposed for finite-state sources, and
shown to be asymptotically optimal. Finally, competitive optimality properties
of guessing in the increasing order of description lengths and Lempel-Ziv
coding lengths are demonstrated.


title: The Bedwyr system for model checking over syntactic expressions

abstract:
  Bedwyr is a generalization of logic programming that allows model checking
directly on syntactic expressions possibly containing bindings. This system,
written in OCaml, is a direct implementation of two recent advances in the
theory of proof search. The first is centered on the fact that both finite
success and finite failure can be captured in the sequent calculus by
incorporating inference rules for definitions that allow fixed points to be
explored. As a result, proof search in such a sequent calculus can capture
simple model checking problems as well as may and must behavior in operational
semantics. The second is that higher-order abstract syntax is directly
supported using term-level $\lambda$-binders and the $\nabla$ quantifier. These
features allow reasoning directly on expressions containing bound variables.


title:
On a family of strong geometric spanners that admit local routing
  strategies

abstract:
  We introduce a family of directed geometric graphs, denoted $\paz$, that
depend on two parameters $\lambda$ and $\theta$. For $0\leq
\theta<\frac{\pi}{2}$ and ${1/2} < \lambda < 1$, the $\paz$ graph is a strong
$t$-spanner, with $t=\frac{1}{(1-\lambda)\cos\theta}$. The out-degree of a node
in the $\paz$ graph is at most $\lfloor2\pi/\min(\theta,
\arccos\frac{1}{2\lambda})\rfloor$. Moreover, we show that routing can be
achieved locally on $\paz$. Next, we show that all strong $t$-spanners are also
$t$-spanners of the unit disk graph. Simulations for various values of the
parameters $\lambda$ and $\theta$ indicate that for random point sets, the
spanning ratio of $\paz$ is better than the proven theoretical bounds.


title: Interpolation-based Decoding of Alternant Codes

abstract:
  We formulate the classical decoding algorithm of alternant codes afresh based
on interpolation as in Sudan's list decoding of Reed-Solomon codes, and thus
get rid of the key equation and the linear recurring sequences in the theory.
The result is a streamlined exposition of the decoding algorithm using a bit of
the theory of Groebner bases of modules.


title: Ulam's Conjecture is True for Connected Graphs

abstract: This submission has been withdrawn at the request of the author.


title:
On the decidability and complexity of Metric Temporal Logic over finite
  words

abstract:
  Metric Temporal Logic (MTL) is a prominent specification formalism for
real-time systems. In this paper, we show that the satisfiability problem for
MTL over finite timed words is decidable, with non-primitive recursive
complexity. We also consider the model-checking problem for MTL: whether all
words accepted by a given Alur-Dill timed automaton satisfy a given MTL
formula. We show that this problem is decidable over finite words. Over
infinite words, we show that model checking the safety fragment of MTL--which
includes invariance and time-bounded response properties--is also decidable.
These results are quite surprising in that they contradict various claims to
the contrary that have appeared in the literature.


title:
Induced Hilbert Space, Markov Chain, Diffusion Map and Fock Space in
  Thermophysics

abstract:
  In this article, we continue to explore Probability Bracket Notation (PBN),
proposed in our previous article. Using both Dirac vector bracket notation
(VBN) and PBN, we define induced Hilbert space and induced sample space, and
propose that there exists an equivalence relation between a Hilbert space and a
sample space constructed from the same base observable(s). Then we investigate
Markov transition matrices and their eigenvectors to make diffusion maps with
two examples: a simple graph theory example, to serve as a prototype of
bidirectional transition operator; a famous text document example in IR
literature, to serve as a tutorial of diffusion map in text document space. We
show that the sample space of the Markov chain and the Hilbert space spanned by
the eigenvectors of the transition matrix are not equivalent. At the end, we
apply our PBN and equivalence proposal to Thermophysics by associating sample
(phase) space with the Hilbert space of a single particle and the Fock space of
many-particle systems.


title:
Transmitter and Precoding Order Optimization for Nonlinear Downlink
  Beamforming

abstract:
  The downlink of a multiple-input multiple output (MIMO) broadcast channel
(BC) is considered, where each receiver is equipped with a single antenna and
the transmitter performs nonlinear Dirty-Paper Coding (DPC). We present an
efficient algorithm that finds the optimum transmit filters and power
allocation as well as the optimum precoding order(s) possibly affording
time-sharing between individual DPC orders. Subsequently necessary and
sufficient conditions for the optimality of an arbitrary precoding order are
derived. Based on these we propose a suboptimal algorithm showing excellent
performance and having low complexity.


title: Tree automata and separable sets of input variables

abstract:
  We consider the computational complexity of tree transducers, depending on
their separable sets of input variables.


title: A Sequential Algorithm for Generating Random Graphs

abstract:
  We present a nearly-linear time algorithm for counting and randomly
generating simple graphs with a given degree sequence in a certain range. For
degree sequence $(d_i)_{i=1}^n$ with maximum degree $d_{\max}=O(m^{1/4-\tau})$,
our algorithm generates almost uniform random graphs with that degree sequence
in time $O(m\,d_{\max})$ where $m=\f{1}{2}\sum_id_i$ is the number of edges in
the graph and $\tau$ is any positive constant. The fastest known algorithm for
uniform generation of these graphs McKay Wormald (1990) has a running time of
$O(m^2d_{\max}^2)$. Our method also gives an independent proof of McKay's
estimate McKay (1985) for the number of such graphs.
  We also use sequential importance sampling to derive fully Polynomial-time
Randomized Approximation Schemes (FPRAS) for counting and uniformly generating
random graphs for the same range of $d_{\max}=O(m^{1/4-\tau})$.
  Moreover, we show that for $d = O(n^{1/2-\tau})$, our algorithm can generate
an asymptotically uniform $d$-regular graph. Our results improve the previous
bound of $d = O(n^{1/3-\tau})$ due to Kim and Vu (2004) for regular graphs.


title: Bayesian Network Tomography and Inference

abstract:
  The aim of this technical report is to give a short overview of known
techniques for network tomography (introduced in the paper of Vardi (1996)),
extended by a Bayesian approach originating Tebaldi and West (1998). Since the
studies of A.K. Erlang (1878-1929) on telephone networks in the last
millennium, lots of needs are seen in todays applications of networks and
network tomography, so for instance networks are a critical component of the
information structure supporting finance, commerce and even civil and national
defence. An attack on a network can be performed as an intrusion in the network
or as sending a lot of fault information and disturbing the network flow. Such
attacks can be detected by modelling the traffic flows in a network, by
counting the source destination packets and even by measuring counts over time
and by drawing a comparison with this 'time series' for instance.


title: Efficient Searching and Retrieval of Documents in PROSA

abstract:
  Retrieving resources in a distributed environment is more difficult than
finding data in centralised databases. In the last decade P2P system arise as
new and effective distributed architectures for resource sharing, but searching
in such environments could be difficult and time-consuming. In this paper we
discuss efficiency of resource discovery in PROSA, a self-organising P2P system
heavily inspired by social networks. All routing choices in PROSA are made
locally, looking only at the relevance of the next peer to each query. We show
that PROSA is able to effectively answer queries for rare documents, forwarding
them through the most convenient path to nodes that much probably share
matching resources. This result is heavily related to the small-world structure
that naturally emerges in PROSA.


title: Exploiting social networks dynamics for P2P resource organisation

abstract:
  In this paper we present a formal description of PROSA, a P2P resource
management system heavily inspired by social networks. Social networks have
been deeply studied in the last two decades in order to understand how
communities of people arise and grow. It is a widely known result that networks
of social relationships usually evolves to small-worlds, i.e. networks where
nodes are strongly connected to neighbours and separated from all other nodes
by a small amount of hops. This work shows that algorithms implemented into
PROSA allow to obtain an efficient small-world P2P network.


title:
Reconstructing the Nonlinear Filter Function of LILI-128 Stream Cipher
  Based on Complexity

abstract:
  In this letter we assert that we have reconstructed the nonlinear filter
function of LILI-128 stream cipher on IBM notebook PC using MATLAB. Our
reconstruction need approximately 2^12~2^13 and the attack consumes 5825.016
sec (using tic and toc sentences of MATLAB) or 5825.016/3600=1.6181hours. We
got the expression of the nonlinear filter function fd of Lili-128 which has 46
items from liner items to nonlinear items based on complexity, the phase space
reconstruction, Clustering and nonlinear prediction. We have verified our
reconstruction result correctness by simulating the overview of Lili-128
keystream generators using our getting fd and implement designers reference
module of the Lili-128 stream cipher, and two methods produce the same
synchronous keystream sequence on same initial state, so that our research work
proves that the nonlinear filter function of LILI-128 stream cipher is
successfully reconstructed.


title: Tree Automata and Essential Input Variables

abstract:
  We introduce and study the essential inputs (variables) for terms (trees) and
tree automata.


title:
Syndrome Decoding of Reed-Solomon Codes Beyond Half the Minimum Distance
  based on Shift-Register Synthesis

abstract:
  In this paper, a new approach for decoding low-rate Reed-Solomon codes beyond
half the minimum distance is considered and analyzed. Unlike the Sudan
algorithm published in 1997, this new approach is based on multi-sequence
shift-register synthesis, which makes it easy to understand and simple to
implement. The computational complexity of this shift-register based algorithm
is of the same order as the complexity of the well-known Berlekamp-Massey
algorithm. Moreover, the error correcting radius coincides with the error
correcting radius of the original Sudan algorithm, and the practical decoding
performance observed on a q-ary symmetric channel (QSC) is virtually identical
to the decoding performance of the Sudan algorithm. Bounds for the failure and
error probability as well as for the QSC decoding performance of the new
algorithm are derived, and the performance is illustrated by means of examples.


title:
AICA: a New Pair Force Evaluation Method for Parallel Molecular Dynamics
  in Arbitrary Geometries

abstract:
  A new algorithm for calculating intermolecular pair forces in Molecular
Dynamics (MD) simulations on a distributed parallel computer is presented. The
Arbitrary Interacting Cells Algorithm (AICA) is designed to operate on
geometrical domains defined by an unstructured, arbitrary polyhedral mesh,
which has been spatially decomposed into irregular portions for
parallelisation. It is intended for nano scale fluid mechanics simulation by MD
in complex geometries, and to provide the MD component of a hybrid MD/continuum
simulation. AICA has been implemented in the open-source computational toolbox
OpenFOAM, and verified against a published MD code.


title:
Uplink Capacity and Interference Avoidance for Two-Tier Femtocell
  Networks

abstract:
  Two-tier femtocell networks-- comprising a conventional macrocellular network
plus embedded femtocell hotspots-- offer an economically viable solution to
achieving high cellular user capacity and improved coverage. With universal
frequency reuse and DS-CDMA transmission however, the ensuing cross-tier
cochannel interference (CCI) causes unacceptable outage probability. This paper
develops an uplink capacity analysis and interference avoidance strategy in
such a two-tier CDMA network. We evaluate a network-wide area spectral
efficiency metric called the \emph{operating contour (OC)} defined as the
feasible combinations of the average number of active macrocell users and
femtocell base stations (BS) per cell-site that satisfy a target outage
constraint. The capacity analysis provides an accurate characterization of the
uplink outage probability, accounting for power control, path-loss and
shadowing effects. Considering worst case CCI at a corner femtocell, results
reveal that interference avoidance through a time-hopped CDMA physical layer
and sectorized antennas allows about a 7x higher femtocell density, relative to
a split spectrum two-tier network with omnidirectional femtocell antennas. A
femtocell exclusion region and a tier selection based handoff policy offers
modest improvements in the OCs. These results provide guidelines for the design
of robust shared spectrum two-tier networks.


title: Fast Exact Method for Solving the Travelling Salesman Problem

abstract:
  This paper describes TSP exact solution of polynomial complexity. It is
considered properties of proposed method. Effectiveness of proposed solution is
illustrated by outcomes of computer modeling.


title: Patterns of technological progress: A Predictability-Based Perspective

abstract:
  The paper tries to identify new emerging patterns in the context of
technological progress. Just as industrialization is associated with
rationalization, mechanization, and automation, the Internet age is associated
with computer models, embedded knowledge, and collaboration. Comparison among
patterns is highlighted and analysis is done from predictability-based
perspective.


title:
High Performance Direct Gravitational N-body Simulations on Graphics
  Processing Units

abstract:
  We present the results of gravitational direct $N$-body simulations using the
commercial graphics processing units (GPU) NVIDIA Quadro FX1400 and GeForce
8800GTX, and compare the results with GRAPE-6Af special purpose hardware. The
force evaluation of the $N$-body problem was implemented in Cg using the GPU
directly to speed-up the calculations. The integration of the equations of
motions were, running on the host computer, implemented in C using the 4th
order predictor-corrector Hermite integrator with block time steps. We find
that for a large number of particles ($N \apgt 10^4$) modern graphics
processing units offer an attractive low cost alternative to GRAPE special
purpose hardware. A modern GPU continues to give a relatively flat scaling with
the number of particles, comparable to that of the GRAPE. Using the same time
step criterion the total energy of the $N$-body system was conserved better
than to one in $10^6$ on the GPU, which is only about an order of magnitude
worse than obtained with GRAPE. For $N\apgt 10^6$ the GeForce 8800GTX was about
20 times faster than the host computer. Though still about an order of
magnitude slower than GRAPE, modern GPU's outperform GRAPE in their low cost,
long mean time between failure and the much larger onboard memory; the
GRAPE-6Af holds at most 256k particles whereas the GeForce 8800GTF can hold 9
million particles in memory.


title: Essential Inputs and Minimal Tree Automata

abstract:
  We continue studying essential inputs of trees and automata. Strongly
essential inputs of trees are introduced and studied. Various examples for
application in Computer Science are shown.


title: Tree Automata and Essential Subtrees

abstract:
  We introduce essential subtrees for terms (trees) and tree automata . There
are some results concerning independent sets of subtrees and separable sets for
a tree and an automaton.


title:
On the Maximal Diversity Order of Spatial Multiplexing with Transmit
  Antenna Selection

abstract:
  Zhang et. al. recently derived upper and lower bounds on the achievable
diversity of an N_R x N_T i.i.d. Rayleigh fading multiple antenna system using
transmit antenna selection, spatial multiplexing and a linear receiver
structure. For the case of L = 2 transmitting (out of N_T available) antennas
the bounds are tight and therefore specify the maximal diversity order. For the
general case with L <= min(N_R,N_T) transmitting antennas it was conjectured
that the maximal diversity is (N_T-L+1)(N_R-L+1) which coincides with the lower
bound. Herein, we prove this conjecture for the zero forcing and zero forcing
decision feedback (with optimal detection ordering) receiver structures.


title:
Characterization of $m$-Sequences of Lengths $2^{2k}-1$ and $2^k-1$ with
  Three-Valued Crosscorrelation

abstract:
  Considered is the distribution of the crosscorrelation between $m$-sequences
of length $2^m-1$, where $m=2k$, and $m$-sequences of shorter length $2^k-1$.
New pairs of $m$-sequences with three-valued crosscorrelation are found and the
complete correlation distribution is determined. Finally, we conjecture that
there are no more cases with a three-valued crosscorrelation apart from the
ones proven here.


title: Assessing the Value of Coooperation in Wikipedia

abstract:
  Since its inception six years ago, the online encyclopedia Wikipedia has
accumulated 6.40 million articles and 250 million edits, contributed in a
predominantly undirected and haphazard fashion by 5.77 million unvetted
volunteers. Despite the apparent lack of order, the 50 million edits by 4.8
million contributors to the 1.5 million articles in the English-language
Wikipedia follow strong certain overall regularities. We show that the
accretion of edits to an article is described by a simple stochastic mechanism,
resulting in a heavy tail of highly visible articles with a large number of
edits. We also demonstrate a crucial correlation between article quality and
number of edits, which validates Wikipedia as a successful collaborative
effort.


title:
Recruitment, Preparation, Retention: A case study of computing culture
  at the University of Illinois at Urbana-Champaign

abstract:
  Computer science is seeing a decline in enrollment at all levels of
education, including undergraduate and graduate study. This paper reports on
the results of a study conducted at the University of Illinois at
Urbana-Champaign which evaluated students attitudes regarding three areas which
can contribute to improved enrollment in the Department of Computer Science:
Recruitment, preparation and retention. The results of our study saw two
themes. First, the department's tight research focus appears to draw
significant attention from other activities -- such as teaching, service, and
other community-building activities -- that are necessary for a department's
excellence. Yet, as demonstrated by our second theme, one partial solution is
to better promote such activities already employed by the department to its
students and faculty. Based on our results, we make recommendations for
improvements and enhancements based on the current state of practice at peer
institutions.


title: An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation

abstract:
  Monotonicity is a simple yet significant qualitative characteristic. We
consider the problem of segmenting an array in up to K segments. We want
segments to be as monotonic as possible and to alternate signs. We propose a
quality metric for this problem, present an optimal linear time algorithm based
on novel formalism, and compare experimentally its performance to a linear time
top-down regression algorithm. We show that our algorithm is faster and more
accurate. Applications include pattern recognition and qualitative modeling.


title: Attribute Value Reordering For Efficient Hybrid OLAP

abstract:
  The normalization of a data cube is the ordering of the attribute values. For
large multidimensional arrays where dense and sparse chunks are stored
differently, proper normalization can lead to improved storage efficiency. We
show that it is NP-hard to compute an optimal normalization even for 1x3
chunks, although we find an exact algorithm for 1x2 chunks. When dimensions are
nearly statistically independent, we show that dimension-wise attribute
frequency sorting is an optimal normalization and takes time O(d n log(n)) for
data cubes of size n^d. When dimensions are not independent, we propose and
evaluate several heuristics. The hybrid OLAP (HOLAP) storage mechanism is
already 19%-30% more efficient than ROLAP, but normalization can improve it
further by 9%-13% for a total gain of 29%-44% over ROLAP.


title: Slope One Predictors for Online Rating-Based Collaborative Filtering

abstract:
  Rating-based collaborative filtering is the process of predicting how a user
would rate a given item from other user ratings. We propose three related slope
one schemes with predictors of the form f(x) = x + b, which precompute the
average difference between the ratings of one item and another for users who
rated both. Slope one algorithms are easy to implement, efficient to query,
reasonably accurate, and they support both online queries and dynamic updates,
which makes them good candidates for real-world systems. The basic slope one
scheme is suggested as a new reference scheme for collaborative filtering. By
factoring in items that a user liked separately from items that a user
disliked, we achieve results competitive with slower memory-based schemes over
the standard benchmark EachMovie and Movielens data sets while better
fulfilling the desiderata of CF applications.


title: Designing a Resource Broker for Heterogeneous Grids

abstract:
  Grids provide uniform access to aggregations of heterogeneous resources and
services such as computers, networks and storage owned by multiple
organizations. However, such a dynamic environment poses many challenges for
application composition and deployment. In this paper, we present the design of
the Gridbus Grid resource broker that allows users to create applications and
specify different objectives through different interfaces without having to
deal with the complexity of Grid infrastructure. We present the unique
requirements that motivated our design and discuss how these provide
flexibility in extending the functionality of the broker to support different
low-level middlewares and user interfaces. We evaluate the broker with
different job profiles and Grid middleware and conclude with the lessons learnt
from our development experience.


title:
A Local Tree Structure is NOT Sufficient for the Local Optimality of
  Message-Passing Decoding in Low Density Parity Check Codes

abstract:
  We address the problem,`Is a local tree structure sufficient for the local
optimality of message passing algorithm in low density parity check codes?'.It
is shown that the answer is negative. Using this observation, we pinpoint a
flaw in the proof of Theorem 1 in the paper `The Capacity of Low-Density
Parity-Check Codes Under Message-Passing Decoding' by Thomas J. Richardson and
R\"udiger L.Urbanke\cite{RUCapacity}. We further provide a new proof of that
theorem based on a different argument.


title:
On the Complexity of Exact Maximum-Likelihood Decoding for
  Asymptotically Good Low Density Parity Check Codes

abstract:
  Since the classical work of Berlekamp, McEliece and van Tilborg, it is well
known that the problem of exact maximum-likelihood (ML) decoding of general
linear codes is NP-hard. In this paper, we show that exact ML decoding of a
classs of asymptotically good error correcting codes--expander codes, a special
case of low density parity check (LDPC) codes--over binary symmetric channels
(BSCs) is possible with an expected polynomial complexity. More precisely, for
any bit-flipping probability, $p$, in a nontrivial range, there exists a rate
region of non-zero support and a family of asymptotically good codes, whose
error probability decays exponentially in coding length $n$, for which ML
decoding is feasible in expected polynomial time. Furthermore, as $p$
approaches zero, this rate region approaches the channel capacity region. The
result is based on the existence of polynomial-time suboptimal decoding
algorithms that provide an ML certificate and the ability to compute the
probability that the suboptimal decoder yields the ML solution. One such ML
certificate decoder is the LP decoder of Feldman; we also propose a more
efficient $O(n^2)$ algorithm based on the work of Sipser and Spielman and the
Ford-Fulkerson algorithm. The results can be extended to AWGN channels and
suggest that it may be feasible to eliminate the error floor phenomenon
associated with message-passage decoding of LDPC codes in the high SNR regime.
Finally, we observe that the argument of Berlekamp, McEliece and van Tilborg
can be used to show that ML decoding of the considered class of codes
constructed from LDPC codes with regular left degree, of which the considered
expander codes are a special case, remains NP-hard; thus giving an interesting
contrast between the worst-case and expected complexities.


title:
Linking Microscopic and Macroscopic Models for Evolution: Markov Chain
  Network Training and Conservation Law Approximations

abstract:
  In this paper, a general framework for the analysis of a connection between
the training of artificial neural networks via the dynamics of Markov chains
and the approximation of conservation law equations is proposed. This framework
allows us to demonstrate an intrinsic link between microscopic and macroscopic
models for evolution via the concept of perturbed generalized dynamic systems.
The main result is exemplified with a number of illustrative examples where
efficient numerical approximations follow directly from network-based
computational models, viewed here as Markov chain approximations. Finally,
stability and consistency conditions of such computational models are
discussed.


title:
Coupling Control and Human-Centered Automation in Mathematical Models of
  Complex Systems

abstract:
  In this paper we analyze mathematically how human factors can be effectively
incorporated into the analysis and control of complex systems. As an example,
we focus our discussion around one of the key problems in the Intelligent
Transportation Systems (ITS) theory and practice, the problem of speed control,
considered here as a decision making process with limited information
available. The problem is cast mathematically in the general framework of
control problems and is treated in the context of dynamically changing
environments where control is coupled to human-centered automation. Since in
this case control might not be limited to a small number of control settings,
as it is often assumed in the control literature, serious difficulties arise in
the solution of this problem. We demonstrate that the problem can be reduced to
a set of Hamilton-Jacobi-Bellman equations where human factors are incorporated
via estimations of the system Hamiltonian. In the ITS context, these
estimations can be obtained with the use of on-board equipment like
sensors/receivers/actuators, in-vehicle communication devices, etc. The
proposed methodology provides a way to integrate human factor into the solving
process of the models for other complex dynamic systems.


title:
A note on rate-distortion functions for nonstationary Gaussian
  autoregressive processes

abstract:
  Source coding theorems and Shannon rate-distortion functions were studied for
the discrete-time Wiener process by Berger and generalized to nonstationary
Gaussian autoregressive processes by Gray and by Hashimoto and Arimoto.
Hashimoto and Arimoto provided an example apparently contradicting the methods
used in Gray, implied that Gray's rate-distortion evaluation was not correct in
the nonstationary case, and derived a new formula that agreed with previous
results for the stationary case and held in the nonstationary case. In this
correspondence it is shown that the rate-distortion formulas of Gray and
Hashimoto and Arimoto are in fact consistent and that the example of of
Hashimoto and Arimoto does not form a counter example to the methods or results
of the earlier paper. Their results do provide an alternative, but equivalent,
formula for the rate-distortion function in the nonstationary case and they
provide a concrete example that the classic Kolmogorov formula differs from the
autoregressive formula when the autoregressive source is not stationary. Some
observations are offered on the different versions of the Toeplitz asymptotic
eigenvalue distribution theorem used in the two papers to emphasize how a
slight modification of the classic theorem avoids the problems with certain
singularities.


title: Succinct Sampling on Streams

abstract:
  A streaming model is one where data items arrive over long period of time,
either one item at a time or in bursts. Typical tasks include computing various
statistics over a sliding window of some fixed time-horizon. What makes the
streaming model interesting is that as the time progresses, old items expire
and new ones arrive. One of the simplest and central tasks in this model is
sampling. That is, the task of maintaining up to $k$ uniformly distributed
items from a current time-window as old items expire and new ones arrive. We
call sampling algorithms {\bf succinct} if they use provably optimal (up to
constant factors) {\bf worst-case} memory to maintain $k$ items (either with or
without replacement). We stress that in many applications structures that have
{\em expected} succinct representation as the time progresses are not
sufficient, as small probability events eventually happen with probability 1.
Thus, in this paper we ask the following question: are Succinct Sampling on
Streams (or $S^3$-algorithms)possible, and if so for what models? Perhaps
somewhat surprisingly, we show that $S^3$-algorithms are possible for {\em all}
variants of the problem mentioned above, i.e. both with and without replacement
and both for one-at-a-time and bursty arrival models. Finally, we use $S^3$
algorithms to solve various problems in sliding windows model, including
frequency moments, counting triangles, entropy and density estimations. For
these problems we present \emph{first} solutions with provable worst-case
memory guarantees.


title:
A Simplified Suspension Calculus and its Relationship to Other Explicit
  Substitution Calculi

abstract:
  This paper concerns the explicit treatment of substitutions in the lambda
calculus. One of its contributions is the simplification and rationalization of
the suspension calculus that embodies such a treatment. The earlier version of
this calculus provides a cumbersome encoding of substitution composition, an
operation that is important to the efficient realization of reduction. This
encoding is simplified here, resulting in a treatment that is easy to use
directly in applications. The rationalization consists of the elimination of a
practically inconsequential flexibility in the unravelling of substitutions
that has the inadvertent side effect of losing contextual information in terms;
the modified calculus now has a structure that naturally supports logical
analyses, such as ones related to the assignment of types, over lambda terms.
The overall calculus is shown to have pleasing theoretical properties such as a
strongly terminating sub-calculus for substitution and confluence even in the
presence of term meta variables that are accorded a grafting interpretation.
Another contribution of the paper is the identification of a broad set of
properties that are desirable for explicit substitution calculi to support and
a classification of a variety of proposed systems based on these. The
suspension calculus is used as a tool in this study. In particular, mappings
are described between it and the other calculi towards understanding the
characteristics of the latter.


title: Games on the Sperner Triangle

abstract:
  We create a new two-player game on the Sperner Triangle based on Sperner's
lemma. Our game has simple rules and several desirable properties. First, the
game is always certain to have a winner. Second, like many other interesting
games such as Hex and Geography, we prove that deciding whether one can win our
game is a PSPACE-complete problem. Third, there is an elegant balance in the
game such that neither the first nor the second player always has a decisive
advantage. We provide a web-based version of the game, playable at:
http://cs-people.bu.edu/paithan/spernerGame/ . In addition we propose other
games, also based on fixed-point theorems.


title:
On the Capacity of the Single Source Multiple Relay Single Destination
  Mesh Network

abstract:
  In this paper, we derive the information theoretic capacity of a special
class of mesh networks. A mesh network is a heterogeneous wireless network in
which the transmission among power limited nodes is assisted by powerful
relays, which use the same wireless medium. We investigate the mesh network
when there is one source, one destination, and multiple relays, which we call
the single source multiple relay single destination (SSMRSD) mesh network. We
derive the asymptotic capacity of the SSMRSD mesh network when the relay powers
grow to infinity. Our approach is as follows. We first look at an upper bound
on the information theoretic capacity of these networks in a Gaussian setting.
We then show that this bound is achievable asymptotically using the
compress-and-forward strategy for the multiple relay channel. We also perform
numerical computations for the case when the relays have finite powers. We
observe that even when the relay power is only a few times larger than the
source power, the compress-and-forward rate gets close to the capacity. The
results indicate the value of cooperation in wireless mesh networks. The
capacity characterization quantifies how the relays can cooperate, using the
compress-and-forward strategy, to either conserve node energy or to increase
transmission rate.


title:
On a characterization of cellular automata in tilings of the hyperbolic
  plane

abstract:
  In this paper, we look at the extention of Hedlund's characterization of
cellular automata to the case of cellular automata in the hyperbolic plane.
This requires an additionnal condition. The new theorem is proved with full
details in the case of the pentagrid and in the case of the ternary heptagrid
and enough indications to show that it holds also on the grids $\{p,q\}$ of the
hyperbolic plane.


title: Analysis of Steiner subtrees of Random Trees for Traceroute Algorithms

abstract:
  We consider in this paper the problem of discovering, via a traceroute
algorithm, the topology of a network, whose graph is spanned by an infinite
branching process. A subset of nodes is selected according to some criterion.
As a measure of efficiency of the algorithm, the Steiner distance of the
selected nodes, i.e. the size of the spanning sub-tree of these nodes, is
investigated. For the selection of nodes, two criteria are considered: A node
is randomly selected with a probability, which is either independent of the
depth of the node (uniform model) or else in the depth biased model, is
exponentially decaying with respect to its depth. The limiting behavior the
size of the discovered subtree is investigated for both models.


title:
In Search of Simplicity: A Self-Organizing Multi-Source Multicast
  Overlay

abstract:
  Multicast communication primitives have broad utility as building blocks for
distributed applications. The challenge is to create and maintain the
distributed structures that support these primitives while accounting for
volatile end nodes and variable network characteristics. Most solutions
proposed to date rely on complex algorithms or global information, thus
limiting the scale of deployments and acceptance outside the academic realm.
This article introduces a low-complexity, self organizing solution for
maintaining multicast trees, that we refer to as UMM (Unstructured Multi-source
Multicast). UMM uses traditional distributed systems techniques: layering,
soft-state, and passive data collection to adapt to the dynamics of the
physical network and maintain data dissemination trees. The result is a simple,
adaptive system with lower overheads than more complex alternatives. We have
implemented UMM and evaluated it on a 100-node PlanetLab testbed and on up to
1024-node emulated ModelNet networks Extensive experimental evaluations
demonstrate UMM's low overhead, efficient network usage compared to alternative
solutions, and ability to quickly adapt to network changes and to recover from
failures.