title: Tree Automata Make Ordinal Theory Easy

abstract: We give a new simple proof of the decidability of the First Order Theory of (omega^omega^i,+) and the Monadic Second Order Theory of (omega^i,<), improving the complexity in both cases. Our algorithm is based on tree automata and a new representation of (sets of) ordinals by (infinite) trees.


title: ECA-RuleML: An Approach combining ECA Rules with temporal interval-based KR Event/Action Logics and Transactional Update Logics

abstract: An important problem to be addressed within Event-Driven Architecture (EDA) is how to correctly and efficiently capture and process the event/action-based logic. This paper endeavors to bridge the gap between the Knowledge Representation (KR) approaches based on durable events/actions and such formalisms as event calculus, on one hand, and event-condition-action (ECA) reaction rules extending the approach of active databases that view events as instantaneous occurrences and/or sequences of events, on the other. We propose formalism based on reaction rules (ECA rules) and a novel interval-based event logic and present concrete RuleML-based syntax, semantics and implementation. We further evaluate this approach theoretically, experimentally and on an example derived from common industry use cases and illustrate its benefits.


title: Presentation Theorems for Coded Character Sets

abstract: The notion of 'presentation', as used in combinatorial group theory, is applied to coded character sets(CCSs) - sets which facilitate the interchange of messages in a digital computer network(DCN) . By grouping each element of the set into two portions and using the idea of group presentation(whereby a group is specified by its set of generators and its set of relators), the presentation of a CCS is described. This is illustrated using the Extended Binary Coded Decimal Interchange Code(EBCDIC) which is one of the most popular CCSs in DCNs. Key words: Group presentation, coded character set, digital computer network


title: On the User Selection for MIMO Broadcast Channels

abstract: In this paper, a downlink communication system, in which a Base Station (BS) equipped with $M$ antennas communicates with $N$ users each equipped with $K$ receive antennas, is considered. An efficient suboptimum algorithm is proposed for selecting a set of users in order to maximize the sum-rate throughput of the system. For the asymptotic case when $N$ tends to infinity, the necessary and sufficient conditions in order to achieve the maximum sum-rate throughput, such that the difference between the achievable sum-rate and the maximum value approaches zero, is derived. The complexity of our algorithm is investigated in terms of the required amount of feedback from the users to the base station, as well as the number of searches required for selecting the users. It is shown that the proposed method is capable of achieving a large portion of the sum-rate capacity, with a very low complexity.


title: Low-complexity modular policies: learning to play Pac-Man and a new framework beyond MDPs

abstract: In this paper we propose a method that learns to play Pac-Man. We define a set of high-level observation and action modules. Actions are temporally extended, and multiple action modules may be in effect concurrently. A decision of the agent is represented as a rule-based policy. For learning, we apply the cross-entropy method, a recent global optimization algorithm. The learned policies reached better score than the hand-crafted policy, and neared the score of average human players. We argue that learning is successful mainly because (i) the policy space includes the combination of individual actions and thus it is sufficiently rich, (ii) the search is biased towards low-complexity policies and low complexity solutions can be found quickly if they exist. Based on these principles, we formulate a new theoretical framework, which can be found in the Appendix as supporting material.


title: Coupling of quantum angular momenta: an insight into analogic/discrete and local/global models of computation

abstract: In the past few years there has been a tumultuous activity aimed at introducing novel conceptual schemes for quantum computing. The approach proposed in (Marzuoli A and Rasetti M 2002, 2005a) relies on the (re)coupling theory of SU(2) angular momenta and can be viewed as a generalization to arbitrary values of the spin variables of the usual quantum-circuit model based on `qubits' and Boolean gates. Computational states belong to finite-dimensional Hilbert spaces labelled by both discrete and continuous parameters, and unitary gates may depend on quantum numbers ranging over finite sets of values as well as continuous (angular) variables. Such a framework is an ideal playground to discuss discrete (digital) and analogic computational processes, together with their relationships occuring when a consistent semiclassical limit takes place on discrete quantum gates. When working with purely discrete unitary gates, the simulator is naturally modelled as families of quantum finite states--machines which in turn represent discrete versions of topological quantum computation models. We argue that our model embodies a sort of unifying paradigm for computing inspired by Nature and, even more ambitiously, a universal setting in which suitably encoded quantum symbolic manipulations of combinatorial, topological and algebraic problems might find their `natural' computational reference model.


title: On the Analysis and Generalization of Extended Visual Cryptography Schemes

abstract: An Extended Visual Cryptography Scheme (EVCS) was proposed by Ateniese et al. [3] to protect a binary secret image with meaningful (innocent-looking) shares. This is implemented by concatenating an extended matrix to each basis matrix. The minimum size of the extended matrix was obtained from a hypergraph coloring model and the scheme was designed for binary images only [3]. In this paper, we give a more concise derivation for this matrix extension for color images. Furthermore, we present a (k, n) scheme to protect multiple color images with meaningful shares. This scheme is an extension of the (n, n) VCS for multiple binary images proposed in Droste scheme [2].


title: On Degree-Based Decentralized Search in Complex Networks

