OpenRaiser/Intern-Atlas huggingface dataset:
Collaborative design : managing task interdependencies and multiple perspectives
Venue: arXiv cs.HC 2007
Year: 2007

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.
Changing our view on design evaluation meetings methodology: a study of software technical review meetings
Venue: arXiv cs.HC 2007
Year: 2007

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.
Cognitive Effort in Collective Software Design: Methodological Perspectives in Cognitive Ergonomics
Venue: arXiv cs.HC 2007
Year: 2007

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.
Predicate Abstraction via Symbolic Decision Procedures
Venue: arXiv cs.LO 2007
Year: 2007

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.
Bounds on Key Appearance Equivocation for Substitution Ciphers
Venue: arXiv cs.IT 2007
Year: 2007

The average conditional entropy of the key given the message and its corresponding cryptogram, H(K|M,C), which is reffer as a key appearance equivocation, was proposed as a theoretical measure of the strength of the cipher system under a known-plaintext attack by Dunham in 1980. In the same work (among other things), lower and upper bounds for H(S}_{M}|M^L,C^L) are found and its asymptotic behaviour as a function of cryptogram length L is described for simple substitution ciphers i.e. when the key space S_{M} is the symmetric group acting on a discrete alphabet M. In the present paper we consider the same problem when the key space is an arbitrary subgroup K of S_{M} and generalize Dunham's result.
Determining the Applicability of Agile Practices to Mission and Life-critical Systems
Venue: arXiv cs.SE 2007
Year: 2007

Adopting agile practices brings about many benefits and improvements to the system being developed. However, in mission and life-critical systems, adopting an inappropriate agile practice has detrimental impacts on the system in various phases of its lifecycle as well as precludes desired qualities from being actualized. This paper presents a three-stage process that provides guidance to organizations on how to identify the agile practices they can benefit from without causing any impact to the mission and life critical system being developed.
$D$-ary Bounded-Length Huffman Coding
Venue: arXiv cs.IT 2007
Year: 2007

Efficient optimal prefix coding has long been accomplished via the Huffman algorithm. However, there is still room for improvement and exploration regarding variants of the Huffman problem. Length-limited Huffman coding, useful for many practical applications, is one such variant, in which codes are restricted to the set of codes in which none of the $n$ codewords is longer than a given length, $l_{\max}$. Binary length-limited coding can be done in $O(n l_{\max})$ time and O(n) space via the widely used Package-Merge algorithm. In this paper the Package-Merge approach is generalized without increasing complexity in order to introduce a minimum codeword length, $l_{\min}$, to allow for objective functions other than the minimization of expected codeword length, and to be applicable to both binary and nonbinary codes; nonbinary codes were previously addressed using a slower dynamic programming approach. These extensions have various applications -- including faster decompression -- and can be used to solve the problem of finding an optimal code with limited fringe, that is, finding the best code among codes with a maximum difference between the longest and shortest codewords. The previously proposed method for solving this problem was nonpolynomial time, whereas solving this using the novel algorithm requires only $O(n (l_{\max}- l_{\min})^2)$ time and O(n) space.
A Reply to Hofman On: "Why LP cannot solve large instances of NP-complete problems in polynomial time"
Venue: arXiv cs.CC 2007
Year: 2007

Using an approach that seems to be patterned after that of Yannakakis, Hofman argues that an NP-complete problem cannot be formulated as a polynomial bounded-sized linear programming problem. He then goes on to propose a "construct" that he claims to be a counter-example to recently published linear programming formulations of the Traveling Salesman Problem (TSP) and the Quadratic Assignment Problems (QAP), respectively. In this paper, we show that Hofman's construct is flawed, and provide further proof that his "counter-example" is invalid.
Performance Analysis of Algebraic Soft-Decision Decoding of Reed-Solomon Codes
Venue: arXiv cs.IT 2007
Year: 2007

We investigate the decoding region for Algebraic Soft-Decision Decoding (ASD) of Reed-Solomon codes in a discrete, memoryless, additive-noise channel. An expression is derived for the error correction radius within which the soft-decision decoder produces a list that contains the transmitted codeword. The error radius for ASD is shown to be larger than that of Guruswami-Sudan hard-decision decoding for a subset of low-rate codes. These results are also extended to multivariable interpolation in the sense of Parvaresh and Vardy. An upper bound is then presented for ASD's probability of error, where an error is defined as the event that the decoder selects an erroneous codeword from its list. This new definition gives a more accurate bound on the probability of error of ASD than the results available in the literature.
New Constructions of a Family of 2-Generator Quasi-Cyclic Two-Weight Codes and Related Codes
Venue: arXiv cs.IT 2007
Year: 2007

