title: Complexity of Networks

abstract: Network or graph structures are ubiquitous in the study of complex systems. Often, we are interested in complexity trends of these system as it evolves under some dynamic. An example might be looking at the complexity of a food web as species enter an ecosystem via migration or speciation, and leave via extinction. In this paper, a complexity measure of networks is proposed based on the {\em complexity is information content} paradigm. To apply this paradigm to any object, one must fix two things: a representation language, in which strings of symbols from some alphabet describe, or stand for the objects being considered; and a means of determining when two such descriptions refer to the same object. With these two things set, the information content of an object can be computed in principle from the number of equivalent descriptions describing a particular object. I propose a simple representation language for undirected graphs that can be encoded as a bitstring, and equivalence is a topological equivalence. I also present an algorithm for computing the complexity of an arbitrary undirected network.


title: Myopic Coding in Multiple Relay Channels

abstract: In this paper, we investigate achievable rates for data transmission from sources to sinks through multiple relay networks. We consider myopic coding, a constrained communication strategy in which each node has only a local view of the network, meaning that nodes can only transmit to and decode from neighboring nodes. We compare this with omniscient coding, in which every node has a global view of the network and all nodes can cooperate. Using Gaussian channels as examples, we find that when the nodes transmit at low power, the rates achievable with two-hop myopic coding are as large as that under omniscient coding in a five-node multiple relay channel and close to that under omniscient coding in a six-node multiple relay channel. These results suggest that we may do local coding and cooperation without compromising much on the transmission rate. Practically, myopic coding schemes are more robust to topology changes because encoding and decoding at a node are not affected when there are changes at remote nodes. Furthermore, myopic coding mitigates the high computational complexity and large buffer/memory requirements of omniscient coding.


title: Families of unitary matrices achieving full diversity

abstract: This paper presents an algebraic construction of families of unitary matrices that achieve full diversity. They are obtained as subsets of cyclic division algebras.


title: Proceedings of the 15th Workshop on Logic-based methods in Programming Environments WLPE'05 -- October 5, 2005 -- Sitges (Barcelona), Spain

abstract: This volume contains papers presented at WLPE 2005, 15th International Workshop on Logic-based methods in Programming Environments. The aim of the workshop is to provide an informal meeting for the researchers working on logic-based tools for development and analysis of programs. This year we emphasized two aspects: on one hand the presentation, pragmatics and experiences of tools for logic programming environments; on the other one, logic-based environmental tools for programming in general. The workshop took place in Sitges (Barcelona), Spain as a satellite workshop of the 21th International Conference on Logic Programming (ICLP 2005). This workshop continues the series of successful international workshops on logic programming environments held in Ohio, USA (1989), Eilat, Israel (1990), Paris, France (1991), Washington, USA (1992), Vancouver, Canada (1993), Santa Margherita Ligure, Italy (1994), Portland, USA (1995), Leuven, Belgium and Port Jefferson, USA (1997), Las Cruces, USA (1999), Paphos, Cyprus (2001), Copenhagen, Denmark (2002), Mumbai, India (2003) and Saint Malo, France (2004). We have received eight submissions (2 from France, 2 Spain-US cooperations, one Spain-Argentina cooperation, one from Japan, one from the United Kingdom and one Sweden-France cooperation). Program committee has decided to accept seven papers. This volume contains revised versions of the accepted papers. We are grateful to the authors of the papers, the reviewers and the members of the Program Committee for the help and fruitful discussions.


title: Re-visiting the One-Time Pad

abstract: In 1949, Shannon proved the perfect secrecy of the Vernam cryptographic system,also popularly known as the One-Time Pad (OTP). Since then, it has been believed that the perfectly random and uncompressible OTP which is transmitted needs to have a length equal to the message length for this result to be true. In this paper, we prove that the length of the transmitted OTP which actually contains useful information need not be compromised and could be less than the message length without sacrificing perfect secrecy. We also provide a new interpretation for the OTP encryption by treating the message bits as making True/False statements about the pad, which we define as a private-object. We introduce the paradigm of private-object cryptography where messages are transmitted by verifying statements about a secret-object. We conclude by suggesting the use of Formal Axiomatic Systems for investing N bits of secret.


title: A 3D RGB Axis-based Color-oriented Cryptography

abstract: In this document, a formal approach to encrypt, decrypt, transmit and receive information using colors is explored. A piece of information consists of set of symbols with a definite property imposed on the generating set. The symbols are usually encoded using ascii scheme. A linear to 3d transformation is presented. The change of axis from traditional xyz to rgb is highlighted and its effect are studied. A point in this new axis is then represented as a unique color and a vector or matrix is associated with it, making it amenable to standard vector or matrix operations. A formal notion on hybrid cryptography is introduced as the algorithm lies on the boundary of symmetric and asymmetric cryptography. No discussion is complete, without mentioning reference to communication aspects of secure information in a channel. Transmission scheme pertaining to light as carrier is introduced and studied. Key-exchanges do not come under the scope of current frame of document.


title: ZEUS - A Domain-Oriented Fact Comparison Based Authentication Protocol

abstract: In this paper, facts existing in different domains are explored, which are comparable by their end result. Properties of various domains and the facts that are part of such a unit are also presented, examples of comparison and methods of usage as means of zero-knowledge protocols are given, finally a zero-knowledge protocol based on afore-mentioned concept is given.


title: The Structure of Collaborative Tagging Systems

abstract: Collaborative tagging describes the process by which many users add metadata in the form of keywords to shared content. Recently, collaborative tagging has grown in popularity on the web, on sites that allow users to tag bookmarks, photographs and other content. In this paper we analyze the structure of collaborative tagging systems as well as their dynamical aspects. Specifically, we discovered regularities in user activity, tag frequencies, kinds of tags used, bursts of popularity in bookmarking and a remarkable stability in the relative proportions of tags within a given url. We also present a dynamical model of collaborative tagging that predicts these stable patterns and relates them to imitation and shared knowledge.


title: A General Framework for Codes Involving Redundancy Minimization

abstract: A framework with two scalar parameters is introduced for various problems of finding a prefix code minimizing a coding penalty function. The framework encompasses problems previously proposed by Huffman, Campbell, Nath, and Drmota and Szpankowski, shedding light on the relationships among these problems. In particular, Nath's range of problems can be seen as bridging the minimum average redundancy problem of Huffman with the minimum maximum pointwise redundancy problem of Drmota and Szpankowski. Using this framework, two linear-time Huffman-like algorithms are devised for the minimum maximum pointwise redundancy problem, the only one in the framework not previously solved with a Huffman-like algorithm. Both algorithms provide solutions common to this problem and a subrange of Nath's problems, the second algorithm being distinguished by its ability to find the minimum variance solution among all solutions common to the minimum maximum pointwise redundancy and Nath problems. Simple redundancy bounds are also presented.


title: Source Coding for Quasiarithmetic Penalties

abstract: Huffman coding finds a prefix code that minimizes mean codeword length for a given probability distribution over a finite number of items. Campbell generalized the Huffman problem to a family of problems in which the goal is to minimize not mean codeword length but rather a generalized mean known as a quasiarithmetic or quasilinear mean. Such generalized means have a number of diverse applications, including applications in queueing. Several quasiarithmetic-mean problems have novel simple redundancy bounds in terms of a generalized entropy. A related property involves the existence of optimal codes: For ``well-behaved'' cost functions, optimal codes always exist for (possibly infinite-alphabet) sources having finite generalized entropy. Solving finite instances of such problems is done by generalizing an algorithm for finding length-limited binary codes to a new algorithm for finding optimal binary codes for any quasiarithmetic mean with a convex cost function. This algorithm can be performed using quadratic time and linear space, and can be extended to other penalty functions, some of which are solvable with similar space and time complexity, and others of which are solvable with slightly greater complexity. This reduces the computational complexity of a problem involving minimum delay in a queue, allows combinations of previously considered problems to be optimized, and greatly expands the space of problems solvable in quadratic time and linear space. The algorithm can be extended for purposes such as breaking ties among possibly different optimal codes, as with bottom-merge Huffman coding.


title: On the Asymptotic Performance of Iterative Decoders for Product Codes

abstract: We consider hard-decision iterative decoders for product codes over the erasure channel, which employ repeated rounds of decoding rows and columns alternatingly. We derive the exact asymptotic probability of decoding failure as a function of the error-correction capabilities of the row and column codes, the number of decoding rounds, and the channel erasure probability. We examine both the case of codes capable of correcting a constant amount of errors, and the case of codes capable of correcting a constant fraction of their length.


title: High-performance BWT-based Encoders

abstract: In 1994, Burrows and Wheeler developed a data compression algorithm which performs significantly better than Lempel-Ziv based algorithms. Since then, a lot of work has been done in order to improve their algorithm, which is based on a reversible transformation of the input string, called BWT (the Burrows-Wheeler transformation). In this paper, we propose a compression scheme based on BWT, MTF (move-to-front coding), and a version of the algorithms presented in [Dragos Trinca, ITCC-2004].


title: Modelling the Eulerian Path Problem using a String Matching Framework

abstract: The well-known Eulerian path problem can be solved in polynomial time (more exactly, there exists a linear time algorithm for this problem). In this paper, we model the problem using a string matching framework, and then initiate an algorithmic study on a variant of this problem, called the (2,1)-STRING-MATCH problem (which is actually a generalization of the Eulerian path problem). Then, we present a polynomial-time algorithm for the (2,1)-STRING-MATCH problem, which is the most important result of this paper. Specifically, we get a lower bound of Omega(n), and an upper bound of O(n^{2}).


title: Special Cases of Encodings by Generalized Adaptive Codes

