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

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


title: The Nature of Novelty Detection

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


title: Degrees of Freedom in Multiuser MIMO

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


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

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


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

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


title: Precoding for 2x2 Doubly-Dispersive WSSUS Channels

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


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

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


title: Optimal Transmit Covariance for Ergodic MIMO Channels

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


title: Nonmonotonic Trust Management for P2P Applications

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


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

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


title: Markerless Human Motion Capture for Gait Analysis

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


title: Acyclic orientations with path constraints

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


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

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


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

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


title: On the Spread of Random Interleaver

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


title: Ultra Wideband Impulse Radio Systems with Multiple Pulse Types

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


title: Comparing Computational Power

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


title: On Coding for Reliable Communication over Packet Networks

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


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

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


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

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


title: Semantic Embedding of Petri Nets into Event-B

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


title: Practical Datatype Specializations with Phantom Types and Recursion Schemes

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


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

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


title: Applying Evolutionary Optimisation to Robot Obstacle Avoidance

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


title: Connection state overhead in a dynamic linear network

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


title: Vector Gaussian Multiple Description with Individual and Central Receivers

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


title: Evidence with Uncertain Likelihoods

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


title: When Ignorance is Bliss

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


title: Virtual Environments for multiphysics code validation on Computing Grids

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


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

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


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

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


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

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


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

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


title: Balanced Allocation on Graphs

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


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

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


title: Lower bounds on Locality Sensitive Hashing

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


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

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


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

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


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

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


title: Context Semantics, Linear Logic and Computational Complexity

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


title: ParFORM: recent development

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


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

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


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

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


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

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


title: Bibliographic Classification using the ADS Databases

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


title: Optimal Prefix Codes for Infinite Alphabets with Nonlinear Costs

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


title: Evolutionary Computing

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


title: The egalitarian effect of search engines

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


title: Logical Relations for Monadic Types

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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


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

abstract: This article is taken out.


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

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


title: Short Quantum Games

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


title: From General Systems to Soft Systems to Soft Computing: Applications for Large and Complex Real World Systems

abstract: This is article is taken out.


title: A Counterexample to Cover's 2P Conjecture on Gaussian Feedback Capacity

abstract: We provide a counterexample to Cover's conjecture that the feedback capacity $C_\textrm{FB}$ of an additive Gaussian noise channel under power constraint $P$ be no greater than the nonfeedback capacity $C$ of the same channel under power constraint $2P$, i.e., $C_\textrm{FB}(P) \le C(2P)$.


title: Pbit and other list sorting algorithms

abstract: Pbit, besides its simplicity, is definitely the fastest list sorting algorithm. It considerably surpasses all already known methods. Among many advantages, it is stable, linear and be made to run in place. I will compare Pbit with algorithm described by Donald E. Knuth in the third volume of ''The Art of Computer Programming'' and other (QuickerSort, MergeSort) list sorting algorithms.


title: Games of fixed rank: A hierarchy of bimatrix games

abstract: We propose a new hierarchical approach to understand the complexity of the open problem of computing a Nash equilibrium in a bimatrix game. Specifically, we investigate a hierarchy of bimatrix games $(A,B)$ which results from restricting the rank of the matrix $A+B$ to be of fixed rank at most $k$. For every fixed $k$, this class strictly generalizes the class of zero-sum games, but is a very special case of general bimatrix games. We show that even for $k=1$ the set of Nash equilibria of these games can consist of an arbitrarily large number of connected components. While the question of exact polynomial time algorithms to find a Nash equilibrium remains open for games of fixed rank, we can provide polynomial time algorithms for finding an $\epsilon$-approximation.


title: Does a Plane Imitate a Bird? Does Computer Vision Have to Follow Biological Paradigms?

abstract: We posit a new paradigm for image information processing. For the last 25 years, this task was usually approached in the frame of Treisman's two-stage paradigm [1]. The latter supposes an unsupervised, bottom-up directed process of preliminary information pieces gathering at the lower processing stages and a supervised, top-down directed process of information pieces binding and grouping at the higher stages. It is acknowledged that these sub-processes interact and intervene between them in a tricky and a complicated manner. Notwithstanding the prevalence of this paradigm in biological and computer vision, we nevertheless propose to replace it with a new one, which we would like to designate as a two-part paradigm. In it, information contained in an image is initially extracted in an independent top-down manner by one part of the system, and then it is examined and interpreted by another, separate system part. We argue that the new paradigm seems to be more plausible than its forerunner. We provide evidence from human attention vision studies and insights of Kolmogorov's complexity theory to support our arguments. We also provide some reasons in favor of separate image interpretation issues.


