title: Impliance: A Next Generation Information Management Appliance

abstract: ably successful in building a large market and adapting to the changes of the last three decades, its impact on the broader market of information management is surprisingly limited. If we were to design an information management system from scratch, based upon today's requirements and hardware capabilities, would it look anything like today's database systems?" In this paper, we introduce Impliance, a next-generation information management system consisting of hardware and software components integrated to form an easy-to-administer appliance that can store, retrieve, and analyze all types of structured, semi-structured, and unstructured information. We first summarize the trends that will shape information management for the foreseeable future. Those trends imply three major requirements for Impliance: (1) to be able to store, manage, and uniformly query all data, not just structured records; (2) to be able to scale out as the volume of this data grows; and (3) to be simple and robust in operation. We then describe four key ideas that are uniquely combined in Impliance to address these requirements, namely the ideas of: (a) integrating software and off-the-shelf hardware into a generic information appliance; (b) automatically discovering, organizing, and managing all data - unstructured as well as structured - in a uniform way; (c) achieving scale-out by exploiting simple, massive parallel processing, and (d) virtualizing compute and storage resources to unify, simplify, and streamline the management of Impliance. Impliance is an ambitious, long-term effort to define simpler, more robust, and more scalable information systems for tomorrow's enterprises.


title: Stratification in P2P Networks - Application to BitTorrent

abstract: We introduce a model for decentralized networks with collaborating peers. The model is based on the stable matching theory which is applied to systems with a global ranking utility function. We consider the dynamics of peers searching for efficient collaborators and we prove that a unique stable solution exists. We prove that the system converges towards the stable solution and analyze its speed of convergence. We also study the stratification properties of the model, both when all collaborations are possible and for random possible collaborations. We present the corresponding fluid limit on the choice of collaborators in the random case. As a practical example, we study the BitTorrent Tit-for-Tat policy. For this system, our model provides an interesting insight on peer download rates and a possible way to optimize peer strategy.


title: Architecting Network-Centric Software Systems: A Style-Based Beginning

abstract: With the advent of potent network technology, software development has evolved from traditional platform-centric construction to network-centric evolution. This change involves largely the way we reason about systems as evidenced in the introduction of Network- Centric Operations (NCO). Unfortunately, it has resulted in conflicting interpretations of how to map NCO concepts to the field of software architecture. In this paper, we capture the core concepts and goals of NCO, investigate the implications of these concepts and goals on software architecture, and identify the operational characteristics that distinguish network-centric software systems from other systems. More importantly, we use architectural design principles to propose an outline for a network-centric architectural style that helps in characterizing network-centric software systems and that provides a means by which their distinguishing operational characteristics can be realized.


title: A New Era in Citation and Bibliometric Analyses: Web of Science, Scopus, and Google Scholar

abstract: Academic institutions, federal agencies, publishers, editors, authors, and librarians increasingly rely on citation analysis for making hiring, promotion, tenure, funding, and/or reviewer and journal evaluation and selection decisions. The Institute for Scientific Information's (ISI) citation databases have been used for decades as a starting point and often as the only tools for locating citations and/or conducting citation analyses. ISI databases (or Web of Science), however, may no longer be adequate as the only or even the main sources of citations because new databases and tools that allow citation searching are now available. Whether these new databases and tools complement or represent alternatives to Web of Science (WoS) is important to explore. Using a group of 15 library and information science faculty members as a case study, this paper examines the effects of using Scopus and Google Scholar (GS) on the citation counts and rankings of scholars as measured by WoS. The paper discusses the strengths and weaknesses of WoS, Scopus, and GS, their overlap and uniqueness, quality and language of the citations, and the implications of the findings for citation analysis. The project involved citation searching for approximately 1,100 scholarly works published by the study group and over 200 works by a test group (an additional 10 faculty members). Overall, more than 10,000 citing and purportedly citing documents were examined. WoS data took about 100 hours of collecting and processing time, Scopus consumed 200 hours, and GS a grueling 3,000 hours.


title: Tales of Huffman

abstract: We study the new problem of Huffman-like codes subject to individual restrictions on the code-word lengths of a subset of the source words. These are prefix codes with minimal expected code-word length for a random source where additionally the code-word lengths of a subset of the source words is prescribed, possibly differently for every such source word. Based on a structural analysis of properties of optimal solutions, we construct an efficient dynamic programming algorithm for this problem, and for an integer programming problem that may be of independent interest.


title: Geometric Complexity Theory II: Towards explicit obstructions for embeddings among class varieties

abstract: In part I we reduced the arithmetic (characteristic zero) version of the P \not \subseteq NP conjecture to the problem of showing that a variety associated with the complexity class NP cannot be embedded in the variety associated the complexity class P. We call these class varieties. In this paper, this approach is developed further, reducing the nonexistence problems, such as the P vs. NP and related lower bound problems, to existence problems: specifically to proving existence of obstructions to such embeddings among class varieties. It gives two results towards explicit construction of such obstructions. The first result is a generalization of the Borel-Weil theorem to a class of orbit closures, which include class varieties. The recond result is a weaker form of a conjectured analogue of the second fundamental theorem of invariant theory for the class variety associated with the complexity class NC. These results indicate that the fundamental lower bound problems in complexity theory are intimately linked with explicit construction problems in algebraic geometry and representation theory.


title: Accommodation of the Service Offered by the Network for Networked Control Systems

abstract: Networked Controlled Systems (NCSs) are more and more used in industrial applications. They are strongly connected to real-time constraints because important delays induced by the network can lead to an unstable process control. Usually, the network used in NCSs is shared with many others applications requiring different Quality of Service. The objective of this paper is to optimize the tuning of the network scheduling mechanisms in taking into account the level of Quality of Control. The goal is to maximize the bandwidth allocation for unconstrained frames in guarantying that the control constraints are respected. In this paper, we focus on switched Ethernet network implementing the Classification of Service (IEEE 802.1p) based on a Weighted Round Robin policy.


title: Experiments on predictability of word in context and information rate in natural language

abstract: Based on data from a large-scale experiment with human subjects, we conclude that the logarithm of probability to guess a word in context (unpredictability) depends linearly on the word length. This result holds both for poetry and prose, even though with prose, the subjects don't know the length of the omitted word. We hypothesize that this effect reflects a tendency of natural language to have an even information rate.


title: Turning Cluster Management into Data Management: A System Overview

abstract: This paper introduces the CondorJ2 cluster management system. Traditionally, cluster management systems such as Condor employ a process-oriented approach with little or no use of modern database system technology. In contrast, CondorJ2 employs a data-centric, 3-tier web-application architecture for all system functions (e.g., job submission, monitoring and scheduling; node configuration, monitoring and management, etc.) except for job execution. Employing a data-oriented approach allows the core challenge (i.e., managing and coordinating a large set of distributed computing resources) to be transformed from a relatively low-level systems problem into a more abstract, higher-level data management problem. Preliminary results suggest that CondorJ2's use of standard 3-tier software represents a significant step forward to the design and implementation of large clusters (1,000 to 10,000 nodes).


title: Accommodating Sample Size Effect on Similarity Measures in Speaker Clustering

abstract: We investigate the symmetric Kullback-Leibler (KL2) distance in speaker clustering and its unreported effects for differently-sized feature matrices. Speaker data is represented as Mel Frequency Cepstral Coefficient (MFCC) vectors, and features are compared using the KL2 metric to form clusters of speech segments for each speaker. We make two observations with respect to clustering based on KL2: 1.) The accuracy of clustering is strongly dependent on the absolute lengths of the speech segments and their extracted feature vectors. 2.) The accuracy of the similarity measure strongly degrades with the length of the shorter of the two speech segments. These effects of length can be attributed to the measure of covariance used in KL2. We demonstrate an empirical correction of this sample-size effect that increases clustering accuracy. We draw parallels to two Vector Quantization-based (VQ) similarity measures, one which exhibits an equivalent effect of sample size, and the second being less influenced by it.


title: Alignment of Speech to Highly Imperfect Text Transcriptions

abstract: We introduce a novel and inexpensive approach for the temporal alignment of speech to highly imperfect transcripts from automatic speech recognition (ASR). Transcripts are generated for extended lecture and presentation videos, which in some cases feature more than 30 speakers with different accents, resulting in highly varying transcription qualities. In our approach we detect a subset of phonemes in the speech track, and align them to the sequence of phonemes extracted from the transcript. We report on the results for 4 speech-transcript sets ranging from 22 to 108 minutes. The alignment performance is promising, showing a correct matching of phonemes within 10, 20, 30 second error margins for more than 60%, 75%, 90% of text, respectively, on average.


title: On simulating nondeterministic stochastic activity networks