abstract: Adaptive (variable-length) codes associate variable-length codewords to symbols being encoded depending on the previous symbols in the input data string. This class of codes has been presented in [Dragos Trinca, cs.DS/0505007] as a new class of non-standard variable-length codes. Generalized adaptive codes (GA codes, for short) have been also presented in [Dragos Trinca, cs.DS/0505007] not only as a new class of non-standard variable-length codes, but also as a natural generalization of adaptive codes of any order. This paper is intended to continue developing the theory of variable-length codes by establishing several interesting connections between adaptive codes and other classes of codes. The connections are discussed not only from a theoretical point of view (by proving new results), but also from an applicative one (by proposing several applications). First, we prove that adaptive Huffman encodings and Lempel-Ziv encodings are particular cases of encodings by GA codes. Second, we show that any (n,1,m) convolutional code satisfying certain conditions can be modelled as an adaptive code of order m. Third, we describe a cryptographic scheme based on the connection between adaptive codes and convolutional codes, and present an insightful analysis of this scheme. Finally, we conclude by generalizing adaptive codes to (p,q)-adaptive codes, and discussing connections between adaptive codes and time-varying codes.


title: Modelling the EAH Data Compression Algorithm using Graph Theory

abstract: Adaptive codes associate variable-length codewords to symbols being encoded depending on the previous symbols in the input data string. This class of codes has been introduced in [Dragos Trinca, cs.DS/0505007] as a new class of non-standard variable-length codes. New algorithms for data compression, based on adaptive codes of order one, have been presented in [Dragos Trinca, ITCC-2004], where we have behaviorally shown that for a large class of input data strings, these algorithms substantially outperform the Lempel-Ziv universal data compression algorithm. EAH has been introduced in [Dragos Trinca, cs.DS/0505061], as an improved generalization of these algorithms. In this paper, we present a translation of the EAH algorithm into the graph theory.


title: Translating the EAH Data Compression Algorithm into Automata Theory

abstract: Adaptive codes have been introduced in [Dragos Trinca, cs.DS/0505007] as a new class of non-standard variable-length codes. These codes associate variable-length codewords to symbols being encoded depending on the previous symbols in the input data string. A new data compression algorithm, called EAH, has been introduced in [Dragos Trinca, cs.DS/0505061], where we have behaviorally shown that for a large class of input data strings, this algorithm substantially outperforms the well-known Lempel-Ziv universal data compression algorithm. In this paper, we translate the EAH encoder into automata theory.


title: Extending Prolog with Incomplete Fuzzy Information

abstract: Incomplete information is a problem in many aspects of actual environments. Furthermore, in many sceneries the knowledge is not represented in a crisp way. It is common to find fuzzy concepts or problems with some level of uncertainty. There are not many practical systems which handle fuzziness and uncertainty and the few examples that we can find are used by a minority. To extend a popular system (which many programmers are using) with the ability of combining crisp and fuzzy knowledge representations seems to be an interesting issue. Our first work (Fuzzy Prolog) was a language that models $\mathcal{B}([0,1])$-valued Fuzzy Logic. In the Borel algebra, $\mathcal{B}([0,1])$, truth value is represented using unions of intervals of real numbers. This work was more general in truth value representation and propagation than previous works. An interpreter for this language using Constraint Logic Programming over Real numbers (CLP(${\cal R}$)) was implemented and is available in the Ciao system. Now, we enhance our former approach by using default knowledge to represent incomplete information in Logic Programming. We also provide the implementation of this new framework. This new release of Fuzzy Prolog handles incomplete information, it has a complete semantics (the previous one was incomplete as Prolog) and moreover it is able to combine crisp and fuzzy logic in Prolog programs. Therefore, new Fuzzy Prolog is more expressive to represent real world. Fuzzy Prolog inherited from Prolog its incompleteness. The incorporation of default reasoning to Fuzzy Prolog removes this problem and requires a richer semantics which we discuss.


title: Summarizing Reports on Evolving Events; Part I: Linear Evolution

abstract: We present an approach for summarization from multiple documents which report on events that evolve through time, taking into account the different document sources. We distinguish the evolution of an event into linear and non-linear. According to our approach, each document is represented by a collection of messages which are then used in order to instantiate the cross-document relations that determine the summary content. The paper presents the summarization system that implements this approach through a case study on linear evolution.


title: Performance of PPM Multipath Synchronization in the Limit of Large Bandwidth

abstract: The acquisition, or synchronization, of the multipath profile for an ultrawideband pulse position modulation (PPM) communication systems is considered. Synchronization is critical for the proper operation of PPM based For the multipath channel, it is assumed that channel gains are known, but path delays are unknown. In the limit of large bandwidth, W, it is assumed that the number of paths, L, grows. The delay spread of the channel, M, is proportional to the bandwidth. The rate of growth of L versus M determines whether synchronization can occur. It is shown that if L/sqrt(M) --> 0, then the maximum likelihood synchronizer cannot acquire any of the paths and alternatively if L/M --> 0, the maximum likelihood synchronizer is guaranteed to miss at least one path.


title: Conference Key Agreement and Quantum Sharing of Classical Secrets with Noisy GHZ States

abstract: We propose a wide class of distillation schemes for multi-partite entangled states that are CSS-states. Our proposal provides not only superior efficiency, but also new insights on the connection between CSS-states and bipartite graph states. We then consider the applications of our distillation schemes for two cryptographic tasks--namely, (a) conference key agreement and (b) quantum sharing of classical secrets. In particular, we construct ``prepare-and-measure'' protocols. Also we study the yield of those protocols and the threshold value of the fidelity above which the protocols can function securely. Surprisingly, our protocols will function securely even when the initial state does not violate the standard Bell-inequalities for GHZ states. Experimental realization involving only bi-partite entanglement is also suggested.


title: Capacity of Ultra Wide Band Wireless Ad Hoc Networks

abstract: Throughput capacity is a critical parameter for the design and evaluation of ad-hoc wireless networks. Consider n identical randomly located nodes, on a unit area, forming an ad-hoc wireless network. Assuming a fixed per node transmission capability of T bits per second at a fixed range, it has been shown that the uniform throughput capacity per node r(n) is Theta((T)/(sqrt{n log n})), a decreasing function of node density n. However an alternate communication model may also be considered, with each node constrained to a maximum transmit power P_0 and capable of utilizing W Hz of bandwidth. Under the limiting case W rightarrow infinity, such as in Ultra Wide Band (UWB) networks, the uniform throughput per node is O ((n log n)^{(alpha-1}/2}) (upper bound) and Omega((n^{(alpha-1)/2})/((log n)^{(alpha +1)/2})) (achievable lower bound). These bounds demonstrate that throughput increases with node density $n$, in contrast to previously published results. This is the result of the large bandwidth, and the assumed power and rate adaptation, which alleviate interference. Thus, the effect of physical layer properties on the capacity of ad hoc wireless networks is demonstrated. Further, the promise of UWB as a physical layer technology for ad-hoc networks is justified.


title: On Multiple User Channels with Causal State Information at the Transmitters

abstract: We extend Shannon's result on the capacity of channels with state information to multiple user channels. More specifically, we characterize the capacity (region) of degraded broadcast channels and physically degraded relay channels where the channel state information is causally available at the transmitters. We also obtain inner and outer bounds on the capacity region for multiple access channels with causal state information at the transmitters.


title: Tightness of LP via Max-product Belief Propagation

abstract: We investigate the question of tightness of linear programming (LP) relaxation for finding a maximum weight independent set (MWIS) in sparse random weighted graphs. We show that an edge-based LP relaxation is asymptotically tight for Erdos-Renyi graph $G(n,c/n)$ for $c \leq 2e$ and random regular graph $G(n,r)$ for $r\leq 4$ when node weights are i.i.d. with exponential distribution of mean 1. We establish these results, through a precise relation between the tightness of LP relaxation and convergence of the max-product belief propagation algorithm. We believe that this novel method of understanding structural properties of combinatorial problems through properties of iterative procedure such as the max-product should be of interest in its own right.


title: An Explicit Construction of Universally Decodable Matrices

abstract: Universally decodable matrices can be used for coding purposes when transmitting over slow fading channels. These matrices are parameterized by positive integers $L$ and $n$ and a prime power $q$. Based on Pascal's triangle we give an explicit construction of universally decodable matrices for any non-zero integers $L$ and $n$ and any prime power $q$ where $L \leq q+1$. This is the largest set of possible parameter values since for any list of universally decodable matrices the value $L$ is upper bounded by $q+1$, except for the trivial case $n = 1$. For the proof of our construction we use properties of Hasse derivatives, and it turns out that our construction has connections to Reed-Solomon codes, Reed-Muller codes, and so-called repeated-root cyclic codes. Additionally, we show how universally decodable matrices can be modified so that they remain universally decodable matrices.


title: Search Process and Probabilistic Bifix Approach

abstract: An analytical approach to a search process is a mathematical prerequisite for digital synchronization acquisition analysis and optimization. A search is performed for an arbitrary set of sequences within random but not equiprobable L-ary data. This paper derives in detail an expression for probability distribution function, from which other statistical parameters - expected value and variance - can be obtained. The probabilistic nature of (cross-) bifix indicators is shown and application examples are outlined, ranging beyond the usual telecommunication field.


title: A primer on Answer Set Programming

abstract: A introduction to the syntax and Semantics of Answer Set Programming intended as an handout to [under]graduate students taking Artificial Intlligence or Logic Programming classes.


title: Maximum Weight Matching via Max-Product Belief Propagation