Based on cyclic simplex codes, a new construction of a family of 2-generator quasi-cyclic two-weight codes is given. New optimal binary quasi-cyclic [195, 8, 96], [210, 8, 104] and [240, 8, 120] codes, good QC ternary [195, 6, 126], [208, 6, 135], [221, 6, 144] codes are thus obtained. Furthermre, binary quasi-cyclic self-complementary codes are also constructed.
A Coding Theorem for a Class of Stationary Channels with Feedback
Venue: arXiv cs.IT 2007
Year: 2007

A coding theorem is proved for a class of stationary channels with feedback in which the output Y_n = f(X_{n-m}^n, Z_{n-m}^n) is the function of the current and past m symbols from the channel input X_n and the stationary ergodic channel noise Z_n. In particular, it is shown that the feedback capacity is equal to $$ \limp_{n\to\infty} \sup_{p(x^n||y^{n-1})} \frac{1}{n} I(X^n \to Y^n), $$ where I(X^n \to Y^n) = \sum_{i=1}^n I(X^i; Y_i|Y^{i-1}) denotes the Massey directed information from the channel input to the output, and the supremum is taken over all causally conditioned distributions p(x^n||y^{n-1}) = \prod_{i=1}^n p(x_i|x^{i-1},y^{i-1}). The main ideas of the proof are the Shannon strategy for coding with side information and a new elementary coding technique for the given channel model without feedback, which is in a sense dual to Gallager's lossy coding of stationary ergodic sources. A similar approach gives a simple alternative proof of coding theorems for finite state channels by Yang-Kavcic-Tatikonda, Chen-Berger, and Permuter-Weissman-Goldsmith.
Sending a Bivariate Gaussian Source over a Gaussian MAC with Feedback
Venue: arXiv cs.IT 2007
Year: 2007

We consider the problem of transmitting a bivariate Gaussian source over a two-user additive Gaussian multiple-access channel with feedback. Each of the transmitters observes one of the source components and tries to describe it to the common receiver. We are interested in the minimal mean squared error at which the receiver can reconstruct each of the source components. In the ``symmetric case'' we show that, below a certain signal-to-noise ratio threshold which is determined by the source correlation, feedback is useless and the minimal distortion is achieved by uncoded transmission. For the general case we give necessary conditions for the achievability of a distortion pair.
New ID Based Multi-Proxy Multi-Signcryption Scheme from Pairings
Venue: arXiv cs.CR 2007
Year: 2007

This paper presents an identity based multi-proxy multi-signcryption scheme from pairings. In this scheme a proxy signcrypter group could authorized as a proxy agent by the coopration of all members in the original signcryption group. Then the proxy signcryption can be generated by the cooperation of all the signcrypters in the authorized proxy signcrypter group on the behalf of the original signcrypter group. As compared to the scheme of Liu and Xiao, the proposed scheme provides public verifiability of the signature along with simplified key management.
On vocabulary size of grammar-based codes
Venue: arXiv cs.IT 2007
Year: 2007

We discuss inequalities holding between the vocabulary size, i.e., the number of distinct nonterminal symbols in a grammar-based compression for a string, and the excess length of the respective universal code, i.e., the code-based analog of algorithmic mutual information. The aim is to strengthen inequalities which were discussed in a weaker form in linguistics but shed some light on redundancy of efficiently computable codes. The main contribution of the paper is a construction of universal grammar-based codes for which the excess lengths can be bounded easily.
Precoding in Multiple-Antenna Broadcast Systems with a Probabilistic Viewpoint
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we investigate the minimum average transmit energy that can be obtained in multiple antenna broadcast systems with channel inversion technique. The achievable gain can be significantly higher than the conventional gains that are mentioned in methods like perturbation technique of Peel, et al. In order to obtain this gain, we introduce a Selective Mapping (SLM) technique (based on random coding arguments). We propose to implement the SLM method by using nested lattice codes in a trellis precoding framework.
Conjugate Gradient Projection Approach for Multi-Antenna Gaussian Broadcast Channels
Venue: arXiv cs.IT 2007
Year: 2007