abstract: In this work we deal with a mechanism for process simulation called a NonDeterministic Stochastic Activity Network (NDSAN). An NDSAN consists basically of a set of activities along with precedence relations involving these activities, which determine their order of execution. Activity durations are stochastic, given by continuous, nonnegative random variables. The nondeterministic behavior of an NDSAN is based on two additional possibilities: (i) by associating choice probabilities with groups of activities, some branches of execution may not be taken; (ii) by allowing iterated executions of groups of activities according to predetermined probabilities, the number of times an activity must be executed is not determined a priori. These properties lead to a rich variety of activity networks, capable of modeling many real situations in process engineering, project design, and troubleshooting. We describe a recursive simulation algorithm for NDSANs, whose repeated execution produces a close approximation to the probability distribution of the completion time of the entire network. We also report on real-world case studies.


title: Exact Failure Frequency Calculations for Extended Systems

abstract: This paper shows how the steady-state availability and failure frequency can be calculated in a single pass for very large systems, when the availability is expressed as a product of matrices. We apply the general procedure to $k$-out-of-$n$:G and linear consecutive $k$-out-of-$n$:F systems, and to a simple ladder network in which each edge and node may fail. We also give the associated generating functions when the components have identical availabilities and failure rates. For large systems, the failure rate of the whole system is asymptotically proportional to its size. This paves the way to ready-to-use formulae for various architectures, as well as proof that the differential operator approach to failure frequency calculations is very useful and straightforward.


title: What is the probability of connecting two points ?

abstract: The two-terminal reliability, known as the pair connectedness or connectivity function in percolation theory, may actually be expressed as a product of transfer matrices in which the probability of operation of each link and site is exactly taken into account. When link and site probabilities are $p$ and $\rho$, it obeys an asymptotic power-law behavior, for which the scaling factor is the transfer matrix's eigenvalue of largest modulus. The location of the complex zeros of the two-terminal reliability polynomial exhibits structural transitions as $0 \leq \rho \leq 1$.


title: Exact solutions for the two- and all-terminal reliabilities of a simple ladder network

abstract: The exact calculation of network reliability in a probabilistic context has been a long-standing issue of practical importance, but a difficult one, even for planar graphs, with perfect nodes and with edges of identical reliability p. Many approaches (determination of bounds, sums of disjoint products algorithms, Monte Carlo evaluations, studies of the reliability polynomials, etc.) can only provide approximations when the network's size increases. We consider here a ladder graph of arbitrary size corresponding to real-life network configurations, and give the exact, analytical solutions for the all- and two-terminal reliabilities. These solutions use transfer matrices, in which individual reliabilities of edges and nodes are taken into account. The special case of identical edge and node reliabilities -- p and rho, respectively -- is solved. We show that the zeros of the two-terminal reliability polynomial exhibit structures which differ substantially for seemingly similar networks, and we compare the sensitivity of various edges. We discuss how the present work may be further extended to lead to a catalog of exactly solvable networks in terms of reliability, which could be useful as elementary bricks for a new and improved set of bounds or benchmarks in the general case.


title: On High Spatial Reuse Link Scheduling in STDMA Wireless Ad Hoc Networks

abstract: Graph-based algorithms for point-to-point link scheduling in Spatial reuse Time Division Multiple Access (STDMA) wireless ad hoc networks often result in a significant number of transmissions having low Signal to Interference and Noise density Ratio (SINR) at intended receivers, leading to low throughput. To overcome this problem, we propose a new algorithm for STDMA link scheduling based on a graph model of the network as well as SINR computations. The performance of our algorithm is evaluated in terms of spatial reuse and computational complexity. Simulation results demonstrate that our algorithm achieves better performance than existing algorithms.


title: Relay Assisted F/TDMA Ad Hoc Networks: Node Classification, Power Allocation and Relaying Strategies

abstract: This paper considers the design of relay assisted F/TDMA ad hoc networks with multiple relay nodes each of which assists the transmission of a predefined subset of source nodes to their respective destinations. Considering the sum capacity as the performance metric, we solve the problem of optimally allocating the total power of each relay node between the transmissions it is assisting. We consider four different relay transmission strategies, namely regenerative decode-and-forward (RDF), nonregenerative decode-and-forward (NDF), amplify-and-forward (AF) and compress-and-forward (CF). We first obtain the optimum power allocation policies for the relay nodes that employ a uniform relaying strategy for all nodes. We show that the optimum power allocation for the RDF and NDF cases are modified water-filling solutions. We observe that for a given relay transmit power, NDF always outperforms RDF whereas CF always provides higher sum capacity than AF. When CF and NDF are compared, it is observed that either of CF or NDF may outperform the other in different scenarios. This observation suggests that the sum capacity can be further improved by having each relay adopt its relaying strategy in helping different source nodes. We investigate this problem next and determine the optimum power allocation and relaying strategy for each source node that relay nodes assist. We observe that optimum power allocation for relay nodes with hybrid relaying strategies provides higher sum capacity than pure RDF, NDF, AF or CF relaying strategies.


title: Magnification Laws of Winner-Relaxing and Winner-Enhancing Kohonen Feature Maps

abstract: Self-Organizing Maps are models for unsupervised representation formation of cortical receptor fields by stimuli-driven self-organization in laterally coupled winner-take-all feedforward structures. This paper discusses modifications of the original Kohonen model that were motivated by a potential function, in their ability to set up a neural mapping of maximal mutual information. Enhancing the winner update, instead of relaxing it, results in an algorithm that generates an infomax map corresponding to magnification exponent of one. Despite there may be more than one algorithm showing the same magnification exponent, the magnification law is an experimentally accessible quantity and therefore suitable for quantitative description of neural optimization principles.


title: An algebraic approach to complexity of data stream computations

abstract: We consider a basic problem in the general data streaming model, namely, to estimate a vector $f \in \Z^n$ that is arbitrarily updated (i.e., incremented or decremented) coordinate-wise. The estimate $\hat{f} \in \Z^n$ must satisfy $\norm{\hat{f}-f}_{\infty}\le \epsilon\norm{f}_1 $, that is, $\forall i ~(\abs{\hat{f}_i - f_i} \le \epsilon \norm{f}_1)$. It is known to have $\tilde{O}(\epsilon^{-1})$ randomized space upper bound \cite{cm:jalgo}, $\Omega(\epsilon^{-1} \log (\epsilon n))$ space lower bound \cite{bkmt:sirocco03} and deterministic space upper bound of $\tilde{\Omega}(\epsilon^{-2})$ bits.\footnote{The $\tilde{O}$ and $\tilde{\Omega}$ notations suppress poly-logarithmic factors in $n, \log \epsilon^{-1}, \norm{f}_{\infty}$ and $\log \delta^{-1}$, where, $\delta$ is the error probability (for randomized algorithm).} We show that any deterministic algorithm for this problem requires space $\Omega(\epsilon^{-2} (\log \norm{f}_1))$ bits.


title: Exact solutions for the two- and all-terminal reliabilities of the Brecht-Colbourn ladder and the generalized fan

abstract: The two- and all-terminal reliabilities of the Brecht-Colbourn ladder and the generalized fan have been calculated exactly for arbitrary size as well as arbitrary individual edge and node reliabilities, using transfer matrices of dimension four at most. While the all-terminal reliabilities of these graphs are identical, the special case of identical edge ($p$) and node ($\rho$) reliabilities shows that their two-terminal reliabilities are quite distinct, as demonstrated by their generating functions and the locations of the zeros of the reliability polynomials, which undergo structural transitions at $\rho = \displaystyle {1/2}$.


title: The Trapping Redundancy of Linear Block Codes

abstract: We generalize the notion of the stopping redundancy in order to study the smallest size of a trapping set in Tanner graphs of linear block codes. In this context, we introduce the notion of the trapping redundancy of a code, which quantifies the relationship between the number of redundant rows in any parity-check matrix of a given code and the size of its smallest trapping set. Trapping sets with certain parameter sizes are known to cause error-floors in the performance curves of iterative belief propagation decoders, and it is therefore important to identify decoding matrices that avoid such sets. Bounds on the trapping redundancy are obtained using probabilistic and constructive methods, and the analysis covers both general and elementary trapping sets. Numerical values for these bounds are computed for the [2640,1320] Margulis code and the class of projective geometry codes, and compared with some new code-specific trapping set size estimates.


title: On the Complexity of the Circular Chromatic Number