abstract: Max-product "belief propagation" is an iterative, local, message-passing algorithm for finding the maximum a posteriori (MAP) assignment of a discrete probability distribution specified by a graphical model. Despite the spectacular success of the algorithm in many application areas such as iterative decoding, computer vision and combinatorial optimization which involve graphs with many cycles, theoretical results about both correctness and convergence of the algorithm are known in few cases (Weiss-Freeman Wainwright, Yeddidia-Weiss-Freeman, Richardson-Urbanke}. In this paper we consider the problem of finding the Maximum Weight Matching (MWM) in a weighted complete bipartite graph. We define a probability distribution on the bipartite graph whose MAP assignment corresponds to the MWM. We use the max-product algorithm for finding the MAP of this distribution or equivalently, the MWM on the bipartite graph. Even though the underlying bipartite graph has many short cycles, we find that surprisingly, the max-product algorithm always converges to the correct MAP assignment as long as the MAP assignment is unique. We provide a bound on the number of iterations required by the algorithm and evaluate the computational cost of the algorithm. We find that for a graph of size $n$, the computational cost of the algorithm scales as $O(n^3)$, which is the same as the computational cost of the best known algorithm. Finally, we establish the precise relation between the max-product algorithm and the celebrated {\em auction} algorithm proposed by Bertsekas. This suggests possible connections between dual algorithm and max-product algorithm for discrete optimization problems.


title: Investigations of Process Damping Forces in Metal Cutting

abstract: Using finite element software developed for metal cutting by Third Wave Systems we investigate the forces involved in chatter, a self-sustained oscillation of the cutting tool. The phenomena is decomposed into a vibrating tool cutting a flat surface work piece, and motionless tool cutting a work piece with a wavy surface. While cutting the wavy surface, the shearplane was seen to oscillate in advance of the oscillation of the depth of cut, as were the cutting, thrust, and shear plane forces. The vibrating tool was used to investigate process damping through the interaction of the relief face of the tool and the workpiece. Crushing forces are isolated and compared to the contact length between the tool and workpiece. We found that the wavelength dependence of the forces depended on the relative size of the wavelength to the length of the relief face of the tool. The results indicate that the damping force from crushing will be proportional to the cutting speed for short tools, and inversely proportional for long tools.


title: Corpus-based Learning of Analogies and Semantic Relations

abstract: We present an algorithm for learning from unlabeled text, based on the Vector Space Model (VSM) of information retrieval, that can solve verbal analogy questions of the kind found in the SAT college entrance exam. A verbal analogy has the form A:B::C:D, meaning "A is to B as C is to D"; for example, mason:stone::carpenter:wood. SAT analogy questions provide a word pair, A:B, and the problem is to select the most analogous word pair, C:D, from a set of five choices. The VSM algorithm correctly answers 47% of a collection of 374 college-level analogy questions (random guessing would yield 20% correct; the average college-bound senior high school student answers about 57% correctly). We motivate this research by applying it to a difficult problem in natural language processing, determining semantic relations in noun-modifier pairs. The problem is to classify a noun-modifier pair, such as "laser printer", according to the semantic relation between the noun (printer) and the modifier (laser). We use a supervised nearest-neighbour algorithm that assigns a class to a given noun-modifier pair by finding the most analogous noun-modifier pair in the training data. With 30 classes of semantic relations, on a collection of 600 labeled noun-modifier pairs, the learning algorithm attains an F value of 26.5% (random guessing: 3.3%). With 5 classes of semantic relations, the F value is 43.2% (random: 20%). The performance is state-of-the-art for both verbal analogies and noun-modifier relations.


title: A Generalised Hadamard Transform

abstract: A Generalised Hadamard Transform for multi-phase or multilevel signals is introduced, which includes the Fourier, Generalised, Discrete Fourier, Walsh-Hadamard and Reverse Jacket Transforms. The jacket construction is formalised and shown to admit a tensor product decomposition. Primary matrices under this decomposition are identified. New examples of primary jacket matrices of orders 8 and 12 are presented.


title: A Tracer Driver for Versatile Dynamic Analyses of Constraint Logic Programs

abstract: Programs with constraints are hard to debug. In this paper, we describe a general architecture to help develop new debugging tools for constraint programming. The possible tools are fed by a single general-purpose tracer. A tracer-driver is used to adapt the actual content of the trace, according to the needs of the tool. This enables the tools and the tracer to communicate in a client-server scheme. Each tool describes its needs of execution data thanks to event patterns. The tracer driver scrutinizes the execution according to these event patterns and sends only the data that are relevant to the connected tools. Experimental measures show that this approach leads to good performance in the context of constraint logic programming, where a large variety of tools exists and the trace is potentially huge.


title: An Improved Non-Termination Criterion for Binary Constraint Logic Programs

abstract: On one hand, termination analysis of logic programs is now a fairly established research topic within the logic programming community. On the other hand, non-termination analysis seems to remain a much less attractive subject. If we divide this line of research into two kinds of approaches: dynamic versus static analysis, this paper belongs to the latter. It proposes a criterion for detecting non-terminating atomic queries with respect to binary CLP clauses, which strictly generalizes our previous works on this subject. We give a generic operational definition and a logical form of this criterion. Then we show that the logical form is correct and complete with respect to the operational definition.


title: New Upper Bounds on A(n,d)

abstract: Upper bounds on the maximum number of codewords in a binary code of a given length and minimum Hamming distance are considered. New bounds are derived by a combination of linear programming and counting arguments. Some of these bounds improve on the best known analytic bounds. Several new record bounds are obtained for codes with small lengths.


title: Proving or Disproving likely Invariants with Constraint Reasoning

abstract: A program invariant is a property that holds for every execution of the program. Recent work suggest to infer likely-only invariants, via dynamic analysis. A likely invariant is a property that holds for some executions but is not guaranteed to hold for all executions. In this paper, we present work in progress addressing the challenging problem of automatically verifying that likely invariants are actual invariants. We propose a constraint-based reasoning approach that is able, unlike other approaches, to both prove or disprove likely invariants. In the latter case, our approach provides counter-examples. We illustrate the approach on a motivating example where automatically generated likely invariants are verified.


title: Enhancing the Alloy Analyzer with Patterns of Analysis

abstract: Formal techniques have been shown to be useful in the development of correct software. But the level of expertise required of practitioners of these techniques prohibits their widespread adoption. Formal techniques need to be tailored to the commercial software developer. Alloy is a lightweight specification language supported by the Alloy Analyzer (AA), a tool based on off-the-shelf SAT technology. The tool allows a user to check interactively whether given properties are consistent or valid with respect to a high-level specification, providing an environment in which the correctness of such a specification may be established. However, Alloy is not particularly suited to expressing program specifications and the feedback provided by AA can be misleading where the specification under analysis or the property being checked contains inconsistencies. In this paper, we address these two shortcomings. Firstly, we present a lightweight language called "Loy", tailored to the specification of object-oriented programs. An encoding of Loy into Alloy is provided so that AA can be used for automated analysis of Loy program specifications. Secondly, we present some "patterns of analysis" that guide a developer through the analysis of a Loy specification in order to establish its correctness before implementation.


title: Relations between semantic security and indistinguishability against cpa, non-adaptive cca and adaptive cca in comparison based framework

abstract: In this paper we try to unify the frameworks of definitions of semantic security, indistinguishability and non-malleability by defining semantic security in comparison based framework. This facilitates the study of relations among these goals against different attack models and makes the proof of the equivalence of semantic security and indistinguishability easier and more understandable. Besides, our proof of the equivalence of semantic security and indistinguishability does not need any intermediate goals such as non devidability to change the definition framework.


title: A Generic Framework for the Analysis and Specialization of Logic Programs

abstract: The relationship between abstract interpretation and partial deduction has received considerable attention and (partial) integrations have been proposed starting from both the partial deduction and abstract interpretation perspectives. In this work we present what we argue is the first fully described generic algorithm for efficient and precise integration of abstract interpretation and partial deduction. Taking as starting point state-of-the-art algorithms for context-sensitive, polyvariant abstract interpretation and (abstract) partial deduction, we present an algorithm which combines the best of both worlds. Key ingredients include the accurate success propagation inherent to abstract interpretation and the powerful program transformations achievable by partial deduction. In our algorithm, the calls which appear in the analysis graph are not analyzed w.r.t. the original definition of the procedure but w.r.t. specialized definitions of these procedures. Such specialized definitions are obtained by applying both unfolding and abstract executability. Our framework is parametric w.r.t. different control strategies and abstract domains. Different combinations of such parameters correspond to existing algorithms for program analysis and specialization. Simultaneously, our approach opens the door to the efficient computation of strictly more precise results than those achievable by each of the individual techniques. The algorithm is now one of the key components of the CiaoPP analysis and specialization system.


title: A study of set-sharing analysis via cliques

abstract: We study the problem of efficient, scalable set-sharing analysis of logic programs. We use the idea of representing sharing information as a pair of abstract substitutions, one of which is a worst-case sharing representation called a clique set, which was previously proposed for the case of inferring pair-sharing. We use the clique-set representation for (1) inferring actual set-sharing information, and (2) analysis within a top-down framework. In particular, we define the abstract functions required by standard top-down analyses, both for sharing alone and also for the case of including freeness in addition to sharing. Our experimental evaluation supports the conclusion that, for inferring set-sharing, as it was the case for inferring pair-sharing, precision losses are limited, while useful efficiency gains are obtained. At the limit, the clique-set representation allowed analyzing some programs that exceeded memory capacity using classical sharing representations.


title: Asymptotically fast polynomial matrix algorithms for multivariable systems

abstract: We present the asymptotically fastest known algorithms for some basic problems on univariate polynomial matrices: rank, nullspace, determinant, generic inverse, reduced form. We show that they essentially can be reduced to two computer algebra techniques, minimal basis computations and matrix fraction expansion/reconstruction, and to polynomial matrix multiplication. Such reductions eventually imply that all these problems can be solved in about the same amount of time as polynomial matrix multiplication.


