title: Conditionally Cycle-Free Generalized Tanner Graphs: Theory and Application to High-Rate Serially Concatenated Codes

abstract: Generalized Tanner graphs have been implicitly studied by a number of authors under the rubric of generalized parity-check matrices. This work considers the conditioning of binary hidden variables in such models in order to break all cycles and thus derive optimal soft-in soft-out (SISO) decoding algorithms. Conditionally cycle-free generalized Tanner graphs are shown to imply optimal SISO decoding algorithms for the first order Reed-Muller codes and their duals - the extended Hamming codes - which are substantially less complex than conventional bit-level trellis decoding. The study of low-complexity optimal SISO decoding algorithms for the family of extended Hamming codes is practically motivated. Specifically, it is shown that exended Hamming codes offer an attractive alternative to high-rate convolutional codes in terms of both performance and complexity for use in very high-rate, very low-floor, serially concatenated coding schemes.


title: Analysis of an Efficient Distributed Algorithm for Mutual Exclusion (Average-Case Analysis of Path Reversal)

abstract: The algorithm analysed by Na\"{i}mi, Trehe and Arnold was the very first distributed algorithm to solve the mutual exclusion problem in complete networks by using a dynamic logical tree structure as its basic distributed data structure, viz. a path reversal transformation in rooted n-node trees; besides, it was also the first one to achieve a logarithmic average-case message complexity. The present paper proposes a direct and general approach to compute the moments of the cost of path reversal. It basically uses one-one correspondences between combinatorial structures and the associated probability generating functions: the expected cost of path reversal is thus proved to be exactly $H_{n-1}$. Moreover, time and message complexity of the algorithm as well as randomized bounds on its worst-case message complexity in arbitrary networks are also given. The average-case analysis of path reversal and the analysis of this distributed algorithm for mutual exclusion are thus fully completed in the paper. The general techniques used should also prove available and fruitful when adapted to the most efficient recent tree-based distributed algorithms for mutual exclusion which require powerful tools, particularly for average-case analyses.


title: On the space complexity of one-pass compression

abstract: We study how much memory one-pass compression algorithms need to compete with the best multi-pass algorithms. We call a one-pass algorithm an (f (n, \ell))-footprint compressor if, given $n$, $\ell$ and an $n$-ary string $S$, it stores $S$ in ((\rule{0ex}{2ex} O (H_\ell (S)) + o (\log n)) |S| + O (n^{\ell + 1} \log n)) bits -- where (H_\ell (S)) is the $\ell$th-order empirical entropy of $S$ -- while using at most (f (n, \ell)) bits of memory. We prove that, for any (\epsilon > 0) and some (f (n, \ell) \in O (n^{\ell + \epsilon} \log n)), there is an (f (n, \ell))-footprint compressor; on the other hand, there is no (f (n, \ell))-footprint compressor for (f (n, \ell) \in o (n^\ell \log n)).


title: Model Theory of Ultrafinitism I: Fuzzy Initial Segments of Arithmetics

abstract: This article is the first of an intended series of works on the model theory of Ultrafinitism. It is roughly divided into two parts. The first one addresses some of the issues related to ultrafinitistic programs, as well as some of the core ideas proposed thus far. The second part of the paper presents a model of ultrafinitistic arithmetics based on the notion of fuzzy initial segments of the standard natural numbers series. We also introduce a proof theory and a semantics for ultrafinitism through which feasibly consistent theories can be treated on the same footing as their classically consistent counterparts. We conclude with a brief sketch of a foundational program, that aims at reproducing the transfinite within the finite realm.


title: Fourier meets M\"{o}bius: fast subset convolution

abstract: We present a fast algorithm for the subset convolution problem: given functions f and g defined on the lattice of subsets of an n-element set N, compute their subset convolution f*g, defined for all S\subseteq N by (f * g)(S) = \sum_{T \subseteq S}f(T) g(S\setminus T), where addition and multiplication is carried out in an arbitrary ring. Via M\"{o}bius transform and inversion, our algorithm evaluates the subset convolution in O(n^2 2^n) additions and multiplications, substantially improving upon the straightforward O(3^n) algorithm. Specifically, if the input functions have an integer range {-M,-M+1,...,M}, their subset convolution over the ordinary sum-product ring can be computed in O^*(2^n log M) time; the notation O^* suppresses polylogarithmic factors. Furthermore, using a standard embedding technique we can compute the subset convolution over the max-sum or min-sum semiring in O^*(2^n M) time. To demonstrate the applicability of fast subset convolution, we present the first O^*(2^k n^2 + n m) algorithm for the minimum Steiner tree problem in graphs with n vertices, k terminals, and m edges with bounded integer weights, improving upon the O^*(3^k n + 2^k n^2 + n m) time bound of the classical Dreyfus-Wagner algorithm. We also discuss extensions to recent O^*(2^n)-time algorithms for covering and partitioning problems (Bj\"{o}rklund and Husfeldt, FOCS 2006; Koivisto, FOCS 2006).


title: Extending the Trusted Path in Client-Server Interaction

abstract: We present a method to secure the complete path between a server and the local human user at a network node. This is useful for scenarios like internet banking, electronic signatures, or online voting. Protection of input authenticity and output integrity and authenticity is accomplished by a combination of traditional and novel technologies, e.g., SSL, ActiveX, and DirectX. Our approach does not require administrative privileges to deploy and is hence suitable for consumer applications. Results are based on the implementation of a proof-of-concept application for the Windows platform.


title: Barriers and local minima in energy landscapes of stochastic local search

abstract: A local search algorithm operating on an instance of a Boolean constraint satisfaction problem (in particular, k-SAT) can be viewed as a stochastic process traversing successive adjacent states in an ``energy landscape'' defined by the problem instance on the n-dimensional Boolean hypercube. We investigate analytically the worst-case topography of such landscapes in the context of satisfiable k-SAT via a random ensemble of satisfiable ``k-regular'' linear equations modulo 2. We show that for each fixed k=3,4,..., the typical k-SAT energy landscape induced by an instance drawn from the ensemble has a set of 2^{\Omega(n)} local energy minima, each separated by an unconditional \Omega(n) energy barrier from each of the O(1) ground states, that is, solution states with zero energy. The main technical aspect of the analysis is that a random k-regular 0/1 matrix constitutes a strong boundary expander with almost full GF(2)-linear rank, a property which also enables us to prove a 2^{\Omega(n)} lower bound for the expected number of steps required by the focused random walk heuristic to solve typical instances drawn from the ensemble. These results paint a grim picture of the worst-case topography of k-SAT for local search, and constitute apparently the first rigorous analysis of the growth of energy barriers in a random ensemble of k-SAT landscapes as the number of variables n is increased.


title: Learning and discrimination through STDP in a top-down modulated associative memory

abstract: This article underlines the learning and discrimination capabilities of a model of associative memory based on artificial networks of spiking neurons. Inspired from neuropsychology and neurobiology, the model implements top-down modulations, as in neocortical layer V pyramidal neurons, with a learning rule based on synaptic plasticity (STDP), for performing a multimodal association learning task. A temporal correlation method of analysis proves the ability of the model to associate specific activity patterns to different samples of stimulation. Even in the absence of initial learning and with continuously varying weights, the activity patterns become stable enough for discrimination.


title: Clustering and Sharing Incentives in BitTorrent Systems

abstract: Peer-to-peer protocols play an increasingly instrumental role in Internet content distribution. Consequently, it is important to gain a full understanding of how these protocols behave in practice and how their parameters impact overall performance. We present the first experimental investigation of the peer selection strategy of the popular BitTorrent protocol in an instrumented private torrent. By observing the decisions of more than 40 nodes, we validate three BitTorrent properties that, though widely believed to hold, have not been demonstrated experimentally. These include the clustering of similar-bandwidth peers, the effectiveness of BitTorrent's sharing incentives, and the peers' high average upload utilization. In addition, our results show that BitTorrent's new choking algorithm in seed state provides uniform service to all peers, and that an underprovisioned initial seed leads to the absence of peer clustering and less effective sharing incentives. Based on our observations, we provide guidelines for seed provisioning by content providers, and discuss a tracker protocol extension that addresses an identified limitation of the protocol.


title: Mixing and non-mixing local minima of the entropy contrast for blind source separation

abstract: In this paper, both non-mixing and mixing local minima of the entropy are analyzed from the viewpoint of blind source separation (BSS); they correspond respectively to acceptable and spurious solutions of the BSS problem. The contribution of this work is twofold. First, a Taylor development is used to show that the \textit{exact} output entropy cost function has a non-mixing minimum when this output is proportional to \textit{any} of the non-Gaussian sources, and not only when the output is proportional to the lowest entropic source. Second, in order to prove that mixing entropy minima exist when the source densities are strongly multimodal, an entropy approximator is proposed. The latter has the major advantage that an error bound can be provided. Even if this approximator (and the associated bound) is used here in the BSS context, it can be applied for estimating the entropy of any random variable with multimodal density.


title: Rectangular Layouts and Contact Graphs

abstract: Contact graphs of isothetic rectangles unify many concepts from applications including VLSI and architectural design, computational geometry, and GIS. Minimizing the area of their corresponding {\em rectangular layouts} is a key problem. We study the area-optimization problem and show that it is NP-hard to find a minimum-area rectangular layout of a given contact graph. We present O(n)-time algorithms that construct $O(n^2)$-area rectangular layouts for general contact graphs and $O(n\log n)$-area rectangular layouts for trees. (For trees, this is an $O(\log n)$-approximation algorithm.) We also present an infinite family of graphs (rsp., trees) that require $\Omega(n^2)$ (rsp., $\Omega(n\log n)$) area. We derive these results by presenting a new characterization of graphs that admit rectangular layouts using the related concept of {\em rectangular duals}. A corollary to our results relates the class of graphs that admit rectangular layouts to {\em rectangle of influence drawings}.


