title: Self-stabilization of Circular Arrays of Automata

abstract: [Gacs, Kurdiumov, Levin, 78] proposed simple one-dimensional cellular automata with 2 states. In an infinite array they are self-stabilizing: if all but a finite minority of automata are in the same state, the minority states disappear. Implicit in the paper was a stronger result that a sufficiently small minority of states vanish even in a finite circular array. The following note makes this strengthening explicit.


title: A topology visualisation tool for large-scale communications networks

abstract: A visualisation tool is presented to facilitate the study on large-scale communications networks. This tool provides a simple and effective way to summarise the topology of a complex network at a coarse level.


title: n-Channel Entropy-Constrained Multiple-Description Lattice Vector Quantization

abstract: In this paper we derive analytical expressions for the central and side quantizers which, under high-resolutions assumptions, minimize the expected distortion of a symmetric multiple-description lattice vector quantization (MD-LVQ) system subject to entropy constraints on the side descriptions for given packet-loss probabilities. We consider a special case of the general n-channel symmetric multiple-description problem where only a single parameter controls the redundancy tradeoffs between the central and the side distortions. Previous work on two-channel MD-LVQ showed that the distortions of the side quantizers can be expressed through the normalized second moment of a sphere. We show here that this is also the case for three-channel MD-LVQ. Furthermore, we conjecture that this is true for the general n-channel MD-LVQ. For given source, target rate and packet-loss probabilities we find the optimal number of descriptions and construct the MD-LVQ system that minimizes the expected distortion. We verify theoretical expressions by numerical simulations and show in a practical setup that significant performance improvements can be achieved over state-of-the-art two-channel MD-LVQ by using three-channel MD-LVQ.


title: R\'{e}seaux d'Automates de Caianiello Revisit\'{e}