title: A Family of Binary Sequences with Optimal Correlation Property and Large Linear Span

abstract: A family of binary sequences is presented and proved to have optimal correlation property and large linear span. It includes the small set of Kasami sequences, No sequence set and TN sequence set as special cases. An explicit lower bound expression on the linear span of sequences in the family is given. With suitable choices of parameters, it is proved that the family has exponentially larger linear spans than both No sequences and TN sequences. A class of ideal autocorrelation sequences is also constructed and proved to have large linear span.


title: New Sequence Sets with Zero-Correlation Zone

abstract: A method for constructing sets of sequences with zero-correlation zone (ZCZ sequences) and sequence sets with low cross correlation is proposed. The method is to use families of short sequences and complete orthogonal sequence sets to derive families of long sequences with desired correlation properties. It is a unification of works of Matsufuji and Torii \emph{et al.}, and there are more choices of parameters of sets for our method. In particular, ZCZ sequence sets generated by the method can achieve a related ZCZ bound. Furthermore, the proposed method can be utilized to derive new ZCZ sets with both longer ZCZ and larger set size from known ZCZ sets. These sequence sets are applicable in broadband satellite IP networks.


title: Quantum Algorithm Processors to Reveal Hamiltonian Cycles

abstract: Quantum computer versus quantum algorithm processor in CMOS are compared to find (in parallel) all Hamiltonian cycles in a graph with m edges and n vertices, each represented by k bits. A quantum computer uses quantum states analogous to CMOS registers. With efficient initialization, number of CMOS registers is proportional to (n-1)! Number of qubits in a quantum computer is approximately proportional to kn+2mn in the approach below. Using CMOS, the bits per register is about proportional to kn, which is less since bits can be irreversibly reset. In either concept, number of gates, or operations to identify Hamiltonian cycles is proportional to kmn. However, a quantum computer needs an additional exponentially large number of operations to accomplish a probabilistic readout. In contrast, CMOS is deterministic and readout is comparable to ordinary memory.


title: Long-term neuronal behavior caused by two synaptic modification mechanisms

abstract: We report the first results of simulating the coupling of neuronal, astrocyte, and cerebrovascular activity. It is suggested that the dynamics of the system is different from systems that only include neurons. In the neuron-vascular coupling, distribution of synapse strengths affects neuronal behavior and thus balance of the blood flow; oscillations are induced in the neuron-to-astrocyte coupling.


title: Unified Theory of Source Coding: Part I -- Two Terminal Problems

abstract: Since the publication of Shannon's theory of one terminal source coding, a number of interesting extensions have been derived by researchers such as Slepian-Wolf, Wyner, Ahlswede-K\"{o}rner, Wyner-Ziv and Berger-Yeung. Specifically, the achievable rate or rate-distortion region has been described by a first order information-theoretic functional of the source statistics in each of the above cases. At the same time several problems have also remained unsolved. Notable two terminal examples include the joint distortion problem, where both sources are reconstructed under a combined distortion criterion, as well as the partial side information problem, where one source is reconstructed under a distortion criterion using information about the other (side information) available at a certain rate (partially). In this paper we solve both of these open problems. Specifically, we give an infinite order description of the achievable rate-distortion region in each case. In our analysis we set the above problems in a general framework and formulate a unified methodology that solves not only the problems at hand but any two terminal problem with noncooperative encoding. The key to such unification is held by a fundamental source coding principle which we derive by extending the typicality arguments of Shannon and Wyner-Ziv. Finally, we demonstrate the expansive scope of our technique by re-deriving known coding theorems. We shall observe that our infinite order descriptions simplify to the expected first order in the known special cases.


title: Unified Theory of Source Coding: Part II -- Multiterminal Problems

abstract: In the first paper of this two part communication, we solved in a unified framework a variety of two terminal source coding problems with noncooperative encoders, thereby consolidating works of Shannon, Slepian-Wolf, Wyner, Ahlswede-K\"{o}rner, Wyner-Ziv, Berger {\em et al.} and Berger-Yeung. To achieve such unification we made use of a fundamental principle that dissociates bulk of the analysis from the distortion criterion at hand (if any) and extends the typicality arguments of Shannon and Wyner-Ziv. In this second paper, we generalize the fundamental principle for any number of sources and on its basis exhaustively solve all multiterminal source coding problems with noncooperative encoders and one decoder. The distortion criteria, when applicable, are required to apply to single letters and be bounded. Our analysis includes cases where side information is, respectively, partially available, completely available and altogether unavailable at the decoder. As seen in our first paper, the achievable regions permit infinite order information-theoretic descriptions. We also show that the entropy-constrained multiterminal estimation problem can be solved as a special case of our theory.


title: Iterative Algorithm for Finding Frequent Patterns in Transactional Databases

abstract: A high-performance algorithm for searching for frequent patterns (FPs) in transactional databases is presented. The search for FPs is carried out by using an iterative sieve algorithm by computing the set of enclosed cycles. In each inner cycle of level FPs composed of elements are generated. The assigned number of enclosed cycles (the parameter of the problem) defines the maximum length of the desired FPs. The efficiency of the algorithm is produced by (i) the extremely simple logical searching scheme, (ii) the avoidance of recursive procedures, and (iii) the usage of only one-dimensional arrays of integers.


title: How Good is Phase-Shift Keying for Peak-Limited Rayleigh Fading Channels in the Low-SNR Regime?

abstract: This paper investigates the achievable information rate of phase-shift keying (PSK) over frequency non-selective Rayleigh fading channels without channel state information (CSI). The fading process exhibits general temporal correlation characterized by its spectral density function. We consider both discrete-time and continuous-time channels, and find their asymptotics at low signal-to-noise ratio (SNR). Compared to known capacity upper bounds under peak constraints, these asymptotics usually lead to negligible rate loss in the low-SNR regime for slowly time-varying fading channels. We further specialize to case studies of Gauss-Markov and Clarke's fading models.


title: Streaming and Sublinear Approximation of Entropy and Information Distances

abstract: In many problems in data mining and machine learning, data items that need to be clustered or classified are not points in a high-dimensional space, but are distributions (points on a high dimensional simplex). For distributions, natural measures of distance are not the $\ell_p$ norms and variants, but information-theoretic measures like the Kullback-Leibler distance, the Hellinger distance, and others. Efficient estimation of these distances is a key component in algorithms for manipulating distributions. Thus, sublinear resource constraints, either in time (property testing) or space (streaming) are crucial. We start by resolving two open questions regarding property testing of distributions. Firstly, we show a tight bound for estimating bounded, symmetric f-divergences between distributions in a general property testing (sublinear time) framework (the so-called combined oracle model). This yields optimal algorithms for estimating such well known distances as the Jensen-Shannon divergence and the Hellinger distance. Secondly, we close a $(\log n)/H$ gap between upper and lower bounds for estimating entropy $H$ in this model. In a stream setting (sublinear space), we give the first algorithm for estimating the entropy of a distribution. Our algorithm runs in polylogarithmic space and yields an asymptotic constant factor approximation scheme. We also provide other results along the space/time/approximation tradeoff curve.


title: On Algorithms and Complexity for Sets with Cardinality Constraints

abstract: Typestate systems ensure many desirable properties of imperative programs, including initialization of object fields and correct use of stateful library interfaces. Abstract sets with cardinality constraints naturally generalize typestate properties: relationships between the typestates of objects can be expressed as subset and disjointness relations on sets, and elements of sets can be represented as sets of cardinality one. Motivated by these applications, this paper presents new algorithms and new complexity results for constraints on sets and their cardinalities. We study several classes of constraints and demonstrate a trade-off between their expressive power and their complexity. Our first result concerns a quantifier-free fragment of Boolean Algebra with Presburger Arithmetic. We give a nondeterministic polynomial-time algorithm for reducing the satisfiability of sets with symbolic cardinalities to constraints on constant cardinalities, and give a polynomial-space algorithm for the resulting problem. In a quest for more efficient fragments, we identify several subclasses of sets with cardinality constraints whose satisfiability is NP-hard. Finally, we identify a class of constraints that has polynomial-time satisfiability and entailment problems and can serve as a foundation for efficient program analysis.


title: Coding Schemes for Line Networks

abstract: We consider a simple network, where a source and destination node are connected with a line of erasure channels. It is well known that in order to achieve the min-cut capacity, the intermediate nodes are required to process the information. We propose coding schemes for this setting, and discuss each scheme in terms of complexity, delay, achievable rate, memory requirement, and adaptability to unknown channel parameters. We also briefly discuss how these schemes can be extended to more general networks.


title: A Sorting Algorithm Based on Calculation

abstract: This article introduces an adaptive sorting algorithm that can relocate elements accurately by substituting their values into a function which we name it the guessing function. We focus on building this function which is the mapping relationship between record values and their corresponding sorted locations essentially. The time complexity of this algorithm O(n),when records distributed uniformly. Additionally, similar approach can be used in the searching algorithm.


title: A Closed-Form Solution for the Finite Length Constant Modulus Receiver

abstract: In this paper, a closed-form solution minimizing the Godard or Constant Modulus (CM) cost function under the practical conditions of finite SNR and finite equalizer length is derived. While previous work has been reported by Zeng et al., IEEE Trans. Information Theory. 1998, to establish the link between the constant modulus and Wiener receivers, we show that under the Gaussian approximation of intersymbol interference at the output of the equalizer, the CM finite-length receiver is equivalent to the nonblind MMSE equalizer up to a complex gain factor. Some simulation results are provided to support the Gaussian approximation assumption.


title: On context-tree prediction of individual sequences