abstract: Decentralized search aims to find the target node in a large network by using only local information. The applications of it include peer-to-peer file sharing, web search and anything else that requires locating a specific target in a complex system. In this paper, we examine the degree-based decentralized search method. Specifically, we evaluate the efficiency of the method in different cases with different amounts of available local information. In addition, we propose a simple refinement algorithm for significantly shortening the length of the route that has been found. Some insights useful for the future developments of efficient decentralized search schemes have been achieved.


title: A Fixed-Parameter Algorithm for #SAT with Parameter Incidence Treewidth

abstract: We present an efficient fixed-parameter algorithm for #SAT parameterized by the incidence treewidth, i.e., the treewidth of the bipartite graph whose vertices are the variables and clauses of the given CNF formula; a variable and a clause are joined by an edge if and only if the variable occurs in the clause. Our algorithm runs in time O(4^k k l N), where k denotes the incidence treewidth, l denotes the size of a largest clause, and N denotes the number of nodes of the tree-decomposition.


title: DSmT: A new paradigm shift for information fusion

abstract: The management and combination of uncertain, imprecise, fuzzy and even paradoxical or high conflicting sources of information has always been and still remains of primal importance for the development of reliable information fusion systems. In this short survey paper, we present the theory of plausible and paradoxical reasoning, known as DSmT (Dezert-Smarandache Theory) in literature, developed for dealing with imprecise, uncertain and potentially highly conflicting sources of information. DSmT is a new paradigm shift for information fusion and recent publications have shown the interest and the potential ability of DSmT to solve fusion problems where Dempster's rule used in Dempster-Shafer Theory (DST) provides counter-intuitive results or fails to provide useful result at all. This paper is focused on the foundations of DSmT and on its main rules of combination (classic, hybrid and Proportional Conflict Redistribution rules). Shafer's model on which is based DST appears as a particular and specific case of DSm hybrid model which can be easily handled by DSmT as well. Several simple but illustrative examples are given throughout this paper to show the interest and the generality of this new theory.


title: A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners

abstract: In this paper we devise an extremely efficient fully dynamic distributed algorithm for maintaining sparse spanners. Our resuls also include the first fully dynamic centralized algorithm for the problem with non-trivial bounds for both incremental and decremental update. Finally, we devise a very efficient streaming algorithm for the problem.


title: Lattice Quantization with Side Information: Codes, Asymptotics, and Applications in Sensor Networks

abstract: We consider the problem of rate/distortion with side information available only at the decoder. For the case of jointly-Gaussian source X and side information Y, and mean-squared error distortion, Wyner proved in 1976 that the rate/distortion function for this problem is identical to the conditional rate/distortion function R_{X|Y}, assuming the side information Y is available at the encoder. In this paper we construct a structured class of asymptotically optimal quantizers for this problem: under the assumption of high correlation between source X and side information Y, we show there exist quantizers within our class whose performance comes arbitrarily close to Wyner's bound. As an application illustrating the relevance of the high-correlation asymptotics, we also explore the use of these quantizers in the context of a problem of data compression for sensor networks, in a setup involving a large number of devices collecting highly correlated measurements within a confined area. An important feature of our formulation is that, although the per-node throughput of the network tends to zero as network size increases, so does the amount of information generated by each transmitter. This is a situation likely to be encountered often in practice, which allows us to cast under new--and more ``optimistic''--light some negative results on the transport capacity of large-scale wireless networks.


title: A Scalable Protocol for Cooperative Time Synchronization Using Spatial Averaging

abstract: Time synchronization is an important aspect of sensor network operation. However, it is well known that synchronization error accumulates over multiple hops. This presents a challenge for large-scale, multi-hop sensor networks with a large number of nodes distributed over wide areas. In this work, we present a protocol that uses spatial averaging to reduce error accumulation in large-scale networks. We provide an analysis to quantify the synchronization improvement achieved using spatial averaging and find that in a basic cooperative network, the skew and offset variance decrease approximately as $1/\bar{N}$ where $\bar{N}$ is the number of cooperating nodes. For general networks, simulation results and a comparison to basic cooperative network results are used to illustrate the improvement in synchronization performance.


title: Linear Abadi and Plotkin Logic

abstract: We present a formalization of a version of Abadi and Plotkin's logic for parametricity for a polymorphic dual intuitionistic/linear type theory with fixed points, and show, following Plotkin's suggestions, that it can be used to define a wide collection of types, including existential types, inductive types, coinductive types and general recursive types. We show that the recursive types satisfy a universal property called dinaturality, and we develop reasoning principles for the constructed types. In the case of recursive types, the reasoning principle is a mixed induction/coinduction principle, with the curious property that coinduction holds for general relations, but induction only for a limited collection of ``admissible'' relations. A similar property was observed in Pitts' 1995 analysis of recursive types in domain theory. In a future paper we will develop a category theoretic notion of models of the logic presented here, and show how the results developed in the logic can be transferred to the models.


title: Protocols for Scholarly Communication