abstract: Circular chromatic number, $\chi_c$ is a natural generalization of chromatic number. It is known that it is \NP-hard to determine whether or not an arbitrary graph $G$ satisfies $\chi(G) = \chi_c(G)$. In this paper we prove that this problem is \NP-hard even if the chromatic number of the graph is known. This answers a question of Xuding Zhu. Also we prove that for all positive integers $k \ge 2$ and $n \ge 3$, for a given graph $G$ with $\chi(G)=n$, it is \NP-complete to verify if $\chi_c(G) \le n- \frac{1}{k}$.


title: On the Computational Complexity of Defining Sets

abstract: Suppose we have a family ${\cal F}$ of sets. For every $S \in {\cal F}$, a set $D \subseteq S$ is a {\sf defining set} for $({\cal F},S)$ if $S$ is the only element of $\cal{F}$ that contains $D$ as a subset. This concept has been studied in numerous cases, such as vertex colorings, perfect matchings, dominating sets, block designs, geodetics, orientations, and Latin squares. In this paper, first, we propose the concept of a defining set of a logical formula, and we prove that the computational complexity of such a problem is $\Sigma_2$-complete. We also show that the computational complexity of the following problem about the defining set of vertex colorings of graphs is $\Sigma_2$-complete: {\sc Instance:} A graph $G$ with a vertex coloring $c$ and an integer $k$. {\sc Question:} If ${\cal C}(G)$ be the set of all $\chi(G)$-colorings of $G$, then does $({\cal C}(G),c)$ have a defining set of size at most $k$? Moreover, we study the computational complexity of some other variants of this problem.


title: Approximation and Inapproximability Results for Maximum Clique of Disc Graphs in High Dimensions

abstract: We prove algorithmic and hardness results for the problem of finding the largest set of a fixed diameter in the Euclidean space. In particular, we prove that if $A^*$ is the largest subset of diameter $r$ of $n$ points in the Euclidean space, then for every $\epsilon>0$ there exists a polynomial time algorithm that outputs a set $B$ of size at least $|A^*|$ and of diameter at most $r(\sqrt{2}+\epsilon)$. On the hardness side, roughly speaking, we show that unless $P=NP$ for every $\epsilon>0$ it is not possible to guarantee the diameter $r(\sqrt{4/3}-\epsilon)$ for $B$ even if the algorithm is allowed to output a set of size $({95\over 94}-\epsilon)^{-1}|A^*|$.


title: Determining the Applicability of Agile Practices to Mission and Life-critical Systems

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


title: Infinite-Alphabet Prefix Codes Optimal for $\beta$-Exponential Penalties

abstract: Let $P = \{p(i)\}$ be a measure of strictly positive probabilities on the set of nonnegative integers. Although the countable number of inputs prevents usage of the Huffman algorithm, there are nontrivial $P$ for which known methods find a source code that is optimal in the sense of minimizing expected codeword length. For some applications, however, a source code should instead minimize one of a family of nonlinear objective functions, $\beta$-exponential means, those of the form $\log_a \sum_i p(i) a^{n(i)}$, where $n(i)$ is the length of the $i$th codeword and $a$ is a positive constant. Applications of such minimizations include a problem of maximizing the chance of message receipt in single-shot communications ($a<1$) and a problem of minimizing the chance of buffer overflow in a queueing system ($a>1$). This paper introduces methods for finding codes optimal for such exponential means. One method applies to geometric distributions, while another applies to distributions with lighter tails. The latter algorithm is applied to Poisson distributions. Both are extended to minimizing maximum pointwise redundancy.


title: $D$-ary Bounded-Length Huffman Coding

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


title: Attribute Value Weighting in K-Modes Clustering

abstract: In this paper, the traditional k-modes clustering algorithm is extended by weighting attribute value matches in dissimilarity computation. The use of attribute value weighting technique makes it possible to generate clusters with stronger intra-similarities, and therefore achieve better clustering performance. Experimental results on real life datasets show that these value weighting based k-modes algorithms are superior to the standard k-modes algorithm with respect to clustering accuracy.


title: A Reply to Hofman On: "Why LP cannot solve large instances of NP-complete problems in polynomial time"

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


title: Asynchronous Implementation of Failure Detectors with partial connectivity and unknown participants

abstract: We consider the problem of failure detection in dynamic networks such as MANETs. Unreliable failure detectors are classical mechanisms which provide information about process failures. However, most of current implementations consider that the network is fully connected and that the initial number of nodes of the system is known. This assumption is not applicable to dynamic environments. Furthermore, such implementations are usually timer-based while in dynamic networks there is no upper bound for communication delays since nodes can move. This paper presents an asynchronous implementation of a failure detector for unknown and mobile networks. Our approach does not rely on timers and neither the composition nor the number of nodes in the system are known. We prove that our algorithm can implement failure detectors of class <>S when behavioral properties and connectivity conditions are satisfied by the underlying system.


title: The Second Law and Informatics

abstract: A unification of thermodynamics and information theory is proposed. It is argued that similarly to the randomness due to collisions in thermal systems, the quenched randomness that exists in data files in informatics systems contributes to entropy. Therefore, it is possible to define equilibrium and to calculate temperature for informatics systems. The obtained temperature yields correctly the Shannon information balance in informatics systems and is consistent with the Clausius inequality and the Carnot cycle.


title: Energy-Efficient Power Control in Impulse Radio UWB Wireless Networks

abstract: In this paper, a game-theoretic model for studying power control for wireless data networks in frequency-selective multipath environments is analyzed. The uplink of an impulse-radio ultrawideband system is considered. The effects of self-interference and multiple-access interference on the performance of generic Rake receivers are investigated for synchronous systems. Focusing on energy efficiency, a noncooperative game is proposed in which users in the network are allowed to choose their transmit powers to maximize their own utilities, and the Nash equilibrium for the proposed game is derived. It is shown that, due to the frequency selective multipath, the noncooperative solution is achieved at different signal-to-interference-plus-noise ratios, depending on the channel realization and the type of Rake receiver employed. A large-system analysis is performed to derive explicit expressions for the achieved utilities. The Pareto-optimal (cooperative) solution is also discussed and compared with the noncooperative approach.


title: Performance Analysis of Algebraic Soft-Decision Decoding of Reed-Solomon Codes

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


title: Flow-optimized Cooperative Transmission for the Relay Channel

abstract: This paper describes an approach for half-duplex cooperative transmission in a classical three-node relay channel. Assuming availability of channel state information at nodes, the approach makes use of this information to optimize distinct flows through the direct link from the source to the destination and the path via the relay, respectively. It is shown that such a design can effectively harness diversity advantage of the relay channel in both high-rate and low-rate scenarios. When the rate requirement is low, the proposed design gives a second-order outage diversity performance approaching that of full-duplex relaying. When the rate requirement becomes asymptotically large, the design still gives a close-to-second-order outage diversity performance. The design also achieves the best diversity-multiplexing tradeoff possible for the relay channel. With optimal long-term power control over the fading relay channel, the proposed design achieves a delay-limited rate performance that is only 3.0dB (5.4dB) worse than the capacity performance of the additive white Gaussian channel in low- (high-) rate scenarios.


title: A nearly optimal and deterministic summary structure for update data streams

abstract: The paper has been withdrawn due to an error in Lemma 1.


title: The Unix KISS: A Case Study

abstract: In this paper we show that the initial philosophy used in designing and developing UNIX in early times has been forgotten due to "fast practices". We question the leitmotif that microkernels, though being by design adherent to the KISS principle, have a number of context switches higher than their monolithic counterparts, running a test suite and verify the results with standard statistical validation tests. We advocate a wiser distribution of shared libraries by statistically analyzing the weight of each shared object in a typical UNIX system, showing that the majority of shared libraries exist in a common space for no real evidence of need. Finally we examine the UNIX heritage with an historical point of view, noticing how habits swiftly replaced the intents of the original authors, moving the focus from the earliest purpose of is avoiding complications, keeping a system simple to use and maintain.


title: Definable functions in the simply typed lambda-calculus

abstract: It is a common knowledge that the integer functions definable in simply typed lambda-calculus are exactly the extended polynomials. This is indeed the case when one interprets integers over the type (p->p)->p->p where p is a base type and/or equality is taken as beta-conversion. It is commonly believed that the same holds for beta-eta equality and for integers represented over any fixed type of the form (t->t)->t->t. In this paper we show that this opinion is not quite true. We prove that the class of functions strictly definable in simply typed lambda-calculus is considerably larger than the extended polynomials. Namely, we define F as the class of strictly definable functions and G as a class that contains extended polynomials and two additional functions, or more precisely, two function schemas, and is closed under composition. We prove that G is a subset of F. We conjecture that G exactly characterizes strictly definable functions, i.e. G=F, and we gather some evidence for this conjecture proving, for example, that every skewly representable finite range function is strictly representable over (t->t)->t->t for some t.