title: On the Complexity of Processing Massive, Unordered, Distributed Data

abstract: An existing approach for dealing with massive data sets is to stream over the input in few passes and perform computations with sublinear resources. This method does not work for truly massive data where even making a single pass over the data with a processor is prohibitive. Successful log processing systems in practice such as Google's MapReduce and Apache's Hadoop use multiple machines. They efficiently perform a certain class of highly distributable computations defined by local computations that can be applied in any order to the input. Motivated by the success of these systems, we introduce a simple algorithmic model for massive, unordered, distributed (mud) computation. We initiate the study of understanding its computational complexity. Our main result is a positive one: any unordered function that can be computed by a streaming algorithm can also be computed with a mud algorithm, with comparable space and communication complexity. We extend this result to some useful classes of approximate and randomized streaming algorithms. We also give negative results, using communication complexity arguments to prove that extensions to private randomness, promise problems and indeterminate functions are impossible. We believe that the line of research we introduce in this paper has the potential for tremendous impact. The distributed systems that motivate our work successfully process data at an unprecedented scale, distributed over hundreds or even thousands of machines, and perform hundreds of such analyses each day. The mud model (and its generalizations) inspire a set of complexity-theoretic questions that lie at their heart.


title: An approach to RAID-6 based on cyclic groups of a prime order

abstract: As the size of data storing arrays of disks grows, it becomes vital to protect data against double disk failures. A popular method of protection is via the Reed-Solomon (RS) code with two parity words. In the present paper we construct alternative examples of linear block codes protecting against two erasures. Our construction is based on an abstract notion of cone. Concrete cones are constructed via matrix representations of cyclic groups of prime order. In particular, this construction produces EVENODD code. Interesting conditions on the prime number arise in our analysis of these codes. At the end, we analyse an assembly implementation of the corresponding system on a general purpose processor and compare its write and recovery speed with the standard DP-RAID system.


title: The Implications of Network-Centric Software Systems on Software Architecture: A Critical Evaluation

abstract: The purpose of this paper is to evaluate the impact of emerging network-centric software systems on the field of software architecture. We first develop an insight concerning the term "network-centric" by presenting its origin and its implications within the context of software architecture. On the basis of this insight, we present our definition of a network-centric framework and its distinguishing characteristics. We then enumerate the challenges that face the field of software architecture as software development shifts from a platform-centric to a network-centric model. In order to face these challenges, we propose a formal approach embodied in a new architectural style that supports overcoming these challenges at the architectural level. Finally, we conclude by presenting an illustrative example to demonstrate the usefulness of the concepts of network centricity, summarizing our contributions, and linking our approach to future work that needs to be done in this area.


title: Distributed Control of Microscopic Robots in Biomedical Applications

abstract: Current developments in molecular electronics, motors and chemical sensors could enable constructing large numbers of devices able to sense, compute and act in micron-scale environments. Such microscopic machines, of sizes comparable to bacteria, could simultaneously monitor entire populations of cells individually in vivo. This paper reviews plausible capabilities for microscopic robots and the physical constraints due to operation in fluids at low Reynolds number, diffusion-limited sensing and thermal noise from Brownian motion. Simple distributed controls are then presented in the context of prototypical biomedical tasks, which require control decisions on millisecond time scales. The resulting behaviors illustrate trade-offs among speed, accuracy and resource use. A specific example is monitoring for patterns of chemicals in a flowing fluid released at chemically distinctive sites. Information collected from a large number of such devices allows estimating properties of cell-sized chemical sources in a macroscopic volume. The microscopic devices moving with the fluid flow in small blood vessels can detect chemicals released by tissues in response to localized injury or infection. We find the devices can readily discriminate a single cell-sized chemical source from the background chemical concentration, providing high-resolution sensing in both time and space. By contrast, such a source would be difficult to distinguish from background when diluted throughout the blood volume as obtained with a blood sample.


title: Channel Coding: The Road to Channel Capacity

abstract: Starting from Shannon's celebrated 1948 channel coding theorem, we trace the evolution of channel coding from Hamming codes to capacity-approaching codes. We focus on the contributions that have led to the most significant improvements in performance vs. complexity for practical applications, particularly on the additive white Gaussian noise (AWGN) channel. We discuss algebraic block codes, and why they did not prove to be the way to get to the Shannon limit. We trace the antecedents of today's capacity-approaching codes: convolutional codes, concatenated codes, and other probabilistic coding schemes. Finally, we sketch some of the practical applications of these codes.


title: An Anthological Review of Research Utilizing MontyLingua, a Python-Based End-to-End Text Processor

abstract: MontyLingua, an integral part of ConceptNet which is currently the largest commonsense knowledge base, is an English text processor developed using Python programming language in MIT Media Lab. The main feature of MontyLingua is the coverage for all aspects of English text processing from raw input text to semantic meanings and summary generation, yet each component in MontyLingua is loosely-coupled to each other at the architectural and code level, which enabled individual components to be used independently or substituted. However, there has been no review exploring the role of MontyLingua in recent research work utilizing it. This paper aims to review the use of and roles played by MontyLingua and its components in research work published in 19 articles between October 2004 and August 2006. We had observed a diversified use of MontyLingua in many different areas, both generic and domain-specific. Although the use of text summarizing component had not been observe, we are optimistic that it will have a crucial role in managing the current trend of information overload in future research.


title: Very Sparse Stable Random Projections, Estimators and Tail Bounds for Stable Random Projections

abstract: This paper will focus on three different aspects in improving the current practice of stable random projections. Firstly, we propose {\em very sparse stable random projections} to significantly reduce the processing and storage cost, by replacing the $\alpha$-stable distribution with a mixture of a symmetric $\alpha$-Pareto distribution (with probability $\beta$, $0<\beta\leq1$) and a point mass at the origin (with a probability $1-\beta$). This leads to a significant $\frac{1}{\beta}$-fold speedup for small $\beta$. Secondly, we provide an improved estimator for recovering the original $l_\alpha$ norms from the projected data. The standard estimator is based on the (absolute) sample median, while we suggest using the geometric mean. The geometric mean estimator we propose is strictly unbiased and is easier to study. Moreover, the geometric mean estimator is more accurate, especially non-asymptotically. Thirdly, we provide an adequate answer to the basic question of how many projections (samples) are needed for achieving some pre-specified level of accuracy. \cite{Proc:Indyk_FOCS00,Article:Indyk_TKDE03} did not provide a criterion that can be used in practice. The geometric mean estimator we propose allows us to derive sharp tail bounds which can be expressed in exponential forms with constants explicitly given.


title: A higher-order active contour model of a `gas of circles' and its application to tree crown extraction

abstract: Many image processing problems involve identifying the region in the image domain occupied by a given entity in the scene. Automatic solution of these problems requires models that incorporate significant prior knowledge about the shape of the region. Many methods for including such knowledge run into difficulties when the topology of the region is unknown a priori, for example when the entity is composed of an unknown number of similar objects. Higher-order active contours (HOACs) represent one method for the modelling of non-trivial prior knowledge about shape without necessarily constraining region topology, via the inclusion of non-local interactions between region boundary points in the energy defining the model. The case of an unknown number of circular objects arises in a number of domains, e.g. medical, biological, nanotechnological, and remote sensing imagery. Regions composed of an a priori unknown number of circles may be referred to as a `gas of circles'. In this report, we present a HOAC model of a `gas of circles'. In order to guarantee stable circles, we conduct a stability analysis via a functional Taylor expansion of the HOAC energy around a circular shape. This analysis fixes one of the model parameters in terms of the others and constrains the rest. In conjunction with a suitable likelihood energy, we apply the model to the extraction of tree crowns from aerial imagery, and show that the new model outperforms other techniques.


title: Discovering Network Topology in the Presence of Byzantine Faults

abstract: We study the problem of Byzantine-robust topology discovery in an arbitrary asynchronous network. We formally state the weak and strong versions of the problem. The weak version requires that either each node discovers the topology of the network or at least one node detects the presence of a faulty node. The strong version requires that each node discovers the topology regardless of faults. We focus on non-cryptographic solutions to these problems. We explore their bounds. We prove that the weak topology discovery problem is solvable only if the connectivity of the network exceeds the number of faults in the system. Similarly, we show that the strong version of the problem is solvable only if the network connectivity is more than twice the number of faults. We present solutions to both versions of the problem. The presented algorithms match the established graph connectivity bounds. The algorithms do not require the individual nodes to know either the diameter or the size of the network. The message complexity of both programs is low polynomial with respect to the network size. We describe how our solutions can be extended to add the property of termination, handle topology changes and perform neighborhood discovery.


title: 2FACE: Bi-Directional Face Traversal for Efficient Geometric Routing