abstract: Motivated by the evident success of context-tree based methods in lossless data compression, we explore, in this paper, methods of the same spirit in universal prediction of individual sequences. By context-tree prediction, we refer to a family of prediction schemes, where at each time instant $t$, after having observed all outcomes of the data sequence $x_1,...,x_{t-1}$, but not yet $x_t$, the prediction is based on a ``context'' (or a state) that consists of the $k$ most recent past outcomes $x_{t-k},...,x_{t-1}$, where the choice of $k$ may depend on the contents of a possibly longer, though limited, portion of the observed past, $x_{t-k_{\max}},...x_{t-1}$. This is different from the study reported in [1], where general finite-state predictors as well as ``Markov'' (finite-memory) predictors of fixed order, were studied in the regime of individual sequences. Another important difference between this study and [1] is the asymptotic regime. While in [1], the resources of the predictor (i.e., the number of states or the memory size) were kept fixed regardless of the length $N$ of the data sequence, here we investigate situations where the number of contexts or states is allowed to grow concurrently with $N$. We are primarily interested in the following fundamental question: What is the critical growth rate of the number of contexts, below which the performance of the best context-tree predictor is still universally achievable, but above which it is not? We show that this critical growth rate is linear in $N$. In particular, we propose a universal context-tree algorithm that essentially achieves optimum performance as long as the growth rate is sublinear, and show that, on the other hand, this is impossible in the linear case.


title: Mapping DEVS Models onto UML Models

abstract: Discrete event simulation specification (DEVS) is a formalism designed to describe both discrete state and continuous state systems. It is a powerful abstract mathematical notation. However, until recently it lacked proper graphical representation, which made computer simulation of DEVS models a challenging issue. Unified modeling language (UML) is a multipurpose graphical modeling language, a de-facto industrial modeling standard. There exist several commercial and open-source UML editors and code generators. Most of them can save UML models in XML-based XMI files ready for further automated processing. In this paper, we propose a mapping of DEVS models onto UML state and component diagrams. This mapping may lead to an eventual unification of the two modeling formalisms, combining the abstractness of DEVS and expressive power and ``computer friendliness'' of the UML.


title: Temporal Phylogenetic Networks and Logic Programming

abstract: The concept of a temporal phylogenetic network is a mathematical model of evolution of a family of natural languages. It takes into account the fact that languages can trade their characteristics with each other when linguistic communities are in contact, and also that a contact is only possible when the languages are spoken at the same time. We show how computational methods of answer set programming and constraint logic programming can be used to generate plausible conjectures about contacts between prehistoric linguistic communities, and illustrate our approach by applying it to the evolutionary history of Indo-European languages. To appear in Theory and Practice of Logic Programming (TPLP).


title: A Fresh Look at the Reliability of Long-term Digital Storage

abstract: Many emerging Web services, such as email, photo sharing, and web site archives, need to preserve large amounts of quickly-accessible data indefinitely into the future. In this paper, we make the case that these applications' demands on large scale storage systems over long time horizons require us to re-evaluate traditional storage system designs. We examine threats to long-lived data from an end-to-end perspective, taking into account not just hardware and software faults but also faults due to humans and organizations. We present a simple model of long-term storage failures that helps us reason about the various strategies for addressing these threats in a cost-effective manner. Using this model we show that the most important strategies for increasing the reliability of long-term storage are detecting latent faults quickly, automating fault repair to make it faster and cheaper, and increasing the independence of data replicas.


title: Point Process Models of 1/f Noise and Internet Traffic

abstract: We present a simple model reproducing the long-range autocorrelations and the power spectrum of the web traffic. The model assumes the traffic as Poisson flow of files with size distributed according to the power-law. In this model the long-range autocorrelations are independent of the network properties as well as of inter-packet time distribution.


title: Planning with Preferences using Logic Programming

abstract: We present a declarative language, PP, for the high-level specification of preferences between possible solutions (or trajectories) of a planning problem. This novel language allows users to elegantly express non-trivial, multi-dimensional preferences and priorities over such preferences. The semantics of PP allows the identification of most preferred trajectories for a given goal. We also provide an answer set programming implementation of planning problems with PP preferences.


title: Decompositions of graphs of functions and efficient iterations of lookup tables

abstract: We show that every function f implemented as a lookup table can be implemented such that the computational complexity of evaluating f^m(x) is small, independently of m and x. The implementation only increases the storage space by a small_constant_ factor.


title: Asymptotic Behavior of Error Exponents in the Wideband Regime

abstract: In this paper, we complement Verd\'{u}'s work on spectral efficiency in the wideband regime by investigating the fundamental tradeoff between rate and bandwidth when a constraint is imposed on the error exponent. Specifically, we consider both AWGN and Rayleigh-fading channels. For the AWGN channel model, the optimal values of $R_z(0)$ and $\dot{R_z}(0)$ are calculated, where $R_z(1/B)$ is the maximum rate at which information can be transmitted over a channel with bandwidth $B/2$ when the error-exponent is constrained to be greater than or equal to $z.$ Based on this calculation, we say that a sequence of input distributions is near optimal if both $R_z(0)$ and $\dot{R_z}(0)$ are achieved. We show that QPSK, a widely-used signaling scheme, is near-optimal within a large class of input distributions for the AWGN channel. Similar results are also established for a fading channel where full CSI is available at the receiver.


title: Component Based Programming in Scientific Computing: The Viable Approach

abstract: Computational scientists are facing a new era where the old ways of developing and reusing code have to be left behind and a few daring steps are to be made towards new horizons. The present work analyzes the needs that drive this change, the factors that contribute to the inertia of the community and slow the transition, the status and perspective of present attempts, the principle, practical and technical problems that are to be addressed in the short and long run.


title: COMODI: Architecture for a Component-Based Scientific Computing System

abstract: The COmputational MODule Integrator (COMODI) is an initiative aiming at a component based framework, component developer tool and component repository for scientific computing. We identify the main ingredients to a solution that would be sufficiently appealing to scientists and engineers to consider alternatives to their deeply rooted programming traditions. The overall structure of the complete solution is sketched with special emphasis on the Component Developer Tool standing at the basis of COMODI.


title: Precoloring co-Meyniel graphs

abstract: The pre-coloring extension problem consists, given a graph $G$ and a subset of nodes to which some colors are already assigned, in finding a coloring of $G$ with the minimum number of colors which respects the pre-coloring assignment. This can be reduced to the usual coloring problem on a certain contracted graph. We prove that pre-coloring extension is polynomial for complements of Meyniel graphs. We answer a question of Hujter and Tuza by showing that ``PrExt perfect'' graphs are exactly the co-Meyniel graphs, which also generalizes results of Hujter and Tuza and of Hertz. Moreover we show that, given a co-Meyniel graph, the corresponding contracted graph belongs to a restricted class of perfect graphs (``co-Artemis'' graphs, which are ``co-perfectly contractile'' graphs), whose perfectness is easier to establish than the strong perfect graph theorem. However, the polynomiality of our algorithm still depends on the ellipsoid method for coloring perfect graphs.


title: Combining Structured Corporate Data and Document Content to Improve Expertise Finding

abstract: In this paper, we present an algorithm for automatically building expertise evidence for finding experts within an organization by combining structured corporate information with different content. We also describe our test data collection and our evaluation method. Evaluation of the algorithm shows that using organizational structure leads to a significant improvement in the precision of finding an expert. Furthermore we evaluate the impact of using different data sources on the quality of the results and conclude that Expert Finding is not a "one engine fits all" solution. It requires an analysis of the information space into which a solution will be placed and the appropriate selection and weighting scheme of the data sources.


title: Optimal space-time codes for the MIMO amplify-and-forward cooperative channel

abstract: In this work, we extend the non-orthogonal amplify-and-forward (NAF) cooperative diversity scheme to the MIMO channel. A family of space-time block codes for a half-duplex MIMO NAF fading cooperative channel with N relays is constructed. The code construction is based on the non-vanishing determinant criterion (NVD) and is shown to achieve the optimal diversity-multiplexing tradeoff (DMT) of the channel. We provide a general explicit algebraic construction, followed by some examples. In particular, in the single relay case, it is proved that the Golden code and the 4x4 Perfect code are optimal for the single-antenna and two-antenna case, respectively. Simulation results reveal that a significant gain (up to 10dB) can be obtained with the proposed codes, especially in the single-antenna case.


title: Non-Data-Aided Parameter Estimation in an Additive White Gaussian Noise Channel

abstract: Non-data-aided (NDA) parameter estimation is considered for binary-phase-shift-keying transmission in an additive white Gaussian noise channel. Cramer-Rao lower bounds (CRLBs) for signal amplitude, noise variance, channel reliability constant and bit-error rate are derived and it is shown how these parameters relate to the signal-to-noise ratio (SNR). An alternative derivation of the iterative maximum likelihood (ML) SNR estimator is presented together with a novel, low complexity NDA SNR estimator. The performance of the proposed estimator is compared to previously suggested estimators and the CRLB. The results show that the proposed estimator performs close to the iterative ML estimator at significantly lower computational complexity.


title: Joint Equalization and Decoding for Nonlinear Two-Dimensional Intersymbol Interference Channels with Application to Optical Storage

abstract: An algorithm that performs joint equalization and decoding for nonlinear two-dimensional intersymbol interference channels is presented. The algorithm performs sum-product message-passing on a factor graph that represents the underlying system. The two-dimensional optical storage (TWODOS) technology is an example of a system with nonlinear two-dimensional intersymbol interference. Simulations for the nonlinear channel model of TWODOS show significant improvement in performance over uncoded performance. Noise tolerance thresholds for the algorithm for the TWODOS channel, computed using density evolution, are also presented and accurately predict the limiting performance of the algorithm as the codeword length increases.


title: Joint Equalization and Decoding for Nonlinear Two-Dimensional Intersymbol Interference Channels