title: A Polynomial Time Algorithm for 3-SAT

abstract: Article describes a class of efficient algorithms for 3SAT and their generalizations on SAT.


title: Secure Communication over Fading Channels

abstract: The fading broadcast channel with confidential messages (BCC) is investigated, where a source node has common information for two receivers (receivers 1 and 2), and has confidential information intended only for receiver 1. The confidential information needs to be kept as secret as possible from receiver 2. The broadcast channel from the source node to receivers 1 and 2 is corrupted by multiplicative fading gain coefficients in addition to additive Gaussian noise terms. The channel state information (CSI) is assumed to be known at both the transmitter and the receivers. The parallel BCC with independent subchannels is first studied, which serves as an information-theoretic model for the fading BCC. The secrecy capacity region of the parallel BCC is established. This result is then specialized to give the secrecy capacity region of the parallel BCC with degraded subchannels. The secrecy capacity region is then established for the parallel Gaussian BCC, and the optimal source power allocations that achieve the boundary of the secrecy capacity region are derived. In particular, the secrecy capacity region is established for the basic Gaussian BCC. The secrecy capacity results are then applied to study the fading BCC. Both the ergodic and outage performances are studied.


title: Free deconvolution for signal processing applications

abstract: Situations in many fields of research, such as digital communications, nuclear physics and mathematical finance, can be modelled with random matrices. When the matrices get large, free probability theory is an invaluable tool for describing the asymptotic behaviour of many systems. It will be shown how free probability can be used to aid in source detection for certain systems. Sample covariance matrices for systems with noise are the starting point in our source detection problem. Multiplicative free deconvolution is shown to be a method which can aid in expressing limit eigenvalue distributions for sample covariance matrices, and to simplify estimators for eigenvalue distributions of covariance matrices.


title: Analysis of Sequential Decoding Complexity Using the Berry-Esseen Inequality

abstract: his study presents a novel technique to estimate the computational complexity of sequential decoding using the Berry-Esseen theorem. Unlike the theoretical bounds determined by the conventional central limit theorem argument, which often holds only for sufficiently large codeword length, the new bound obtained from the Berry-Esseen theorem is valid for any blocklength. The accuracy of the new bound is then examined for two sequential decoding algorithms, an ordering-free variant of the generalized Dijkstra's algorithm (GDA)(or simplified GDA) and the maximum-likelihood sequential decoding algorithm (MLSDA). Empirically investigating codes of small blocklength reveals that the theoretical upper bound for the simplified GDA almost matches the simulation results as the signal-to-noise ratio (SNR) per information bit ($\gamma_b$) is greater than or equal to 8 dB. However, the theoretical bound may become markedly higher than the simulated average complexity when $\gamma_b$ is small. For the MLSDA, the theoretical upper bound is quite close to the simulation results for both high SNR ($\gamma_b\geq 6$ dB) and low SNR ($\gamma_b\leq 2$ dB). Even for moderate SNR, the simulation results and the theoretical bound differ by at most \makeblue{0.8} on a $\log_{10}$ scale.


title: The source coding game with a cheating switcher

abstract: Berger's paper `The Source Coding Game', IEEE Trans. Inform. Theory, 1971, considers the problem of finding the rate-distortion function for an adversarial source comprised of multiple known IID sources. The adversary, called the `switcher', was allowed only causal access to the source realizations and the rate-distortion function was obtained through the use of a type covering lemma. In this paper, the rate-distortion function of the adversarial source is described, under the assumption that the switcher has non-causal access to all source realizations. The proof utilizes the type covering lemma and simple conditional, random `switching' rules. The rate-distortion function is once again the maximization of the R(D) function for a region of attainable IID distributions.


title: Statistical keyword detection in literary corpora

abstract: Understanding the complexity of human language requires an appropriate analysis of the statistical distribution of words in texts. We consider the information retrieval problem of detecting and ranking the relevant words of a text by means of statistical information referring to the "spatial" use of the words. Shannon's entropy of information is used as a tool for automatic keyword extraction. By using The Origin of Species by Charles Darwin as a representative text sample, we show the performance of our detector and compare it with another proposals in the literature. The random shuffled text receives special attention as a tool for calibrating the ranking indices.


title: The Inhabitation Problem for Rank Two Intersection Types

abstract: We prove that the inhabitation problem for rank two intersection types is decidable, but (contrary to common belief) EXPTIME-hard. The exponential time hardness is shown by reduction from the in-place acceptance problem for alternating Turing machines.


title: New Constructions of a Family of 2-Generator Quasi-Cyclic Two-Weight Codes and Related Codes

abstract: Based on cyclic simplex codes, a new construction of a family of 2-generator quasi-cyclic two-weight codes is given. New optimal binary quasi-cyclic [195, 8, 96], [210, 8, 104] and [240, 8, 120] codes, good QC ternary [195, 6, 126], [208, 6, 135], [221, 6, 144] codes are thus obtained. Furthermre, binary quasi-cyclic self-complementary codes are also constructed.


title: On the implementation of construction functions for non-free concrete data types

abstract: Many algorithms use concrete data types with some additional invariants. The set of values satisfying the invariants is often a set of representatives for the equivalence classes of some equational theory. For instance, a sorted list is a particular representative wrt commutativity. Theories like associativity, neutral element, idempotence, etc. are also very common. Now, when one wants to combine various invariants, it may be difficult to find the suitable representatives and to efficiently implement the invariants. The preservation of invariants throughout the whole program is even more difficult and error prone. Classically, the programmer solves this problem using a combination of two techniques: the definition of appropriate construction functions for the representatives and the consistent usage of these functions ensured via compiler verifications. The common way of ensuring consistency is to use an abstract data type for the representatives; unfortunately, pattern matching on representatives is lost. A more appealing alternative is to define a concrete data type with private constructors so that both compiler verification and pattern matching on representatives are granted. In this paper, we detail the notion of private data type and study the existence of construction functions. We also describe a prototype, called Moca, that addresses the entire problem of...


title: Polygraphic programs and polynomial-time functions

abstract: We study the computational model of polygraphs. For that, we consider polygraphic programs, a subclass of these objects, as a formal description of first-order functional programs. We explain their semantics and prove that they form a Turing-complete computational model. Their algebraic structure is used by analysis tools, called polygraphic interpretations, for complexity analysis. In particular, we delineate a subclass of polygraphic programs that compute exactly the functions that are Turing-computable in polynomial time.


title: A Counterexample to a Proposed Proof of P=NP by S. Gubin

abstract: In a recent paper by S. Gubin [cs/0701023v1], a polynomial-time solution to the 3SAT problem was presented as proof that P=NP. The proposed algorithm cannot be made to work, which I shall demonstrate.


title: Performance of Rake Receivers in IR-UWB Networks Using Energy-Efficient Power Control

abstract: This paper studies the performance of partial-Rake (PRake) receivers in impulse-radio ultrawideband wireless networks when an energy-efficient power control scheme is adopted. Due to the large bandwidth of the system, the multipath channel is assumed to be frequency-selective. By making use of noncooperative game-theoretic models and large-system analysis tools, explicit expressions are derived in terms of network parameters to measure the effects of self-interference and multiple-access interference at a receiving access point. Performance of the PRake receivers is thus compared in terms of achieved utilities and loss to that of the all-Rake receiver. Simulation results are provided to validate the analysis.


title: Finding Astronomical Communities Through Co-readership Analysis

abstract: Whenever a large group of people are engaged in an activity, communities will form. The nature of these communities depends on the relationship considered. In the group of people who regularly use scholarly literature, a relationship like ``person i and person j have cited the same paper'' might reveal communities of people working in a particular field. On this poster, we will investigate the relationship ``person i and person j have read the same paper''. Using the data logs of the NASA/Smithsonian Astrophysics Data System (ADS), we first determine the population that will participate by requiring that a user queries the ADS at a certain rate. Next, we apply the relationship to this population. The result of this will be an abstract ``relationship space'', which we will describe in terms of various ``representations''. Examples of such ``representations'' are the projection of co-read vectors onto Principal Components and the spectral density of the co-read network. We will show that the co-read relationship results in structure, we will describe this structure and we will provide a first attempt in the classification of this structure in terms of astronomical communities. The ADS is funded by NASA Grant NNG06GG68G.


title: Compression-based methods for nonparametric density estimation, on-line prediction, regression and classification for time series