abstract: We propose bi-directional face traversal algorithm $2FACE$ to shorten the path the message takes to reach the destination in geometric routing. Our algorithm combines the practicality of the best single-direction traversal algorithms with the worst case message complexity of $O(|E|)$, where $E$ is the number of network edges. We apply $2FACE$ to a variety of geometric routing algorithms. Our simulation results indicate that bi-directional face traversal decreases the latency of message delivery two to three times compared to single direction face traversal. The thus selected path approaches the shortest possible route. This gain in speed comes with a similar message overhead increase. We describe an algorithm which compensates for this message overhead by recording the preferable face traversal direction. Thus, if a source has several messages to send to the destination, the subsequent messages follow the shortest route. Our simulation results show that with most geometric routing algorithms the message overhead of finding the short route by bi-directional face traversal is compensated within two to four repeat messages.


title: A Neutrosophic Description Logic

abstract: Description Logics (DLs) are appropriate, widely used, logics for managing structured knowledge. They allow reasoning about individuals and concepts, i.e. set of individuals with common properties. Typically, DLs are limited to dealing with crisp, well defined concepts. That is, concepts for which the problem whether an individual is an instance of it is yes/no question. More often than not, the concepts encountered in the real world do not have a precisely defined criteria of membership: we may say that an individual is an instance of a concept only to a certain degree, depending on the individual's properties. The DLs that deal with such fuzzy concepts are called fuzzy DLs. In order to deal with fuzzy, incomplete, indeterminate and inconsistent concepts, we need to extend the fuzzy DLs, combining the neutrosophic logic with a classical DL. In particular, concepts become neutrosophic (here neutrosophic means fuzzy, incomplete, indeterminate, and inconsistent), thus reasoning about neutrosophic concepts is supported. We'll define its syntax, its semantics, and describe its properties.


title: Expressiveness of Metric modalities for continuous time

abstract: We prove a conjecture by A. Pnueli and strengthen it showing a sequence of "counting modalities" none of which is expressible in the temporal logic generated by the previous modalities, over the real line, or over the positive reals. Moreover, there is no finite temporal logic that can express all of them over the real line, so that no finite metric temporal logic is expressively complete.


title: Wireless Information-Theoretic Security - Part I: Theoretical Aspects

abstract: In this two-part paper, we consider the transmission of confidential data over wireless wiretap channels. The first part presents an information-theoretic problem formulation in which two legitimate partners communicate over a quasi-static fading channel and an eavesdropper observes their transmissions through another independent quasi-static fading channel. We define the secrecy capacity in terms of outage probability and provide a complete characterization of the maximum transmission rate at which the eavesdropper is unable to decode any information. In sharp contrast with known results for Gaussian wiretap channels (without feedback), our contribution shows that in the presence of fading information-theoretic security is achievable even when the eavesdropper has a better average signal-to-noise ratio (SNR) than the legitimate receiver - fading thus turns out to be a friend and not a foe. The issue of imperfect channel state information is also addressed. Practical schemes for wireless information-theoretic security are presented in Part II, which in some cases comes close to the secrecy capacity limits given in this paper.


title: Wireless Information-Theoretic Security - Part II: Practical Implementation

abstract: In Part I of this two-part paper on confidential communication over wireless channels, we studied the fundamental security limits of quasi-static fading channels from the point of view of outage secrecy capacity with perfect and imperfect channel state information. In Part II, we develop a practical secret key agreement protocol for Gaussian and quasi-static fading wiretap channels. The protocol uses a four-step procedure to secure communications: establish common randomness via an opportunistic transmission, perform message reconciliation, establish a common key via privacy amplification, and use of the key. We introduce a new reconciliation procedure that uses multilevel coding and optimized low density parity check codes which in some cases comes close to achieving the secrecy capacity limits established in Part I. Finally, we develop new metrics for assessing average secure key generation rates and show that our protocol is effective in secure key renewal.


title: Knowledge Representation Concepts for Automated SLA Management

abstract: Outsourcing of complex IT infrastructure to IT service providers has increased substantially during the past years. IT service providers must be able to fulfil their service-quality commitments based upon predefined Service Level Agreements (SLAs) with the service customer. They need to manage, execute and maintain thousands of SLAs for different customers and different types of services, which needs new levels of flexibility and automation not available with the current technology. The complexity of contractual logic in SLAs requires new forms of knowledge representation to automatically draw inferences and execute contractual agreements. A logic-based approach provides several advantages including automated rule chaining allowing for compact knowledge representation as well as flexibility to adapt to rapidly changing business requirements. We suggest adequate logical formalisms for representation and enforcement of SLA rules and describe a proof-of-concept implementation. The article describes selected formalisms of the ContractLog KR and their adequacy for automated SLA management and presents results of experiments to demonstrate flexibility and scalability of the approach.


title: Functional Bregman Divergence and Bayesian Estimation of Distributions

abstract: A class of distortions termed functional Bregman divergences is defined, which includes squared error and relative entropy. A functional Bregman divergence acts on functions or distributions, and generalizes the standard Bregman divergence for vectors and a previous pointwise Bregman divergence that was defined for functions. A recently published result showed that the mean minimizes the expected Bregman divergence. The new functional definition enables the extension of this result to the continuous case to show that the mean minimizes the expected functional Bregman divergence over a set of functions or distributions. It is shown how this theorem applies to the Bayesian estimation of distributions. Estimation of the uniform distribution from independent and identically drawn samples is used as a case study.


title: Low-rank matrix factorization with attributes

abstract: We develop a new collaborative filtering (CF) method that combines both previously known users' preferences, i.e. standard CF, as well as product/user attributes, i.e. classical function approximation, to predict a given user's interest in a particular product. Our method is a generalized low rank matrix completion problem, where we learn a function whose inputs are pairs of vectors -- the standard low rank matrix completion problem being a special case where the inputs to the function are the row and column indices of the matrix. We solve this generalized matrix completion problem using tensor product kernels for which we also formally generalize standard kernel properties. Benchmark experiments on movie ratings show the advantages of our generalized matrix completion method over the standard matrix completion one with no information about movies or people, as well as over standard multi-task or single task learning methods.


title: Relay Channels with Confidential Messages

abstract: We consider a relay channel where a relay helps the transmission of messages from one sender to one receiver. The relay is considered not only as a sender that helps the message transmission but as a wire-tapper who can obtain some knowledge about the transmitted messages. In this paper we study the coding problem of the relay channel under the situation that some of transmitted messages are confidential to the relay. A security of such confidential messages is measured by the conditional entropy. The rate region is defined by the set of transmission rates for which messages are reliably transmitted and the security of confidential messages is larger than a prescribed level. In this paper we give two definition of the rate region. We first define the rate region in the case of deterministic encoder and call it the deterministic rate region. Next, we define the rate region in the case of stochastic encoder and call it the stochastic rate region. We derive explicit inner and outer bounds for the above two rate regions and present a class of relay channels where two bounds match. Furthermore, we show that stochastic encoder can enlarge the rate region. We also evaluate the deterministic rate region of the Gaussian relay channel with confidential messages.


title: Hereditary Discrepancies in Different Numbers of Colors II

abstract: We bound the hereditary discrepancy of a hypergraph $\HH$ in two colors in terms of its hereditary discrepancy in $c$ colors. We show that $\herdisc(\HH,2) \le K c \herdisc(\HH,c)$, where $K$ is some absolute constant. This bound is sharp.


title: Coupling Methodology within the Software Platform Alliances

abstract: CEA, ANDRA and EDF are jointly developing the software platform ALLIANCES which aim is to produce a tool for the simulation of nuclear waste storage and disposal repository. This type of simulations deals with highly coupled thermo-hydro-mechanical and chemical (T-H-M-C) processes. A key objective of Alliances is to give the capability for coupling algorithms development between existing codes. The aim of this paper is to present coupling methodology use in the context of this software platform.


title: Scale-Free Overlay Topologies with Hard Cutoffs for Unstructured Peer-to-Peer Networks

abstract: In unstructured peer-to-peer (P2P) networks, the overlay topology (or connectivity graph) among peers is a crucial component in addition to the peer/data organization and search. Topological characteristics have profound impact on the efficiency of search on such unstructured P2P networks as well as other networks. It has been well-known that search on small-world topologies of N nodes can be as efficient as O(ln N), while scale-free (power-law) topologies offer even better search efficiencies like as good as O(lnln N) for a range of degree distribution exponents. However, generation and maintenance of such scale-free topologies are hard to realize in a distributed and potentially uncooperative environments as in the P2P networks. A key limitation of scale-free topologies is the high load (i.e. high degree) on very few number of hub nodes. In a typical unstructured P2P network, peers are not willing to maintain high degrees/loads as they may not want to store large number of entries for construction of the overlay topology. So, to achieve fairness and practicality among all peers, hard cutoffs on the number of entries are imposed by the individual peers, which limits scale-freeness of the overall topology. Thus, efficiency of the flooding search reduces as the size of the hard cutoff does. We investigate construction of scale-free topologies with hard cutoffs (i.e. there are not any major hubs) and effect of these hard cutoffs on the search efficiency. Interestingly, we observe that the efficiency of normalized flooding and random walk search algorithms increases as the hard cutoff decreases.


title: Shannon's secrecy system with informed receivers and its application to systematic coding for wiretapped channels

abstract: Shannon's secrecy system is studied in a setting, where both the legitimate decoder and the wiretapper have access to side information sequences correlated to the source, but the wiretapper receives both the coded information and the side information via channels that are more noisy than the respective channels of the legitmate decoder, which in turn, also shares a secret key with the encoder. A single--letter characterization is provided for the achievable region in the space of five figures of merit: the equivocation at the wiretapper, the key rate, the distortion of the source reconstruction at the legitimate receiver, the bandwidth expansion factor of the coded channels, and the average transmission cost (generalized power). Beyond the fact that this is an extension of earlier studies, it also provides a framework for studying fundamental performance limits of systematic codes in the presence of a wiretap channel. The best achievable performance of systematic codes is then compared to that of a general code in several respects, and a few examples are given.