title: Verifying nondeterministic probabilistic channel systems against $\omega$-regular linear-time properties

abstract: Lossy channel systems (LCSs) are systems of finite state automata that communicate via unreliable unbounded fifo channels. In order to circumvent the undecidability of model checking for nondeterministic LCSs, probabilistic models have been introduced, where it can be decided whether a linear-time property holds almost surely. However, such fully probabilistic systems are not a faithful model of nondeterministic protocols. We study a hybrid model for LCSs where losses of messages are seen as faults occurring with some given probability, and where the internal behavior of the system remains nondeterministic. Thus the semantics is in terms of infinite-state Markov decision processes. The purpose of this article is to discuss the decidability of linear-time properties formalized by formulas of linear temporal logic (LTL). Our focus is on the qualitative setting where one asks, e.g., whether a LTL-formula holds almost surely or with zero probability (in case the formula describes the bad behaviors). Surprisingly, it turns out that -- in contrast to finite-state Markov decision processes -- the satisfaction relation for LTL formulas depends on the chosen type of schedulers that resolve the nondeterminism. While all variants of the qualitative LTL model checking problem for the full class of history-dependent schedulers are undecidable, the same questions for finite-memory scheduler can be solved algorithmically. However, the restriction to reachability properties and special kinds of recurrent reachability properties yields decidable verification problems for the full class of schedulers, which -- for this restricted class of properties -- are as powerful as finite-memory schedulers, or even a subclass of them.


title: Heat kernel expansion for a family of stochastic volatility models : delta-geometry

abstract: In this paper, we study a family of stochastic volatility processes; this family features a mean reversion term for the volatility and a double CEV-like exponent that generalizes SABR and Heston's models. We derive approximated closed form formulas for the digital prices, the local and implied volatilities. Our formulas are efficient for small maturities. Our method is based on differential geometry, especially small time diffusions on riemanian spaces. This geometrical point of view can be extended to other processes, and is very accurate to produce variate smiles for small maturities and small moneyness.


title: Logic Column 14: Nominal Logic and Abstract Syntax

abstract: Formalizing syntactic proofs of properties of logics, programming languages, security protocols, and other formal systems is a significant challenge, in large part because of the obligation to handle name-binding correctly. We present an approach called nominal abstract syntax that has attracted considerable interest since its introduction approximately six years ago. After an overview of other approaches, we describe nominal abstract syntax and nominal logic, a logic for reasoning about nominal abstract syntax. We also discuss applications of nominal techniques to programming, automated reasoning, and identify some future directions.


title: A Decision Theoretic Framework for Real-Time Communication

abstract: We consider a communication system in which the outputs of a Markov source are encoded and decoded in \emph{real-time} by a finite memory receiver, and the distortion measure does not tolerate delays. The objective is to choose designs, i.e. real-time encoding, decoding and memory update strategies that minimize a total expected distortion measure. This is a dynamic team problem with non-classical information structure [Witsenhausen:1971]. We use the structural results of [Teneketzis:2004] to develop a sequential decomposition for the finite and infinite horizon problems. Thus, we obtain a systematic methodology for the determination of jointly optimal encoding decoding and memory update strategies for real-time point-to-point communication systems.


title: Discrete Network Dynamics. Part 1: Operator Theory

abstract: An operator algebra implementation of Markov chain Monte Carlo algorithms for simulating Markov random fields is proposed. It allows the dynamics of networks whose nodes have discrete state spaces to be specified by the action of an update operator that is composed of creation and annihilation operators. This formulation of discrete network dynamics has properties that are similar to those of a quantum field theory of bosons, which allows reuse of many conceptual and theoretical structures from QFT. The equilibrium behaviour of one of these generalised MRFs and of the adaptive cluster expansion network (ACEnet) are shown to be equivalent, which provides a way of unifying these two theories.


title: MIMO Diversity in the Presence of Double Scattering