abstract: We address the problem of nonparametric estimation of characteristics for stationary and ergodic time series. We consider finite-alphabet time series and real-valued ones and the following four problems: i) estimation of the (limiting) probability (or estimation of the density for real-valued time series), ii) on-line prediction, iii) regression and iv) classification (or so-called problems with side information). We show that so-called archivers (or data compressors) can be used as a tool for solving these problems. In particular, firstly, it is proven that any so-called universal code (or universal data compressor) can be used as a basis for constructing asymptotically optimal methods for the above problems. (By definition, a universal code can "compress" any sequence generated by a stationary and ergodic source asymptotically till the Shannon entropy of the source.) And, secondly, we show experimentally that estimates, which are based on practically used methods of data compression, have a reasonable precision.


title: DMTCP: Transparent Checkpointing for Cluster Computations and the Desktop

abstract: DMTCP (Distributed MultiThreaded CheckPointing) is a transparent user-level checkpointing package for distributed applications. Checkpointing and restart is demonstrated for a wide range of over 20 well known applications, including MATLAB, Python, TightVNC, MPICH2, OpenMPI, and runCMS. RunCMS runs as a 680 MB image in memory that includes 540 dynamic libraries, and is used for the CMS experiment of the Large Hadron Collider at CERN. DMTCP transparently checkpoints general cluster computations consisting of many nodes, processes, and threads; as well as typical desktop applications. On 128 distributed cores (32 nodes), checkpoint and restart times are typically 2 seconds, with negligible run-time overhead. Typical checkpoint times are reduced to 0.2 seconds when using forked checkpointing. Experimental results show that checkpoint time remains nearly constant as the number of nodes increases on a medium-size cluster. DMTCP automatically accounts for fork, exec, ssh, mutexes/semaphores, TCP/IP sockets, UNIX domain sockets, pipes, ptys (pseudo-terminals), terminal modes, ownership of controlling terminals, signal handlers, open file descriptors, shared open file descriptors, I/O (including the readline library), shared memory (via mmap), parent-child process relationships, pid virtualization, and other operating system artifacts. By emphasizing an unprivileged, user-space approach, compatibility is maintained across Linux kernels from 2.6.9 through the current 2.6.28. Since DMTCP is unprivileged and does not require special kernel modules or kernel patches, DMTCP can be incorporated and distributed as a checkpoint-restart module within some larger package.


title: Approximate Eigenstructure of LTV Channels with Compactly Supported Spreading

abstract: In this article we obtain estimates on the approximate eigenstructure of channels with a spreading function supported only on a set of finite measure $|U|$.Because in typical application like wireless communication the spreading function is a random process corresponding to a random Hilbert--Schmidt channel operator $\BH$ we measure this approximation in terms of the ratio of the $p$--norm of the deviation from variants of the Weyl symbol calculus to the $a$--norm of the spreading function itself. This generalizes recent results obtained for the case $p=2$ and $a=1$. We provide a general approach to this topic and consider then operators with $|U|<\infty$ in more detail. We show the relation to pulse shaping and weighted norms of ambiguity functions. Finally we derive several necessary conditions on $|U|$, such that the approximation error is below certain levels.


title: On the Complexity of the Numerically Definite Syllogistic and Related Fragments

abstract: In this paper, we determine the complexity of the satisfiability problem for various logics obtained by adding numerical quantifiers, and other constructions, to the traditional syllogistic. In addition, we demonstrate the incompleteness of some recently proposed proof-systems for these logics.


title: Curve Tracking Control for Legged Locomotion in Horizontal Plane

abstract: We derive a hybrid feedback control law for the lateral leg spring (LLS) model so that the center of mass of a legged runner follows a curved path in horizontal plane. The control law enables the runner to change the placement and the elasticity of its legs to move in a desired direction. Stable motion along a curved path is achieved using curvature, bearing and relative distance between the runner and the curve as feedback. Constraints on leg parameters determine the class of curves that can be followed. We also derive an optimal control law that stabilizes the orientation of the runner's body relative to the velocity of the runner's center of mass.


title: A Coding Theorem for a Class of Stationary Channels with Feedback

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


title: Sending a Bivariate Gaussian Source over a Gaussian MAC with Feedback

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


title: Adaptive Alternating Minimization Algorithms

abstract: The classical alternating minimization (or projection) algorithm has been successful in the context of solving optimization problems over two variables. The iterative nature and simplicity of the algorithm has led to its application to many areas such as signal processing, information theory, control, and finance. A general set of sufficient conditions for the convergence and correctness of the algorithm is quite well-known when the underlying problem parameters are fixed. In many practical situations, however, the underlying problem parameters are changing over time, and the use of an adaptive algorithm is more appropriate. In this paper, we study such an adaptive version of the alternating minimization algorithm. As a main result of this paper, we provide a general set of sufficient conditions for the convergence and correctness of the adaptive algorithm. Perhaps surprisingly, these conditions seem to be the minimal ones one would expect in such an adaptive setting. We present applications of our results to adaptive decomposition of mixtures, adaptive log-optimal portfolio selection, and adaptive filter design.


title: New ID Based Multi-Proxy Multi-Signcryption Scheme from Pairings

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


title: Polygon Convexity: Another O(n) Test

abstract: An n-gon is defined as a sequence \P=(V_0,...,V_{n-1}) of n points on the plane. An n-gon \P is said to be convex if the boundary of the convex hull of the set {V_0,...,V_{n-1}} of the vertices of \P coincides with the union of the edges [V_0,V_1],...,[V_{n-1},V_0]; if at that no three vertices of \P are collinear then \P is called strictly convex. We prove that an n-gon \P with n\ge3 is strictly convex if and only if a cyclic shift of the sequence (\al_0,...,\al_{n-1})\in[0,2\pi)^n of the angles between the x-axis and the vectors V_1-V_0,...,V_0-V_{n-1} is strictly monotone. A ``non-strict'' version of this result is also proved.


title: Cooperation Between Stations in Wireless Networks

abstract: In a wireless network, mobile nodes (MNs) repeatedly perform tasks such as layer 2 (L2) handoff, layer 3 (L3) handoff and authentication. These tasks are critical, particularly for real-time applications such as VoIP. We propose a novel approach, namely Cooperative Roaming (CR), in which MNs can collaborate with each other and share useful information about the network in which they move. We show how we can achieve seamless L2 and L3 handoffs regardless of the authentication mechanism used and without any changes to either the infrastructure or the protocol. In particular, we provide a working implementation of CR and show how, with CR, MNs can achieve a total L2+L3 handoff time of less than 16 ms in an open network and of about 21 ms in an IEEE 802.11i network. We consider behaviors typical of IEEE 802.11 networks, although many of the concepts and problems addressed here apply to any kind of mobile network.


title: On vocabulary size of grammar-based codes

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


title: Energy Conscious Interactive Communication for Sensor Networks

abstract: In this work, we are concerned with maximizing the lifetime of a cluster of sensors engaged in single-hop communication with a base-station. In a data-gathering network, the spatio-temporal correlation in sensor data induces data-redundancy. Also, the interaction between two communicating parties is well-known to reduce the communication complexity. This paper proposes a formalism that exploits these two opportunities to reduce the number of bits transmitted by a sensor node in a cluster, hence enhancing its lifetime. We argue that our approach has several inherent advantages in scenarios where the sensor nodes are acutely energy and computing-power constrained, but the base-station is not so. This provides us an opportunity to develop communication protocols, where most of the computing and communication is done by the base-station. The proposed framework casts the sensor nodes and base-station communication problem as the problem of multiple informants with correlated information communicating with a recipient and attempts to extend extant work on interactive communication between an informant-recipient pair to such scenarios. Our work makes four major contributions. Firstly, we explicitly show that in such scenarios interaction can help in reducing the communication complexity. Secondly, we show that the order in which the informants communicate with the recipient may determine the communication complexity. Thirdly, we provide the framework to compute the $m$-message communication complexity in such scenarios. Lastly, we prove that in a typical sensor network scenario, the proposed formalism significantly reduces the communication and computational complexities.


title: On the Complexity of a Derivative Chess Problem

abstract: We introduce QUEENS, a derivative chess problem based on the classical n-queens problem. We prove that QUEENS is NP-complete, with respect to polynomial-time reductions.


title: A Simple Proof of the Entropy-Power Inequality via Properties of Mutual Information

abstract: While most useful information theoretic inequalities can be deduced from the basic properties of entropy or mutual information, Shannon's entropy power inequality (EPI) seems to be an exception: available information theoretic proofs of the EPI hinge on integral representations of differential entropy using either Fisher's information (FI) or minimum mean-square error (MMSE). In this paper, we first present a unified view of proofs via FI and MMSE, showing that they are essentially dual versions of the same proof, and then fill the gap by providing a new, simple proof of the EPI, which is solely based on the properties of mutual information and sidesteps both FI or MMSE representations.


title: Coding, Scheduling, and Cooperation in Wireless Sensor Networks