abstract: CERN, the European Organization for Nuclear Research, has operated an institutional preprint repository for more than 10 years. The repository contains over 850,000 records of which more than 450,000 are full-text OA preprints, mostly in the field of particle physics, and it is integrated with the library's holdings of books, conference proceedings, journals and other grey literature. In order to encourage effective propagation and open access to scholarly material, CERN is implementing a range of innovative library services into its document repository: automatic keywording, reference extraction, collaborative management tools and bibliometric tools. Some of these services, such as user reviewing and automatic metadata extraction, could make up an interesting testbed for future publishing solutions and certainly provide an exciting environment for e-science possibilities. The future protocol for scientific communication should naturally guide authors towards OA publication and CERN wants to help reach a full open access publishing environment for the particle physics community and the related sciences in the next few years.


title: Evolving controllers for simulated car racing

abstract: This paper describes the evolution of controllers for racing a simulated radio-controlled car around a track, modelled on a real physical track. Five different controller architectures were compared, based on neural networks, force fields and action sequences. The controllers use either egocentric (first person), Newtonian (third person) or no information about the state of the car (open-loop controller). The only controller that was able to evolve good racing behaviour was based on a neural network acting on egocentric inputs.


title: MIMO Multichannel Beamforming: SER and Outage Using New Eigenvalue Distributions of Complex Noncentral Wishart Matrices

abstract: This paper analyzes MIMO systems with multichannel beamforming in Ricean fading. Our results apply to a wide class of multichannel systems which transmit on the eigenmodes of the MIMO channel. We first present new closed-form expressions for the marginal ordered eigenvalue distributions of complex noncentral Wishart matrices. These are used to characterize the statistics of the signal to noise ratio (SNR) on each eigenmode. Based on this, we present exact symbol error rate (SER) expressions. We also derive closed-form expressions for the diversity order, array gain, and outage probability. We show that the global SER performance is dominated by the subchannel corresponding to the minimum channel singular value. We also show that, at low outage levels, the outage probability varies inversely with the Ricean K-factor for cases where transmission is only on the most dominant subchannel (i.e. a singlechannel beamforming system). Numerical results are presented to validate the theoretical analysis.


title: Why Linear Programming cannot solve large instances of NP-complete problems in polynomial time

abstract: This article discusses ability of Linear Programming models to be used as solvers of NP-complete problems. Integer Linear Programming is known as NP-complete problem, but non-integer Linear Programming problems can be solved in polynomial time, what places them in P class. During past three years there appeared some articles using LP to solve NP-complete problems. This methods use large number of variables (O(n^9)) solving correctly almost all instances that can be solved in reasonable time. Can they solve infinitively large instances? This article gives answer to this question.


title: Efficient constraint propagation engines

abstract: This paper presents a model and implementation techniques for speeding up constraint propagation. Three fundamental approaches to improving constraint propagation based on propagators as implementations of constraints are explored: keeping track of which propagators are at fixpoint, choosing which propagator to apply next, and how to combine several propagators for the same constraint. We show how idempotence reasoning and events help track fixpoints more accurately. We improve these methods by using them dynamically (taking into account current domains to improve accuracy). We define priority-based approaches to choosing a next propagator and show that dynamic priorities can improve propagation. We illustrate that the use of multiple propagators for the same constraint can be advantageous with priorities, and introduce staged propagators that combine the effects of multiple propagators with priorities for greater efficiency.


title: On the structure of generalized toric codes

abstract: Toric codes are obtained by evaluating rational functions of a nonsingular toric variety at the algebraic torus. One can extend toric codes to the so called generalized toric codes. This extension consists on evaluating elements of an arbitrary polynomial algebra at the algebraic torus instead of a linear combination of monomials whose exponents are rational points of a convex polytope. We study their multicyclic and metric structure, and we use them to express their dual and to estimate their minimum distance.


title: Hedging predictions in machine learning

abstract: Recent advances in machine learning make it possible to design efficient prediction algorithms for data sets with huge numbers of parameters. This paper describes a new technique for "hedging" the predictions output by many such algorithms, including support vector machines, kernel ridge regression, kernel nearest neighbours, and by many other state-of-the-art methods. The hedged predictions for the labels of new objects include quantitative measures of their own accuracy and reliability. These measures are provably valid under the assumption of randomness, traditional in machine learning: the objects and their labels are assumed to be generated independently from the same probability distribution. In particular, it becomes possible to control (up to statistical fluctuations) the number of erroneous predictions by selecting a suitable confidence level. Validity being achieved automatically, the remaining goal of hedged prediction is efficiency: taking full account of the new objects' features and other available information to produce as accurate predictions as possible. This can be done successfully using the powerful machinery of modern machine learning.


title: Asymptotic SER and Outage Probability of MIMO MRC in Correlated Fading

abstract: This letter derives the asymptotic symbol error rate (SER) and outage probability of multiple-input multiple-output (MIMO) maximum ratio combining (MRC) systems. We consider Rayleigh fading channels with both transmit and receive spatial correlation. Our results are based on new asymptotic expressions which we derive for the p.d.f. and c.d.f. of the maximum eigenvalue of positive-definite quadratic forms in complex Gaussian matrices. We prove that spatial correlation does not affect the diversity order, but that it reduces the array gain and hence increases the SER in the high SNR regime.


title: Developing strategies to produce better scientific papers: a Recipe for non-native users of English