abstract: We exhibit a family of neural networks of McCulloch and Pitts of size $2nk+2$ which can be simulated by a neural networks of Caianiello of size $2n+2$ and memory length $k$. This simulation allows us to find again one of the result of the following article: [Cycles exponentiels des r\'{e}seaux de Caianiello et compteurs en arithm\'{e}tique redondante, Technique et Science Informatiques Vol. 19, pages 985-1008] on the existence of neural networks of Caianiello of size $2n+2$ and memory length $k$ which describes a cycle of length $k \times 2^{nk}$.


title: Cryptanalysis of the CFVZ cryptosystem

abstract: The paper analyzes a new public key cryptosystem whose security is based on a matrix version of the discrete logarithm problem over an elliptic curve. It is shown that the complexity of solving the underlying problem for the proposed system is dominated by the complexity of solving a fixed number of discrete logarithm problems in the group of an elliptic curve. Using an adapted Pollard rho algorithm it is shown that this problem is essentially as hard as solving one discrete logarithm problem in the group of an elliptic curve.


title: Minimum Cost Homomorphisms to Proper Interval Graphs and Bigraphs

abstract: For graphs $G$ and $H$, a mapping $f: V(G)\dom V(H)$ is a homomorphism of $G$ to $H$ if $uv\in E(G)$ implies $f(u)f(v)\in E(H).$ If, moreover, each vertex $u \in V(G)$ is associated with costs $c_i(u), i \in V(H)$, then the cost of the homomorphism $f$ is $\sum_{u\in V(G)}c_{f(u)}(u)$. For each fixed graph $H$, we have the {\em minimum cost homomorphism problem}, written as MinHOM($H)$. The problem is to decide, for an input graph $G$ with costs $c_i(u),$ $u \in V(G), i\in V(H)$, whether there exists a homomorphism of $G$ to $H$ and, if one exists, to find one of minimum cost. Minimum cost homomorphism problems encompass (or are related to) many well studied optimization problems. We describe a dichotomy of the minimum cost homomorphism problems for graphs $H$, with loops allowed. When each connected component of $H$ is either a reflexive proper interval graph or an irreflexive proper interval bigraph, the problem MinHOM($H)$ is polynomial time solvable. In all other cases the problem MinHOM($H)$ is NP-hard. This solves an open problem from an earlier paper. Along the way, we prove a new characterization of the class of proper interval bigraphs.


title: Path Summaries and Path Partitioning in Modern XML Databases

abstract: We study the applicability of XML path summaries in the context of current-day XML databases. We find that summaries provide an excellent basis for optimizing data access methods, which furthermore mixes very well with path-partitioned stores. We provide practical algorithms for building and exploiting summaries, and prove its benefits through extensive experiments.


title: PLTL Partitioned Model Checking for Reactive Systems under Fairness Assumptions

abstract: We are interested in verifying dynamic properties of finite state reactive systems under fairness assumptions by model checking. The systems we want to verify are specified through a top-down refinement process. In order to deal with the state explosion problem, we have proposed in previous works to partition the reachability graph, and to perform the verification on each part separately. Moreover, we have defined a class, called Bmod, of dynamic properties that are verifiable by parts, whatever the partition. We decide if a property P belongs to Bmod by looking at the form of the Buchi automaton that accepts the negation of P. However, when a property P belongs to Bmod, the property f => P, where f is a fairness assumption, does not necessarily belong to Bmod. In this paper, we propose to use the refinement process in order to build the parts on which the verification has to be performed. We then show that with such a partition, if a property P is verifiable by parts and if f is the expression of the fairness assumptions on a system, then the property f => P is still verifiable by parts. This approach is illustrated by its application to the chip card protocol T=1 using the B engineering design language.


title: Why neighbor-joining works

abstract: We show that the neighbor-joining algorithm is a robust quartet method for constructing trees from distances. This leads to a new performance guarantee that contains Atteson's optimal radius bound as a special case and explains many cases where neighbor-joining is successful even when Atteson's criterion is not satisfied. We also provide a proof for Atteson's conjecture on the optimal edge radius of the neighbor-joining algorithm. The strong performance guarantees we provide also hold for the quadratic time fast neighbor-joining algorithm, thus providing a theoretical basis for inferring very large phylogenies with neighbor-joining.


title: New security and control protocol for VoIP based on steganography and digital watermarking

abstract: In this paper new security and control protocol for Voice over Internet Protocol (VoIP) service is presented. It is the alternative for the IETF's (Internet Engineering Task Force) RTCP (Real-Time Control Protocol) for real-time application's traffic. Additionally this solution offers authentication and integrity, it is capable of exchanging and verifying QoS and security parameters. It is based on digital watermarking and steganography that is why it does not consume additional bandwidth and the data transmitted is inseparably bound to the voice content.


title: Computing Nash Equilibria: Approximation and Smoothed Complexity

abstract: We show that the BIMATRIX game does not have a fully polynomial-time approximation scheme, unless PPAD is in P. In other words, no algorithm with time polynomial in n and 1/\epsilon can compute an \epsilon-approximate Nash equilibrium of an n by nbimatrix game, unless PPAD is in P. Instrumental to our proof, we introduce a new discrete fixed-point problem on a high-dimensional cube with a constant side-length, such as on an n-dimensional cube with side-length 7, and show that they are PPAD-complete. Furthermore, we prove, unless PPAD is in RP, that the smoothed complexity of the Lemke-Howson algorithm or any algorithm for computing a Nash equilibrium of a bimatrix game is polynomial in n and 1/\sigma under perturbations with magnitude \sigma. Our result answers a major open question in the smoothed analysis of algorithms and the approximation of Nash equilibria.


title: Multilevel Thresholding for Image Segmentation through a Fast Statistical Recursive Algorithm

abstract: A novel algorithm is proposed for segmenting an image into multiple levels using its mean and variance. Starting from the extreme pixel values at both ends of the histogram plot, the algorithm is applied recursively on sub-ranges computed from the previous step, so as to find a threshold level and a new sub-range for the next step, until no significant improvement in image quality can be achieved. The method makes use of the fact that a number of distributions tend towards Dirac delta function, peaking at the mean, in the limiting condition of vanishing variance. The procedure naturally provides for variable size segmentation with bigger blocks near the extreme pixel values and finer divisions around the mean or other chosen value for better visualization. Experiments on a variety of images show that the new algorithm effectively segments the image in computationally very less time.


title: Emergence Explained

abstract: Emergence (macro-level effects from micro-level causes) is at the heart of the conflict between reductionism and functionalism. How can there be autonomous higher level laws of nature (the functionalist claim) if everything can be reduced to the fundamental forces of physics (the reductionist position)? We cut through this debate by applying a computer science lens to the way we view nature. We conclude (a) that what functionalism calls the special sciences (sciences other than physics) do indeed study autonomous laws and furthermore that those laws pertain to real higher level entities but (b) that interactions among such higher-level entities is epiphenomenal in that they can always be reduced to primitive physical forces. In other words, epiphenomena, which we will identify with emergent phenomena, do real higher-level work. The proposed perspective provides a framework for understanding many thorny issues including the nature of entities, stigmergy, the evolution of complexity, phase transitions, supervenience, and downward entailment. We also discuss some practical considerations pertaining to systems of systems and the limitations of modeling.


title: Analysis of LDGM and compound codes for lossy compression and binning

abstract: Recent work has suggested that low-density generator matrix (LDGM) codes are likely to be effective for lossy source coding problems. We derive rigorous upper bounds on the effective rate-distortion function of LDGM codes for the binary symmetric source, showing that they quickly approach the rate-distortion function as the degree increases. We also compare and contrast the standard LDGM construction with a compound LDPC/LDGM construction introduced in our previous work, which provably saturates the rate-distortion bound with finite degrees. Moreover, this compound construction can be used to generate nested codes that are simultaneously good as source and channel codes, and are hence well-suited to source/channel coding with side information. The sparse and high-girth graphical structure of our constructions render them well-suited to message-passing encoding.


title: Approximability of Integer Programming with Generalised Constraints

abstract: We study a family of problems, called \prob{Maximum Solution}, where the objective is to maximise a linear goal function over the feasible integer assignments to a set of variables subject to a set of constraints. When the domain is Boolean (i.e. restricted to $\{0,1\}$), the maximum solution problem is identical to the well-studied \prob{Max Ones} problem, and the approximability is completely understood for all restrictions on the underlying constraints [Khanna et al., SIAM J. Comput., 30 (2001), pp. 1863-1920]. We continue this line of research by considering domains containing more than two elements. We present two main results: a complete classification for the approximability of all maximal constraint languages over domains of cardinality at most 4, and a complete classification of the approximability of the problem when the set of allowed constraints contains all permutation constraints. Under the assumption that a conjecture due to Szczepara holds, we give a complete classification for all maximal constraint languages. These classes of languages are well-studied in universal algebra and computer science; they have, for instance, been considered in connection with machine learning and constraint satisfaction. Our results are proved by using algebraic results from clone theory and the results indicates that this approach is very powerful for classifying the approximability of certain optimisation problems.


title: On the Optimality of the ARQ-DDF Protocol

abstract: The performance of the automatic repeat request-dynamic decode and forward (ARQ-DDF) cooperation protocol is analyzed in two distinct scenarios. The first scenario is the multiple access relay (MAR) channel where a single relay is dedicated to simultaneously help several multiple access users. For this setup, it is shown that the ARQ-DDF protocol achieves the optimal diversity multiplexing tradeoff (DMT) of the channel. The second scenario is the cooperative vector multiple access (CVMA) channel where the users cooperate in delivering their messages to a destination equipped with multiple receiving antennas. For this setup, we develop a new variant of the ARQ-DDF protocol where the users are purposefully instructed not to cooperate in the first round of transmission. Lower and upper bounds on the achievable DMT are then derived. These bounds are shown to converge to the optimal tradeoff as the number of transmission rounds increases.


title: Cooperative Lattice Coding and Decoding

abstract: A novel lattice coding framework is proposed for outage-limited cooperative channels. This framework provides practical implementations for the optimal cooperation protocols proposed by Azarian et al. In particular, for the relay channel we implement a variant of the dynamic decode and forward protocol, which uses orthogonal constellations to reduce the channel seen by the destination to a single-input single-output time-selective one, while inheriting the same diversity-multiplexing tradeoff. This simplification allows for building the receiver using traditional belief propagation or tree search architectures. Our framework also generalizes the coding scheme of Yang and Belfiore in the context of amplify and forward cooperation. For the cooperative multiple access channel, a tree coding approach, matched to the optimal linear cooperation protocol of Azarain et al, is developed. For this scenario, the MMSE-DFE Fano decoder is shown to enjoy an excellent tradeoff between performance and complexity. Finally, the utility of the proposed schemes is established via a comprehensive simulation study.


title: Outage Capacity of the Fading Relay Channel in the Low SNR Regime

abstract: In slow fading scenarios, cooperation between nodes can increase the amount of diversity for communication. We study the performance limit in such scenarios by analyzing the outage capacity of slow fading relay channels. Our focus is on the low SNR and low outage probability regime, where the adverse impact of fading is greatest but so are the potential gains from cooperation. We showed that while the standard Amplify-Forward protocol performs very poorly in this regime, a modified version we called the Bursty Amplify-Forward protocol is optimal and achieves the outage capacity of the network. Moreover, this performance can be achieved without a priori channel knowledge at the receivers. In contrast, the Decode-Forward protocol is strictly sub-optimal in this regime. Our results directly yield the outage capacity per unit energy of fading relay channels.


title: On the utility of the multimodal problem generator for assessing the performance of Evolutionary Algorithms

abstract: This paper looks in detail at how an evolutionary algorithm attempts to solve instances from the multimodal problem generator. The paper shows that in order to consistently reach the global optimum, an evolutionary algorithm requires a population size that should grow at least linearly with the number of peaks. It is also shown a close relationship between the supply and decision making issues that have been identified previously in the context of population sizing models for additively decomposable problems. The most important result of the paper, however, is that solving an instance of the multimodal problem generator is like solving a peak-in-a-haystack, and it is argued that evolutionary algorithms are not the best algorithms for such a task. Finally, and as opposed to what several researchers have been doing, it is our strong belief that the multimodal problem generator is not adequate for assessing the performance of evolutionary algorithms.


title: The OverRelational Manifesto

abstract: The OverRelational Manifesto (below ORM) proposes a possible approach to creation of data storage systems of the next generation. ORM starts from the requirement that information in a relational database is represented by a set of relation values. Accordingly, it is assumed that the information about any entity of an enterprise must also be represented as a set of relation values (the ORM main requirement). A system of types is introduced, which allows one to fulfill the main requirement. The data are represented in the form of complex objects, and the state of any object is described as a set of relation values. Emphasize that the types describing the objects are encapsulated, inherited, and polymorphic. Then, it is shown that the data represented as a set of such objects may also be represented as a set of relational values defined on the set of scalar domains (dual data representation). In the general case, any class is associated with a set of relation variables (R-variables) each one containing some data about all objects of this class existing in the system. One of the key points is the fact that the usage of complex (from the user's viewpoint) refined names of R-variables and their attributes makes it possible to preserve the semantics of complex data structures represented in the form of a set of relation values. The most important part of the data storage system created on the approach proposed is an object-oriented translator operating over a relational DBMS. The expressiveness of such a system is comparable with that of OO programming languages.


title: How to Beat the Adaptive Multi-Armed Bandit

abstract: The multi-armed bandit is a concise model for the problem of iterated decision-making under uncertainty. In each round, a gambler must pull one of $K$ arms of a slot machine, without any foreknowledge of their payouts, except that they are uniformly bounded. A standard objective is to minimize the gambler's regret, defined as the gambler's total payout minus the largest payout which would have been achieved by any fixed arm, in hindsight. Note that the gambler is only told the payout for the arm actually chosen, not for the unchosen arms. Almost all previous work on this problem assumed the payouts to be non-adaptive, in the sense that the distribution of the payout of arm $j$ in round $i$ is completely independent of the choices made by the gambler on rounds $1, \dots, i-1$. In the more general model of adaptive payouts, the payouts in round $i$ may depend arbitrarily on the history of past choices made by the algorithm. We present a new algorithm for this problem, and prove nearly optimal guarantees for the regret against both non-adaptive and adaptive adversaries. After $T$ rounds, our algorithm has regret $O(\sqrt{T})$ with high probability (the tail probability decays exponentially). This dependence on $T$ is best possible, and matches that of the full-information version of the problem, in which the gambler is told the payouts for all $K$ arms after each round. Previously, even for non-adaptive payouts, the best high-probability bounds known were $O(T^{2/3})$, due to Auer, Cesa-Bianchi, Freund and Schapire. The expected regret of their algorithm is $O(T^{1/2}) for non-adaptive payouts, but as we show, $\Omega(T^{2/3})$ for adaptive payouts.


title: Explicit Space-Time Codes Achieving The Diversity-Multiplexing Gain Tradeoff

abstract: A recent result of Zheng and Tse states that over a quasi-static channel, there exists a fundamental tradeoff, referred to as the diversity-multiplexing gain (D-MG) tradeoff, between the spatial multiplexing gain and the diversity gain that can be simultaneously achieved by a space-time (ST) block code. This tradeoff is precisely known in the case of i.i.d. Rayleigh-fading, for T>= n_t+n_r-1 where T is the number of time slots over which coding takes place and n_t,n_r are the number of transmit and receive antennas respectively. For T < n_t+n_r-1, only upper and lower bounds on the D-MG tradeoff are available. In this paper, we present a complete solution to the problem of explicitly constructing D-MG optimal ST codes, i.e., codes that achieve the D-MG tradeoff for any number of receive antennas. We do this by showing that for the square minimum-delay case when T=n_t=n, cyclic-division-algebra (CDA) based ST codes having the non-vanishing determinant property are D-MG optimal. While constructions of such codes were previously known for restricted values of n, we provide here a construction for such codes that is valid for all n. For the rectangular, T > n_t case, we present two general techniques for building D-MG-optimal rectangular ST codes from their square counterparts. A byproduct of our results establishes that the D-MG tradeoff for all T>= n_t is the same as that previously known to hold for T >= n_t + n_r -1.


title: Revisiting Evolutionary Algorithms with On-the-Fly Population Size Adjustment

abstract: In an evolutionary algorithm, the population has a very important role as its size has direct implications regarding solution quality, speed, and reliability. Theoretical studies have been done in the past to investigate the role of population sizing in evolutionary algorithms. In addition to those studies, several self-adjusting population sizing mechanisms have been proposed in the literature. This paper revisits the latter topic and pays special attention to the genetic algorithm with adaptive population size (APGA), for which several researchers have claimed to be very effective at autonomously (re)sizing the population. As opposed to those previous claims, this paper suggests a complete opposite view. Specifically, it shows that APGA is not capable of adapting the population size at all. This claim is supported on theoretical grounds and confirmed by computer simulations.


title: Building Scenarios for Environmental Management and Planning: An IT-Based Approach

abstract: Oftentimes, the need to build multidiscipline knowledge bases, oriented to policy scenarios, entails the involvement of stakeholders in manifold domains, with a juxtaposition of different languages whose semantics can hardly allow inter-domain transfers. A useful support for planning is the building up of durable IT based interactive platforms, where it is possible to modify initial positions toward a semantic convergence. The present paper shows an area-based application of these tools, for the integrated distance-management of different forms of knowledge expressed by selected stakeholders about environmental planning issues, in order to build alternative development scenarios. Keywords: Environmental planning, Scenario building, Multi-source knowledge, IT-based


title: Plane Decompositions as Tools for Approximation

abstract: Tree decompositions were developed by Robertson and Seymour. Since then algorithms have been developed to solve intractable problems efficiently for graphs of bounded treewidth. In this paper we extend tree decompositions to allow cycles to exist in the decomposition graph; we call these new decompositions plane decompositions because we require that the decomposition graph be planar. First, we give some background material about tree decompositions and an overview of algorithms both for decompositions and for approximations of planar graphs. Then, we give our plane decomposition definition and an algorithm that uses this decomposition to approximate the size of the maximum independent set of the underlying graph in polynomial time.


title: Incremental Redundancy Cooperative Coding for Wireless Networks: Cooperative Diversity, Coding, and Transmission Energy Gain

abstract: We study an incremental redundancy (IR) cooperative coding scheme for wireless networks. To exploit the spatial diversity benefit we propose a cluster-based collaborating strategy for a quasi-static Rayleigh fading channel model and based on a network geometric distance profile. Our scheme enhances the network performance by embedding an IR cooperative coding scheme into an existing noncooperative route. More precisely, for each hop, we form a collaborating cluster of M-1 nodes between the (hop) sender and the (hop) destination. The transmitted message is encoded using a mother code and partitioned into M blocks corresponding to the each of M slots. In the first slot, the (hop) sender broadcasts its information by transmitting the first block, and its helpers attempt to relay this message. In the remaining slots, the each of left-over M-1 blocks is sent either through a helper which has successfully decoded the message or directly by the (hop) sender where a dynamic schedule is based on the ACK-based feedback from the cluster. By employing powerful good codes (e.g., turbo codes, LDPC codes, and raptor codes) whose performance is characterized by a threshold behavior, our approach improves the reliability of a multi-hop routing through not only cooperation diversity benefit but also a coding advantage. The study of the diversity and the coding gain of the proposed scheme is based on a new simple threshold bound on the frame-error rate (FER) of maximum likelihood decoding. A average FER upper bound and its asymptotic (in large SNR) version are derived as a function of the average fading channel SNRs and the code threshold.


title: D2D: Digital Archive to MPEG-21 DIDL

abstract: Digital Archive to MPEG-21 DIDL (D2D) analyzes the contents of the digital archive and produces an MPEG-21 Digital Item Declaration Language (DIDL) encapsulating the analysis results. DIDL is an extensible XML-based language that aggregates resources and the metadata. We provide a brief report on several analysis techniques applied on the digital archive by the D2D and provide an evaluation of its run-time performance.


title: eJournal interface can influence usage statistics: implications for libraries, publishers, and Project COUNTER

abstract: The design of a publisher's electronic interface can have a measurable effect on electronic journal usage statistics. A study of journal usage from six COUNTER-compliant publishers at thirty-two research institutions in the United States, the United Kingdom and Sweden indicates that the ratio of PDF to HTML views is not consistent across publisher interfaces, even after controlling for differences in publisher content. The number of fulltext downloads may be artificially inflated when publishers require users to view HTML versions before accessing PDF versions or when linking mechanisms, such as CrossRef, direct users to the full text, rather than the abstract, of each article. These results suggest that usage reports from COUNTER-compliant publishers are not directly comparable in their current form. One solution may be to modify publisher numbers with adjustment factors deemed to be representative of the benefit or disadvantage due to its interface. Standardization of some interface and linking protocols may obviate these differences and allow for more accurate cross-publisher comparisons.


title: The Computational and Storage Potential of Volunteer Computing

abstract: "Volunteer computing" uses Internet-connected computers, volunteered by their owners, as a source of computing power and storage. This paper studies the potential capacity of volunteer computing. We analyzed measurements of over 330,000 hosts participating in a volunteer computing project. These measurements include processing power, memory, disk space, network throughput, host availability, user-specified limits on resource usage, and host churn. We show that volunteer computing can support applications that are significantly more data-intensive, or have larger memory and storage requirements, than those in current projects.


title: Learning rational stochastic languages

abstract: Given a finite set of words w1,...,wn independently drawn according to a fixed unknown distribution law P called a stochastic language, an usual goal in Grammatical Inference is to infer an estimate of P in some class of probabilistic models, such as Probabilistic Automata (PA). Here, we study the class of rational stochastic languages, which consists in stochastic languages that can be generated by Multiplicity Automata (MA) and which strictly includes the class of stochastic languages generated by PA. Rational stochastic languages have minimal normal representation which may be very concise, and whose parameters can be efficiently estimated from stochastic samples. We design an efficient inference algorithm DEES which aims at building a minimal normal representation of the target. Despite the fact that no recursively enumerable class of MA computes exactly the set of rational stochastic languages over Q, we show that DEES strongly identifies tis set in the limit. We study the intermediary MA output by DEES and show that they compute rational series which converge absolutely to one and which can be used to provide stochastic languages which closely estimate the target.


title: Group Signature Schemes Using Braid Groups

abstract: Artin's braid groups have been recently suggested as a new source for public-key cryptography. In this paper we propose the first group signature schemes based on the conjugacy problem, decomposition problem and root problem in the braid groups which are believed to be hard problems.


title: Computing spectral sequences

abstract: In this paper, a set of programs enhancing the Kenzo system is presented. Kenzo is a Common Lisp program designed for computing in Algebraic Topology, in particular it allows the user to calculate homology and homotopy groups of complicated spaces. The new programs presented here entirely compute Serre and Eilenberg-Moore spectral sequences, in particular the groups and differential maps for arbitrary r. They also determine when the spectral sequence has converged and describe the filtration of the target homology groups induced by the spectral sequence.


title: Similarity of Objects and the Meaning of Words

abstract: We survey the emerging area of compression-based, parameter-free, similarity distance measures useful in data-mining, pattern recognition, learning and automatic semantics extraction. Given a family of distances on a set of objects, a distance is universal up to a certain precision for that family if it minorizes every distance in the family between every two objects in the set, up to the stated precision (we do not require the universal distance to be an element of the family). We consider similarity distances for two types of objects: literal objects that as such contain all of their meaning, like genomes or books, and names for objects. The latter may have literal embodyments like the first type, but may also be abstract like ``red'' or ``christianity.'' For the first type we consider a family of computable distance measures corresponding to parameters expressing similarity according to particular featuresdistances generated by web users corresponding to particular semantic relations between the (names for) the designated objects. For both families we give universal similarity distance measures, incorporating all particular distance measures in the family. In the first case the universal distance is based on compression and in the second case it is based on Google page counts related to search terms. In both cases experiments on a massive scale give evidence of the viability of the approaches. between pairs of literal objects. For the second type we consider similarity


title: Natural Economics

abstract: A few considerations on the nature of Economics and its relationship to human communities through the prism of Self-Organizing-Systems.


title: Renyi to Renyi -- Source Coding under Siege

abstract: A novel lossless source coding paradigm applies to problems of unreliable lossless channels with low bit rates, in which a vital message needs to be transmitted prior to termination of communications. This paradigm can be applied to Alfred Renyi's secondhand account of an ancient siege in which a spy was sent to scout the enemy but was captured. After escaping, the spy returned to his base in no condition to speak and unable to write. His commander asked him questions that he could answer by nodding or shaking his head, and the fortress was defended with this information. Renyi told this story with reference to prefix coding, but maximizing probability of survival in the siege scenario is distinct from yet related to the traditional source coding objective of minimizing expected codeword length. Rather than finding a code minimizing expected codeword length $\sum_{i=1}^n p(i) l(i)$, the siege problem involves maximizing $\sum_{i=1}^n p(i) \theta^{l(i)}$ for a known $\theta \in (0,1)$. When there are no restrictions on codewords, this problem can be solve using a known generalization of Huffman coding. The optimal solution has coding bounds which are functions of Renyi entropy; in addition to known bounds, new bounds are derived here. The alphabetically constrained version of this problem has applications in search trees and diagnostic testing. A novel dynamic programming algorithm -- based upon the oldest known algorithm for the traditional alphabetic problem -- optimizes this problem in $O(n^3)$ time and $O(n^2)$ space, whereas two novel approximation algorithms can find a suboptimal solution faster: one in linear time, the other in $O(n \log n)$. Coding bounds for the alphabetic version of this problem are also presented.


title: Parallel Symbolic Computation of Curvature Invariants in General Relativity

abstract: We present a practical application of parallel symbolic computation in General Relativity: the calculation of curvature invariants for large dimension. We discuss the structure of the calculations, an implementation of the technique and scaling of the computation with spacetime dimension for various invariants.


title: Faster Algorithms for Constructing a Concept (Galois) Lattice

abstract: In this paper, we present a fast algorithm for constructing a concept (Galois) lattice of a binary relation, including computing all concepts and their lattice order. We also present two efficient variants of the algorithm, one for computing all concepts only, and one for constructing a frequent closed itemset lattice. The running time of our algorithms depends on the lattice structure and is faster than all other existing algorithms for these problems.


title: Methods for scaling a large member base

abstract: The technical challenges of scaling websites with large and growing member bases, like social networking sites, are numerous. One of these challenges is how to evenly distribute the growing member base across all available resources. This paper will explore various methods that address this issue. The techniques used in this paper can be generalized and applied to various other problems that need to distribute data evenly amongst a finite amount of resources.


title: Geographic Gossip: Efficient Aggregation for Sensor Networks

abstract: Gossip algorithms for aggregation have recently received significant attention for sensor network applications because of their simplicity and robustness in noisy and uncertain environments. However, gossip algorithms can waste significant energy by essentially passing around redundant information multiple times. For realistic sensor network model topologies like grids and random geometric graphs, the inefficiency of gossip schemes is caused by slow mixing times of random walks on those graphs. We propose and analyze an alternative gossiping scheme that exploits geographic information. By utilizing a simple resampling method, we can demonstrate substantial gains over previously proposed gossip protocols. In particular, for random geometric graphs, our algorithm computes the true average to accuracy $1/n^a$ using $O(n^{1.5}\sqrt{\log n})$ radio transmissions, which reduces the energy consumption by a $\sqrt{\frac{n}{\log n}}$ factor over standard gossip algorithms.


title: Turbo Decoding on the Binary Erasure Channel: Finite-Length Analysis and Turbo Stopping Sets

abstract: This paper is devoted to the finite-length analysis of turbo decoding over the binary erasure channel (BEC). The performance of iterative belief-propagation (BP) decoding of low-density parity-check (LDPC) codes over the BEC can be characterized in terms of stopping sets. We describe turbo decoding on the BEC which is simpler than turbo decoding on other channels. We then adapt the concept of stopping sets to turbo decoding and state an exact condition for decoding failure. Apply turbo decoding until the transmitted codeword has been recovered, or the decoder fails to progress further. Then the set of erased positions that will remain when the decoder stops is equal to the unique maximum-size turbo stopping set which is also a subset of the set of erased positions. Furthermore, we present some improvements of the basic turbo decoding algorithm on the BEC. The proposed improved turbo decoding algorithm has substantially better error performance as illustrated by the given simulation results. Finally, we give an expression for the turbo stopping set size enumerating function under the uniform interleaver assumption, and an efficient enumeration algorithm of small-size turbo stopping sets for a particular interleaver. The solution is based on the algorithm proposed by Garello et al. in 2001 to compute an exhaustive list of all low-weight codewords in a turbo code.


title: An O(n^{2.75}) algorithm for online topological ordering

abstract: We present a simple algorithm which maintains the topological order of a directed acyclic graph with n nodes under an online edge insertion sequence in O(n^{2.75}) time, independent of the number of edges m inserted. For dense DAGs, this is an improvement over the previous best result of O(min(m^{3/2} log(n), m^{3/2} + n^2 log(n)) by Katriel and Bodlaender. We also provide an empirical comparison of our algorithm with other algorithms for online topological sorting. Our implementation outperforms them on certain hard instances while it is still competitive on random edge insertion sequences leading to complete DAGs.


title: The entropy rate of the binary symmetric channel in the rare transitions regime

abstract: This note has been withdrawn by the author as the more complete result was recently proved by A.Quas and Y.Peres


title: The approximability of MAX CSP with fixed-value constraints

abstract: In the maximum constraint satisfaction problem (MAX CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given finite domain to the variables so as to maximize the number (or the total weight, for the weighted case) of satisfied constraints. This problem is NP-hard in general, and, therefore, it is natural to study how restricting the allowed types of constraints affects the approximability of the problem. In this paper, we show that any MAX CSP problem with a finite set of allowed constraint types, which includes all fixed-value constraints (i.e., constraints of the form x=a), is either solvable exactly in polynomial-time or else is APX-complete, even if the number of occurrences of variables in instances are bounded. Moreover, we present a simple description of all polynomial-time solvable cases of our problem. This description relies on the well-known algebraic combinatorial property of supermodularity.


title: Exploring term-document matrices from matrix models in text mining

abstract: We explore a matrix-space model, that is a natural extension to the vector space model for Information Retrieval. Each document can be represented by a matrix that is based on document extracts (e.g. sentences, paragraphs, sections). We focus on the performance of this model for the specific case in which documents are originally represented as term-by-sentence matrices. We use the singular value decomposition to approximate the term-by-sentence matrices and assemble these results to form the pseudo-``term-document'' matrix that forms the basis of a text mining method alternative to traditional VSM and LSI. We investigate the singular values of this matrix and provide experimental evidence suggesting that the method can be particularly effective in terms of accuracy for text collections with multi-topic documents, such as web pages with news.


title: Bisimulations of enrichments

abstract: In this paper we show that classical notions from automata theory such as simulation and bisimulation can be lifted to the context of enriched categories. The usual properties of bisimulation are nearly all preserved in this new context. The class of enriched functors that correspond to functionnal bisimulations surjective on objects is investigated and appears "nearly" open in the sense of Joyal and Moerdijk. Seeing the change of base techniques as a convenient means to define process refinement/abstractions, we give sufficient conditions for the change of base categories to preserve bisimularity. We apply these concepts to Betti's generalized automata, categorical transition systems, and other exotic categories.


title: Associative Memory For Reversible Programming and Charge Recovery

abstract: Presented below is an interesting type of associative memory called toggle memory based on the concept of T flip flops, as opposed to D flip flops. Toggle memory supports both reversible programming and charge recovery. Circuits designed using the principles delineated below permit matchlines to charge and discharge with near zero energy dissipation. The resulting lethargy is compensated by the massive parallelism of associative memory. Simulation indicates over 33x reduction in energy dissipation using a sinusoidal power supply at 2 MHz, assuming realistic 50 nm MOSFET models.


title: SISO APP Searches in Lattices with Tanner Graphs

abstract: An efficient, low-complexity, soft-output detector for general lattices is presented, based on their Tanner graph (TG) representations. Closest-point searches in lattices can be performed as non-binary belief propagation on associated TGs; soft-information output is naturally generated in the process; the algorithm requires no backtrack (cf. classic sphere decoding), and extracts extrinsic information. A lattice's coding gain enables equivalence relations between lattice points, which can be thereby partitioned in cosets. Total and extrinsic a posteriori probabilities at the detector's output further enable the use of soft detection information in iterative schemes. The algorithm is illustrated via two scenarios that transmit a 32-point, uncoded super-orthogonal (SO) constellation for multiple-input multiple-output (MIMO) channels, carved from an 8-dimensional non-orthogonal lattice (a direct sum of two 4-dimensional checkerboard lattice): it achieves maximum likelihood performance in quasistatic fading; and, performs close to interference-free transmission, and identically to list sphere decoding, in independent fading with coordinate interleaving and iterative equalization and detection. Latter scenario outperforms former despite the absence of forward error correction coding---because the inherent lattice coding gain allows for the refining of extrinsic information. The lattice constellation is the same as the one employed in the SO space-time trellis codes first introduced for 2-by-2 MIMO by Ionescu et al., then independently by Jafarkhani and Seshadri. Complexity is log-linear in lattice dimensionality, vs. cubic in sphere decoders.


title: Pants Decomposition of the Punctured Plane

abstract: A pants decomposition of an orientable surface S is a collection of simple cycles that partition S into pants, i.e., surfaces of genus zero with three boundary cycles. Given a set P of n points in the plane, we consider the problem of computing a pants decomposition of the surface S which is the plane minus P, of minimum total length. We give a polynomial-time approximation scheme using Mitchell's guillotine rectilinear subdivisions. We give a quartic-time algorithm to compute the shortest pants decomposition of S when the cycles are restricted to be axis-aligned boxes, and a quadratic-time algorithm when all the points lie on a line; both exact algorithms use dynamic programming with Yao's speedup.


title: Low-Density Parity-Check Code with Fast Decoding Speed

abstract: Low-Density Parity-Check (LDPC) codes received much attention recently due to their capacity-approaching performance. The iterative message-passing algorithm is a widely adopted decoding algorithm for LDPC codes \cite{Kschischang01}. An important design issue for LDPC codes is designing codes with fast decoding speed while maintaining capacity-approaching performance. In another words, it is desirable that the code can be successfully decoded in few number of decoding iterations, at the same time, achieves a significant portion of the channel capacity. Despite of its importance, this design issue received little attention so far. In this paper, we address this design issue for the case of binary erasure channel. We prove that density-efficient capacity-approaching LDPC codes satisfy a so called "flatness condition". We show an asymptotic approximation to the number of decoding iterations. Based on these facts, we propose an approximated optimization approach to finding the codes with good decoding speed. We further show that the optimal codes in the sense of decoding speed are "right-concentrated". That is, the degrees of check nodes concentrate around the average right degree.


title: Digital Libraries: From Process Modelling to Grid-based Service Oriented Architecture

abstract: Graphical Business Process Modelling Languages (BPML) like Role Activity Diagrams (RAD) provide ease and flexibility for modelling business behaviour. However, these languages show limited applicability in terms of enactment over distributed systems paradigms like Service Oriented Architecture (SOA) based grid computing. This paper investigates RAD modelling of a Scientific Publishing Process (SPP) for Digital Libraries (DL) and tries to determine the suitability of Pi-Calculus based formal approaches to enact SOA based grid computing. In order to achieve this purpose, the Pi-Calculus based formal transformation from a RAD model of SPP for DL draws attention towards a number of challenging issues including issues that require particular design considerations for appropriate enactment in a SOA based grid system.


title: A third level trigger programmable on FPGA for the gamma/hadron separation in a Cherenkov telescope using pseudo-Zernike moments and the SVM classifier

abstract: We studied the application of the Pseudo-Zernike features as image parameters (instead of the Hillas parameters) for the discrimination between the images produced by atmospheric electromagnetic showers caused by gamma-rays and the ones produced by atmospheric electromagnetic showers caused by hadrons in the MAGIC Experiment. We used a Support Vector Machine as classification algorithm with the computed Pseudo-Zernike features as classification parameters. We implemented on a FPGA board a kernel function of the SVM and the Pseudo-Zernike features to build a third level trigger for the gamma-hadron separation task of the MAGIC Experiment.


title: Universal Codes as a Basis for Time Series Testing

abstract: We suggest a new approach to hypothesis testing for ergodic and stationary processes. In contrast to standard methods, the suggested approach gives a possibility to make tests, based on any lossless data compression method even if the distribution law of the codeword lengths is not known. We apply this approach to the following four problems: goodness-of-fit testing (or identity testing), testing for independence, testing of serial independence and homogeneity testing and suggest nonparametric statistical tests for these problems. It is important to note that practically used so-called archivers can be used for suggested testing.


title: Twenty (or so) Questions: $D$-ary Length-Bounded Prefix Coding

abstract: Efficient optimal prefix coding has long been accomplished via the Huffman algorithm. However, there is still room for improvement and exploration regarding variants of the Huffman problem. Length-limited Huffman coding, useful for many practical applications, is one such variant, for which codes are restricted to the set of codes in which none of the $n$ codewords is longer than a given length, $l_{\max}$. Binary length-limited coding can be done in $O(n l_{\max})$ time and O(n) space via the widely used Package-Merge algorithm and with even smaller asymptotic complexity using a lesser-known algorithm. In this paper these algorithms are generalized without increasing complexity in order to introduce a minimum codeword length constraint $l_{\min}$, to allow for objective functions other than the minimization of expected codeword length, and to be applicable to both binary and nonbinary codes; nonbinary codes were previously addressed using a slower dynamic programming approach. These extensions have various applications -- including fast decompression and a modified version of the game ``Twenty Questions'' -- and can be used to solve the problem of finding an optimal code with limited fringe, that is, finding the best code among codes with a maximum difference between the longest and shortest codewords. The previously proposed method for solving this problem was nonpolynomial time, whereas solving this using the novel linear-space algorithm requires only $O(n (l_{\max}- l_{\min})^2)$ time, or even less if $l_{\max}- l_{\min}$ is not $O(\log n)$.


title: On the Block Error Probability of LP Decoding of LDPC Codes

abstract: In his thesis, Wiberg showed the existence of thresholds for families of regular low-density parity-check codes under min-sum algorithm decoding. He also derived analytic bounds on these thresholds. In this paper, we formulate similar results for linear programming decoding of regular low-density parity-check codes.


title: Bounds on the Threshold of Linear Programming Decoding

abstract: Whereas many results are known about thresholds for ensembles of low-density parity-check codes under message-passing iterative decoding, this is not the case for linear programming decoding. Towards closing this knowledge gap, this paper presents some bounds on the thresholds of low-density parity-check code ensembles under linear programming decoding.


title: Towards Low-Complexity Linear-Programming Decoding

abstract: We consider linear-programming (LP) decoding of low-density parity-check (LDPC) codes. While it is clear that one can use any general-purpose LP solver to solve the LP that appears in the decoding problem, we argue in this paper that the LP at hand is equipped with a lot of structure that one should take advantage of. Towards this goal, we study the dual LP and show how coordinate-ascent methods lead to very simple update rules that are tightly connected to the min-sum algorithm. Moreover, replacing minima in the formula of the dual LP with soft-minima one obtains update rules that are tightly connected to the sum-product algorithm. This shows that LP solvers with complexity similar to the min-sum algorithm and the sum-product algorithm are feasible. Finally, we also discuss some sub-gradient-based methods.


title: Pseudo-Codeword Analysis of Tanner Graphs from Projective and Euclidean Planes

abstract: In order to understand the performance of a code under maximum-likelihood (ML) decoding, one studies the codewords, in particular the minimal codewords, and their Hamming weights. In the context of linear programming (LP) decoding, one's attention needs to be shifted to the pseudo-codewords, in particular to the minimal pseudo-codewords, and their pseudo-weights. In this paper we investigate some families of codes that have good properties under LP decoding, namely certain families of low-density parity-check (LDPC) codes that are derived from projective and Euclidean planes: we study the structure of their minimal pseudo-codewords and give lower bounds on their pseudo-weight.


title: On the Approximation and Smoothed Complexity of Leontief Market Equilibria

abstract: We show that the problem of finding an \epsilon-approximate Nash equilibrium of an n by n two-person games can be reduced to the computation of an (\epsilon/n)^2-approximate market equilibrium of a Leontief economy. Together with a recent result of Chen, Deng and Teng, this polynomial reduction implies that the Leontief market exchange problem does not have a fully polynomial-time approximation scheme, that is, there is no algorithm that can compute an \epsilon-approximate market equilibrium in time polynomial in m, n, and 1/\epsilon, unless PPAD is not in P, We also extend the analysis of our reduction to show, unless PPAD is not in RP, that the smoothed complexity of the Scarf's general fixed-point approximation algorithm (when applying to solve the approximate Leontief market exchange problem) or of any algorithm for computing an approximate market equilibrium of Leontief economies is not polynomial in n and 1/\sigma, under Gaussian or uniform perturbations with magnitude \sigma.


title: Feedback Capacity of Stationary Gaussian Channels

abstract: The feedback capacity of additive stationary Gaussian noise channels is characterized as the solution to a variational problem. Toward this end, it is proved that the optimal feedback coding scheme is stationary. When specialized to the first-order autoregressive moving average noise spectrum, this variational characterization yields a closed-form expression for the feedback capacity. In particular, this result shows that the celebrated Schalkwijk-Kailath coding scheme achieves the feedback capacity for the first-order autoregressive moving average Gaussian channel, positively answering a long-standing open problem studied by Butman, Schalkwijk-Tiernan, Wolfowitz, Ozarow, Ordentlich, Yang-Kavcic-Tatikonda, and others. More generally, it is shown that a k-dimensional generalization of the Schalkwijk-Kailath coding scheme achieves the feedback capacity for any autoregressive moving average noise spectrum of order k. Simply put, the optimal transmitter iteratively refines the receiver's knowledge of the intended message.


title: Inconsistent parameter estimation in Markov random fields: Benefits in the computation-limited setting

abstract: Consider the problem of joint parameter estimation and prediction in a Markov random field: i.e., the model parameters are estimated on the basis of an initial set of data, and then the fitted model is used to perform prediction (e.g., smoothing, denoising, interpolation) on a new noisy observation. Working under the restriction of limited computation, we analyze a joint method in which the \emph{same convex variational relaxation} is used to construct an M-estimator for fitting parameters, and to perform approximate marginalization for the prediction step. The key result of this paper is that in the computation-limited setting, using an inconsistent parameter estimator (i.e., an estimator that returns the ``wrong'' model even in the infinite data limit) can be provably beneficial, since the resulting errors can partially compensate for errors made by using an approximate prediction technique. En route to this result, we analyze the asymptotic properties of M-estimators based on convex variational relaxations, and establish a Lipschitz stability property that holds for a broad class of variational methods. We show that joint estimation/prediction based on the reweighted sum-product algorithm substantially outperforms a commonly used heuristic based on ordinary sum-product.


title: Rational stochastic languages

abstract: The goal of the present paper is to provide a systematic and comprehensive study of rational stochastic languages over a semiring K \in {Q, Q +, R, R+}. A rational stochastic language is a probability distribution over a free monoid \Sigma^* which is rational over K, that is which can be generated by a multiplicity automata with parameters in K. We study the relations between the classes of rational stochastic languages S rat K (\Sigma). We define the notion of residual of a stochastic language and we use it to investigate properties of several subclasses of rational stochastic languages. Lastly, we study the representation of rational stochastic languages by means of multiplicity automata.


title: Effect of CSMA/CD on Self-Similarity of Network Traffic

abstract: It is now well known that Internet traffic exhibits self-similarity, which cannot be described by traditional Markovian models such as the Poisson process. The causes of self-similarity of network traffic must be identified because understanding the nature of network traffic is critical in order to properly design and implement computer networks and network services like the World Wide Web. While some researchers have argued self similarity is generated by the typical applications or caused by Transport layer Protocols, it is also possible that the CSMA/CD protocol may cause or at least contribute to this phenomenon. In this paper, we use NS simulator to study the effect of CSMA/CD Exponential Backoff retransmission algorithm on Traffic Self similarity.


title: Epsilon-Unfolding Orthogonal Polyhedra

abstract: An unfolding of a polyhedron is produced by cutting the surface and flattening to a single, connected, planar piece without overlap (except possibly at boundary points). It is a long unsolved problem to determine whether every polyhedron may be unfolded. Here we prove, via an algorithm, that every orthogonal polyhedron (one whose faces meet at right angles) of genus zero may be unfolded. Our cuts are not necessarily along edges of the polyhedron, but they are always parallel to polyhedron edges. For a polyhedron of n vertices, portions of the unfolding will be rectangular strips which, in the worst case, may need to be as thin as epsilon = 1/2^{Omega(n)}.


title: Difficulties in the Implementation of Quantum Computers

abstract: This paper reviews various engineering hurdles facing the field of quantum computing. Specifically, problems related to decoherence, state preparation, error correction, and implementability of gates are considered.


title: The Cubic Public-Key Transformation

abstract: We propose the use of the cubic transformation for public-key applications and digital signatures. Transformations modulo a prime p or a composite n=pq, where p and q are primes, are used in such a fashion that each transformed value has only 3 roots that makes it a more efficient transformation than the squaring transformation of Rabin, which has 4 roots. Such a transformation, together with additional tag information, makes it possible to uniquely invert each transformed value. The method may be used for other exponents as well.


title: Compositional Semantics for the Procedural Interpretation of Logic

abstract: Semantics of logic programs has been given by proof theory, model theory and by fixpoint of the immediate-consequence operator. If clausal logic is a programming language, then it should also have a compositional semantics. Compositional semantics for programming languages follows the abstract syntax of programs, composing the meaning of a unit by a mathematical operation on the meanings of its constituent units. The procedural interpretation of logic has only yielded an incomplete abstract syntax for logic programs. We complete it and use the result as basis of a compositional semantics. We present for comparison Tarski's algebraization of first-order predicate logic, which is in substance the compositional semantics for his choice of syntax. We characterize our semantics by equivalence with the immediate-consequence operator.


title: Towards Applicative Relational Programming

abstract: Functional programming comes in two flavours: one where ``functions are first-class citizens'' (we call this applicative) and one which is based on equations (we call this declarative). In relational programming clauses play the role of equations. Hence Prolog is declarative. The purpose of this paper is to provide in relational programming a mathematical basis for the relational analog of applicative functional programming. We use the cylindric semantics of first-order logic due to Tarski and provide a new notation for the required cylinders that we call tables. We define the Table/Relation Algebra with operators sufficient to translate Horn clauses into algebraic form. We establish basic mathematical properties of these operators. We show how relations can be first-class citizens, and devise mechanisms for modularity, for local scoping of predicates, and for exporting/importing relations between programs.


title: BioSig - An application of Octave

abstract: BioSig is an open source software library for biomedical signal processing. Most users in the field are using Matlab; however, significant effort was undertaken to provide compatibility to Octave, too. This effort has been widely successful, only some non-critical components relying on a graphical user interface are missing. Now, installing BioSig on Octave is as easy as on Matlab. Moreover, a benchmark test based on BioSig has been developed and the benchmark results of several platforms are presented.


title: On comparing sums of square roots of small integers

abstract: Let $k$ and $n$ be positive integers, $n>k$. Define $r(n,k)$ to be the minimum positive value of $$ |\sqrt{a_1} + ... + \sqrt{a_k} - \sqrt{b_1} - >... -\sqrt{b_k} | $$ where $ a_1, a_2, ..., a_k, b_1, b_2, ..., b_k $ are positive integers no larger than $n$. It is an important problem in computational geometry to determine a good upper bound of $-\log r(n,k)$. In this paper we prove an upper bound of $ 2^{O(n/\log n)} \log n$, which is better than the best known result $O(2^{2k} \log n)$ whenever $ n \leq ck\log k$ for some constant $c$. In particular, our result implies a {\em subexponential} algorithm to compare two sums of square roots of integers of size $o(k\log k)$.


title: Analyse non standard du bruit

abstract: Thanks to the nonstandard formalization of fast oscillating functions, due to P. Cartier and Y. Perrin, an appropriate mathematical framework is derived for new non-asymptotic estimation techniques, which do not necessitate any statistical analysis of the noises corrupting any sensor. Various applications are deduced for multiplicative noises, for the length of the parametric estimation windows, and for burst errors.


title: Lamarckian Evolution and the Baldwin Effect in Evolutionary Neural Networks

abstract: Hybrid neuro-evolutionary algorithms may be inspired on Darwinian or Lamarckian evolu- tion. In the case of Darwinian evolution, the Baldwin effect, that is, the progressive incorporation of learned characteristics to the genotypes, can be observed and leveraged to improve the search. The purpose of this paper is to carry out an exper- imental study into how learning can improve G-Prop genetic search. Two ways of combining learning and genetic search are explored: one exploits the Baldwin effect, while the other uses a Lamarckian strategy. Our experiments show that using a Lamarckian op- erator makes the algorithm find networks with a low error rate, and the smallest size, while using the Bald- win effect obtains MLPs with the smallest error rate, and a larger size, taking longer to reach a solution. Both approaches obtain a lower average error than other BP-based algorithms like RPROP, other evolu- tionary methods and fuzzy logic based methods


title: A Basic Introduction on Math-Link in Mathematica

abstract: Starting from the basic ideas of mathematica, we give a detailed description about the way of linking of external programs with mathematica through proper mathlink commands. This article may be quite helpful for the beginners to start with and write programs in mathematica. In the first part, we illustrate how to use a mathemtica notebook and write a complete program in the notebook. Following with this, we also mention elaborately about the utility of the local and global variables those are very essential for writing a program in mathematica. All the commands needed for doing different mathematical operations can be found with some proper examples in the mathematica book written by Stephen Wolfram \cite{wolfram}. In the rest of this article, we concentrate our study on the most significant issue which is the process of linking of {\em external programs} with mathematica, so-called the mathlink operation. By using proper mathlink commands one can run very tedious jobs efficiently and the operations become extremely fast.


title: Pivotal and Pivotal-discriminative Consequence Relations

abstract: In the present paper, we investigate consequence relations that are both paraconsistent and plausible (but still monotonic). More precisely, we put the focus on pivotal consequence relations, i.e. those relations that can be defined by a pivot (in the style of e.g. D. Makinson). A pivot is a fixed subset of valuations which are considered to be the important ones in the absolute sense. We worked with a general notion of valuation that covers e.g. the classical valuations as well as certain kinds of many-valued valuations. In the many-valued cases, pivotal consequence relations are paraconsistant (in addition to be plausible), i.e. they are capable of drawing reasonable conclusions which contain contradictions. We will provide in our general framework syntactic characterizations of several families of pivotal relations. In addition, we will provide, again in our general framework, characterizations of several families of pivotal discriminative consequence relations. The latter are defined exactly as the plain version, but contradictory conclusions are rejected. We will also answer negatively a representation problem that was left open by Makinson. Finally, we will put in evidence a connexion with X-logics from Forget, Risch, and Siegel. The motivations and the framework of the present paper are very close to those of a previous paper of the author which is about preferential consequence relations.


title: Complete Enumeration of Stopping Sets of Full-Rank Parity-Check Matrices of Hamming Codes

abstract: Stopping sets, and in particular their numbers and sizes, play an important role in determining the performance of iterative decoders of linear codes over binary erasure channels. In the 2004 Shannon Lecture, McEliece presented an expression for the number of stopping sets of size three for a full-rank parity-check matrix of the Hamming code. In this correspondence, we derive an expression for the number of stopping sets of any given size for the same parity-check matrix.


title: Linear Secret Sharing from Algebraic-Geometric Codes

abstract: It is well-known that the linear secret-sharing scheme (LSSS) can be constructed from linear error-correcting codes (Brickell [1], R.J. McEliece and D.V.Sarwate [2],Cramer, el.,[3]). The theory of linear codes from algebraic-geometric curves (algebraic-geometric (AG) codes or geometric Goppa code) has been well-developed since the work of V.Goppa and Tsfasman, Vladut, and Zink(see [17], [18] and [19]). In this paper the linear secret-sharing scheme from algebraic-geometric codes, which are non-threshold scheme for curves of genus greater than 0, are presented . We analysis the minimal access structure, $d_{min}$ and $d_{cheat}$([8]), (strongly) multiplicativity and the applications in verifiable secret-sharing (VSS) scheme and secure multi-party computation (MPC) of this construction([3] and [10-11]). Our construction also offers many examples of the self-dually $GF(q)$-representable matroids and many examples of new ideal linear secret-sharing schemes addressing to the problem of the characterization of the access structures for ideal secret-sharing schemes([3] and [9]). The access structures of the linear secret-sharing schemes from the codes on elliptic curves are given explicitly. From the work in this paper we can see that the algebraic-geometric structure of the underlying algebraic curves is an important resource for secret-sharing, matroid theory, verifiable secret-sharing and secure multi-party computation.


title: An Achievability Result for the General Relay Channel

abstract: See cs.IT/0605135: R. Dabora, S. D. Servetto; On the Role of Estimate-and-Forward with Time-Sharing in Cooperative Communications.


title: Asymptotic constant-factor approximation algorithm for the Traveling Salesperson Problem for Dubins' vehicle

abstract: This article proposes the first known algorithm that achieves a constant-factor approximation of the minimum length tour for a Dubins' vehicle through $n$ points on the plane. By Dubins' vehicle, we mean a vehicle constrained to move at constant speed along paths with bounded curvature without reversing direction. For this version of the classic Traveling Salesperson Problem, our algorithm closes the gap between previously established lower and upper bounds; the achievable performance is of order $n^{2/3}$.


title: Intrinsically Legal-For-Trade Objects by Digital Signatures

abstract: The established techniques for legal-for-trade registration of weight values meet the legal requirements, but in praxis they show serious disadvantages. We report on the first implementation of intrinsically legal-for-trade objects, namely weight values signed by the scale, that is accepted by the approval authority. The strict requirements from both the approval- and the verification-authority as well as the limitations due to the hardware of the scale were a special challenge. The presented solution fulfills all legal requirements and eliminates the existing practical disadvantages.


title: Improved Bounds and Schemes for the Declustering Problem

abstract: The declustering problem is to allocate given data on parallel working storage devices in such a manner that typical requests find their data evenly distributed on the devices. Using deep results from discrepancy theory, we improve previous work of several authors concerning range queries to higher-dimensional data. We give a declustering scheme with an additive error of $O_d(\log^{d-1} M)$ independent of the data size, where $d$ is the dimension, $M$ the number of storage devices and $d-1$ does not exceed the smallest prime power in the canonical decomposition of $M$ into prime powers. In particular, our schemes work for arbitrary $M$ in dimensions two and three. For general $d$, they work for all $M\geq d-1$ that are powers of two. Concerning lower bounds, we show that a recent proof of a $\Omega_d(\log^{\frac{d-1}{2}} M)$ bound contains an error. We close the gap in the proof and thus establish the bound.


title: On the MacWilliams Identity for Convolutional Codes

abstract: The adjacency matrix associated with a convolutional code collects in a detailed manner information about the weight distribution of the code. A MacWilliams Identity Conjecture, stating that the adjacency matrix of a code fully determines the adjacency matrix of the dual code, will be formulated, and an explicit formula for the transformation will be stated. The formula involves the MacWilliams matrix known from complete weight enumerators of block codes. The conjecture will be proven for the class of convolutional codes where either the code itself or its dual does not have Forney indices bigger than one. For the general case the conjecture is backed up by many examples, and a weaker version will be established.


title: Near orders and codes

abstract: Hoholdt, van Lint and Pellikaan used order functions to construct codes by means of Linear Algebra and Semigroup Theory only. However, Geometric Goppa codes that can be represented by this method are mainly those based on just one point. In this paper we introduce the concept of near order function with the aim of generalize this approach in such a way that a of wider family of Geometric Goppa codes can be studied on a more elementary setting.


title: The Basic Kak Neural Network with Complex Inputs

abstract: The Kak family of neural networks is able to learn patterns quickly, and this speed of learning can be a decisive advantage over other competing models in many applications. Amongst the implementations of these networks are those using reconfigurable networks, FPGAs and optical networks. In some applications, it is useful to use complex data, and it is with that in mind that this introduction to the basic Kak network with complex inputs is being presented. The training algorithm is prescriptive and the network weights are assigned simply upon examining the inputs. The input is mapped using quaternary encoding for purpose of efficienty. This network family is part of a larger hierarchy of learning schemes that include quantum models.


title: Object-Oriented Modeling of Programming Paradigms

abstract: For the right application, the use of programming paradigms such as functional or logic programming can enormously increase productivity in software development. But these powerful paradigms are tied to exotic programming languages, while the management of software development dictates standardization on a single language. This dilemma can be resolved by using object-oriented programming in a new way. It is conventional to analyze an application by object-oriented modeling. In the new approach, the analysis identifies the paradigm that is ideal for the application; development starts with object-oriented modeling of the paradigm. In this paper we illustrate the new approach by giving examples of object-oriented modeling of dataflow and constraint programming. These examples suggest that it is no longer necessary to embody a programming paradigm in a language dedicated to it.


title: A Measure of Space for Computing over the Reals

abstract: We propose a new complexity measure of space for the BSS model of computation. We define LOGSPACE\_W and PSPACE\_W complexity classes over the reals. We prove that LOGSPACE\_W is included in NC^2\_R and in P\_W, i.e. is small enough for being relevant. We prove that the Real Circuit Decision Problem is P\_R-complete under LOGSPACE\_W reductions, i.e. that LOGSPACE\_W is large enough for containing natural algorithms. We also prove that PSPACE\_W is included in PAR\_R.


title: On Non-coherent MIMO Channels in the Wideband Regime: Capacity and Reliability

abstract: We consider a multiple-input, multiple-output (MIMO) wideband Rayleigh block fading channel where the channel state is unknown to both the transmitter and the receiver and there is only an average power constraint on the input. We compute the capacity and analyze its dependence on coherence length, number of antennas and receive signal-to-noise ratio (SNR) per degree of freedom. We establish conditions on the coherence length and number of antennas for the non-coherent channel to have a "near coherent" performance in the wideband regime. We also propose a signaling scheme that is near-capacity achieving in this regime. We compute the error probability for this wideband non-coherent MIMO channel and study its dependence on SNR, number of transmit and receive antennas and coherence length. We show that error probability decays inversely with coherence length and exponentially with the product of the number of transmit and receive antennas. Moreover, channel outage dominates error probability in the wideband regime. We also show that the critical as well as cut-off rates are much smaller than channel capacity in this regime.


title: Characterizing the NP-PSPACE Gap in the Satisfiability Problem for Modal Logic

abstract: There has been a great of work on characterizing the complexity of the satisfiability and validity problem for modal logics. In particular, Ladner showed that the validity problem for all logics between K, T, and S4 is {\sl PSPACE}-complete, while for S5 it is {\sl NP}-complete. We show that, in a precise sense, it is \emph{negative introspection}, the axiom $\neg K p \rimp K \neg K p$, that causes the gap. In a precise sense, if we require this axiom, then the satisfiability problem is {\sl NP}-complete; without it, it is {\sl PSPACE}-complete.


title: Reasoning About Knowledge of Unawareness

abstract: Awareness has been shown to be a useful addition to standard epistemic logic for many applications. However, standard propositional logics for knowledge and awareness cannot express the fact that an agent knows that there are facts of which he is unaware without there being an explicit fact that the agent knows he is unaware of. We propose a logic for reasoning about knowledge of unawareness, by extending Fagin and Halpern's \emph{Logic of General Awareness}. The logic allows quantification over variables, so that there is a formula in the language that can express the fact that ``an agent explicitly knows that there exists a fact of which he is unaware''. Moreover, that formula can be true without the agent explicitly knowing that he is unaware of any particular formula. We provide a sound and complete axiomatization of the logic, using standard axioms from the literature to capture the quantification operator. Finally, we show that the validity problem for the logic is recursively enumerable, but not decidable.


title: Language Support for Optional Functionality

abstract: We recommend a programming construct - availability check - for programs that need to automatically adjust to presence or absence of segments of code. The idea is to check the existence of a valid definition before a function call is invoked. The syntax is that of a simple 'if' statement. The vision is to enable customization of application functionality through addition or removal of optional components, but without requiring complete re-building. Focus is on C-like compiled procedural languages and UNIX-based systems. Essentially, our approach attempts to combine the flexibility of dynamic libraries with the usability of utility (dependency) libraries. We outline the benefits over prevalent strategies mainly in terms of development complexity, crudely measured as lesser lines of code. We also allude to performance and flexibility facets. A Preliminary implementation and figures from early experimental evaluation are presented.


title: On Separation, Randomness and Linearity for Network Codes over Finite Fields

abstract: We examine the issue of separation and code design for networks that operate over finite fields. We demonstrate that source-channel (or source-network) separation holds for several canonical network examples like the noisy multiple access channel and the erasure degraded broadcast channel, when the whole network operates over a common finite field. This robustness of separation is predicated on the fact that noise and inputs are independent, and we examine the failure of separation when noise is dependent on inputs in multiple access channels. Our approach is based on the sufficiency of linear codes. Using a simple and unifying framework, we not only re-establish with economy the optimality of linear codes for single-transmitter, single-receiver channels and for Slepian-Wolf source coding, but also establish the optimality of linear codes for multiple access and for erasure degraded broadcast channels. The linearity allows us to obtain simple optimal code constructions and to study capacity regions of the noisy multiple access and the degraded broadcast channel. The linearity of both source and network coding blurs the delineation between source and network codes. While our results point to the fact that separation of source coding and channel coding is optimal in some canonical networks, we show that decomposing networks into canonical subnetworks may not be effective. Thus, we argue that it may be the lack of decomposability of a network into canonical network modules, rather than the lack of separation between source and channel coding, that presents major challenges for coding over networks.


title: Metric State Space Reinforcement Learning for a Vision-Capable Mobile Robot

abstract: We address the problem of autonomously learning controllers for vision-capable mobile robots. We extend McCallum's (1995) Nearest-Sequence Memory algorithm to allow for general metrics over state-action trajectories. We demonstrate the feasibility of our approach by successfully running our algorithm on a real mobile robot. The algorithm is novel and unique in that it (a) explores the environment and learns directly on a mobile robot without using a hand-made computer model as an intermediate step, (b) does not require manual discretization of the sensor input space, (c) works in piecewise continuous perceptual spaces, and (d) copes with partial observability. Together this allows learning from much less experience compared to previous methods.


title: Representing Contextualized Information in the NSDL

abstract: The NSDL (National Science Digital Library) is funded by the National Science Foundation to advance science and match education. The inital product was a metadata-based digital library providing search and access to distributed resources. Our recent work recognizes the importance of context - relations, metadata, annotations - for the pedagogical value of a digital library. This new architecture uses Fedora, a tool for representing complex content, data, metadata, web-based services, and semantic relationships, as the basis of an information network overlay (INO). The INO provides an extensible knowl-edge base for an expanding suite of digital library services.


title: Open Answer Set Programming with Guarded Programs

abstract: Open answer set programming (OASP) is an extension of answer set programming where one may ground a program with an arbitrary superset of the program's constants. We define a fixed point logic (FPL) extension of Clark's completion such that open answer sets correspond to models of FPL formulas and identify a syntactic subclass of programs, called (loosely) guarded programs. Whereas reasoning with general programs in OASP is undecidable, the FPL translation of (loosely) guarded programs falls in the decidable (loosely) guarded fixed point logic (mu(L)GF). Moreover, we reduce normal closed ASP to loosely guarded OASP, enabling for the first time, a characterization of an answer set semantics by muLGF formulas. We further extend the open answer set semantics for programs with generalized literals. Such generalized programs (gPs) have interesting properties, e.g., the ability to express infinity axioms. We restrict the syntax of gPs such that both rules and generalized literals are guarded. Via a translation to guarded fixed point logic, we deduce 2-exptime-completeness of satisfiability checking in such guarded gPs (GgPs). Bound GgPs are restricted GgPs with exptime-complete satisfiability checking, but still sufficiently expressive to optimally simulate computation tree logic (CTL). We translate Datalog lite programs to GgPs, establishing equivalence of GgPs under an open answer set semantics, alternation-free muGF, and Datalog lite.


title: The Snowblower Problem

abstract: We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to compute a short tour for the snowblower to follow to remove all the snow from a domain (driveway, sidewalk, etc.). When a snowblower passes over each region along the tour, it displaces snow into a nearby region. The constraint is that if the snow is piled too high, then the snowblower cannot clear the pile. We give an algorithmic study of the SBP. We show that in general, the problem is NP-complete, and we present polynomial-time approximation algorithms for removing snow under various assumptions about the operation of the snowblower. Most commercially-available snowblowers allow the user to control the direction in which the snow is thrown. We differentiate between the cases in which the snow can be thrown in any direction, in any direction except backwards, and only to the right. For all cases, we give constant-factor approximation algorithms; the constants increase as the throw direction becomes more restricted. Our results are also applicable to robotic vacuuming (or lawnmowing) with bounded capacity dust bin and to some versions of material-handling problems, in which the goal is to rearrange cartons on the floor of a warehouse.


title: On the Second-Order Statistics of the Instantaneous Mutual Information in Rayleigh Fading Channels

abstract: In this paper, the second-order statistics of the instantaneous mutual information are studied, in time-varying Rayleigh fading channels, assuming general non-isotropic scattering environments. Specifically, first the autocorrelation function, correlation coefficient, level crossing rate, and the average outage duration of the instantaneous mutual information are investigated in single-input single-output (SISO) systems. Closed-form exact expressions are derived, as well as accurate approximations in low- and high-SNR regimes. Then, the results are extended to multiple-input single-output and single-input multiple-output systems, as well as multiple-input multiple-output systems with orthogonal space-time block code transmission. Monte Carlo simulations are provided to verify the accuracy of the analytical results. The results shed more light on the dynamic behavior of the instantaneous mutual information in mobile fading channels.


title: On the tree-transformation power of XSLT

abstract: XSLT is a standard rule-based programming language for expressing transformations of XML data. The language is currently in transition from version 1.0 to 2.0. In order to understand the computational consequences of this transition, we restrict XSLT to its pure tree-transformation capabilities. Under this focus, we observe that XSLT~1.0 was not yet a computationally complete tree-transformation language: every 1.0 program can be implemented in exponential time. A crucial new feature of version~2.0, however, which allows nodesets over temporary trees, yields completeness. We provide a formal operational semantics for XSLT programs, and establish confluence for this semantics.


title: A d-Sequence based Recursive Random Number Generator

abstract: This paper proposes a new recursive technique using d-sequences to generate random numbers.


title: A Service-Centric Approach to a Parameterized RBAC Service

abstract: Significant research has been done in the area of Role Based Access Control [RBAC]. Within this research there has been a thread of work focusing on adding parameters to the role and permissions within RBAC. The primary benefit of parameter support in RBAC comes in the form of a significant increase in specificity in how permissions may be granted. This paper focuses on implementing a parameterized implementation based heavily upon existing standards.


title: Performance Analysis of CDMA Signature Optimization with Finite Rate Feedback

abstract: We analyze the performance of CDMA signature optimization with finite rate feedback. For a particular user, the receiver selects a signature vector from a signature codebook to avoid the interference from other users, and feeds the corresponding index back to this user through a finite rate and error-free feedback link. We assume the codebook is randomly constructed where the entries are independent and isotropically distributed. It has been shown that the randomly constructed codebook is asymptotically optimal. In this paper, we consider two types of signature selection criteria. One is to select the signature vector that minimizes the interference from other users. The other one is to select the signature vector to match the weakest interference directions. By letting the processing gain, number of users and feedback bits approach infinity with fixed ratios, we derive the exact asymptotic formulas to calculate the average interference for both criteria. Our simulations demonstrate the theoretical formulas. The analysis can be extended to evaluate the signal-to-interference plus noise ratio performance for both match filter and linear minimum mean-square error receivers.


title: Market Equilibrium for Bundle Auctions and the Matching Core of Nonnegative TU Games

abstract: We discuss bundle auctions within the framework of an integer allocation problem. We show that for multi-unit auctions, of which bundle auctions are a special case, market equilibrium and constrained market equilibrium are equivalent concepts. This equivalence, allows us to obtain a computable necessary and sufficient condition for the existence of constrained market equilibrium for bundle auctions. We use this result to obtain a necessary and sufficient condition for the existence of market equilibrium for multi-unit auctions. After obtaining the induced bundle auction of a nonnegative TU game, we show that the existence of market equilibrium implies the existence of a possibly different market equilibrium as well, which corresponds very naturally to an outcome in the matching core of the TU game. Consequently we show that the matching core of the nonnegative TU game is non-empty if and only if the induced market game has a market equilibrium.


title: Inter-component communication methods in object-oriented frameworks

abstract: Modern frameworks for development of graphical interfaces are using the native controls of the operating system. Because of that they are using operating system events model for inter-component communication. We consider a method to increase inter-component communication speed by sending messages from one component to the other passing over the operating system. Besides the messages subscription helps to avoid receiving of unnecessary messages.


title: Metatheory of actions: beyond consistency

abstract: Consistency check has been the only criterion for theory evaluation in logic-based approaches to reasoning about actions. This work goes beyond that and contributes to the metatheory of actions by investigating what other properties a good domain description in reasoning about actions should have. We state some metatheoretical postulates concerning this sore spot. When all postulates are satisfied together we have a modular action theory. Besides being easier to understand and more elaboration tolerant in McCarthy's sense, modular theories have interesting properties. We point out the problems that arise when the postulates about modularity are violated and propose algorithmic checks that can help the designer of an action theory to overcome them.


title: Final Results from and Exploitation Plans for MammoGrid

abstract: The MammoGrid project has delivered the first deployed instance of a healthgrid for clinical mammography that spans national boundaries. During the last year, the final MammoGrid prototype has undergone a series of rigorous tests undertaken by radiologists in the UK and Italy and this paper draws conclusions from those tests for the benefit of the Healthgrid community. In addition, lessons learned during the lifetime of the project are detailed and recommendations drawn for future health applications using grids. Following the completion of the project, plans have been put in place for the commercialisation of the MammoGrid system and this is also reported in this article. Particular emphasis is placed on the issues surrounding the transition from collaborative research project to a marketable product. This paper concludes by highlighting some of the potential areas of future development and research.


title: Health-e-Child : An Integrated Biomedical Platform for Grid-Based Paediatric Applications

abstract: There is a compelling demand for the integration and exploitation of heterogeneous biomedical information for improved clinical practice, medical research, and personalised healthcare across the EU. The Health-e-Child project aims at developing an integrated healthcare platform for European Paediatrics, providing seamless integration of traditional and emerging sources of biomedical information. The long-term goal of the project is to provide uninhibited access to universal biomedical knowledge repositories for personalised and preventive healthcare, large-scale information-based biomedical research and training, and informed policy making. The project focus will be on individualised disease prevention, screening, early diagnosis, therapy and follow-up of paediatric heart diseases, inflammatory diseases, and brain tumours. The project will build a Grid-enabled European network of leading clinical centres that will share and annotate biomedical data, validate systems clinically, and diffuse clinical excellence across Europe by setting up new technologies, clinical workflows, and standards. This paper outlines the design approach being adopted in Health-e-Child to enable the delivery of an integrated biomedical information platform.


title: Deriving Conceptual Data Models from Domain Ontologies for Bioinformatics

abstract: This paper studies the role that ontologies can play in establishing conceptual data models during the process of information systems development. A mapping algorithm has been proposed and embedded in a special purpose Transformation-Engine to generate a conceptual data model from a given domain ontology. In addition, this paper focuses on applying the proposed approach to a bioinformatics context as the nature of biological data is considered a barrier in representing biological conceptual data models. Both quantitative and qualitative methods have been adopted to critically evaluate this new approach. The results of this evaluation indicate that the quality of the generated conceptual data models can reflect the problem domain entities and the associations between them. The results are encouraging and support the potential role that this approach can play in providing a suitable starting point for conceptual data model development.


title: Estimation of linear, non-gaussian causal models in the presence of confounding latent variables

abstract: The estimation of linear causal models (also known as structural equation models) from data is a well-known problem which has received much attention in the past. Most previous work has, however, made an explicit or implicit assumption of gaussianity, limiting the identifiability of the models. We have recently shown (Shimizu et al, 2005; Hoyer et al, 2006) that for non-gaussian distributions the full causal model can be estimated in the no hidden variables case. In this contribution, we discuss the estimation of the model when confounding latent variables are present. Although in this case uniqueness is no longer guaranteed, there is at most a finite set of models which can fit the data. We develop an algorithm for estimating this set, and describe numerical simulations which confirm the theoretical arguments and demonstrate the practical viability of the approach. Full Matlab code is provided for all simulations.


title: Quantization Bounds on Grassmann Manifolds and Applications to MIMO Communications

abstract: This paper considers the quantization problem on the Grassmann manifold \mathcal{G}_{n,p}, the set of all p-dimensional planes (through the origin) in the n-dimensional Euclidean space. The chief result is a closed-form formula for the volume of a metric ball in the Grassmann manifold when the radius is sufficiently small. This volume formula holds for Grassmann manifolds with arbitrary dimension n and p, while previous results pertained only to p=1, or a fixed p with asymptotically large n. Based on this result, several quantization bounds are derived for sphere packing and rate distortion tradeoff. We establish asymptotically equivalent lower and upper bounds for the rate distortion tradeoff. Since the upper bound is derived by constructing random codes, this result implies that the random codes are asymptotically optimal. The above results are also extended to the more general case, in which \mathcal{G}_{n,q} is quantized through a code in \mathcal{G}_{n,p}, where p and q are not necessarily the same. Finally, we discuss some applications of the derived results to multi-antenna communication systems.