abstract: The potential benefits of multiple-antenna systems may be limited by two types of channel degradations rank deficiency and spatial fading correlation of the channel. In this paper, we assess the effects of these degradations on the diversity performance of multiple-input multiple-output (MIMO) systems, with an emphasis on orthogonal space-time block codes, in terms of the symbol error probability, the effective fading figure (EFF), and the capacity at low signal-to-noise ratio (SNR). In particular, we consider a general family of MIMO channels known as double-scattering channels, which encompasses a variety of propagation environments from independent and identically distributed Rayleigh to degenerate keyhole or pinhole cases by embracing both rank-deficient and spatial correlation effects. It is shown that a MIMO system with $n_T$ transmit and $n_R$ receive antennas achieves the diversity of order $\frac{\n_T n_S n_R}{\max(n_T,n_S,n_R)}$ in a double-scattering channel with $n_S$ effective scatterers. We also quantify the combined effect of the spatial correlation and the lack of scattering richness on the EFF and the low-SNR capacity in terms of the correlation figures of transmit, receive, and scatterer correlation matrices. We further show the monotonicity properties of these performance measures with respect to the strength of spatial correlation, characterized by the eigenvalue majorization relations of the correlation matrices.


title: Non-coherent Rayleigh fading MIMO channels: Capacity Supremum

abstract: This paper investigates the limits of information transfer over a fast Rayleigh fading MIMO channel, where neither the transmitter nor the receiver has the knowledge of the channel state information (CSI) except the fading statistics. We develop a scalar channel model due to absence of the phase information in non-coherent Rayleigh fading and derive a capacity supremum with the number of receive antennas at any signal to noise ratio (SNR) using Lagrange optimisation. Also, we conceptualise the discrete nature of the optimal input distribution by posing the optimisation on the channel mutual information for $N$ discrete inputs. Furthermore, we derive an expression for the asymptotic capacity when the input power is large, and compare with the existing capacity results when the receiver is equipped with a large number of antennas.


title: The Linear Arrangement Problem Parameterized Above Guaranteed Value

abstract: A linear arrangement (LA) is an assignment of distinct integers to the vertices of a graph. The cost of an LA is the sum of lengths of the edges of the graph, where the length of an edge is defined as the absolute value of the difference of the integers assigned to its ends. For many application one hopes to find an LA with small cost. However, it is a classical NP-complete problem to decide whether a given graph $G$ admits an LA of cost bounded by a given integer. Since every edge of $G$ contributes at least one to the cost of any LA, the problem becomes trivially fixed-parameter tractable (FPT) if parameterized by the upper bound of the cost. Fernau asked whether the problem remains FPT if parameterized by the upper bound of the cost minus the number of edges of the given graph; thus whether the problem is FPT ``parameterized above guaranteed value.'' We answer this question positively by deriving an algorithm which decides in time $O(m+n+5.88^k)$ whether a given graph with $m$ edges and $n$ vertices admits an LA of cost at most $m+k$ (the algorithm computes such an LA if it exists). Our algorithm is based on a procedure which generates a problem kernel of linear size in linear time for a connected graph $G$. We also prove that more general parameterized LA problems stated by Serna and Thilikos are not FPT, unless P=NP.


title: Internet Protocol Black Holes: A E-Security Threat

abstract: The paper is taken out.


title: Spatiotemporal sensistivity and visual attention for efficient rendering of dynamic environments

abstract: We present a method to accelerate global illumination computation in dynamic environments by taking advantage of limitations of the human visual system. A model of visual attention is used to locate regions of interest in a scene and to modulate spatiotemporal sensitivity. The method is applied in the form of a spatiotemporal error tolerance map. Perceptual acceleration combined with good sampling protocols provide a global illumination solution feasible for use in animation. Results indicate an order of magnitude improvement in computational speed. The method is adaptable and can also be used in image-based rendering, geometry level of detail selection, realistic image synthesis, video telephony and video compression.


title: Fast (Multi-)Evaluation of Linearly Recurrent Sequences: Improvements and Applications