abstract: An algorithm that performs joint equalization and decoding for channels with nonlinear two-dimensional intersymbol interference is presented. The algorithm performs sum-product message-passing on a factor graph that represents the underlying system. The two-dimensional optical storage (TwoDOS) technology is an example of a system with nonlinear two-dimensional intersymbol interference. Simulations for the nonlinear channel model of TwoDOS show significant improvement in performance over uncoded performance. Noise tolerance thresholds for the TwoDOS channel computed using density evolution are also presented.


title: Minimum Mean-Square-Error Equalization using Priors for Two-Dimensional Intersymbol Interference

abstract: Joint equalization and decoding schemes are described for two-dimensional intersymbol interference (ISI) channels. Equalization is performed using the minimum mean-square-error (MMSE) criterion. Low-density parity-check codes are used for error correction. The MMSE schemes are the extension of those proposed by Tuechler et al. (2002) for one-dimensional ISI channels. Extrinsic information transfer charts, density evolution, and bit-error rate versus signal-to-noise ratio curves are used to study the performance of the schemes.


title: Clustering Mixed Numeric and Categorical Data: A Cluster Ensemble Approach

abstract: Clustering is a widely used technique in data mining applications for discovering patterns in underlying data. Most traditional clustering algorithms are limited to handling datasets that contain either numeric or categorical attributes. However, datasets with mixed types of attributes are common in real life data mining applications. In this paper, we propose a novel divide-and-conquer technique to solve this problem. First, the original mixed dataset is divided into two sub-datasets: the pure categorical dataset and the pure numeric dataset. Next, existing well established clustering algorithms designed for different types of datasets are employed to produce corresponding clusters. Last, the clustering results on the categorical and numeric dataset are combined as a categorical dataset, on which the categorical data clustering algorithm is used to get the final clusters. Our contribution in this paper is to provide an algorithm framework for the mixed attributes clustering problem, in which existing clustering algorithms can be easily integrated, the capabilities of different kinds of clustering algorithms and characteristics of different types of datasets could be fully exploited. Comparisons with other clustering algorithms on real life datasets illustrate the superiority of our approach.


title: Kriging Scenario For Capital Markets

abstract: An introduction to numerical statistics.


title: On the variational distance of independently repeated experiments

abstract: Let P and Q be two probability distributions which differ only for values with non-zero probability. We show that the variational distance between the n-fold product distributions P^n and Q^n cannot grow faster than the square root of n.


title: Density Evolution for Asymmetric Memoryless Channels

abstract: Density evolution is one of the most powerful analytical tools for low-density parity-check (LDPC) codes and graph codes with message passing decoding algorithms. With channel symmetry as one of its fundamental assumptions, density evolution (DE) has been widely and successfully applied to different channels, including binary erasure channels, binary symmetric channels, binary additive white Gaussian noise channels, etc. This paper generalizes density evolution for non-symmetric memoryless channels, which in turn broadens the applications to general memoryless channels, e.g. z-channels, composite white Gaussian noise channels, etc. The central theorem underpinning this generalization is the convergence to perfect projection for any fixed size supporting tree. A new iterative formula of the same complexity is then presented and the necessary theorems for the performance concentration theorems are developed. Several properties of the new density evolution method are explored, including stability results for general asymmetric memoryless channels. Simulations, code optimizations, and possible new applications suggested by this new density evolution method are also provided. This result is also used to prove the typicality of linear LDPC codes among the coset code ensemble when the minimum check node degree is sufficiently large. It is shown that the convergence to perfect projection is essential to the belief propagation algorithm even when only symmetric channels are considered. Hence the proof of the convergence to perfect projection serves also as a completion of the theory of classical density evolution for symmetric memoryless channels.


title: Optimal Prefix Codes with Fewer Distinct Codeword Lengths are Faster to Construct

abstract: A new method for constructing minimum-redundancy binary prefix codes is described. Our method does not explicitly build a Huffman tree; instead it uses a property of optimal prefix codes to compute the codeword lengths corresponding to the input weights. Let $n$ be the number of weights and $k$ be the number of distinct codeword lengths as produced by the algorithm for the optimum codes. The running time of our algorithm is $O(k \cdot n)$. Following our previous work in \cite{be}, no algorithm can possibly construct optimal prefix codes in $o(k \cdot n)$ time. When the given weights are presorted our algorithm performs $O(9^k \cdot \log^{2k}{n})$ comparisons.


title: NP-hardness of the cluster minimization problem revisited

abstract: The computational complexity of the "cluster minimization problem" is revisited [L. T. Wille and J. Vennik, J. Phys. A 18, L419 (1985)]. It is argued that the original NP-hardness proof does not apply to pairwise potentials of physical interest, such as those that depend on the geometric distance between the particles. A geometric analog of the original problem is formulated, and a new proof for such potentials is provided by polynomial time transformation from the independent set problem for unit disk graphs. Limitations of this formulation are pointed out, and new subproblems that bear more direct consequences to the numerical study of clusters are suggested.


title: Traders imprint themselves by adaptively updating their own avatar

abstract: Simulations of artificial stock markets were considered as early as 1964 and multi-agent ones were introduced as early as 1989. Starting the early 90's, collaborations of economists and physicists produced increasingly realistic simulation platforms. Currently, the market stylized facts are easily reproduced and one has now to address the realistic details of the Market Microstructure and of the Traders Behaviour. This calls for new methods and tools capable of bridging smoothly between simulations and experiments in economics. We propose here the following Avatar-Based Method (ABM). The subjects implement and maintain their Avatars (programs encoding their personal decision making procedures) on NatLab, a market simulation platform. Once these procedures are fed in a computer edible format, they can be operationally used as such without the need for belabouring, interpreting or conceptualising them. Thus ABM short-circuits the usual behavioural economics experiments that search for the psychological mechanisms underlying the subjects behaviour. Finally, ABM maintains a level of objectivity close to the classical behaviourism while extending its scope to subjects' decision making mechanisms. We report on experiments where Avatars designed and maintained by humans from different backgrounds (including real traders) compete in a continuous double-auction market. We hope this unbiased way of capturing the adaptive evolution of real subjects behaviour may lead to a new kind of behavioural economics experiments with a high degree of reliability, analysability and reproducibility.


title: Requirements for Digital Preservation Systems: A Bottom-Up Approach

abstract: The field of digital preservation is being defined by a set of standards developed top-down, starting with an abstract reference model (OAIS) and gradually adding more specific detail. Systems claiming conformance to these standards are entering production use. Work is underway to certify that systems conform to requirements derived from OAIS. We complement these requirements derived top-down by presenting an alternate, bottom-up view of the field. The fundamental goal of these systems is to ensure that the information they contain remains accessible for the long term. We develop a parallel set of requirements based on observations of how existing systems handle this task, and on an analysis of the threats to achieving the goal. On this basis we suggest disclosures that systems should provide as to how they satisfy their goals.


title: Comparing hierarchies of total functionals

abstract: In this paper we consider two hierarchies of hereditarily total and continuous functionals over the reals based on one extensional and one intensional representation of real numbers, and we discuss under which asumptions these hierarchies coincide. This coincidense problem is equivalent to a statement about the topology of the Kleene-Kreisel continuous functionals. As a tool of independent interest, we show that the Kleene-Kreisel functionals may be embedded into both these hierarchies.


title: Transitive Text Mining for Information Extraction and Hypothesis Generation

abstract: Transitive text mining - also named Swanson Linking (SL) after its primary and principal researcher - tries to establish meaningful links between literature sets which are virtually disjoint in the sense that each does not mention the main concept of the other. If successful, SL may give rise to the development of new hypotheses. In this communication we describe our approach to transitive text mining which employs co-occurrence analysis of the medical subject headings (MeSH), the descriptors assigned to papers indexed in PubMed. In addition, we will outline the current state of our web-based information system which will enable our users to perform literature-driven hypothesis building on their own.


title: The Throughput-Reliability Tradeoff in MIMO Channels

abstract: In this paper, an outage limited MIMO channel is considered. We build on Zheng and Tse's elegant formulation of the diversity-multiplexing tradeoff to develop a better understanding of the asymptotic relationship between the probability of error, transmission rate, and signal-to-noise ratio. In particular, we identify the limitation imposed by the multiplexing gain notion and develop a new formulation for the throughput-reliability tradeoff that avoids this limitation. The new characterization is then used to elucidate the asymptotic trends exhibited by the outage probability curves of MIMO channels.


title: Achievable Rates for Pattern Recognition

abstract: Biological and machine pattern recognition systems face a common challenge: Given sensory data about an unknown object, classify the object by comparing the sensory data with a library of internal representations stored in memory. In many cases of interest, the number of patterns to be discriminated and the richness of the raw data force recognition systems to internally represent memory and sensory information in a compressed format. However, these representations must preserve enough information to accommodate the variability and complexity of the environment, or else recognition will be unreliable. Thus, there is an intrinsic tradeoff between the amount of resources devoted to data representation and the complexity of the environment in which a recognition system may reliably operate. In this paper we describe a general mathematical model for pattern recognition systems subject to resource constraints, and show how the aforementioned resource-complexity tradeoff can be characterized in terms of three rates related to number of bits available for representing memory and sensory data, and the number of patterns populating a given statistical environment. We prove single-letter information theoretic bounds governing the achievable rates, and illustrate the theory by analyzing the elementary cases where the pattern data is either binary or Gaussian.


title: Coloring vertices of a graph or finding a Meyniel obstruction

abstract: A Meyniel obstruction is an odd cycle with at least five vertices and at most one chord. A graph is Meyniel if and only if it has no Meyniel obstruction as an induced subgraph. Here we give a O(n^2) algorithm that, for any graph, finds either a clique and coloring of the same size or a Meyniel obstruction. We also give a O(n^3) algorithm that, for any graph, finds either aneasily recognizable strong stable set or a Meyniel obstruction.