title: Quantitative Analysis of the Publishing Landscape in High-Energy Physics

abstract: World-wide collaboration in high-energy physics (HEP) is a tradition which dates back several decades, with scientific publications mostly coauthored by scientists from different countries. This coauthorship phenomenon makes it difficult to identify precisely the ``share'' of each country in HEP scientific production. One year's worth of HEP scientific articles published in peer-reviewed journals is analysed and their authors are uniquely assigned to countries. This method allows the first correct estimation on a ``pro rata'' basis of the share of HEP scientific publishing among several countries and institutions. The results provide an interesting insight into the geographical collaborative patterns of the HEP community. The HEP publishing landscape is further analysed to provide information on the journals favoured by the HEP community and on the geographical variation of their author bases. These results provide quantitative input to the ongoing debate on the possible transition of HEP publishing to an Open Access model.


title: Scatter Networks: A New Approach for Analyzing Information Scatter on the Web

abstract: Information on any given topic is often scattered across the web. Previously this scatter has been characterized through the distribution of a set of facts (i.e. pieces of information) across web pages, showing that typically a few pages contain many facts on the topic, while many pages contain just a few. While such approaches have revealed important scatter phenomena, they are lossy in that they conceal how specific facts (e.g. rare facts) occur in specific types of pages (e.g. fact-rich pages). To reveal such regularities, we construct bi-partite networks, consisting of two types of vertices: the facts contained in webpages and the webpages themselves. Such a representation enables the application of a series of network analysis techniques, revealing structural features such as connectivity, robustness, and clustering. We discuss the implications of each of these features to the users' ability to find comprehensive information online. Finally, we compare the bipartite graph structure of webpages and facts with the hyperlink structure between the webpages.


title: The specifications making in complex CAD-system of renovation of the enterprises on the basis of modules in the drawing and electronic catalogues

abstract: The experience of automation of the specifications making of the projects of renovation of the industrial enterprises is described, being based on the special modules in the drawing containing the visible image and additional parameters, and electronic catalogues


title: The modelling of the automation schemes of technological processes in CAD-system of renovation of the enterprises

abstract: According to the requirements of the Russian standards, the automation schemes are necessary practically in each project of renovation of industrial buildings and facilities, in which any technological processes are realized. The model representations of the automation schemes in CAD-system TechnoCAD GlassX are described. The models follow a principle "to exclude a repeated input operations"


title: Hard Disk Drive as a Magnetomechanical Logic Device

abstract: We consider the conditions how two binary numbers can be superimposed on the same track with the use of different recording magnetic fields. As a result the average magnetization of longitudinal medium along the track can have three states: -M, 0 and +M. Possibility to perform logic operations with these states is considered. We demonstrate OR, AND, XOR and NOT operations and discuss a modification of a recording device.


title: Genetic Programming for Kernel-based Learning with Co-evolving Subsets Selection

abstract: Support Vector Machines (SVMs) are well-established Machine Learning (ML) algorithms. They rely on the fact that i) linear learning can be formalized as a well-posed optimization problem; ii) non-linear learning can be brought into linear learning thanks to the kernel trick and the mapping of the initial search space onto a high dimensional feature space. The kernel is designed by the ML expert and it governs the efficiency of the SVM approach. In this paper, a new approach for the automatic design of kernels by Genetic Programming, called the Evolutionary Kernel Machine (EKM), is presented. EKM combines a well-founded fitness function inspired from the margin criterion, and a co-evolution framework ensuring the computational scalability of the approach. Empirical validation on standard ML benchmark demonstrates that EKM is competitive using state-of-the-art SVMs with tuned hyper-parameters.


title: Neural Computation with Rings of Quasiperiodic Oscillators

abstract: We describe the use of quasiperiodic oscillators for computation and control of robots. We also describe their relationship to central pattern generators in simple organisms and develop a group theory for describing the dynamics of these systems.


title: Rhythms of social interaction: messaging within a massive online network

abstract: We have analyzed the fully-anonymized headers of 362 million messages exchanged by 4.2 million users of Facebook, an online social network of college students, during a 26 month interval. The data reveal a number of strong daily and weekly regularities which provide insights into the time use of college students and their social lives, including seasonal variations. We also examined how factors such as school affiliation and informal online friend lists affect the observed behavior and temporal patterns. Finally, we show that Facebook users appear to be clustered by school with respect to their temporal messaging patterns.


title: Functional Brain Imaging with Multi-Objective Multi-Modal Evolutionary Optimization

abstract: Functional brain imaging is a source of spatio-temporal data mining problems. A new framework hybridizing multi-objective and multi-modal optimization is proposed to formalize these data mining problems, and addressed through Evolutionary Computation (EC). The merits of EC for spatio-temporal data mining are demonstrated as the approach facilitates the modelling of the experts' requirements, and flexibly accommodates their changing goals.


title: Static Safety for an Actor Dedicated Process Calculus by Abstract Interpretation

abstract: The actor model eases the definition of concurrent programs with non uniform behaviors. Static analysis of such a model was previously done in a data-flow oriented way, with type systems. This approach was based on constraint set resolution and was not able to deal with precise properties for communications of behaviors. We present here a new approach, control-flow oriented, based on the abstract interpretation framework, able to deal with communication of behaviors. Within our new analyses, we are able to verify most of the previous properties we observed as well as new ones, principally based on occurrence counting.


title: On the Benefits of Inoculation, an Example in Train Scheduling

abstract: The local reconstruction of a railway schedule following a small perturbation of the traffic, seeking minimization of the total accumulated delay, is a very difficult and tightly constrained combinatorial problem. Notoriously enough, the railway company's public image degrades proportionally to the amount of daily delays, and the same goes for its profit! This paper describes an inoculation procedure which greatly enhances an evolutionary algorithm for train re-scheduling. The procedure consists in building the initial population around a pre-computed solution based on problem-related information available beforehand. The optimization is performed by adapting times of departure and arrival, as well as allocation of tracks, for each train at each station. This is achieved by a permutation-based evolutionary algorithm that relies on a semi-greedy heuristic scheduler to gradually reconstruct the schedule by inserting trains one after another. Experimental results are presented on various instances of a large real-world case involving around 500 trains and more than 1 million constraints. In terms of competition with commercial math ematical programming tool ILOG CPLEX, it appears that within a large class of instances, excluding trivial instances as well as too difficult ones, and with very few exceptions, a clever initialization turns an encouraging failure into a clear-cut success auguring of substantial financial savings.


title: A Generic Global Constraint based on MDDs

abstract: The paper suggests the use of Multi-Valued Decision Diagrams (MDDs) as the supporting data structure for a generic global constraint. We give an algorithm for maintaining generalized arc consistency (GAC) on this constraint that amortizes the cost of the GAC computation over a root-to-terminal path in the search tree. The technique used is an extension of the GAC algorithm for the regular language constraint on finite length input. Our approach adds support for skipped variables, maintains the reduced property of the MDD dynamically and provides domain entailment detection. Finally we also show how to adapt the approach to constraint types that are closely related to MDDs, such as AOMDDs and Case DAGs.


title: A Symbolic Intruder Model for Hash-Collision Attacks

abstract: In the recent years, several practical methods have been published to compute collisions on some commonly used hash functions. In this paper we present a method to take into account, at the symbolic level, that an intruder actively attacking a protocol execution may use these collision algorithms in reasonable time during the attack. Our decision procedure relies on the reduction of constraint solving for an intruder exploiting the collision properties of hush functions to constraint solving for an intruder operating on words.


title: An informational approach to the global optimization of expensive-to-evaluate functions

abstract: In many global optimization problems motivated by engineering applications, the number of function evaluations is severely limited by time or cost. To ensure that each evaluation contributes to the localization of good candidates for the role of global minimizer, a sequential choice of evaluation points is usually carried out. In particular, when Kriging is used to interpolate past evaluations, the uncertainty associated with the lack of information on the function can be expressed and used to compute a number of criteria accounting for the interest of an additional evaluation at any given point. This paper introduces minimizer entropy as a new Kriging-based criterion for the sequential choice of points at which the function should be evaluated. Based on \emph{stepwise uncertainty reduction}, it accounts for the informational gain on the minimizer expected from a new evaluation. The criterion is approximated using conditional simulations of the Gaussian process model behind Kriging, and then inserted into an algorithm similar in spirit to the \emph{Efficient Global Optimization} (EGO) algorithm. An empirical comparison is carried out between our criterion and \emph{expected improvement}, one of the reference criteria in the literature. Experimental results indicate major evaluation savings over EGO. Finally, the method, which we call IAGO (for Informational Approach to Global Optimization) is extended to robust optimization problems, where both the factors to be tuned and the function evaluations are corrupted by noise.


title: Coding Improves the Optimal Delay-Throughput Trade-offs in Mobile Ad-Hoc Networks: Two-Dimensional I.I.D. Mobility Models