abstract: In this paper we introduce the AMADEUS strategy, which has been used to produce scientific writing tools for non-native users of English for 15 years, and emphasize a learn-by-doing approach through which students and novice writers can improve their scientific writing. More specifically, we provide a 9-step recipe for the students to compile writing material according to a procedure that has proven efficient in scientific writing courses.


title: Interactive Problem Solving in Prolog

abstract: This paper presents an environment for solving Prolog problems which has been implemented as a module for the virtual laboratory VILAB. During the problem solving processes the learners get fast adaptive feedback. As a result analysing the learner's actions the system suggests the use of suitable auxiliary predicates which will also be checked for proper implementation. The focus of the environment has been set on robustness and the integration in VILAB.


title: On the Fairness of Rate Allocation in Gaussian Multiple Access Channel and Broadcast Channel

abstract: The capacity region of a channel consists of all achievable rate vectors. Picking a particular point in the capacity region is synonymous with rate allocation. The issue of fairness in rate allocation is addressed in this paper. We review several notions of fairness, including max-min fairness, proportional fairness and Nash bargaining solution. Their efficiencies for general multiuser channels are discussed. We apply these ideas to the Gaussian multiple access channel (MAC) and the Gaussian broadcast channel (BC). We show that in the Gaussian MAC, max-min fairness and proportional fairness coincide. For both Gaussian MAC and BC, we devise efficient algorithms that locate the fair point in the capacity region. Some elementary properties of fair rate allocations are proved.


title: Increasing Data Resilience of Mobile Devices with a Collaborative Backup Service

abstract: Whoever has had his cell phone stolen knows how frustrating it is to be unable to get his contact list back. To avoid data loss when losing or destroying a mobile device like a PDA or a cell phone, data is usually backed-up to a fixed station. However, in the time between the last backup and the failure, important data can have been produced and then lost. To handle this issue, we propose a transparent collaborative backup system. Indeed, by saving data on other mobile devices between two connections to a global infrastructure, we can resist to such scenarios. In this paper, after a general description of such a system, we present a way to replicate data on mobile devices to attain a prerequired resilience for the backup.


title: A New Data Processing Inequality and Its Applications in Distributed Source and Channel Coding

abstract: In the distributed coding of correlated sources, the problem of characterizing the joint probability distribution of a pair of random variables satisfying an n-letter Markov chain arises. The exact solution of this problem is intractable. In this paper, we seek a single-letter necessary condition for this n-letter Markov chain. To this end, we propose a new data processing inequality on a new measure of correlation by means of spectrum analysis. Based on this new data processing inequality, we provide a single-letter necessary condition for the required joint probability distribution. We apply our results to two specific examples involving the distributed coding of correlated sources: multi-terminal rate-distortion region and multiple access channel with correlated sources, and propose new necessary conditions for these two problems.


title: Logic Column 17: A Rendezvous of Logic, Complexity, and Algebra

abstract: This article surveys recent advances in applying algebraic techniques to constraint satisfaction problems.


title: Algorithmic Aspects of a General Modular Decomposition Theory

abstract: A new general decomposition theory inspired from modular graph decomposition is presented. This helps unifying modular decomposition on different structures, including (but not restricted to) graphs. Moreover, even in the case of graphs, the terminology ``module'' not only captures the classical graph modules but also allows to handle 2-connected components, star-cutsets, and other vertex subsets. The main result is that most of the nice algorithmic tools developed for modular decomposition of graphs still apply efficiently on our generalisation of modules. Besides, when an essential axiom is satisfied, almost all the important properties can be retrieved. For this case, an algorithm given by Ehrenfeucht, Gabow, McConnell and Sullivan 1994 is generalised and yields a very efficient solution to the associated decomposition problem.


title: An associative memory for the on-line recognition and prediction of temporal sequences

abstract: This paper presents the design of an associative memory with feedback that is capable of on-line temporal sequence learning. A framework for on-line sequence learning has been proposed, and different sequence learning models have been analysed according to this framework. The network model is an associative memory with a separate store for the sequence context of a symbol. A sparse distributed memory is used to gain scalability. The context store combines the functionality of a neural layer with a shift register. The sensitivity of the machine to the sequence context is controllable, resulting in different characteristic behaviours. The model can store and predict on-line sequences of various types and length. Numerical simulations on the model have been carried out to determine its properties.


title: Relatively inertial delays

abstract: The paper studies the relatively inertial delays that represent one of the most important concepts in the modeling of the asynchronous circuits.


title: Multirobot rendezvous with visibility sensors in nonconvex environments

abstract: This paper presents a coordination algorithm for mobile autonomous robots. Relying upon distributed sensing the robots achieve rendezvous, that is, they move to a common location. Each robot is a point mass moving in a nonconvex environment according to an omnidirectional kinematic model. Each robot is equipped with line-of-sight limited-range sensors, i.e., a robot can measure the relative position of any object (robots or environment boundary) if and only if the object is within a given distance and there are no obstacles in-between. The algorithm is designed using the notions of robust visibility, connectivity-preserving constraint sets, and proximity graphs. Simulations illustrate the theoretical results on the correctness of the proposed algorithm, and its performance in asynchronous setups and with sensor measurement and control errors.


title: Faster Streaming algorithms for graph spanners