title: Well-founded and Stable Semantics of Logic Programs with Aggregates

abstract: In this paper, we present a framework for the semantics and the computation of aggregates in the context of logic programming. In our study, an aggregate can be an arbitrary interpreted second order predicate or function. We define extensions of the Kripke-Kleene, the well-founded and the stable semantics for aggregate programs. The semantics is based on the concept of a three-valued immediate consequence operator of an aggregate program. Such an operator approximates the standard two-valued immediate consequence operator of the program, and induces a unique Kripke-Kleene model, a unique well-founded model and a collection of stable models. We study different ways of defining such operators and thus obtain a framework of semantics, offering different trade-offs between precision and tractability. In particular, we investigate conditions on the operator that guarantee that the computation of the three types of semantics remains on the same level as for logic programs without aggregates. Other results show that, in practice, even efficient three-valued immediate consequence operators which are very low in the precision hierarchy, still provide optimal precision.


title: A formally verified proof of the prime number theorem

abstract: The prime number theorem, established by Hadamard and de la Vall'ee Poussin independently in 1896, asserts that the density of primes in the positive integers is asymptotic to 1 / ln x. Whereas their proofs made serious use of the methods of complex analysis, elementary proofs were provided by Selberg and Erd"os in 1948. We describe a formally verified version of Selberg's proof, obtained using the Isabelle proof assistant.


title: Sampling to estimate arbitrary subset sums

abstract: Starting with a set of weighted items, we want to create a generic sample of a certain size that we can later use to estimate the total weight of arbitrary subsets. For this purpose, we propose priority sampling which tested on Internet data performed better than previous methods by orders of magnitude. Priority sampling is simple to define and implement: we consider a steam of items i=0,...,n-1 with weights w_i. For each item i, we generate a random number r_i in (0,1) and create a priority q_i=w_i/r_i. The sample S consists of the k highest priority items. Let t be the (k+1)th highest priority. Each sampled item i in S gets a weight estimate W_i=max{w_i,t}, while non-sampled items get weight estimate W_i=0. Magically, it turns out that the weight estimates are unbiased, that is, E[W_i]=w_i, and by linearity of expectation, we get unbiased estimators over any subset sum simply by adding the sampled weight estimates from the subset. Also, we can estimate the variance of the estimates, and surpricingly, there is no co-variance between different weight estimates W_i and W_j. We conjecture an extremely strong near-optimality; namely that for any weight sequence, there exists no specialized scheme for sampling k items with unbiased estimators that gets smaller total variance than priority sampling with k+1 items. Very recently Mario Szegedy has settled this conjecture.


title: Haskell's overlooked object system

abstract: Haskell provides type-class-bounded and parametric polymorphism as opposed to subtype polymorphism of object-oriented languages such as Java and OCaml. It is a contentious question whether Haskell 98 without extensions, or with common extensions, or with new extensions can fully support conventional object-oriented programming with encapsulation, mutable state, inheritance, overriding, statically checked implicit and explicit subtyping, and so on. We systematically substantiate that Haskell 98, with some common extensions, supports all the conventional OO features plus more advanced ones, including first-class lexically scoped classes, implicitly polymorphic classes, flexible multiple inheritance, safe downcasts and safe co-variant arguments. Haskell indeed can support width and depth, structural and nominal subtyping. We address the particular challenge to preserve Haskell's type inference even for objects and object-operating functions. The OO features are introduced in Haskell as the OOHaskell library. OOHaskell lends itself as a sandbox for typed OO language design.


title: Projecting the Forward Rate Flow onto a Finite Dimensional Manifold

abstract: Given a Heath-Jarrow-Morton (HJM) interest rate model $\mathcal{M}$ and a parametrized family of finite dimensional forward rate curves $\mathcal{G}$, this paper provides a technique for projecting the infinite dimensional forward rate curve $r_{t}$ given by $\mathcal{M}$ onto the finite dimensional manifold $\mathcal{G}$.The Stratonovich dynamics of the projected finite dimensional forward curve are derived and it is shown that, under the regularity conditions, the given Stratonovich differential equation has a unique strong solution. Moreover, this projection leads to an efficient algorithm for implicit parametric estimation of the infinite dimensional HJM model. The feasibility of this method is demonstrated by applying the generalized method of moments.


title: Quickest detection of a minimum of disorder times

abstract: A multi-source quickest detection problem is considered. Assume there are two independent Poisson processes $X^{1}$ and $X^{2}$ with disorder times $\theta_{1}$ and $\theta_{2}$, respectively; that is, the intensities of $X^1$ and $X^2$ change at random unobservable times $\theta_1$ and $\theta_2$, respectively. $\theta_1$ and $\theta_2$ are independent of each other and are exponentially distributed. Define $\theta \triangleq \theta_1 \wedge \theta_2=\min\{\theta_{1},\theta_{2}\}$ . For any stopping time $\tau$ that is measurable with respect to the filtration generated by the observations define a penalty function of the form \[ R_{\tau}=\mathbb{P}(\tau<\theta)+c \mathbb{E}[(\tau-\theta)^{+}], \] where $c>0$ and $(\tau-\theta)^{+}$ is the positive part of $\tau-\theta$. It is of interest to find a stopping time $\tau$ that minimizes the above performance index. Since both observations $X^{1}$ and $X^{2}$ reveal information about the disorder time $\theta$, even this simple problem is more involved than solving the disorder problems for $X^{1}$ and $X^{2}$ separately. This problem is formulated in terms of a three dimensional sufficient statistic, and the corresponding optimal stopping problem is examined. A two dimensional optimal stopping problem whose optimal stopping time turns out to coincide with the optimal stopping time of the original problem for some range of parameters is also solved. The value function of this problem serves as a tight upper bound for the original problem's value function. The two solutions are characterized by iterating suitable functional operators.


title: Multi-Proxy Multi-Signcryption Scheme from Pairings

abstract: A first multi-proxy multi-signcryption scheme from pairings, which efficiently combines a multi-proxy multi-signature scheme with a signcryption, is proposed. Its security is analyzed in detail. In our scheme, a proxy signcrypter group could be authorized as a proxy agent by the cooperation of all members in the original signcrypter group. Then the proxy signcryptions can be generated by the cooperation of all the signcrypters in the authorized proxy signcrypter group on behalf of the original signcrypter group. The correctness and the security of this scheme are proved.


title: On the Worst-case Performance of the Sum-of-Squares Algorithm for Bin Packing

abstract: The Sum of Squares algorithm for bin packing was defined in [2] and studied in great detail in [1], where it was proved that its worst case performance ratio is at most 3. In this note, we improve the asymptotic worst case bound to 2.7777...


title: A Simple Model to Generate Hard Satisfiable Instances

abstract: In this paper, we try to further demonstrate that the models of random CSP instances proposed by [Xu and Li, 2000; 2003] are of theoretical and practical interest. Indeed, these models, called RB and RD, present several nice features. First, it is quite easy to generate random instances of any arity since no particular structure has to be integrated, or property enforced, in such instances. Then, the existence of an asymptotic phase transition can be guaranteed while applying a limited restriction on domain size and on constraint tightness. In that case, a threshold point can be precisely located and all instances have the guarantee to be hard at the threshold, i.e., to have an exponential tree-resolution complexity. Next, a formal analysis shows that it is possible to generate forced satisfiable instances whose hardness is similar to unforced satisfiable ones. This analysis is supported by some representative results taken from an intensive experimentation that we have carried out, using complete and incomplete search methods.


title: K-Histograms: An Efficient Clustering Algorithm for Categorical Dataset

abstract: Clustering categorical data is an integral part of data mining and has attracted much attention recently. In this paper, we present k-histogram, a new efficient algorithm for clustering categorical data. The k-histogram algorithm extends the k-means algorithm to categorical domain by replacing the means of clusters with histograms, and dynamically updates histograms in the clustering process. Experimental results on real datasets show that k-histogram algorithm can produce better clustering results than k-modes algorithm, the one related with our work most closely.


title: N-free extensions of posets.Note on a theorem of P.A.Grillet

abstract: Let $S\_{N}(P)$ be the poset obtained by adding a dummy vertex on each diagonal edge of the $N$'s of a finite poset $P$. We show that $S\_{N}(S\_{N}(P))$ is $N$-free. It follows that this poset is the smallest $N$-free barycentric subdivision of the diagram of $P$, poset whose existence was proved by P.A. Grillet. This is also the poset obtained by the algorithm starting with $P\_0:=P$ and consisting at step $m$ of adding a dummy vertex on a diagonal edge of some $N$ in $P\_m$, proving that the result of this algorithm does not depend upon the particular choice of the diagonal edge choosen at each step. These results are linked to drawing of posets.


title: Cryptanalysis of an MPEG-Video Encryption Scheme Based on Secret Huffman Tables

abstract: This paper studies the security of a recently-proposed MPEG-video encryption scheme based on secret Huffman tables. Our cryptanalysis shows that: 1) the key space of the encryption scheme is not sufficiently large against divide-and-conquer (DAC) attack and known-plaintext attack; 2) it is possible to decrypt a cipher-video with a partially-known key, thus dramatically reducing the complexity of the DAC brute-force attack in some cases; 3) its security against the chosen-plaintext attack is very weak. Some experimental results are included to support the cryptanalytic results with a brief discuss on how to improve this MPEG-video encryption scheme.


title: Security Problems with Improper Implementations of Improved FEA-M