abstract: In this paper, we investigate the delay-throughput trade-offs in mobile ad-hoc networks under two-dimensional i.i.d. mobility models. We consider two mobility time-scales: (i) Fast mobility where node mobility is at the same time-scale as data transmissions; (ii) Slow mobility where node mobility is assumed to occur at a much slower time-scale than data transmissions. Given a delay constraint $D,$ the main results are as follows: (1) For the two-dimensional i.i.d. mobility model with fast mobiles, the maximum throughput per source-destination (S-D) pair is shown to be $O(\sqrt{D/n}),$ where $n$ is the number of mobiles. (2) For the two-dimensional i.i.d. mobility model with slow mobiles, the maximum throughput per S-D pair is shown to be $O(\sqrt[3]{D/n}).$ (3) For each case, we propose a joint coding-scheduling algorithm to achieve the optimal delay-throughput trade-offs.


title: A Unified View of TD Algorithms; Introducing Full-Gradient TD and Equi-Gradient Descent TD

abstract: This paper addresses the issue of policy evaluation in Markov Decision Processes, using linear function approximation. It provides a unified view of algorithms such as TD(lambda), LSTD(lambda), iLSTD, residual-gradient TD. It is asserted that they all consist in minimizing a gradient function and differ by the form of this function and their means of minimizing it. Two new schemes are introduced in that framework: Full-gradient TD which uses a generalization of the principle introduced in iLSTD, and EGD TD, which reduces the gradient by successive equi-gradient descents. These three algorithms form a new intermediate family with the interesting property of making much better use of the samples than TD while keeping a gradient descent scheme, which is useful for complexity issues and optimistic policy iteration.


title: Linear-Codes-Based Lossless Joint Source-Channel Coding for Multiple-Access Channels

abstract: A general lossless joint source-channel coding (JSCC) scheme based on linear codes and random interleavers for multiple-access channels (MACs) is presented and then analyzed in this paper. By the information-spectrum approach and the code-spectrum approach, it is shown that a linear code with a good joint spectrum can be used to establish limit-approaching lossless JSCC schemes for correlated general sources and general MACs, where the joint spectrum is a generalization of the input-output weight distribution. Some properties of linear codes with good joint spectra are investigated. A formula on the "distance" property of linear codes with good joint spectra is derived, based on which, it is further proved that, the rate of any systematic codes with good joint spectra cannot be larger than the reciprocal of the corresponding alphabet cardinality, and any sparse generator matrices cannot yield linear codes with good joint spectra. The problem of designing arbitrary rate coding schemes is also discussed. A novel idea called "generalized puncturing" is proposed, which makes it possible that one good low-rate linear code is enough for the design of coding schemes with multiple rates. Finally, various coding problems of MACs are reviewed in a unified framework established by the code-spectrum approach, under which, criteria and candidates of good linear codes in terms of spectrum requirements for such problems are clearly presented.


title: P is not equal to NP

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


title: Next Generation Language Resources using GRID

abstract: This paper presents a case study concerning the challenges and requirements posed by next generation language resources, realized as an overall model of open, distributed and collaborative language infrastructure. If a sort of "new paradigm" is required, we think that the emerging and still evolving technology connected to Grid computing is a very interesting and suitable one for a concrete realization of this vision. Given the current limitations of Grid computing, it is very important to test the new environment on basic language analysis tools, in order to get the feeling of what are the potentialities and possible limitations connected to its use in NLP. For this reason, we have done some experiments on a module of Linguistic Miner, i.e. the extraction of linguistic patterns from restricted domain corpora.


title: Comparison between Networked Control System behaviour based on CAN and Switched Ethernet networks

abstract: The distributed control systems are more and more used in many industrial applications. These systems are often referred as "Networked control systems". The goal of this paper is to show the network influence on feedback control systems. Two networks are considered: Switched Ethernet network and CAN fieldbus. The first one represents the non deterministic network and second one represents the deterministic one. Several scenarii are studied to analyse the stability of system according to different network parameters (packets losses, congestion and frame priority). The Truetime simulator is used in this work.


title: A Novel Bayesian Classifier using Copula Functions

abstract: A useful method for representing Bayesian classifiers is through \emph{discriminant functions}. Here, using copula functions, we propose a new model for discriminants. This model provides a rich and generalized class of decision boundaries. These decision boundaries significantly boost the classification accuracy especially for high dimensional feature spaces. We strengthen our analysis through simulation results.


title: Collaborative design : managing task interdependencies and multiple perspectives

abstract: This paper focuses on two characteristics of collaborative design with respect to cooperative work: the importance of work interdependencies linked to the nature of design problems; and the fundamental function of design cooperative work arrangement which is the confrontation and combination of perspectives. These two intrinsic characteristics of the design work stress specific cooperative processes: coordination processes in order to manage task interdependencies, establishment of common ground and negotiation mechanisms in order to manage the integration of multiple perspectives in design.


title: Viewpoints in co-design: a field study in concurrent engineering

abstract: We present a field study aimed at analysing the use of viewpoints in co-design meetings. A viewpoint is a representation characterised by a certain combination of constraints. Three types of viewpoints are distinguished: prescribed viewpoint, discipline-specific viewpoint and integrated viewpoint. The contribution of our work consists in characterising the viewpoints of various stakeholders involved in co-design ("design office" disciplines, and production and maintenance disciplines), the dynamics of viewpoints confrontation and the cooperative modes that enable these different viewpoints to be integrated.


title: Changing our view on design evaluation meetings methodology: a study of software technical review meetings

abstract: By contrast to design meetings, design evaluation meetings (DEMs) have generally been considered as situations in which, according to DEMs methodologies, design activities are quite marginal. In a study of DEMs in software development, i.e. in technical review meetings following a particular review methodology, we showed: (i) the occurrence of design activities as part of an argumentation process; (ii) the relative importance of cognitive synchronisation as a prerequisite for evaluation; (iii) the important role played in evaluation by argumentation that makes explicit the underlying design rationale (DR). On the basis of our results, we discuss the potential for using DR methodologies in this kind of meetings.


title: Assessing the cognitive consequences of the object-oriented approach: a survey of empirical research on object-oriented design by individuals and teams

abstract: This paper presents a state-of-art review of empirical research on object-oriented (OO) design. Many claims about the cognitive benefits of the OO paradigm have been made by its advocates. These claims concern the ease of designing and reusing software at the individual level as well as the benefits of this paradigm at the team level. Since these claims are cognitive in nature, its seems important to assess them empirically. After a brief presentation of the main concepts of the OO paradigm, the claims about the superiority of OO design are outlined. The core of this paper consists of a review of empirical studies of OOD. We first discuss results concerning OOD by individuals. On the basis of empirical work, we (1) analyse the design activity of novice OO designers, (2) compare OO design with procedural design and, (3) discuss a typology of problems relevant for the OO approach. Then we assess the claims about naturalness and ease of OO design. The next part discusses results on OO software reuse. On the basis of empirical work, we (1) compare reuse in the OO versus procedural paradigm, (2) discuss the potential for OO software reuse and (3) analyse reuse activity in the OO paradigm. Then we assess claims on reusability. The final part reviews empirical work on OO design by teams. We present results on communication, coordination, knowledge dissemination and interactions with clients. Then we assess claims about OOD at the software design team level. In a general conclusion, we discuss the limitations of these studies and give some directions for future research.


title: Zig-zag and Replacement Product Graphs and LDPC Codes

abstract: The performance of codes defined from graphs depends on the expansion property of the underlying graph in a crucial way. Graph products, such as the zig-zag product and replacement product provide new infinite families of constant degree expander graphs. The paper investigates the use of zig-zag and replacement product graphs for the construction of codes on graphs. A modification of the zig-zag product is also introduced, which can operate on two unbalanced biregular bipartite graphs.


title: D-MG Tradeoff and Optimal Codes for a Class of AF and DF Cooperative Communication Protocols

abstract: We consider cooperative relay communication in a fading channel environment under the Orthogonal Amplify and Forward (OAF) and Orthogonal and Non-Orthogonal Selection Decode and Forward (OSDF and NSDF) protocols. For all these protocols, we compute the Diversity-Multiplexing Gain Tradeoff (DMT). We construct DMT optimal codes for the protocols which are sphere decodable and, in certain cases, incur minimum possible delay. Our results establish that the DMT of the OAF protocol is identical to the DMT of the Non-Orthogonal Amplify and Forward (NAF) protocol. Two variants of the NSDF protocol are considered: fixed-NSDF and variable-NSDF protocol. In the variable-NSDF protocol, the fraction of time duration for which the source alone transmits is allowed to vary with the rate of communication. Among the class of static amplify-and-forward and decode-and-forward protocols, the variable-NSDF protocol is shown to have the best known DMT for any number of relays apart from the two-relay case. When there are two relays, the variable-NSDF protocol is shown to improve on the DMT of the best previously-known protocol for higher values of the multiplexing gain. Our results also establish that the fixed-NSDF protocol has a better DMT than the NAF protocol for any number of relays. Finally, we present a DMT optimal code construction for the NAF protocol.


title: Bounding the Bias of Tree-Like Sampling in IP Topologies

abstract: It is widely believed that the Internet's AS-graph degree distribution obeys a power-law form. Most of the evidence showing the power-law distribution is based on BGP data. However, it was recently argued that since BGP collects data in a tree-like fashion, it only produces a sample of the degree distribution, and this sample may be biased. This argument was backed by simulation data and mathematical analysis, which demonstrated that under certain conditions a tree sampling procedure can produce an artificail power-law in the degree distribution. Thus, although the observed degree distribution of the AS-graph follows a power-law, this phenomenon may be an artifact of the sampling process. In this work we provide some evidence to the contrary. We show, by analysis and simulation, that when the underlying graph degree distribution obeys a power-law with an exponent larger than 2, a tree-like sampling process produces a negligible bias in the sampled degree distribution. Furthermore, recent data collected from the DIMES project, which is not based on BGP sampling, indicates that the underlying AS-graph indeed obeys a power-law degree distribution with an exponent larger than 2. By combining this empirical data with our analysis, we conclude that the bias in the degree distribution calculated from BGP data is negligible.