abstract: Given an undirected graph $G=(V,E)$ on $n$ vertices, $m$ edges, and an integer $t\ge 1$, a subgraph $(V,E_S)$, $E_S\subseteq E$ is called a $t$-spanner if for any pair of vertices $u,v \in V$, the distance between them in the subgraph is at most $t$ times the actual distance. We present streaming algorithms for computing a $t$-spanner of essentially optimal size-stretch trade offs for any undirected graph. Our first algorithm is for the classical streaming model and works for unweighted graphs only. The algorithm performs a single pass on the stream of edges and requires $O(m)$ time to process the entire stream of edges. This drastically improves the previous best single pass streaming algorithm for computing a $t$-spanner which requires $\theta(mn^{\frac{2}{t}})$ time to process the stream and computes spanner with size slightly larger than the optimal. Our second algorithm is for {\em StreamSort} model introduced by Aggarwal et al. [FOCS 2004], which is the streaming model augmented with a sorting primitive. The {\em StreamSort} model has been shown to be a more powerful and still very realistic model than the streaming model for massive data sets applications. Our algorithm, which works of weighted graphs as well, performs $O(t)$ passes using $O(\log n)$ bits of working memory only. Our both the algorithms require elementary data structures.


title: A Relational Approach to Functional Decomposition of Logic Circuits

abstract: Functional decomposition of logic circuits has profound influence on all quality aspects of the cost-effective implementation of modern digital systems. In this paper, a relational approach to the decomposition of logic circuits is proposed. This approach is parallel to the normalization of relational databases, they are governed by the same concepts of functional dependency (FD) and multi-valued dependency (MVD). It is manifest that the functional decomposition of switching function actually exploits the same idea and serves a similar purpose as database normalization. Partitions play an important role in the decomposition. The interdependency of two partitions can be represented by a bipartite graph. We demonstrate that both FD and MVD can be represented by bipartite graphs with specific topological properties, which are delineated by partitions of minterms. It follows that our algorithms are procedures of constructing those specific bipartite graphs of interest to meet the information-lossless criteria of functional decomposition.


title: A Logical Approach to Efficient Max-SAT solving

abstract: Weighted Max-SAT is the optimization version of SAT and many important problems can be naturally encoded as such. Solving weighted Max-SAT is an important problem from both a theoretical and a practical point of view. In recent years, there has been considerable interest in finding efficient solving techniques. Most of this work focus on the computation of good quality lower bounds to be used within a branch and bound DPLL-like algorithm. Most often, these lower bounds are described in a procedural way. Because of that, it is difficult to realize the {\em logic} that is behind. In this paper we introduce an original framework for Max-SAT that stresses the parallelism with classical SAT. Then, we extend the two basic SAT solving techniques: {\em search} and {\em inference}. We show that many algorithmic {\em tricks} used in state-of-the-art Max-SAT solvers are easily expressable in {\em logic} terms with our framework in a unified manner. Besides, we introduce an original search algorithm that performs a restricted amount of {\em weighted resolution} at each visited node. We empirically compare our algorithm with a variety of solving alternatives on several benchmarks. Our experiments, which constitute to the best of our knowledge the most comprehensive Max-sat evaluation ever reported, show that our algorithm is generally orders of magnitude faster than any competitor.