abstract: We consider a single-hop data gathering sensor cluster consisting of a set of sensors that need to transmit data periodically to a base-station. We are interested in maximizing the lifetime of this network. Even though the setting of our problem is very simple, it turns out that the solution is far from easy. The complexity arises from several competing system-level opportunities available to reduce the energy consumed in radio transmission. First, sensor data is spatially and temporally correlated. Recent advances in distributed source-coding allow us to take advantage of these correlations to reduce the number of transmitted bits, with concomitant savings in energy. Second, it is also well-known that channel-coding can be used to reduce transmission energy by increasing transmission time. Finally, sensor nodes are cooperative, unlike nodes in an ad hoc network that are often modeled as competitive, allowing us to take full advantage of the first two opportunities for the purpose of maximizing cluster lifetime. In this paper, we pose the problem of maximizing lifetime as a max-min optimization problem subject to the constraint of successful data collection and limited energy supply at each node. By introducing the notion of instantaneous decoding, we are able to simplify this optimization problem into a joint scheduling and time allocation problem. We show that even with our ample simplification, the problem remains NP-hard. We provide some algorithms, heuristics and insight for various scenarios. Our chief contribution is to illustrate both the challenges and gains provided by joint source-channel coding and scheduling.


title: Time Series Forecasting: Obtaining Long Term Trends with Self-Organizing Maps

abstract: Kohonen self-organisation maps are a well know classification tool, commonly used in a wide variety of problems, but with limited applications in time series forecasting context. In this paper, we propose a forecasting method specifically designed for multi-dimensional long-term trends prediction, with a double application of the Kohonen algorithm. Practical applications of the method are also presented.


title: A Case For Amplify-Forward Relaying in the Block-Fading Multi-Access Channel

abstract: This paper demonstrates the significant gains that multi-access users can achieve from sharing a single amplify-forward relay in slow fading environments. The proposed protocol, namely the multi-access relay amplify-forward, allows for a low-complexity relay and achieves the optimal diversity-multiplexing trade-off at high multiplexing gains. Analysis of the protocol reveals that it uniformly dominates the compress-forward strategy and further outperforms the dynamic decode-forward protocol at high multiplexing gains. An interesting feature of the proposed protocol is that, at high multiplexing gains, it resembles a multiple-input single-output system, and at low multiplexing gains, it provides each user with the same diversity-multiplexing trade-off as if there is no contention for the relay from the other users.


title: Nearly-Exponential Size Lower Bounds for Symbolic Quantifier Elimination Algorithms and OBDD-Based Proofs of Unsatisfiability

abstract: We demonstrate a family of propositional formulas in conjunctive normal form so that a formula of size $N$ requires size $2^{\Omega(\sqrt[7]{N/logN})}$ to refute using the tree-like OBDD refutation system of Atserias, Kolaitis and Vardi with respect to all variable orderings. All known symbolic quantifier elimination algorithms for satisfiability generate tree-like proofs when run on unsatisfiable CNFs, so this lower bound applies to the run-times of these algorithms. Furthermore, the lower bound generalizes earlier results on OBDD-based proofs of unsatisfiability in that it applies for all variable orderings, it applies when the clauses are processed according to an arbitrary schedule, and it applies when variables are eliminated via quantification.


title: Bounds on Space-Time-Frequency Dimensionality

abstract: We bound the number of electromagnetic signals which may be observed over a frequency range $2W$ for a time $T$ within a region of space enclosed by a radius $R$. Our result implies that broadband fields in space cannot be arbitrarily complex: there is a finite amount of information which may be extracted from a region of space via electromagnetic radiation. Three-dimensional space allows a trade-off between large carrier frequency and bandwidth. We demonstrate applications in super-resolution and broadband communication.


title: Space-Time-Frequency Degrees of Freedom: Fundamental Limits for Spatial Information

abstract: We bound the number of electromagnetic signals which may be observed over a frequency range $[F-W,F+W]$ a time interval $[0,T]$ within a sphere of radius $R$. We show that the such constrained signals may be represented by a series expansion whose terms are bounded exponentially to zero beyond a threshold. Our result implies there is a finite amount of information which may be extracted from a region of space via electromagnetic radiation.


title: Cooperative Optimization for Energy Minimization: A Case Study of Stereo Matching

abstract: Often times, individuals working together as a team can solve hard problems beyond the capability of any individual in the team. Cooperative optimization is a newly proposed general method for attacking hard optimization problems inspired by cooperation principles in team playing. It has an established theoretical foundation and has demonstrated outstanding performances in solving real-world optimization problems. With some general settings, a cooperative optimization algorithm has a unique equilibrium and converges to it with an exponential rate regardless initial conditions and insensitive to perturbations. It also possesses a number of global optimality conditions for identifying global optima so that it can terminate its search process efficiently. This paper offers a general description of cooperative optimization, addresses a number of design issues, and presents a case study to demonstrate its power.


title: Precoding in Multiple-Antenna Broadcast Systems with a Probabilistic Viewpoint

abstract: In this paper, we investigate the minimum average transmit energy that can be obtained in multiple antenna broadcast systems with channel inversion technique. The achievable gain can be significantly higher than the conventional gains that are mentioned in methods like perturbation technique of Peel, et al. In order to obtain this gain, we introduce a Selective Mapping (SLM) technique (based on random coding arguments). We propose to implement the SLM method by using nested lattice codes in a trellis precoding framework.


title: Enhancing Sensor Network Lifetime Using Interactive Communication

abstract: We are concerned with maximizing the lifetime of a data-gathering wireless sensor network consisting of set of nodes directly communicating with a base-station. We model this scenario as the m-message interactive communication between multiple correlated informants (sensor nodes) and a recipient (base-station). With this framework, we show that m-message interactive communication can indeed enhance network lifetime. Both worst-case and average-case performances are considered.


title: Duadic Group Algebra Codes

abstract: Duadic group algebra codes are a generalization of quadratic residue codes. This paper settles an open problem raised by Zhu concerning the existence of duadic group algebra codes. These codes can be used to construct degenerate quantum stabilizer codes that have the nice feature that many errors of small weight do not need error correction; this fact is illustrated by an example.


title: Conjugate Gradient Projection Approach for Multi-Antenna Gaussian Broadcast Channels

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


title: Network Coding over a Noisy Relay : a Belief Propagation Approach

abstract: In recent years, network coding has been investigated as a method to obtain improvements in wireless networks. A typical assumption of previous work is that relay nodes performing network coding can decode the messages from sources perfectly. On a simple relay network, we design a scheme to obtain network coding gain even when the relay node cannot perfectly decode its received messages. In our scheme, the operation at the relay node resembles message passing in belief propagation, sending the logarithm likelihood ratio (LLR) of the network coded message to the destination. Simulation results demonstrate the gain obtained over different channel conditions. The goal of this paper is not to give a theoretical result, but to point to possible interaction of network coding with user cooperation in noisy scenario. The extrinsic information transfer (EXIT) chart is shown to be a useful engineering tool to analyze the performance of joint channel coding and network coding in the network.


title: Hierarchical Decoupling Principle of a MIMO-CDMA Channel in Asymptotic Limits

abstract: We analyze an uplink of a fast flat fading MIMO-CDMA channel in the case where the data symbol vector for each user follows an arbitrary distribution. The spectral efficiency of the channel with CSI at the receiver is evaluated analytically with the replica method. The main result is that the hierarchical decoupling principle holds in the MIMO-CDMA channel, i.e., the MIMO-CDMA channel is decoupled into a bank of single-user MIMO channels in the many-user limit, and each single-user MIMO channel is further decoupled into a bank of scalar Gaussian channels in the many-antenna limit for a fading model with a limited number of scatterers.


title: Causing Communication Closure: Safe Program Composition with Reliable Non-FIFO Channels

abstract: A semantic framework for analyzing safe composition of distributed programs is presented. Its applicability is illustrated by a study of program composition when communication is reliable but not necessarily FIFO\@. In this model, special care must be taken to ensure that messages do not accidentally overtake one another in the composed program. We show that barriers do not exist in this model. Indeed, no program that sends or receives messages can automatically be composed with arbitrary programs without jeopardizing their intended behavior. Safety of composition becomes context-sensitive and new tools are needed for ensuring it. A notion of \emph{sealing} is defined, where if a program $P$ is immediately followed by a program $Q$ that seals $P$ then $P$ will be communication-closed--it will execute as if it runs in isolation. The investigation of sealing in this model reveals a novel connection between Lamport causality and safe composition. A characterization of sealable programs is given, as well as efficient algorithms for testing if $Q$ seals $P$ and for constructing a seal for a significant class of programs. It is shown that every sealable program that is open to interference on $O(n^2)$ channels can be sealed using O(n) messages.