abstract: This paper reports security problems with improper implementations of an improved version of FEA-M (fast encryption algorithm for multimedia). It is found that an implementation-dependent differential chosen-plaintext attack or its chosen-ciphertext counterpart can reveal the secret key of the cryptosystem, if the involved (pseudo-)random process can be tampered (for example, through a public time service). The implementation-dependent differential attack is very efficient in complexity and needs only $O(n^2)$ chosen plaintext or ciphertext bits. In addition, this paper also points out a minor security problem with the selection of the session key. In real implementations of the cryptosystem, these security problems should be carefully avoided, or the cryptosystem has to be further enhanced to work under such weak implementations.


title: Friends for Free: Self-Organizing Artificial Social Networks for Trust and Cooperation

abstract: By harvesting friendship networks from e-mail contacts or instant message "buddy lists" Peer-to-Peer (P2P) applications can improve performance in low trust environments such as the Internet. However, natural social networks are not always suitable, reliable or available. We propose an algorithm (SLACER) that allows peer nodes to create and manage their own friendship networks. We evaluate performance using a canonical test application, requiring cooperation between peers for socially optimal outcomes. The Artificial Social Networks (ASN) produced are connected, cooperative and robust - possessing many of the disable properties of human friendship networks such as trust between friends (directly linked peers) and short paths linking everyone via a chain of friends. In addition to new application possibilities, SLACER could supply ASN to P2P applications that currently depend on human social networks thus transforming them into fully autonomous, self-managing systems.


title: Algorithms for Max Hamming Exact Satisfiability

abstract: We here study Max Hamming XSAT, ie, the problem of finding two XSAT models at maximum Hamming distance. By using a recent XSAT solver as an auxiliary function, an O(1.911^n) time algorithm can be constructed, where n is the number of variables. This upper time bound can be further improved to O(1.8348^n) by introducing a new kind of branching, more directly suited for finding models at maximum Hamming distance. The techniques presented here are likely to be of practical use as well as of theoretical value, proving that there are non-trivial algorithms for maximum Hamming distance problems.


title: Coding for the feedback Gel'fand-Pinsker channel and the feedforward Wyner-Ziv source

abstract: We consider both channel coding and source coding, with perfect past feedback/feedforward, in the presence of side information. It is first observed that feedback does not increase the capacity of the Gel'fand-Pinsker channel, nor does feedforward improve the achievable rate-distortion performance in the Wyner-Ziv problem. We then focus on the Gaussian case showing that, as in the absence of side information, feedback/feedforward allows to efficiently attain the respective performance limits. In particular, we derive schemes via variations on that of Schalkwijk and Kailath. These variants, which are as simple as their origins and require no binning, are shown to achieve, respectively, the capacity of Costa's channel, and the Wyner-Ziv rate distortion function. Finally, we consider the finite-alphabet setting and derive schemes for both the channel and the source coding problems that attain the fundamental limits, using variations on schemes of Ahlswede and Ooi and Wornell, and of Martinian and Wornell, respectively.


title: Authoring case based training by document data extraction

abstract: In this paper, we propose an scalable approach to modeling based upon word processing documents, and we describe the tool Phoenix providing the technical infrastructure. For our training environment d3web.Train, we developed a tool to extract case knowledge from existing documents, usually dismissal records, extending Phoenix to d3web.CaseImporter. Independent authors used this tool to develop training systems, observing a significant decrease of time for setteling-in and a decrease of time necessary for developing a case.


title: Efficient Reconciliation of Correlated Continuous Random Variables using LDPC Codes

abstract: This paper investigates an efficient and practical information reconciliation method in the case where two parties have access to correlated continuous random variables. We show that reconciliation is a special case of channel coding and that existing coded modulation techniques can be adapted for reconciliation. We describe an explicit reconciliation method based on LDPC codes in the case of correlated Gaussian variables. We believe that the proposed method can improve the efficiency of quantum key distribution protocols based on continuous-spectrum quantum states.


title: Computing over the Reals: Foundations for Scientific Computing

abstract: We give a detailed treatment of the ``bit-model'' of computability and complexity of real functions and subsets of R^n, and argue that this is a good way to formalize many problems of scientific computation. In the introduction we also discuss the alternative Blum-Shub-Smale model. In the final section we discuss the issue of whether physical systems could defeat the Church-Turing Thesis.


title: Optimal Power Control for Multiuser CDMA Channels

abstract: In this paper, we define the power region as the set of power allocations for K users such that everybody meets a minimum signal-to-interference ratio (SIR). The SIR is modeled in a multiuser CDMA system with fixed linear receiver and signature sequences. We show that the power region is convex in linear and logarithmic scale. It furthermore has a componentwise minimal element. Power constraints are included by the intersection with the set of all viable power adjustments. In this framework, we aim at minimizing the total expended power by minimizing a componentwise monotone functional. If the feasible power region is nonempty, the minimum is attained. Otherwise, as a solution to balance conflicting interests, we suggest the projection of the minimum point in the power region onto the set of viable power settings. Finally, with an appropriate utility function, the problem of minimizing the total expended power can be seen as finding the Nash bargaining solution, which sheds light on power assignment from a game theoretic point of view. Convexity and componentwise monotonicity are essential prerequisites for this result.


title: Accumulate-Repeat-Accumulate Codes: Systematic Codes Achieving the Binary Erasure Channel Capacity with Bounded Complexity

abstract: The paper introduces ensembles of accumulate-repeat-accumulate (ARA) codes which asymptotically achieve capacity on the binary erasure channel (BEC) with {\em bounded complexity} per information bit. It also introduces symmetry properties which play a central role in the construction of capacity-achieving ensembles for the BEC. The results here improve on the tradeoff between performance and complexity provided by the first capacity-achieving ensembles of irregular repeat-accumulate (IRA) codes with bounded complexity per information bit; these IRA ensembles were previously constructed by Pfister, Sason and Urbanke. The superiority of ARA codes with moderate to large block length is exemplified by computer simulations which compare their performance with those of previously reported capacity-achieving ensembles of LDPC and IRA codes. The ARA codes also have the advantage of being systematic.


title: On Hats and other Covers

abstract: We study a game puzzle that has enjoyed recent popularity among mathematicians, computer scientist, coding theorists and even the mass press. In the game, $n$ players are fitted with randomly assigned colored hats. Individual players can see their teammates' hat colors, but not their own. Based on this information, and without any further communication, each player must attempt to guess his hat color, or pass. The team wins if there is at least one correct guess, and no incorrect ones. The goal is to devise guessing strategies that maximize the team winning probability. We show that for the case of two hat colors, and for any value of $n$, playing strategies are equivalent to binary covering codes of radius one. This link, in particular with Hamming codes, had been observed for values of $n$ of the form $2^m-1$. We extend the analysis to games with hats of $q$ colors, $q\geq 2$, where 1-coverings are not sufficient to characterize the best strategies. Instead, we introduce the more appropriate notion of a {\em strong covering}, and show efficient constructions of these coverings, which achieve winning probabilities approaching unity. Finally, we briefly discuss results on variants of the problem, including arbitrary input distributions, randomized playing strategies, and symmetric strategies.


title: On the number of t-ary trees with a given path length

abstract: We show that the number of $t$-ary trees with path length equal to $p$ is $\exp(h(t^{-1})t\log t \frac{p}{\log p}(1+o(1)))$, where $\entropy(x){=}{-}x\log x {-}(1{-}x)\log (1{-}x)$ is the binary entropy function. Besides its intrinsic combinatorial interest, the question recently arose in the context of information theory, where the number of $t$-ary trees with path length $p$ estimates the number of universal types, or, equivalently, the number of different possible Lempel-Ziv'78 dictionaries for sequences of length $p$ over an alphabet of size $t$.


title: Secure multiplex coding to attain the channel capacity in wiretap channels

abstract: It is known that a message can be transmitted safely against any wiretapper via a noisy channel without a secret key if the coding rate is less than the so-called secrecy capacity $C_S$, which is usually smaller than the channel capacity $C$. In order to remove the loss $C - C_S$, we propose a multiplex coding scheme with plural independent messages. In this paper, it is shown that the proposed multiplex coding scheme can attain the channel capacity as the total rate of the plural messages and the perfect secrecy for each message. The coding theorem is proved by extending Hayashi's proof, in which the coding of the channel resolvability is applied to wiretap channels.


title: Capacity of Complexity-Constrained Noise-Free CDMA

abstract: An interference-limited noise-free CDMA downlink channel operating under a complexity constraint on the receiver is introduced. According to this paradigm, detected bits, obtained by performing hard decisions directly on the channel's matched filter output, must be the same as the transmitted binary inputs. This channel setting, allowing the use of the simplest receiver scheme, seems to be worthless, making reliable communication at any rate impossible. We prove, by adopting statistical mechanics notion, that in the large-system limit such a complexity-constrained CDMA channel gives rise to a non-trivial Shannon-theoretic capacity, rigorously analyzed and corroborated using finite-size channel simulations.


title: On the Achievable Information Rates of CDMA Downlink with Trivial Receivers

abstract: A noisy CDMA downlink channel operating under a strict complexity constraint on the receiver is introduced. According to this constraint, detected bits, obtained by performing hard decisions directly on the channel's matched filter output, must be the same as the transmitted binary inputs. This channel setting, allowing the use of the simplest receiver scheme, seems to be worthless, making reliable communication at any rate impossible. However, recently this communication paradigm was shown to yield valuable information rates in the case of a noiseless channel. This finding calls for the investigation of this attractive complexity-constrained transmission scheme for the more practical noisy channel case. By adopting the statistical mechanics notion of metastable states of the renowned Hopfield model, it is proved that under a bounded noise assumption such complexity-constrained CDMA channel gives rise to a non-trivial Shannon-theoretic capacity, rigorously analyzed and corroborated using finite-size channel simulations. For unbounded noise the channel's outage capacity is addressed and specifically described for the popular additive white Gaussian noise.