title: Un mod\`ele g\'en\'erique d'organisation de corpus en ligne: application \`a la FReeBank

abstract: The few available French resources for evaluating linguistic models or algorithms on other linguistic levels than morpho-syntax are either insufficient from quantitative as well as qualitative point of view or not freely accessible. Based on this fact, the FREEBANK project intends to create French corpora constructed using manually revised output from a hybrid Constraint Grammar parser and annotated on several linguistic levels (structure, morpho-syntax, syntax, coreference), with the objective to make them available on-line for research purposes. Therefore, we will focus on using standard annotation schemes, integration of existing resources and maintenance allowing for continuous enrichment of the annotations. Prior to the actual presentation of the prototype that has been implemented, this paper describes a generic model for the organization and deployment of a linguistic resource archive, in compliance with the various works currently conducted within international standardization initiatives (TEI and ISO/TC 37/SC 4).


title: Efficient and Dynamic Group Key Agreement in Ad hoc Networks

abstract: Confidentiality, integrity and authentication are more relevant issues in Ad hoc networks than in wired fixed networks. One way to address these issues is the use of symmetric key cryptography, relying on a secret key shared by all members of the network. But establishing and maintaining such a key (also called the session key) is a non-trivial problem. We show that Group Key Agreement (GKA) protocols are suitable for establishing and maintaining such a session key in these dynamic networks. We take an existing GKA protocol, which is robust to connectivity losses and discuss all the issues for good functioning of this protocol in Ad hoc networks. We give implementation details and network parameters, which significantly reduce the computational burden of using public key cryptography in such networks.


title: A Decomposition Theory for Binary Linear Codes

abstract: The decomposition theory of matroids initiated by Paul Seymour in the 1980's has had an enormous impact on research in matroid theory. This theory, when applied to matrices over the binary field, yields a powerful decomposition theory for binary linear codes. In this paper, we give an overview of this code decomposition theory, and discuss some of its implications in the context of the recently discovered formulation of maximum-likelihood (ML) decoding of a binary linear code over a discrete memoryless channel as a linear programming problem. We translate matroid-theoretic results of Gr\"otschel and Truemper from the combinatorial optimization literature to give examples of non-trivial families of codes for which the ML decoding problem can be solved in time polynomial in the length of the code. One such family is that consisting of codes $C$ for which the codeword polytope is identical to the Koetter-Vontobel fundamental polytope derived from the entire dual code $C^\perp$. However, we also show that such families of codes are not good in a coding-theoretic sense -- either their dimension or their minimum distance must grow sub-linearly with codelength. As a consequence, we have that decoding by linear programming, when applied to good codes, cannot avoid failing occasionally due to the presence of pseudocodewords.


title: Linear Encodings of Bounded LTL Model Checking

abstract: We consider the problem of bounded model checking (BMC) for linear temporal logic (LTL). We present several efficient encodings that have size linear in the bound. Furthermore, we show how the encodings can be extended to LTL with past operators (PLTL). The generalised encoding is still of linear size, but cannot detect minimal length counterexamples. By using the virtual unrolling technique minimal length counterexamples can be captured, however, the size of the encoding is quadratic in the specification. We also extend virtual unrolling to Buchi automata, enabling them to accept minimal length counterexamples. Our BMC encodings can be made incremental in order to benefit from incremental SAT technology. With fairly small modifications the incremental encoding can be further enhanced with a termination check, allowing us to prove properties with BMC. Experiments clearly show that our new encodings improve performance of BMC considerably, particularly in the case of the incremental encoding, and that they are very competitive for finding bugs. An analysis of the liveness-to-safety transformation reveals many similarities to the BMC encodings in this paper. Using the liveness-to-safety translation with BDD-based invariant checking results in an efficient method to find shortest counterexamples that complements the BMC-based approach.


title: Nonextensive Pythagoras' Theorem

abstract: Kullback-Leibler relative-entropy, in cases involving distributions resulting from relative-entropy minimization, has a celebrated property reminiscent of squared Euclidean distance: it satisfies an analogue of the Pythagoras' theorem. And hence, this property is referred to as Pythagoras' theorem of relative-entropy minimization or triangle equality and plays a fundamental role in geometrical approaches of statistical estimation theory like information geometry. Equvalent of Pythagoras' theorem in the generalized nonextensive formalism is established in (Dukkipati at el., Physica A, 361 (2006) 124-138). In this paper we give a detailed account of it.


title: Efficient Threshold Aggregation of Moving Objects

abstract: Calculating aggregation operators of moving point objects, using time as a continuous variable, presents unique problems when querying for congestion in a moving and changing (or dynamic) query space. We present a set of congestion query operators, based on a threshold value, that estimate the following 5 aggregation operations in d-dimensions. 1) We call the count of point objects that intersect the dynamic query space during the query time interval, the CountRange. 2) We call the Maximum (or Minimum) congestion in the dynamic query space at any time during the query time interval, the MaxCount (or MinCount). 3) We call the sum of time that the dynamic query space is congested, the ThresholdSum. 4) We call the number of times that the dynamic query space is congested, the ThresholdCount. And 5) we call the average length of time of all the time intervals when the dynamic query space is congested, the ThresholdAverage. These operators rely on a novel approach to transforming the problem of selection based on position to a problem of selection based on a threshold. These operators can be used to predict concentrations of migrating birds that may carry disease such as Bird Flu and hence the information may be used to predict high risk areas. On a smaller scale, those operators are also applicable to maintaining safety in airplane operations. We present the theory of our estimation operators and provide algorithms for exact operators. The implementations of those operators, and experiments, which include data from more than 7500 queries, indicate that our estimation operators produce fast, efficient results with error under 5%.


title: V-like formations in flocks of artificial birds

abstract: We consider flocks of artificial birds and study the emergence of V-like formations during flight. We introduce a small set of fully distributed positioning rules to guide the birds' movements and demonstrate, by means of simulations, that they tend to lead to stabilization into several of the well-known V-like formations that have been observed in nature. We also provide quantitative indicators that we believe are closely related to achieving V-like formations, and study their behavior over a large set of independent simulations.


title: Cryptanalyse de Achterbahn-128/80

abstract: This paper presents two attacks against Achterbahn-128/80, the last version of one of the stream cipher proposals in the eSTREAM project. The attack against the 80-bit variant, Achterbahn-80, has complexity 2^{56.32}. The attack against Achterbahn-128 requires 2^{75.4} operations and 2^{61} keystream bits. These attacks are based on an improvement of the attack due to Hell and Johansson against Achterbahn version 2 and also on an algorithm that makes profit of the short lengths of the constituent registers. ***** Ce papier pr\'{e}sente deux attaques sur Achterbahn-128/80, la derni\`{e}re version d'un des algorithmes propos\'{e}s dans le cadre de eSTREAM. L'attaque sur la version de 80 bits, Achterbahn-80, est en 2^{56.32}. L'attaque sur Achterbahn-128 a besoin de 2^{75.4} calculs et 2^{61} bits de suite chiffrante. Ces attaques sont bas\'{e}es sur une am\'{e}lioration de l'attaque propos\'{e}e par Hell et Johansson sur la version 2 d'Achterbahn et aussi sur un algorithme qui tire profit des petites longueurs des registres.


title: Strategies for Replica Placement in Tree Networks

abstract: In this paper, we discuss and compare several policies to place replicas in tree networks, subject to server capacity and QoS constraints. The client requests are known beforehand, while the number and location of the servers are to be determined. The standard approach in the literature is to enforce that all requests of a client be served by the closest server in the tree. We introduce and study two new policies. In the first policy, all requests from a given client are still processed by the same server, but this server can be located anywhere in the path from the client to the root. In the second policy, the requests of a given client can be processed by multiple servers. One major contribution of this paper is to assess the impact of these new policies on the total replication cost. Another important goal is to assess the impact of server heterogeneity, both from a theoretical and a practical perspective. In this paper, we establish several new complexity results, and provide several efficient polynomial heuristics for NP-complete instances of the problem. These heuristics are compared to an absolute lower bound provided by the formulation of the problem in terms of the solution of an integer linear program.


title: The Role of Quasi-identifiers in k-Anonymity Revisited

abstract: The concept of k-anonymity, used in the recent literature to formally evaluate the privacy preservation of published tables, was introduced based on the notion of quasi-identifiers (or QI for short). The process of obtaining k-anonymity for a given private table is first to recognize the QIs in the table, and then to anonymize the QI values, the latter being called k-anonymization. While k-anonymization is usually rigorously validated by the authors, the definition of QI remains mostly informal, and different authors seem to have different interpretations of the concept of QI. The purpose of this paper is to provide a formal underpinning of QI and examine the correctness and incorrectness of various interpretations of QI in our formal framework. We observe that in cases where the concept has been used correctly, its application has been conservative; this note provides a formal understanding of the conservative nature in such cases.


title: Intra-site Level Cultural Heritage Documentation: Combination of Survey, Modeling and Imagery Data in a Web Information System

abstract: Cultural heritage documentation induces the use of computerized techniques to manage and preserve the information produced. Geographical information systems have proved their potentialities in this scope, but they are not always adapted for the management of features at the scale of a particular archaeological site. Moreover, computer applications in archaeology are often technology driven and software constrained. Thus, we propose a tool that tries to avoid these difficulties. We are developing an information system that works over the Internet and that is joined with a web site. Aims are to assist the work of archaeological sites managers and to be a documentation tool about these sites, dedicated to everyone. We devote therefore our system both to the professionals who are in charge of the site, and to the general public who visits it or who wants to have information on it. The system permits to do exploratory analyses of the data, especially at spatial and temporal levels. We propose to record metadata about the archaeological features in XML and to access these features through interactive 2D and 3D representations, and through queries systems (keywords and images). The 2D images, photos, or vectors are generated in SVG, while 3D models are generated in X3D. Archaeological features are also automatically integrated in a MySQL database. The web site is an exchange platform with the information system and is written in PHP. Our first application case is the medieval castle of Vianden, Luxembourg.


title: On Conditional Branches in Optimal Decision Trees

abstract: The decision tree is one of the most fundamental programming abstractions. A commonly used type of decision tree is the alphabetic binary tree, which uses (without loss of generality) ``less than'' versus ''greater than or equal to'' tests in order to determine one of $n$ outcome events. The process of finding an optimal alphabetic binary tree for a known probability distribution on outcome events usually has the underlying assumption that the cost (time) per decision is uniform and thus independent of the outcome of the decision. This assumption, however, is incorrect in the case of software to be optimized for a given microprocessor, e.g., in compiling switch statements or in fine-tuning program bottlenecks. The operation of the microprocessor generally means that the cost for the more likely decision outcome can or will be less -- often far less -- than the less likely decision outcome. Here we formulate a variety of $O(n^3)$-time $O(n^2)$-space dynamic programming algorithms to solve such optimal binary decision tree problems, optimizing for the behavior of processors with predictive branch capabilities, both static and dynamic. In the static case, we use existing results to arrive at entropy-based performance bounds. Solutions to this formulation are often faster in practice than ``optimal'' decision trees as formulated in the literature, and, for small problems, are easily worth the extra complexity in finding the better solution. This can be applied in fast implementation of decoding Huffman codes.


title: Nonsymmetric entropy I: basic concepts and results

abstract: A new concept named nonsymmetric entropy which generalizes the concepts of Boltzman's entropy and shannon's entropy, was introduced. Maximal nonsymmetric entropy principle was proven. Some important distribution laws were derived naturally from maximal nonsymmetric entropy principle.


title: Substitutions for tilings $\{p,q\}$

abstract: In this paper we consider tiling $\{p, q \}$ of the Euclidean space and of the hyperbolic space, and its dual graph $\Gamma_{q, p}$ from a combinatorial point of view. A substitution $\sigma_{q, p}$ on an appropriate finite alphabet is constructed. The homogeneity of graph $\Gamma_{q, p}$ and its generation function are the basic tools for the construction. The tree associated with substitution $\sigma_{q, p}$ is a spanning tree of graph $\Gamma_{q, p}$. Let $u_n$ be the number of tiles of tiling $\{p, q \}$ of generation $n$. The characteristic polynomial of the transition matrix of substitution $\sigma_{q, p}$ is a characteristic polynomial of a linear recurrence. The sequence $(u_n)_{n \geq 0}$ is a solution of this recurrence. The growth of sequence $(u_n)_{n \geq 0}$ is given by the dominant root of the characteristic polynomial.


title: The Formal System lambda-delta

abstract: The formal system lambda-delta is a typed lambda calculus that pursues the unification of terms, types, environments and contexts as the main goal. lambda-delta takes some features from the Automath-related lambda calculi and some from the pure type systems, but differs from both in that it does not include the Pi construction while it provides for an abbreviation mechanism at the level of terms. lambda-delta enjoys some important desirable properties such as the confluence of reduction, the correctness of types, the uniqueness of types up to conversion, the subject reduction of the type assignment, the strong normalization of the typed terms and, as a corollary, the decidability of type inference problem.


title: Groebner Bases Applied to Systems of Linear Difference Equations

abstract: In this paper we consider systems of partial (multidimensional) linear difference equations. Specifically, such systems arise in scientific computing under discretization of linear partial differential equations and in computational high energy physics as recurrence relations for multiloop Feynman integrals. The most universal algorithmic tool for investigation of linear difference systems is based on their transformation into an equivalent Groebner basis form. We present an algorithm for this transformation implemented in Maple. The algorithm and its implementation can be applied to automatic generation of difference schemes for linear partial differential equations and to reduction of Feynman integrals. Some illustrative examples are given.


title: CSCR:Computer Supported Collaborative Research

abstract: It is suggested that a new area of CSCR (Computer Supported Collaborative Research) is distinguished from CSCW and CSCL and that the demarcation between the three areas could do with greater clarification and prescription.


title: On the Convexity of log det (I + K X^{-1})

abstract: A simple proof is given for the convexity of log det (I+K X^{-1}) in the positive definite matrix variable X with a given positive semidefinite K.


title: Protection of the information in a complex CAD system of renovation of industrial firms

abstract: The threats to security of the information originating owing to involuntary operations of the users of a CAD, and methods of its protection implemented in a complex CAD system of renovation of firms are considered: rollback, autosave, automatic backup copying and electronic subscript. The specificity of a complex CAD is reflected in necessity of rollback and autosave both of the draw and the parametric representations of its parts, which are the information models of the problem-oriented extensions of the CAD


title: The evolution of the parametric models of drawings (modules) in the enterprises reconstruction CAD system

abstract: Progressing methods of drawings creating automation is discussed on the basis of so-called modules containing parametric representation of a part of the drawing and the geometrical elements. The stages of evolution of modular technology of automation of engineering are describing alternatives of applying of moduluss for simple association of elements of the drawing without parametric representation with an opportunity of its commenting, for graphic symbols creating in the schemas of automation and drawings of pipelines, for storage of the specific properties of elements, for development of the specialized parts of the project: the axonometric schemas, profiles of outboard pipe networks etc.


title: Analytic Tableaux Calculi for KLM Logics of Nonmonotonic Reasoning

abstract: We present tableau calculi for some logics of nonmonotonic reasoning, as defined by Kraus, Lehmann and Magidor. We give a tableau proof procedure for all KLM logics, namely preferential, loop-cumulative, cumulative and rational logics. Our calculi are obtained by introducing suitable modalities to interpret conditional assertions. We provide a decision procedure for the logics considered, and we study their complexity.


title: The Reaction RuleML Classification of the Event / Action / State Processing and Reasoning Space

abstract: Reaction RuleML is a general, practical, compact and user-friendly XML-serialized language for the family of reaction rules. In this white paper we give a review of the history of event / action /state processing and reaction rule approaches and systems in different domains, define basic concepts and give a classification of the event, action, state processing and reasoning space as well as a discussion of relevant / related work


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

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


title: On numerical stability of recursive present value computation method

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


title: HowTo Authenticate and Encrypt

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


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

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


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

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


title: Capacity of a Class of Deterministic Relay Channels

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


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

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


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

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


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

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


title: Formalising Sylow's theorems in Coq

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


title: Advances in Self Organising Maps

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


title: Is the cyclic prefix necessary?

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


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

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


title: Multivariate Integral Perturbation Techniques - I (Theory)

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


title: A framework for compositional verification of security protocols

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


title: Characterizing Optimal Adword Auctions

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


title: Distributed Link Scheduling with Constant Overhead

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


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

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


title: A modular eballot system - V0.6

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


title: Implementing the modular eballot system V0.6

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


title: Wikipedia: organisation from a bottom-up approach

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


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

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


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

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


title: Capabilities Engineering: Constructing Change-Tolerant Systems

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


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

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


title: Prefix Codes for Power Laws with Countable Support

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


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

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


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

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


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

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


title: Evolutionary Optimization in an Algorithmic Setting

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


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

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


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

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


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

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


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

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


title: The Computational Complexity of the Traveling Salesman Problem

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


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

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


title: Large Scale In Silico Screening on Grid Infrastructures

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


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

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


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

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


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

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


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

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


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

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


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

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


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

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


title: Design approaches in technology enhanced learning

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


title: Effectiveness of Garbage Collection in MIT/GNU Scheme

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


title: Reducing Order Enforcement Cost in Complex Query Plans

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


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

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


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

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