title: Can Punctured Rate-1/2 Turbo Codes Achieve a Lower Error Floor than their Rate-1/3 Parent Codes?

abstract: In this paper we concentrate on rate-1/3 systematic parallel concatenated convolutional codes and their rate-1/2 punctured child codes. Assuming maximum-likelihood decoding over an additive white Gaussian channel, we demonstrate that a rate-1/2 non-systematic child code can exhibit a lower error floor than that of its rate-1/3 parent code, if a particular condition is met. However, assuming iterative decoding, convergence of the non-systematic code towards low bit-error rates is problematic. To alleviate this problem, we propose rate-1/2 partially-systematic codes that can still achieve a lower error floor than that of their rate-1/3 parent codes. Results obtained from extrinsic information transfer charts and simulations support our conclusion.


title: Non-binary Hybrid LDPC Codes: Structure, Decoding and Optimization

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


title: On Four-group ML Decodable Distributed Space Time Codes for Cooperative Communication

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


title: Distributed Space-Time Codes for Cooperative Networks with Partial CSI

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


title: Finding low-weight polynomial multiples using discrete logarithm

abstract: Finding low-weight multiples of a binary polynomial is a difficult problem arising in the context of stream ciphers cryptanalysis. The classical algorithm to solve this problem is based on a time memory trade-off. We will present an improvement to this approach using discrete logarithm rather than a direct representation of the involved polynomials. This gives an algorithm which improves the theoretical complexity, and is also very flexible in practice.


title: On formulas for decoding binary cyclic codes

abstract: We adress the problem of the algebraic decoding of any cyclic code up to the true minimum distance. For this, we use the classical formulation of the problem, which is to find the error locator polynomial in terms of the syndroms of the received word. This is usually done with the Berlekamp-Massey algorithm in the case of BCH codes and related codes, but for the general case, there is no generic algorithm to decode cyclic codes. Even in the case of the quadratic residue codes, which are good codes with a very strong algebraic structure, there is no available general decoding algorithm. For this particular case of quadratic residue codes, several authors have worked out, by hand, formulas for the coefficients of the locator polynomial in terms of the syndroms, using the Newton identities. This work has to be done for each particular quadratic residue code, and is more and more difficult as the length is growing. Furthermore, it is error-prone. We propose to automate these computations, using elimination theory and Grbner bases. We prove that, by computing appropriate Grbner bases, one automatically recovers formulas for the coefficients of the locator polynomial, in terms of the syndroms.


title: A bounded-degree network formation game

abstract: Motivated by applications in peer-to-peer and overlay networks we define and study the \emph{Bounded Degree Network Formation} (BDNF) game. In an $(n,k)$-BDNF game, we are given $n$ nodes, a bound $k$ on the out-degree of each node, and a weight $w_{vu}$ for each ordered pair $(v,u)$ representing the traffic rate from node $v$ to node $u$. Each node $v$ uses up to $k$ directed links to connect to other nodes with an objective to minimize its average distance, using weights $w_{vu}$, to all other destinations. We study the existence of pure Nash equilibria for $(n,k)$-BDNF games. We show that if the weights are arbitrary, then a pure Nash wiring may not exist. Furthermore, it is NP-hard to determine whether a pure Nash wiring exists for a given $(n,k)$-BDNF instance. A major focus of this paper is on uniform $(n,k)$-BDNF games, in which all weights are 1. We describe how to construct a pure Nash equilibrium wiring given any $n$ and $k$, and establish that in all pure Nash wirings the cost of individual nodes cannot differ by more than a factor of nearly 2, whereas the diameter cannot exceed $O(\sqrt{n \log_k n})$. We also analyze best-response walks on the configuration space defined by the uniform game, and show that starting from any initial configuration, strong connectivity is reached within $\Theta(n^2)$ rounds. Convergence to a pure Nash equilibrium, however, is not guaranteed. We present simulation results that suggest that loop-free best-response walks always exist, but may not be polynomially bounded. We also study a special family of \emph{regular} wirings, the class of Abelian Cayley graphs, in which all nodes imitate the same wiring pattern, and show that if $n$ is sufficiently large no such regular wiring can be a pure Nash equilibrium.


title: Tagging, Folksonomy & Co - Renaissance of Manual Indexing?

abstract: This paper gives an overview of current trends in manual indexing on the Web. Along with a general rise of user generated content there are more and more tagging systems that allow users to annotate digital resources with tags (keywords) and share their annotations with other users. Tagging is frequently seen in contrast to traditional knowledge organization systems or as something completely new. This paper shows that tagging should better be seen as a popular form of manual indexing on the Web. Difference between controlled and free indexing blurs with sufficient feedback mechanisms. A revised typology of tagging systems is presented that includes different user roles and knowledge organization systems with hierarchical relationships and vocabulary control. A detailed bibliography of current research in collaborative tagging is included.


title: A decision procedure for linear "big O" equations

abstract: Let $F$ be the set of functions from an infinite set, $S$, to an ordered ring, $R$. For $f$, $g$, and $h$ in $F$, the assertion $f = g + O(h)$ means that for some constant $C$, $|f(x) - g(x)| \leq C |h(x)|$ for every $x$ in $S$. Let $L$ be the first-order language with variables ranging over such functions, symbols for $0, +, -, \min, \max$, and absolute value, and a ternary relation $f = g + O(h)$. We show that the set of quantifier-free formulas in this language that are valid in the intended class of interpretations is decidable, and does not depend on the underlying set, $S$, or the ordered ring, $R$. If $R$ is a subfield of the real numbers, we can add a constant 1 function, as well as multiplication by constants from any computable subfield. We obtain further decidability results for certain situations in which one adds symbols denoting the elements of a fixed sequence of functions of strictly increasing rates of growth.


title: On the robustness of the h-index

abstract: The h-index (Hirsch, 2005) is robust, remaining relatively unaffected by errors in the long tails of the citations-rank distribution, such as typographic errors that short-change frequently-cited papers and create bogus additional records. This robustness, and the ease with which h-indices can be verified, support the use of a Hirsch-type index over alternatives such as the journal impact factor. These merits of the h-index apply to both individuals and to journals.


title: Open-architecture Implementation of Fragment Molecular Orbital Method for Peta-scale Computing

abstract: We present our perspective and goals on highperformance computing for nanoscience in accordance with the global trend toward "peta-scale computing." After reviewing our results obtained through the grid-enabled version of the fragment molecular orbital method (FMO) on the grid testbed by the Japanese Grid Project, National Research Grid Initiative (NAREGI), we show that FMO is one of the best candidates for peta-scale applications by predicting its effective performance in peta-scale computers. Finally, we introduce our new project constructing a peta-scale application in an open-architecture implementation of FMO in order to realize both goals of highperformance in peta-scale computers and extendibility to multiphysics simulations.


title: Time-complexity semantics for feasible affine recursions (extended abstract)

abstract: The authors' ATR programming formalism is a version of call-by-value PCF under a complexity-theoretically motivated type system. ATR programs run in type-2 polynomial-time and all standard type-2 basic feasible functionals are ATR-definable (ATR types are confined to levels 0, 1, and 2). A limitation of the original version of ATR is that the only directly expressible recursions are tail-recursions. Here we extend ATR so that a broad range of affine recursions are directly expressible. In particular, the revised ATR can fairly naturally express the classic insertion- and selection-sort algorithms, thus overcoming a sticking point of most prior implicit-complexity-based formalisms. The paper's main work is in extending and simplifying the original time-complexity semantics for ATR to develop a set of tools for extracting and solving the higher-type recurrences arising from feasible affine recursions.


title: Asynchronous Distributed Searchlight Scheduling

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


title: Low SNR Capacity of Fading Channels -- MIMO and Delay Spread

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


title: Practical Binary Adaptive Block Coder

abstract: This paper describes design of a low-complexity algorithm for adaptive encoding/ decoding of binary sequences produced by memoryless sources. The algorithm implements universal block codes constructed for a set of contexts identified by the numbers of non-zero bits in previous bits in a sequence. We derive a precise formula for asymptotic redundancy of such codes, which refines previous well-known estimate by Krichevsky and Trofimov, and provide experimental verification of this result. In our experimental study we also compare our implementation with existing binary adaptive encoders, such as JBIG's Q-coder, and MPEG AVC (ITU-T H.264)'s CABAC algorithms.


title: Analysis of the Sufficient Path Elimination Window for the Maximum-Likelihood Sequential-Search Decoding Algorithm for Binary Convolutional Codes