title: Articulation entre \'{e}laboration de solutions et argumentation polyphonique

abstract: In this paper, we propose an analytical framework that aims to bring out the nature of participants' contributions to co-design meetings, in a way that synthesises content and function dimensions, together with the dimension of dialogicality. We term the resulting global vision of contribution, the "interactive profile".


title: Cognitive Effort in Collective Software Design: Methodological Perspectives in Cognitive Ergonomics

abstract: Empirical software engineering is concerned with measuring, or estimating, both the effort put into the software process and the quality of its product. We defend the idea that measuring process effort and product quality and establishing a relation between the two cannot be performed without a model of cognitive and collective activities involved in software design, and without measurement of these activities. This is the object of our field, i.e. Cognitive Ergonomics of design. After a brief presentation of its theoretical and methodological foundations, we will discuss a cognitive approach to design activities and its potential to provide new directions in ESE. Then we will present and discuss an illustration of the methodological directions we have proposed for the analysis and measurement of cognitive activities in the context of collective software design. The two situations analysed are technical review meetings, and Request For Comments-like procedures in Open Source Software design.


title: Complementary Sets, Generalized Reed-Muller Codes, and Power Control for OFDM

abstract: The use of error-correcting codes for tight control of the peak-to-mean envelope power ratio (PMEPR) in orthogonal frequency-division multiplexing (OFDM) transmission is considered in this correspondence. By generalizing a result by Paterson, it is shown that each q-phase (q is even) sequence of length 2^m lies in a complementary set of size 2^{k+1}, where k is a nonnegative integer that can be easily determined from the generalized Boolean function associated with the sequence. For small k this result provides a reasonably tight bound for the PMEPR of q-phase sequences of length 2^m. A new 2^h-ary generalization of the classical Reed-Muller code is then used together with the result on complementary sets to derive flexible OFDM coding schemes with low PMEPR. These codes include the codes developed by Davis and Jedwab as a special case. In certain situations the codes in the present correspondence are similar to Paterson's code constructions and often outperform them.


title: On the Peak-to-Mean Envelope Power Ratio of Phase-Shifted Binary Codes

abstract: The peak-to-mean envelope power ratio (PMEPR) of a code employed in orthogonal frequency-division multiplexing (OFDM) systems can be reduced by permuting its coordinates and by rotating each coordinate by a fixed phase shift. Motivated by some previous designs of phase shifts using suboptimal methods, the following question is considered in this paper. For a given binary code, how much PMEPR reduction can be achieved when the phase shifts are taken from a 2^h-ary phase-shift keying (2^h-PSK) constellation? A lower bound on the achievable PMEPR is established, which is related to the covering radius of the binary code. Generally speaking, the achievable region of the PMEPR shrinks as the covering radius of the binary code decreases. The bound is then applied to some well understood codes, including nonredundant BPSK signaling, BCH codes and their duals, Reed-Muller codes, and convolutional codes. It is demonstrated that most (presumably not optimal) phase-shift designs from the literature attain or approach our bound.


title: Quaternary Constant-Amplitude Codes for Multicode CDMA

abstract: A constant-amplitude code is a code that reduces the peak-to-average power ratio (PAPR) in multicode code-division multiple access (MC-CDMA) systems to the favorable value 1. In this paper quaternary constant-amplitude codes (codes over Z_4) of length 2^m with error-correction capabilities are studied. These codes exist for every positive integer m, while binary constant-amplitude codes cannot exist if m is odd. Every word of such a code corresponds to a function from the binary m-tuples to Z_4 having the bent property, i.e., its Fourier transform has magnitudes 2^{m/2}. Several constructions of such functions are presented, which are exploited in connection with algebraic codes over Z_4 (in particular quaternary Reed-Muller, Kerdock, and Delsarte-Goethals codes) to construct families of quaternary constant-amplitude codes. Mappings from binary to quaternary constant-amplitude codes are presented as well.


title: On Measuring the Impact of Human Actions in the Machine Learning of a Board Game's Playing Policies

abstract: We investigate systematically the impact of human intervention in the training of computer players in a strategy board game. In that game, computer players utilise reinforcement learning with neural networks for evolving their playing strategies and demonstrate a slow learning speed. Human intervention can significantly enhance learning performance, but carry-ing it out systematically seems to be more of a problem of an integrated game development environment as opposed to automatic evolutionary learning.


title: Player co-modelling in a strategy board game: discovering how to play fast

abstract: In this paper we experiment with a 2-player strategy board game where playing models are evolved using reinforcement learning and neural networks. The models are evolved to speed up automatic game development based on human involvement at varying levels of sophistication and density when compared to fully autonomous playing. The experimental results suggest a clear and measurable association between the ability to win games and the ability to do that fast, while at the same time demonstrating that there is a minimum level of human involvement beyond which no learning really occurs.


title: Partially ordered distributed computations on asynchronous point-to-point networks

abstract: Asynchronous executions of a distributed algorithm differ from each other due to the nondeterminism in the order in which the messages exchanged are handled. In many situations of interest, the asynchronous executions induced by restricting nondeterminism are more efficient, in an application-specific sense, than the others. In this work, we define partially ordered executions of a distributed algorithm as the executions satisfying some restricted orders of their actions in two different frameworks, those of the so-called event- and pulse-driven computations. The aim of these restrictions is to characterize asynchronous executions that are likely to be more efficient for some important classes of applications. Also, an asynchronous algorithm that ensures the occurrence of partially ordered executions is given for each case. Two of the applications that we believe may benefit from the restricted nondeterminism are backtrack search, in the event-driven case, and iterative algorithms for systems of linear equations, in the pulse-driven case.


title: Lossless fitness inheritance in genetic algorithms for decision trees

abstract: When genetic algorithms are used to evolve decision trees, key tree quality parameters can be recursively computed and re-used across generations of partially similar decision trees. Simply storing instance indices at leaves is enough for fitness to be piecewise computed in a lossless fashion. We show the derivation of the (substantial) expected speed-up on two bounding case problems and trace the attractive property of lossless fitness inheritance to the divide-and-conquer nature of decision trees. The theoretical results are supported by experimental evidence.


title: Polynomial Time Symmetry and Isomorphism Testing for Connected Graphs

abstract: We use the concept of a Kirchhoff resistor network (alternatively random walk on a network) to probe connected graphs and produce symmetry revealing canonical labelings of the graph(s) nodes and edges.


title: Reuse of designs: Desperately seeking an interdisciplinary cognitive approach

abstract: This text analyses the papers accepted for the workshop "Reuse of designs: an interdisciplinary cognitive approach". Several dimensions and questions considered as important (by the authors and/or by us) are addressed: What about the "interdisciplinary cognitive" character of the approaches adopted by the authors? Is design indeed a domain where the use of CBR is particularly suitable? Are there important distinctions between CBR and other approaches? Which types of knowledge -other than cases- is being, or might be, used in CBR systems? With respect to cases: are there different "types" of case and different types of case use? which formats are adopted for their representation? do cases have "components"? how are cases organised in the case memory? Concerning their retrieval: which types of index are used? on which types of relation is retrieval based? how does one retrieve only a selected number of cases, i.e., how does one retrieve only the "best" cases? which processes and strategies are used, by the system and by its user? Finally, some important aspects of CBR system development are shortly discussed: should CBR systems be assistance or autonomous systems? how can case knowledge be "acquired"? what about the empirical evaluation of CBR systems? The conclusion points out some lacking points: not much attention is paid to the user, and few papers have indeed adopted an interdisciplinary cognitive approach.


title: Predicate Abstraction via Symbolic Decision Procedures

abstract: We present a new approach for performing predicate abstraction based on symbolic decision procedures. Intuitively, a symbolic decision procedure for a theory takes a set of predicates in the theory and symbolically executes a decision procedure on all the subsets over the set of predicates. The result of the symbolic decision procedure is a shared expression (represented by a directed acyclic graph) that implicitly represents the answer to a predicate abstraction query. We present symbolic decision procedures for the logic of Equality and Uninterpreted Functions (EUF) and Difference logic (DIFF) and show that these procedures run in pseudo-polynomial (rather than exponential) time. We then provide a method to construct symbolic decision procedures for simple mixed theories (including the two theories mentioned above) using an extension of the Nelson-Oppen combination method. We present preliminary evaluation of our Procedure on predicate abstraction benchmarks from device driver verification in SLAM.


title: Object-Oriented Program Comprehension: Effect of Expertise, Task and Phase

abstract: The goal of our study is to evaluate the effect on program comprehension of three factors that have not previously been studied in a single experiment. These factors are programmer expertise (expert vs. novice), programming task (documentation vs. reuse), and the development of understanding over time (phase 1 vs. phase 2). This study is carried out in the context of the mental model approach to comprehension based on van Dijk and Kintsch's model (1983). One key aspect of this model is the distinction between two kinds of representation the reader might construct from a text: 1) the textbase, which refers to what is said in the text and how it is said, and 2) the situation model, which represents the situation referred to by the text. We have evaluated the effect of the three factors mentioned above on the development of both the textbase (or program model) and the situation model in object-oriented program comprehension. We found a four-way interaction of expertise, phase, task and type of model. For the documentation group we found that experts and novices differ in the elaboration of their situation model but not their program model. There was no interaction of expertise with phase and type of model in the documentation group. For the reuse group, there was a three-way interaction between phase, expertise and type of model. For the novice reuse group, the effect of the phase was to increase the construction of the situation model but not the program model. With respect to the task, our results show that novices do not spontaneously construct a strong situation model but are able to do so if the task demands it.