It has been shown recently that the dirty-paper coding is the optimal strategy for maximizing the sum rate of multiple-input multiple-output Gaussian broadcast channels (MIMO BC). Moreover, by the channel duality, the nonconvex MIMO BC sum rate problem can be transformed to the convex dual MIMO multiple-access channel (MIMO MAC) problem with a sum power constraint. In this paper, we design an efficient algorithm based on conjugate gradient projection (CGP) to solve the MIMO BC maximum sum rate problem. Our proposed CGP algorithm solves the dual sum power MAC problem by utilizing the powerful concept of Hessian conjugacy. We also develop a rigorous algorithm to solve the projection problem. We show that CGP enjoys provable convergence, nice scalability, and great efficiency for large MIMO BC systems.
Non-binary Hybrid LDPC Codes: Structure, Decoding and Optimization
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we propose to study and optimize a very general class of LDPC codes whose variable nodes belong to finite sets with different orders. We named this class of codes Hybrid LDPC codes. Although efficient optimization techniques exist for binary LDPC codes and more recently for non-binary LDPC codes, they both exhibit drawbacks due to different reasons. Our goal is to capitalize on the advantages of both families by building codes with binary (or small finite set order) and non-binary parts in their factor graph representation. The class of Hybrid LDPC codes is obviously larger than existing types of codes, which gives more degrees of freedom to find good codes where the existing codes show their limits. We give two examples where hybrid LDPC codes show their interest.
On Four-group ML Decodable Distributed Space Time Codes for Cooperative Communication
Venue: arXiv cs.IT 2007
Year: 2007

A construction of a new family of distributed space time codes (DSTCs) having full diversity and low Maximum Likelihood (ML) decoding complexity is provided for the two phase based cooperative diversity protocols of Jing-Hassibi and the recently proposed Generalized Non-orthogonal Amplify and Forward (GNAF) protocol of Rajan et al. The salient feature of the proposed DSTCs is that they satisfy the extra constraints imposed by the protocols and are also four-group ML decodable which leads to significant reduction in ML decoding complexity compared to all existing DSTC constructions. Moreover these codes have uniform distribution of power among the relays as well as in time. Also, simulations results indicate that these codes perform better in comparison with the only known DSTC with the same rate and decoding complexity, namely the Coordinate Interleaved Orthogonal Design (CIOD). Furthermore, they perform very close to DSTCs from field extensions which have same rate but higher decoding complexity.
Distributed Space-Time Codes for Cooperative Networks with Partial CSI
Venue: arXiv cs.IT 2007
Year: 2007

Design criteria and full-diversity Distributed Space Time Codes (DSTCs) for the two phase transmission based cooperative diversity protocol of Jing-Hassibi and the Generalized Nonorthogonal Amplify and Forward (GNAF) protocol are reported, when the relay nodes are assumed to have knowledge of the phase component of the source to relay channel gains. It is shown that this under this partial channel state information (CSI), several well known space time codes for the colocated MIMO (Multiple Input Multiple Output) channel become amenable for use as DSTCs. In particular, the well known complex orthogonal designs, generalized coordinate interleaved orthogonal designs (GCIODs) and unitary weight single symbol decodable (UW-SSD) codes are shown to satisfy the required design constraints for DSTCs. Exploiting the relaxed code design constraints, we propose DSTCs obtained from Clifford Algebras which have low ML decoding complexity.
Asynchronous Distributed Searchlight Scheduling
Venue: arXiv cs.MA 2007
Year: 2007

This paper develops and compares two simple asynchronous distributed searchlight scheduling algorithms for multiple robotic agents in nonconvex polygonal environments. A searchlight is a ray emitted by an agent which cannot penetrate the boundary of the environment. A point is detected by a searchlight if and only if the point is on the ray at some instant. Targets are points which can move continuously with unbounded speed. The objective of the proposed algorithms is for the agents to coordinate the slewing (rotation about a point) of their searchlights in a distributed manner, i.e., using only local sensing and limited communication, such that any target will necessarily be detected in finite time. The first algorithm we develop, called the DOWSS (Distributed One Way Sweep Strategy), is a distributed version of a known algorithm described originally in 1990 by Sugihara et al \cite{KS-IS-MY:90}, but it can be very slow in clearing the entire environment because only one searchlight may slew at a time. In an effort to reduce the time to clear the environment, we develop a second algorithm, called the PTSS (Parallel Tree Sweep Strategy), in which searchlights sweep in parallel if guards are placed according to an environment partition belonging to a class we call PTSS partitions. Finally, we discuss how DOWSS and PTSS could be combined with with deployment, or extended to environments with holes.
Low SNR Capacity of Fading Channels -- MIMO and Delay Spread
Venue: arXiv cs.IT 2007
Year: 2007