abstract: A common problem on sequential-type decoding is that at the signal-to-noise ratio (SNR) below the one corresponding to the cutoff rate, the average decoding complexity per information bit and the required stack size grow rapidly with the information length. In order to alleviate the problem in the maximum-likelihood sequential decoding algorithm (MLSDA), we propose to directly eliminate the top path whose end node is $\Delta$-trellis-level prior to the farthest one among all nodes that have been expanded thus far by the sequential search. Following random coding argument, we analyze the early-elimination window $\Delta$ that results in negligible performance degradation for the MLSDA. Our analytical results indicate that the required early elimination window for negligible performance degradation is just twice of the constraint length for rate one-half convolutional codes. For rate one-third convolutional codes, the required early-elimination window even reduces to the constraint length. The suggestive theoretical level thresholds almost coincide with the simulation results. As a consequence of the small early-elimination window required for near maximum-likelihood performance, the MLSDA with early-elimination modification rules out considerable computational burdens, as well as memory requirement, by directly eliminating a big number of the top paths, which makes the MLSDA with early elimination very suitable for applications that dictate a low-complexity software implementation with near maximum-likelihood performance.


title: Fingerprinting Logic Programs

abstract: In this work we present work in progress on functionality duplication detection in logic programs. Eliminating duplicated functionality recently became prominent in context of refactoring. We describe a quantitative approach that allows to measure the ``similarity'' between two predicate definitions. Moreover, we show how to compute a so-called ``fingerprint'' for every predicate. Fingerprints capture those characteristics of the predicate that are significant when searching for duplicated functionality. Since reasoning on fingerprints is much easier than reasoning on predicate definitions, comparing the fingerprints is a promising direction in automated code duplication in logic programs.


title: Recurrence with affine level mappings is P-time decidable for CLP(R)

abstract: In this paper we introduce a class of constraint logic programs such that their termination can be proved by using affine level mappings. We show that membership to this class is decidable in polynomial time.


title: A Backtracking-Based Algorithm for Computing Hypertree-Decompositions

abstract: Hypertree decompositions of hypergraphs are a generalization of tree decompositions of graphs. The corresponding hypertree-width is a measure for the cyclicity and therefore tractability of the encoded computation problem. Many NP-hard decision and computation problems are known to be tractable on instances whose structure corresponds to hypergraphs of bounded hypertree-width. Intuitively, the smaller the hypertree-width, the faster the computation problem can be solved. In this paper, we present the new backtracking-based algorithm det-k-decomp for computing hypertree decompositions of small width. Our benchmark evaluations have shown that det-k-decomp significantly outperforms opt-k-decomp, the only exact hypertree decomposition algorithm so far. Even compared to the best heuristic algorithm, we obtained competitive results as long as the hypergraphs are not too large.


title: Pseudo-codeword Landscape

abstract: We discuss the performance of Low-Density-Parity-Check (LDPC) codes decoded by means of Linear Programming (LP) at moderate and large Signal-to-Noise-Ratios (SNR). Utilizing a combination of the previously introduced pseudo-codeword-search method and a new "dendro" trick, which allows us to reduce the complexity of the LP decoding, we analyze the dependence of the Frame-Error-Rate (FER) on the SNR. Under Maximum-A-Posteriori (MAP) decoding the dendro-code, having only checks with connectivity degree three, performs identically to its original code with high-connectivity checks. For a number of popular LDPC codes performing over the Additive-White-Gaussian-Noise (AWGN) channel we found that either an error-floor sets at a relatively low SNR, or otherwise a transient asymptote, characterized by a faster decay of FER with the SNR increase, precedes the error-floor asymptote. We explain these regimes in terms of the pseudo-codeword spectra of the codes.


title: Variations on the Fibonacci Universal Code

abstract: This note presents variations on the Fibonacci universal code, that may also be called the Gopala-Hemachandra code, that can have applications in source coding as well as in cryptography.


title: Loop Calculus and Belief Propagation for q-ary Alphabet: Loop Tower

abstract: Loop Calculus introduced in [Chertkov, Chernyak '06] constitutes a new theoretical tool that explicitly expresses the symbol Maximum-A-Posteriori (MAP) solution of a general statistical inference problem via a solution of the Belief Propagation (BP) equations. This finding brought a new significance to the BP concept, which in the past was thought of as just a loop-free approximation. In this paper we continue a discussion of the Loop Calculus. We introduce an invariant formulation which allows to generalize the Loop Calculus approach to a q-are alphabet.


title: Artificiality in Social Sciences

abstract: This text provides with an introduction to the modern approach of artificiality and simulation in social sciences. It presents the relationship between complexity and artificiality, before introducing the field of artificial societies which greatly benefited from the computer power fast increase, gifting social sciences with formalization and experimentation tools previously owned by "hard" sciences alone. It shows that as "a new way of doing social sciences", artificial societies should undoubtedly contribute to a renewed approach in the study of sociality and should play a significant part in the elaboration of original theories of social phenomena.


title: A Theory and Calculus for Reasoning about Sequential Behavior

abstract: Basic results in combinatorial mathematics provide the foundation for a theory and calculus for reasoning about sequential behavior. A key concept of the theory is a generalization of Boolean implicant which deals with statements of the form: A sequence of Boolean expressions alpha is an implicant of a set of sequences of Boolean expressions A This notion of a generalized implicant takes on special significance when each of the sequences in the set A describes a disallowed pattern of behavior. That is because a disallowed sequence of Boolean expressions represents a logical/temporal dependency, and because the implicants of a set of disallowed Boolean sequences A are themselves disallowed and represent precisely those dependencies that follow as a logical consequence from the dependencies represented by A. The main result of the theory is a necessary and sufficient condition for a sequence of Boolean expressions to be an implicant of a regular set of sequences of Boolean expressions. This result is the foundation for two new proof methods. Sequential resolution is a generalization of Boolean resolution which allows new logical/temporal dependencies to be inferred from existing dependencies. Normalization starts with a model (system) and a set of logical/temporal dependencies and determines which of those dependencies are satisfied by the model.


title: Constructive Dimension and Turing Degrees

abstract: This paper examines the constructive Hausdorff and packing dimensions of Turing degrees. The main result is that every infinite sequence S with constructive Hausdorff dimension dim_H(S) and constructive packing dimension dim_P(S) is Turing equivalent to a sequence R with dim_H(R) <= (dim_H(S) / dim_P(S)) - epsilon, for arbitrary epsilon > 0. Furthermore, if dim_P(S) > 0, then dim_P(R) >= 1 - epsilon. The reduction thus serves as a *randomness extractor* that increases the algorithmic randomness of S, as measured by constructive dimension. A number of applications of this result shed new light on the constructive dimensions of Turing degrees. A lower bound of dim_H(S) / dim_P(S) is shown to hold for the Turing degree of any sequence S. A new proof is given of a previously-known zero-one law for the constructive packing dimension of Turing degrees. It is also shown that, for any regular sequence S (that is, dim_H(S) = dim_P(S)) such that dim_H(S) > 0, the Turing degree of S has constructive Hausdorff and packing dimension equal to 1. Finally, it is shown that no single Turing reduction can be a universal constructive Hausdorff dimension extractor, and that bounded Turing reductions cannot extract constructive Hausdorff dimension. We also exhibit sequences on which weak truth-table and bounded Turing reductions differ in their ability to extract dimension.


title: Ergodic Capacity of Discrete- and Continuous-Time, Frequency-Selective Rayleigh Fading Channels with Correlated Scattering

abstract: We study the ergodic capacity of a frequency-selective Rayleigh fading channel with correlated scattering, which finds application in the area of UWB. Under an average power constraint, we consider a single-user, single-antenna transmission. Coherent reception is assumed with full CSI at the receiver and no CSI at the transmitter. We distinguish between a continuous- and a discrete-time channel, modeled either as random process or random vector with generic covariance. As a practically relevant example, we examine an exponentially attenuated Ornstein-Uhlenbeck process in detail. Finally, we give numerical results, discuss the relation between the continuous- and the discrete-time channel model and show the significant impact of correlated scattering.


title: Iterative LDPC decoding using neighborhood reliabilities

abstract: In this paper we study the impact of the processing order of nodes of a bipartite graph, on the performance of an iterative message-passing decoding. To this end, we introduce the concept of neighborhood reliabilities of graph's nodes. Nodes reliabilities are calculated at each iteration and then are used to obtain a processing order within a serial or serial/parallel scheduling. The basic idea is that by processing first the most reliable data, the decoder is reinforced before processing the less reliable one. Using neighborhood reliabilities, the Min-Sum decoder of LDPC codes approaches the performance of the Sum-Product decoder.


title: The Multiplexing Gain of MIMO X-Channels with Partial Transmit Side-Information

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