title: Quantitative Measurements of the Influence of Participant Roles during Peer Review Meetings

abstract: Peer review meetings (PRMs) are formal meetings during which peers systematically analyze artifacts to improve their quality and report on non-conformities. This paper presents an approach based on protocol analysis for quantifying the influence of participant roles during PRMs. Three views are used to characterize the seven defined participant roles. The project view defines three roles supervisor, procedure expert and developer. The meeting view defines two roles: author and reviewer, and the task view defines the roles reflecting direct and indirect interest in the artifact under review. The analysis, based on log-linear modeling, shows that review activities have different patterns, depending on their focus: form or content. The influence of each role is analyzed with respect to this focus. Interpretation of the quantitative data leads to the suggestion that PRMs could be improved by creating three different types of reviews, each of which collects together specific roles: form review, cognitive synchronization review and content review.


title: Evocation and elaboration of solutions: Different types of problem-solving actions. An empirical study on the design of an aerospace artifact

abstract: An observational study was conducted on a professional designer working on a design project in aerospace industry. The protocol data were analyzed in order to gain insight into the actions the designer used for the development of a solution to the corresponding problem. Different processes are described: from the "simple" evocation of a solution existing in memory, to the elaboration of a "new" solution out of mnesic entities without any clear link to the current problem. Control is addressed in so far as it concerns the priority among the different types of development processes: the progression from evocation of a "standard" solution to elaboration of a "new" solution is supposed to correspond to the resulting order, that is, the one in which the designer's activity proceeds. Short discussions of * the double status of "problem" and "solution," * the problem/solution knowledge units in memory and their access, and * the different abstraction levels on which problem and solution representations are developed, are illustrated by the results.


title: High SNR Analysis for MIMO Broadcast Channels: Dirty Paper Coding vs. Linear Precoding

abstract: We study the MIMO broadcast channel and compare the achievable throughput for the optimal strategy of dirty paper coding to that achieved with sub-optimal and lower complexity linear precoding (e.g., zero-forcing and block diagonalization) transmission. Both strategies utilize all available spatial dimensions and therefore have the same multiplexing gain, but an absolute difference in terms of throughput does exist. The sum rate difference between the two strategies is analytically computed at asymptotically high SNR, and it is seen that this asymptotic statistic provides an accurate characterization at even moderate SNR levels. Furthermore, the difference is not affected by asymmetric channel behavior when each user a has different average SNR. Weighted sum rate maximization is also considered, and a similar quantification of the throughput difference between the two strategies is performed. In the process, it is shown that allocating user powers in direct proportion to user weights asymptotically maximizes weighted sum rate. For multiple antenna users, uniform power allocation across the receive antennas is applied after distributing power proportional to the user weight.


title: Design Strategies and Knowledge in Object-Oriented Programming: Effects of Experience

abstract: An empirical study was conducted to analyse design strategies and knowledge used in object-oriented software design. Eight professional programmers experienced with procedural programming languages and either experienced or not experienced in object-oriented design strategies related to two central aspects of the object-oriented paradigm: (1) associating actions, i.e., execution steps, of a complex plan to different objects and revising a complex plan, and (2) defining simple plans at different levels in the class hierarchy. As regards the development of complex plans elements attached to different objects, our results show that, for beginners in OOP, the description of objects and the description of actions are not always integrated in an early design phase, particularly for the declarative problem whereas, for the programmers experienced in OOP, the description of objects and the description of actions tend to be integrated in their first drafts of solutions whichever the problem type. The analysis of design strategies reveal the use of different knowledge according to subjects' language experience: (1) schemas related to procedural languages; actions are organized in an execution order, or (2) schemas related to object-oriented languages; actions and objects are integrated, and actions are organised around objects.


title: Users' participation to the design process in an Open Source Software online community

abstract: The objective of this research is to analyse the ways members of open-source software communities participate in design. In particular we focus on how users of an Open Source (OS) programming language (Python) participate in adding new functionalities to the language. Indeed, in the OS communities, users are highly skilled in computer sciences; they do not correspond to the common representation of end-users and can potentially participate to the design process. Our study characterizes the Python galaxy and analyses a formal process to introduce new functionalities to the language called Python Enhancement Proposal (PEP) from the idea of language evolution to the PEP implementation. The analysis of a particular pushed-by-users PEP from one application domain community (financial), shows: that the design process is distributed and specialized between online and physical interactions spaces; and there are some cross participants between users and developers communities which may reveal boundary spanners roles.


title: Articulation entre composantes verbale et graphico-gestuelle de l'interaction dans des r\'{e}unions de conception architecturale

abstract: This study is focused on the role of external representations, e.g., skteches, in collaborative architectural design. In particular, we analyse (1) the use of graphico-gestural modalities and, (2) the articulation modes between graphico-gestural and verbal modalities in design interaction. We have elaborated a first classification which distinguishes between two modes of articulation, articulation in integrated activities versus articulation in parallel activities.


title: Estimation of Bit and Frame Error Rates of Low-Density Parity-Check Codes on Binary Symmetric Channels

abstract: A method for estimating the performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms on binary symmetric channels (BSC) is proposed. Based on the enumeration of the smallest weight error patterns that can not be all corrected by the decoder, this method estimates both the frame error rate (FER) and the bit error rate (BER) of a given LDPC code with very good precision for all crossover probabilities of practical interest. Through a number of examples, we show that the proposed method can be effectively applied to both regular and irregular LDPC codes and to a variety of hard-decision iterative decoding algorithms. Compared with the conventional Monte Carlo simulation, the proposed method has a much smaller computational complexity, particularly for lower error rates.


title: Geographic Gossip on Geometric Random Graphs via Affine Combinations

abstract: In recent times, a considerable amount of work has been devoted to the development and analysis of gossip algorithms in Geometric Random Graphs. In a recently introduced model termed "Geographic Gossip," each node is aware of its position but possesses no further information. Traditionally, gossip protocols have always used convex linear combinations to achieve averaging. We develop a new protocol for Geographic Gossip, in which counter-intuitively, we use {\it non-convex affine combinations} as updates in addition to convex combinations to accelerate the averaging process. The dependence of the number of transmissions used by our algorithm on the number of sensors $n$ is $n \exp(O(\log \log n)^2) = n^{1 + o(1)}$. For the previous algorithm, this dependence was $\tilde{O}(n^{1.5})$. The exponent 1+ o(1) of our algorithm is asymptotically optimal. Our algorithm involves a hierarchical structure of $\log \log n$ depth and is not completely decentralized. However, the extent of control exercised by a sensor on another is restricted to switching the other on or off.


title: Economy-based Content Replication for Peering Content Delivery Networks

abstract: Existing Content Delivery Networks (CDNs) exhibit the nature of closed delivery networks which do not cooperate with other CDNs and in practice, islands of CDNs are formed. The logical separation between contents and services in this context results in two content networking domains. In addition to that, meeting the Quality of Service requirements of users according to negotiated Service Level Agreement is crucial for a CDN. Present trends in content networks and content networking capabilities give rise to the interest in interconnecting content networks. Hence, in this paper, we present an open, scalable, and Service-Oriented Architecture (SOA)-based system that assist the creation of open Content and Service Delivery Networks (CSDNs), which scale and supports sharing of resources through peering with other CSDNs. To encourage resource sharing and peering arrangements between different CDN providers at global level, we propose using market-based models by introducing an economy-based strategy for content replication.


title: Going Stupid with EcoLab

abstract: In 2005, Railsback et al. proposed a very simple model ({\em Stupid Model}) that could be implemented within a couple of hours, and later extended to demonstrate the use of common ABM platform functionality. They provided implementations of the model in several agent based modelling platforms, and compared the platforms for ease of implementation of this simple model, and performance. In this paper, I implement Railsback et al's Stupid Model in the EcoLab simulation platform, a C++ based modelling platform, demonstrating that it is a feasible platform for these sorts of models, and compare the performance of the implementation with Repast, Mason and Swarm versions.


title: On the intersection of additive perfect codes

abstract: The intersection problem for additive (extended and non-extended) perfect codes, i.e. which are the possibilities for the number of codewords in the intersection of two additive codes C1 and C2 of the same length, is investigated. Lower and upper bounds for the intersection number are computed and, for any value between these bounds, codes which have this given intersection value are constructed. For all these codes the abelian group structure of the intersection is characterized. The parameters of this abelian group structure corresponding to the intersection codes are computed and lower and upper bounds for these parameters are established. Finally, constructions of codes the intersection of which fits any parameters between these bounds are given.


title: Memory of past designs: distinctive roles in individual and collective design

abstract: Empirical studies on design have emphasised the role of memory of past solutions. Design involves the use of generic knowledge as well as episodic knowledge about past designs for analogous problems : in this way, it involves the reuse of past designs. We analyse this mechanism of reuse from a socio-cognitive viewpoint. According to a purely cognitive approach, reuse involves cognitive mechanisms linked to the problem solving activity itself. Our socio-cognitive approach accounts for these phenomena as well as reuse mechanisms linked to cooperation, in particular coordination, and confrontation/integration of viewpoints.


title: Confrontation of viewpoints in a concurrent engineering process