Discrete-time Rayleigh fading multiple-input multiple-output (MIMO) channels are considered, with no channel state information at the transmitter and receiver. The fading is assumed to be correlated in time and independent from antenna to antenna. Peak and average transmit power constraints are imposed, either on the sum over antennas, or on each individual antenna. In both cases, an upper bound and an asymptotic lower bound, as the signal-to-noise ratio approaches zero, on the channel capacity are presented. The limit of normalized capacity is identified under the sum power constraints, and, for a subclass of channels, for individual power constraints. These results carry over to a SISO channel with delay spread (i.e. frequency selective fading).
The Multiplexing Gain of MIMO X-Channels with Partial Transmit Side-Information
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we obtain the scaling laws of the sum-rate capacity of a MIMO X-channel, a 2 independent sender, 2 independent receiver channel with messages from each transmitter to each receiver, at high signal to noise ratios (SNR). The X-channel has sparked recent interest in the context of cooperative networks and it encompasses the interference, multiple access, and broadcast channels as special cases. Here, we consider the case with partially cooperative transmitters in which only partial and asymmetric side-information is available at one of the transmitters. It is proved that when there are M antennas at all four nodes, the sum-rate scales like 2Mlog(SNR) which is in sharp contrast to [\lfloor 4M/3 \rfloor,4M/3]log(SNR) for non-cooperative X-channels \cite{maddah-ali,jafar_degrees}. This further proves that, in terms of sum-rate scaling at high SNR, partial side-information at one of the transmitters and full side-information at both transmitters are equivalent in the MIMO X-channel.
On using Tracer Driver for External Dynamic Process Observation
Venue: arXiv cs.PL 2007
Year: 2007

One is interested here in the observation of dynamic processes starting from the traces which they leave or those that one makes them produce. It is considered here that it should be possible to make several observations simultaneously, using a large variety of independently developed analyzers. For this purpose, we introduce the original notion of ``full trace'' to capture the idea that a process can be instrumented in such a way that it may broadcast all information which could ever be requested by any kind of observer. Each analyzer can then find in the full trace the data elements which it needs. This approach uses what has been called a "tracer driver" which completes the tracer and drives it to answer the requests of the analyzers. A tracer driver allows to restrict the flow of information and makes this approach tractable. On the other side, the potential size of a full trace seems to make the idea of full trace unrealistic. In this work we explore the consequences of this notion in term of potential efficiency, by analyzing the respective workloads between the (full) tracer and many different analyzers, all being likely run in true parallel environments. To illustrate this study, we use the example of the observation of the resolution of constraints systems (proof-tree, search-tree and propagation) using sophisticated visualization tools, as developed in the project OADymPPaC (2001-2004). The processes considered here are computer programs, but we believe the approach can be extended to many other kinds of processes.
Some Issues on Incremental Abstraction-Carrying Code
Venue: arXiv cs.PL 2007
Year: 2007

Abstraction-Carrying Code (ACC) has recently been proposed as a framework for proof-carrying code (PCC) in which the code supplier provides a program together with an abstraction (or abstract model of the program) whose validity entails compliance with a predefined safety policy. The abstraction thus plays the role of safety certificate and its generation (and validation) is carried out automatically by a fixed-point analyzer. Existing approaches for PCC are developed under the assumption that the consumer reads and validates the entire program w.r.t. the full certificate at once, in a non incremental way. In this abstract, we overview the main issues on incremental ACC. In particular, in the context of logic programming, we discuss both the generation of incremental certificates and the design of an incremental checking algorithm for untrusted updates of a (trusted) program, i.e., when a producer provides a modified version of a previously validated program. By update, we refer to any arbitrary change on a program, i.e., the extension of the program with new predicates, the deletion of existing predicates and the replacement of existing predicates by new versions for them. We also discuss how each kind of update affects the incremental extension in terms of accuracy and correctness.