abstract: For a linearly recurrent vector sequence P[n+1] = A(n) * P[n], consider the problem of calculating either the n-th term P[n] or L<=n arbitrary terms P[n_1],...,P[n_L], both for the case of constant coefficients A(n)=A and for a matrix A(n) with entries polynomial in n. We improve and extend known algorithms for this problem and present new applications for it. Specifically it turns out that for instance * any family (p_n) of classical orthogonal polynomials admits evaluation at given x within O(n^{1/2} log n) operations INDEPENDENT of the family (p_n) under consideration. * For any L indices n_1,...,n_L <= n, the values p_{n_i}(x) can be calculated simultaneously using O(n^{1/2} log n + L log(n/L)) arithmetic operations; again this running time bound holds uniformly. * Every hypergeometric (or, more generally, holonomic) function admits approximate evaluation up to absolute error e>0 within O((log(1/e)^{1/2} loglog(1/e)) -- as opposed to O(log(1/e)) -- arithmetic steps. * Given m and a polynomial p of degree d over a field of characteristic zero, the coefficient of p^m to term X^n can be computed within O(d^2 M(n^{1/2})) steps where M(n) denotes the cost of multiplying two degree-n polynomials. * The same time bound holds for the joint calculation of any L<=n^{1/2} desired coefficients of p^m to terms X^{n_i}, n_1,...,n_L <= n.


title: Generalized Hermitian Codes over GF(2^r)

abstract: In this paper we studied generalization of Hermitian function field proposed by A.Garcia and H.Stichtenoth. We calculated a Weierstrass semigroup of the point at infinity for the case q=2, r>=3. It turned out that unlike Hermitian case, we have already three generators for the semigroup. We then applied this result to codes, constructed on generalized Hermitian function fields. Further, we applied results of C.Kirfel and R.Pellikaan to estimating a Feng-Rao designed distance for GH-codes, which improved on Goppa designed distance. Next, we studied the question of codes dual to GH-codes. We identified that the duals are also GH-codes and gave an explicit formula. We concluded with some computational results. In particular, a new record-giving [32,16,>=12]-code over GF(8) was presented.


title: Decoding the structure of the WWW: facts versus sampling biases

abstract: The understanding of the immense and intricate topological structure of the World Wide Web (WWW) is a major scientific and technological challenge. This has been tackled recently by characterizing the properties of its representative graphs in which vertices and directed edges are identified with web-pages and hyperlinks, respectively. Data gathered in large scale crawls have been analyzed by several groups resulting in a general picture of the WWW that encompasses many of the complex properties typical of rapidly evolving networks. In this paper, we report a detailed statistical analysis of the topological properties of four different WWW graphs obtained with different crawlers. We find that, despite the very large size of the samples, the statistical measures characterizing these graphs differ quantitatively, and in some cases qualitatively, depending on the domain analyzed and the crawl used for gathering the data. This spurs the issue of the presence of sampling biases and structural differences of Web crawls that might induce properties not representative of the actual global underlying graph. In order to provide a more accurate characterization of the Web graph and identify observables which are clearly discriminating with respect to the sampling process, we study the behavior of degree-degree correlation functions and the statistics of reciprocal connections. The latter appears to enclose the relevant correlations of the WWW graph and carry most of the topological information of theWeb. The analysis of this quantity is also of major interest in relation to the navigability and searchability of the Web.


title: A Capacity Achieving and Low Complexity Multilevel Coding Scheme for ISI Channels

abstract: We propose a computationally efficient multilevel coding scheme to achieve the capacity of an ISI channel using layers of binary inputs. The transmitter employs multilevel coding with linear mapping. The receiver uses multistage decoding where each stage performs a separate linear minimum mean square error (LMMSE) equalization and decoding. The optimality of the scheme is due to the fact that the LMMSE equalizer is information lossless in an ISI channel when signal to noise ratio is sufficiently low. The computational complexity is low and scales linearly with the length of the channel impulse response and the number of layers. The decoder at each layer sees an equivalent AWGN channel, which makes coding straightforward.


title: Trellis Pruning for Peak-to-Average Power Ratio Reduction

abstract: This paper introduces a new trellis pruning method which uses nonlinear convolutional coding for peak-to-average power ratio (PAPR) reduction of filtered QPSK and 16-QAM modulations. The Nyquist filter is viewed as a convolutional encoder that controls the analog waveforms of the filter output directly. Pruning some edges of the encoder trellis can effectively reduce the PAPR. The only tradeoff is a slightly lower channel capacity and increased complexity. The paper presents simulation results of the pruning action and the resulting PAPR, and also discusses the decoding algorithm and the capacity of the filtered and pruned QPSK and 16-QAM modulations on the AWGN channel. Simulation results show that the pruning method reduces the PAPR significantly without much damage to capacity.


title: Towards a unified theory of logic programming semantics: Level mapping characterizations of selector generated models

abstract: Currently, the variety of expressive extensions and different semantics created for logic programs with negation is diverse and heterogeneous, and there is a lack of comprehensive comparative studies which map out the multitude of perspectives in a uniform way. Most recently, however, new methodologies have been proposed which allow one to derive uniform characterizations of different declarative semantics for logic programs with negation. In this paper, we study the relationship between two of these approaches, namely the level mapping characterizations due to [Hitzler and Wendt 2005], and the selector generated models due to [Schwarz 2004]. We will show that the latter can be captured by means of the former, thereby supporting the claim that level mappings provide a very flexible framework which is applicable to very diversely defined semantics.


title: The Generalized Area Theorem and Some of its Consequences

abstract: There is a fundamental relationship between belief propagation and maximum a posteriori decoding. The case of transmission over the binary erasure channel was investigated in detail in a companion paper. This paper investigates the extension to general memoryless channels (paying special attention to the binary case). An area theorem for transmission over general memoryless channels is introduced and some of its many consequences are discussed. We show that this area theorem gives rise to an upper-bound on the maximum a posteriori threshold for sparse graph codes. In situations where this bound is tight, the extrinsic soft bit estimates delivered by the belief propagation decoder coincide with the correct a posteriori probabilities above the maximum a posteriori threshold. More generally, it is conjectured that the fundamental relationship between the maximum a posteriori and the belief propagation decoder which was observed for transmission over the binary erasure channel carries over to the general case. We finally demonstrate that in order for the design rate of an ensemble to approach the capacity under belief propagation decoding the component codes have to be perfectly matched, a statement which is well known for the special case of transmission over the binary erasure channel.


title: Design and Analysis of Nonbinary LDPC Codes for Arbitrary Discrete-Memoryless Channels

abstract: We present an analysis, under iterative decoding, of coset LDPC codes over GF(q), designed for use over arbitrary discrete-memoryless channels (particularly nonbinary and asymmetric channels). We use a random-coset analysis to produce an effect that is similar to output-symmetry with binary channels. We show that the random selection of the nonzero elements of the GF(q) parity-check matrix induces a permutation-invariance property on the densities of the decoder messages, which simplifies their analysis and approximation. We generalize several properties, including symmetry and stability from the analysis of binary LDPC codes. We show that under a Gaussian approximation, the entire q-1 dimensional distribution of the vector messages is described by a single scalar parameter (like the distributions of binary LDPC messages). We apply this property to develop EXIT charts for our codes. We use appropriately designed signal constellations to obtain substantial shaping gains. Simulation results indicate that our codes outperform multilevel codes at short block lengths. We also present simulation results for the AWGN channel, including results within 0.56 dB of the unconstrained Shannon limit (i.e. not restricted to any signal constellation) at a spectral efficiency of 6 bits/s/Hz.


title: Logic Programming with Default, Weak and Strict Negations

abstract: This paper treats logic programming with three kinds of negation: default, weak and strict negations. A 3-valued logic model theory is discussed for logic programs with three kinds of negation. The procedure is constructed for negations so that a soundness of the procedure is guaranteed in terms of 3-valued logic model theory.


title: Dimensions of Neural-symbolic Integration - A Structured Survey

abstract: Research on integrated neural-symbolic systems has made significant progress in the recent past. In particular the understanding of ways to deal with symbolic knowledge within connectionist systems (also called artificial neural networks) has reached a critical mass which enables the community to strive for applicable implementations and use cases. Recent work has covered a great variety of logics used in artificial intelligence and provides a multitude of techniques for dealing with them within the context of artificial neural networks. We present a comprehensive survey of the field of neural-symbolic integration, including a new classification of system according to their architectures and abilities.


title: Poseidon: a 2-tier Anomaly-based Intrusion Detection System

abstract: We present Poseidon, a new anomaly based intrusion detection system. Poseidon is payload-based, and presents a two-tier architecture: the first stage consists of a Self-Organizing Map, while the second one is a modified PAYL system. Our benchmarks on the 1999 DARPA data set show a higher detection rate and lower number of false positives than PAYL and PHAD.


title: Various Solutions to the Firing Squad Synchronization Problems

abstract: We present different classes of solutions to the Firing Squad Synchronization Problem on networks of different shapes. The nodes are finite state processors that work at unison discrete steps. The networks considered are the line, the ring and the square. For all of these models we have considered one and two-way communication modes and also constrained the quantity of information that adjacent processors can exchange each step. We are given a particular time expressed as a function of the number of nodes of the network, $f(n)$ and present synchronization algorithms in time $n^2$, $n \log n$, $n\sqrt n$, $2^n$. The solutions are presented as {\em signals} that are used as building blocks to compose new solutions for all times expressed by polynomials with nonnegative coefficients.


title: An Invariant Cost Model for the Lambda Calculus

abstract: We define a new cost model for the call-by-value lambda-calculus satisfying the invariance thesis. That is, under the proposed cost model, Turing machines and the call-by-value lambda-calculus can simulate each other within a polynomial time overhead. The model only relies on combinatorial properties of usual beta-reduction, without any reference to a specific machine or evaluator. In particular, the cost of a single beta reduction is proportional to the difference between the size of the redex and the size of the reduct. In this way, the total cost of normalizing a lambda term will take into account the size of all intermediate results (as well as the number of steps to normal form).


title: Generalized Kasami Sequences: The Large Set

abstract: In this paper new binary sequence families $\mathcal{F}^k$ of period $2^n-1$ are constructed for even $n$ and any $k$ with ${\rm gcd}(k,n)=2$ if $n/2$ is odd or ${\rm gcd}(k,n)=1$ if $n/2$ is even. The distribution of their correlation values is completely determined. These families have maximum correlation $2^{n/2+1}+1$ and family size $2^{3n/2}+2^{n/2}$ for odd $n/2$ or $2^{3n/2}+2^{n/2}-1$ for even $n/2$. The construction of the large set of Kasami sequences which is exactly the $\mathcal{F}^{k}$ with $k=n/2+1$ is generalized.


title: The Secret Key-Private Key Capacity Region for Three Terminals

abstract: We consider a model for secrecy generation, with three terminals, by means of public interterminal communication, and examine the problem of characterizing all the rates at which all three terminals can generate a ``secret key,'' and -- simultaneously -- two designated terminals can generate a ``private key'' which is effectively concealed from the remaining terminal; both keys are also concealed from an eavesdropper that observes the public communication. Inner and outer bounds for the ``secret key--private key capacity region'' are derived. Under a certain special condition, these bounds coincide to yield the (exact) secret key--private key capacity region.


title: Joint Network-Source Coding: An Achievable Region with Diversity Routing

abstract: We are interested in how to best communicate a (usually real valued) source to a number of destinations (sinks) over a network with capacity constraints in a collective fidelity metric over all the sinks, a problem which we call joint network-source coding. Unlike the lossless network coding problem, lossy reconstruction of the source at the sinks is permitted. We make a first attempt to characterize the set of all distortions achievable by a set of sinks in a given network. While the entire region of all achievable distortions remains largely an open problem, we find a large, non-trivial subset of it using ideas in multiple description coding. The achievable region is derived over all balanced multiple-description codes and over all network flows, while the network nodes are allowed to forward and duplicate data packets.


title: Entropy, Convex Optimization, and Competitive Quantum Interactions

abstract: This paper has been withdrawn by the author due to errors.


title: Secret Key and Private Key Constructions for Simple Multiterminal Source Models

abstract: This work is motivated by recent results of Csiszar and Narayan (IEEE Trans. on Inform. Theory, Dec. 2004), which highlight innate connections between secrecy generation by multiple terminals and multiterminal Slepian-Wolf near-lossless data compression (sans secrecy restrictions). We propose a new approach for constructing secret and private keys based on the long-known Slepian-Wolf code for sources connected by a virtual additive noise channel, due to Wyner (IEEE Trans. on Inform. Theory, Jan. 1974). Explicit procedures for such constructions, and their substantiation, are provided.


title: The Private Key Capacity Region for Three Terminals

abstract: We consider a model with three terminals and examine the problem of characterizing the largest rates at which two pairs of terminals can simultaneously generate private keys, each of which is effectively concealed from the remaining terminal.


title: Mining Cellular Automata DataBases throug PCA Models

abstract: Cellular Automata are discrete dynamical systems that evolve following simple and local rules. Despite of its local simplicity, knowledge discovery in CA is a NP problem. This is the main motivation for using data mining techniques for CA study. The Principal Component Analysis (PCA) is a useful tool for data mining because it provides a compact and optimal description of data sets. Such feature have been explored to compute the best subspace which maximizes the projection of the I/O patterns of CA onto the principal axis. The stability of the principal components against the input patterns is the main result of this approach. In this paper we perform such analysis but in the presence of noise which randomly reverses the CA output values with probability $p$. As expected, the number of principal components increases when the pattern size is increased. However, it seems to remain stable when the pattern size is unchanged but the noise intensity gets larger. We describe our experiments and point out further works using KL transform theory and parameter sensitivity analysis.


title: A Model Based Approach to Reachability Routing

abstract: Current directions in network routing research have not kept pace with the latest developments in network architectures, such as peer-to-peer networks, sensor networks, ad-hoc wireless networks, and overlay networks. A common characteristic among all of these new technologies is the presence of highly dynamic network topologies. Currently deployed single-path routing protocols cannot adequately cope with this dynamism, and existing multi-path algorithms make trade-offs which lead to less than optimal performance on these networks. This drives the need for routing protocols designed with the unique characteristics of these networks in mind. In this paper we propose the notion of reachability routing as a solution to the challenges posed by routing on such dynamic networks. In particular, our formulation of reachability routing provides cost-sensitive multi-path forwarding along with loop avoidance within the confines of the Internet Protocol (IP) architecture. This is achieved through the application of reinforcement learning within a probabilistic routing framework. Following an explanation of our design decisions and a description of the algorithm, we provide an evaluation of the performance of the algorithm on a variety of network topologies. The results show consistently superior performance compared to other reinforcement learning based routing algorithms.


title: Eigenvalue Distributions of Sums and Products of Large Random Matrices via Incremental Matrix Expansions

abstract: This paper uses an incremental matrix expansion approach to derive asymptotic eigenvalue distributions (a.e.d.'s) of sums and products of large random matrices. We show that the result can be derived directly as a consequence of two common assumptions, and matches the results obtained from using R- and S-transforms in free probability theory. We also give a direct derivation of the a.e.d. of the sum of certain random matrices which are not free. This is used to determine the asymptotic signal-to-interference-ratio of a multiuser CDMA system with a minimum mean-square error linear receiver.


title: Embedding Defeasible Logic into Logic Programming

abstract: Defeasible reasoning is a simple but efficient approach to nonmonotonic reasoning that has recently attracted considerable interest and that has found various applications. Defeasible logic and its variants are an important family of defeasible reasoning methods. So far no relationship has been established between defeasible logic and mainstream nonmonotonic reasoning approaches. In this paper we establish close links to known semantics of logic programs. In particular, we give a translation of a defeasible theory D into a meta-program P(D). We show that under a condition of decisiveness, the defeasible consequences of D correspond exactly to the sceptical conclusions of P(D) under the stable model semantics. Without decisiveness, the result holds only in one direction (all defeasible consequences of D are included in all stable models of P(D)). If we wish a complete embedding for the general case, we need to use the Kunen semantics of P(D), instead.


title: Improved Upper Bounds on Stopping Redundancy

abstract: Let C be a linear code with length n and minimum distance d. The stopping redundancy of C is defined as the minimum number of rows in a parity-check matrix for C such that the smallest stopping sets in the corresponding Tanner graph have size d. We derive new upper bounds on the stopping redundancy of linear codes in general, and of maximum distance separable (MDS) codes specifically, and show how they improve upon previously known results. For MDS codes, the new bounds are found by upper bounding the stopping redundancy by a combinatorial quantity closely related to Turan numbers. (The Turan number, T(v,k,t), is the smallest number of t-subsets of a v-set, such that every k-subset of the v-set contains at least one of the t-subsets.) We further show that the stopping redundancy of MDS codes is T(n,d-1,d-2)(1+O(n^{-1})) for fixed d, and is at most T(n,d-1,d-2)(3+O(n^{-1})) for fixed code dimension k=n-d+1. For d=3,4, we prove that the stopping redundancy of MDS codes is equal to T(n,d-1,d-2), for which exact formulas are known. For d=5, we show that the stopping redundancy of MDS codes is either T(n,4,3) or T(n,4,3)+1.


title: Quantized Indexing: Beyond Arithmetic Coding

abstract: Quantized Indexing is a fast and space-efficient form of enumerative (combinatorial) coding, the strongest among asymptotically optimal universal entropy coding algorithms. The present advance in enumerative coding is similar to that made by arithmetic coding with respect to its unlimited precision predecessor, Elias coding. The arithmetic precision, execution time, table sizes and coding delay are all reduced by a factor O(n) at a redundancy below 2*log(e)/2^g bits/symbol (for n input symbols and g-bit QI precision). Due to its tighter enumeration, QI output redundancy is below that of arithmetic coding (which can be derived as a lower accuracy approximation of QI). The relative compression gain vanishes in large n and in high entropy limits and increases for shorter outputs and for less predictable data. QI is significantly faster than the fastest arithmetic coders, from factor 6 in high entropy limit to over 100 in low entropy limit (`typically' 10-20 times faster). These speedups are result of using only 3 adds, 1 shift and 2 array lookups (all in 32 bit precision) per less probable symbol and no coding operations for the most probable symbol . Further, the exact enumeration algorithm is sharpened and its lattice walks formulation is generalized. A new numeric type with a broader applicability, sliding window integer, is introduced.


title: On-line regression competitive with reproducing kernel Hilbert spaces

abstract: We consider the problem of on-line prediction of real-valued labels, assumed bounded in absolute value by a known constant, of new objects from known labeled objects. The prediction algorithm's performance is measured by the squared deviation of the predictions from the actual labels. No stochastic assumptions are made about the way the labels and objects are generated. Instead, we are given a benchmark class of prediction rules some of which are hoped to produce good predictions. We show that for a wide range of infinite-dimensional benchmark classes one can construct a prediction algorithm whose cumulative loss over the first N examples does not exceed the cumulative loss of any prediction rule in the class plus O(sqrt(N)); the main differences from the known results are that we do not impose any upper bound on the norm of the considered prediction rules and that we achieve an optimal leading term in the excess loss of our algorithm. If the benchmark class is "universal" (dense in the class of continuous functions on each compact set), this provides an on-line non-stochastic analogue of universally consistent prediction in non-parametric statistics. We use two proof techniques: one is based on the Aggregating Algorithm and the other on the recently developed method of defensive forecasting.


title: Virtual Coordinate Backtracking for Void Traversal in Geographic Routing

abstract: Geographical routing protocols have several desirable features for use in ad hoc and sensor networks but are susceptible to voids and localization errors. Virtual coordinate systems are an alternative solution to geographically based routing protocols that works by overlaying a coordinate system on the sensors relative to well chosen reference points. VC is resilient to localization errors; however, we show that it is vulnerable to different forms of the void problem and have no viable complementary approach to overcome them. Specifically, we show that there are instances when packets reach nodes with no viable next hop nodes in the forwarding set. In addition, it is possible for nodes with the same coordinates to arise at different points in the network in the presence of voids. This paper identifies and analyzes these problems. It also compares several existing routing protocols based on Virtual Coordinate systems. Finally, it presents a new routing algorithm that uses backtracking to overcome voids to achieve high connectivity in the greedy phase, higher overall path quality and more resilience to localization errors. We show these properties using extensive simulation analysis.


title: On Quadratic Inverses for Quadratic Permutation Polynomials over Integer Rings

abstract: An interleaver is a critical component for the channel coding performance of turbo codes. Algebraic constructions are of particular interest because they admit analytical designs and simple, practical hardware implementation. Sun and Takeshita have recently shown that the class of quadratic permutation polynomials over integer rings provides excellent performance for turbo codes. In this correspondence, a necessary and sufficient condition is proven for the existence of a quadratic inverse polynomial for a quadratic permutation polynomial over an integer ring. Further, a simple construction is given for the quadratic inverse. All but one of the quadratic interleavers proposed earlier by Sun and Takeshita are found to admit a quadratic inverse, although none were explicitly designed to do so. An explanation is argued for the observation that restriction to a quadratic inverse polynomial does not narrow the pool of good quadratic interleavers for turbo codes.


title: Truly On-The-Fly LTL Model Checking

abstract: We propose a novel algorithm for automata-based LTL model checking that interleaves the construction of the generalized B\"{u}chi automaton for the negation of the formula and the emptiness check. Our algorithm first converts the LTL formula into a linear weak alternating automaton; configurations of the alternating automaton correspond to the locations of a generalized B\"{u}chi automaton, and a variant of Tarjan's algorithm is used to decide the existence of an accepting run of the product of the transition system and the automaton. Because we avoid an explicit construction of the B\"{u}chi automaton, our approach can yield significant improvements in runtime and memory, for large LTL formulas. The algorithm has been implemented within the SPIN model checker, and we present experimental results for some benchmark examples.


title: Analytic performance comparison of routing protocols in master-slave PLC networks

abstract: In the wide area master-slave PLC (powerline communication) system, the source node cannot reach the destination node without packet relay. Due to the time-variable attenuation in the powerline, the communication distance cannot be defined. Two kind of dynamic repeater algorithms are developed, dynamic source routing and flooding based routing. In this paper, we use analytic approach to compare the performance of those two routing protocols. We give formulas to calculate the average duration of a polling cycle for each protocols. Then we present simulation results to bolster the results of our analysis. We use three metrics, which are bandwidth consumed for routing signaling, normalized routing load and average duration of a polling cycle to evaluate those routing protocols.