abstract: We present an empirical study aimed at analysing the use of viewpoints in an industrial Concurrent Engineering context. Our focus is on the viewpoints expressed in the argumentative process taking place in evaluation meetings. Our results show that arguments enabling a viewpoint or proposal to be defended are often characterized by the use of constraints. One result involved the way in which the proposals for solutions are assessed during these meetings. We have revealed the existence of specific assessment modes in these meetings as well as their combination. Then, we show that, even if some constraints are apparently identically used by the different specialists involved in meetings, various meanings and weightings are associated with these constraints by these different specialists.


title: Mental Representations Constructed by Experts and Novices in Object-Oriented Program Comprehension

abstract: Previous studies on program comprehension were carried out largely in the context of procedural languages. Our purpose is to develop and evaluate a cognitive model of object-oriented (OO) program understanding. Our model is based on the van Dijk and Kintsch's model of text understanding (1983). One key aspect of this theoretical approach is the distinction between two kinds of representation the reader might construct from a text: the textbase and the situation model. On the basis of results of an experiment we have conducted, we evaluate the cognitive validity of this distinction in OO program understanding. We examine how the construction of these two representations is differentially affected by the programmer's expertise and how they evolve differentially over time.


title: On Finite Memory Universal Data Compression and Classification of Individual Sequences

abstract: Consider the case where consecutive blocks of N letters of a semi-infinite individual sequence X over a finite-alphabet are being compressed into binary sequences by some one-to-one mapping. No a-priori information about X is available at the encoder, which must therefore adopt a universal data-compression algorithm. It is known that if the universal LZ77 data compression algorithm is successively applied to N-blocks then the best error-free compression for the particular individual sequence X is achieved, as $N$ tends to infinity. The best possible compression that may be achieved by any universal data compression algorithm for finite N-blocks is discussed. It is demonstrated that context tree coding essentially achieves it. Next, consider a device called classifier (or discriminator) that observes an individual training sequence X. The classifier's task is to examine individual test sequences of length N and decide whether the test N-sequence has the same features as those that are captured by the training sequence X, or is sufficiently different, according to some appropriatecriterion. Here again, it is demonstrated that a particular universal context classifier with a storage-space complexity that is linear in N, is essentially optimal. This may contribute a theoretical "individual sequence" justification for the Probabilistic Suffix Tree (PST) approach in learning theory and in computational biology.


title: Analysing viewpoints in design through the argumentation process

abstract: We present an empirical study aimed at analysing the use of viewpoints in an industrial Concurrent Engineering context. Our focus is on the viewpoints expressed in the argumentative process taking place in evaluation meetings. Our results show that arguments enabling a viewpoint or proposal to be defended are often characterized by the use of constraints. Firstly, we show that, even if some constraints are apparently identically used by the different specialists involved in meetings, various meanings and weightings are associated with these constraints by these different specialists. Secondly, we show that the implicit or explicit nature of constraints depends on several interlocutive factors. Thirdly, we show that an argument often covers not only one constraint but a network of constraints. The type of combination reflects viewpoints which have specific status in the meeting. Then, we will propose a first model of the dynamics of viewpoints confrontation/integration.


title: Multimodality and parallelism in design interaction: co-designers' alignment and coalitions

abstract: This paper presents an analysis of various forms of articulation between graphico-gestural and verbal modalities in parallel interactions between designers in a collaborative design situation. Based on our methodological framework, we illustrate several forms of multimodal articulations, that is, integrated and non-integrated, through extracts from a corpus on an architectural design meeting. These modes reveal alignment or disalignment between designers, with respect to the focus of their activities. They also show different forms of coalition.


title: Both Generic Design and Different Forms of Designing

abstract: This paper defends an augmented cognitively oriented "generic-design hypothesis": There are both significant similarities between the design activities implemented in different situations and crucial differences between these and other cognitive activities; yet, characteristics of a design situation (i.e., related to the designers, the artefact, and other task variables influencing these two) introduce specificities in the corresponding design activities and cognitive structures that are used. We thus combine the generic-design hypothesis with that of different "forms" of designing. In this paper, outlining a number of directions that need further elaboration, we propose a series of candidate dimensions underlying such forms of design.


title: Reusing processes and documenting processes: toward an integrated framework

abstract: This paper presents a cognitive typology of reuse processes, and a cognitive typology of documenting processes. Empirical studies on design with reuse and on software documenting provide evidence for a generalized cognitive model. First, these studies emphasize the cyclical nature of design: cycles of planning, writing and revising occur. Second, natural language documentation follows the hierarchy of cognitive entities manipulated during design. Similarly software reuse involves exploiting various types of knowledge depending on the phase of design in which reuse is involved. We suggest that these observations can be explained based on cognitive models of text processing: the van Dijk and Kintsch (1983) model of text comprehension, and the Hayes and Flower (1980) model of text production. Based on our generalized cognitive model, we suggest a framework for documenting reusable components.


title: On the Maximum Sum-rate Capacity of Cognitive Multiple Access Channel

abstract: We consider the communication scenario where multiple cognitive users wish to communicate to the same receiver, in the presence of primary transmission. The cognitive transmitters are assumed to have the side information about the primary transmission. The capacity region of cognitive users is formulated under the constraint that the capacity of primary transmission is not changed as if no cognitive users exist. Moreover, the maximum sum-rate point of the capacity region is characterized, by optimally allocating the power of each cognitive user to transmit its own information.


title: Registers

abstract: Entry in: Encyclopedia of Algorithms, Ming-Yang Kao, Ed., Springer, To appear. Synonyms: Wait-free registers, wait-free shared variables, asynchronous communication hardware. Problem Definition: Consider a system of asynchronous processes that communicate among themselves by only executing read and write operations on a set of shared variables (also known as shared registers). The system has no global clock or other synchronization primitives.


title: A disk-covering problem with application in optical interferometry

abstract: Given a disk O in the plane called the objective, we want to find n small disks P_1,...,P_n called the pupils such that $\bigcup_{i,j=1}^n P_i \ominus P_j \supseteq O$, where $\ominus$ denotes the Minkowski difference operator, while minimizing the number of pupils, the sum of the radii or the total area of the pupils. This problem is motivated by the construction of very large telescopes from several smaller ones by so-called Optical Aperture Synthesis. In this paper, we provide exact, approximate and heuristic solutions to several variations of the problem.


title: Experimental Information and Statistical Modeling of Physical Laws

abstract: Statistical modeling of physical laws connects experiments with mathematical descriptions of natural phenomena. The modeling is based on the probability density of measured variables expressed by experimental data via a kernel estimator. As an objective kernel the scattering function determined by calibration of the instrument is introduced. This function provides for a new definition of experimental information and redundancy of experimentation in terms of information entropy. The redundancy increases with the number of experiments, while the experimental information converges to a value that describes the complexity of the data. The difference between the redundancy and the experimental information is proposed as the model cost function. From its minimum, a proper number of data in the model is estimated. As an optimal, nonparametric estimator of the relation between measured variables the conditional average extracted from the kernel estimator is proposed. The modeling is demonstrated on noisy chaotic data.


title: Using Combinatorics to Prune Search Trees: Independent and Dominating Set

abstract: This paper has been withdrawn by the author.


title: A Classification of 6R Manipulators

abstract: This paper presents a classification of generic 6-revolute jointed (6R) manipulators using homotopy class of their critical point manifold. A part of classification is listed in this paper because of the complexity of homotopy class of 4-torus. The results of this classification will serve future research of the classification and topological properties of maniplators joint space and workspace.


title: Loop corrections for approximate inference

abstract: We propose a method for improving approximate inference methods that corrects for the influence of loops in the graphical model. The method is applicable to arbitrary factor graphs, provided that the size of the Markov blankets is not too large. It is an alternative implementation of an idea introduced recently by Montanari and Rizzo (2005). In its simplest form, which amounts to the assumption that no loops are present, the method reduces to the minimal Cluster Variation Method approximation (which uses maximal factors as outer clusters). On the other hand, using estimates of the effect of loops (obtained by some approximate inference algorithm) and applying the Loop Correcting (LC) method usually gives significantly better results than applying the approximate inference algorithm directly without loop corrections. Indeed, we often observe that the loop corrected error is approximately the square of the error of the approximate inference method used to estimate the effect of loops. We compare different variants of the Loop Correcting method with other approximate inference methods on a variety of graphical models, including "real world" networks, and conclude that the LC approach generally obtains the most accurate results.


title: Estimating Aggregate Properties on Probabilistic Streams

abstract: The probabilistic-stream model was introduced by Jayram et al. \cite{JKV07}. It is a generalization of the data stream model that is suited to handling ``probabilistic'' data where each item of the stream represents a probability distribution over a set of possible events. Therefore, a probabilistic stream determines a distribution over potentially a very large number of classical "deterministic" streams where each item is deterministically one of the domain values. The probabilistic model is applicable for not only analyzing streams where the input has uncertainties (such as sensor data streams that measure physical processes) but also where the streams are derived from the input data by post-processing, such as tagging or reconciling inconsistent and poor quality data. We present streaming algorithms for computing commonly used aggregates on a probabilistic stream. We present the first known, one pass streaming algorithm for estimating the \AVG, improving results in \cite{JKV07}. We present the first known streaming algorithms for estimating the number of \DISTINCT items on probabilistic streams. Further, we present extensions to other aggregates such as the repeat rate, quantiles, etc. In all cases, our algorithms work with provable accuracy guarantees and within the space constraints of the data stream model.