Search

The impressive capabilities of the mammalian brain--ranging from perception, pattern recognition and memory formation to decision making and motor activity control--have inspired their re-creation in a wide range of artificial intelligence systems for applications such as face recognition, anomaly detection, medical diagnosis and robotic vehicle control (1). Yet before neuron-based brains evolved, complex biomolecular circuits provided individual cells with the 'intelligent' behaviour required for survival (2). However, the study of how molecules can 'think' has not produced an equal variety of computational models and applications of artificial chemical systems. Although biomolecular systems have been hypothesized to carry out neural-network-like computations in vivo (3,2,4) and the synthesis of artificial chemical analogues has been proposed theoretically (5-9), experimental work (10-13) has so far fallen short of fully implementing even a single neuron. Here, building on the richness of DNA computing (14) and strand displacement circuitry (15), we show how molecular systems can exhibit autonomous brain-like behaviours. Using a simple DNA gate architecture (16) that allows experimental scale-up of multilayer digital circuits (17), we systematically transform arbitrary linear threshold circuits (18) (an artificial neural network model) into DNA strand displacement cascades that function as small neural networks. Our approach even allows us to implement a Hopfield associative memory (19) with four fully connected artificial neurons that, after training insilico, remembers four single-stranded DNA patterns and recalls the most similar one when presented with an incomplete pattern. Our results suggest that DNA strand displacement cascades could be used to endow autonomous chemical systems with the capability of recognizing patterns of molecular events, making decisions and responding to the environment., The human brain is composed of ~[10.sup.11] neurons, and each has a few thousand synapses. Each synapse can receive signals from other neurons, raising or lowering the electrical potential inside [...]

We explore a novel data representation scheme for multilevel flash memory cells, in which a set of n cells stores information in the permutation induced by the different charge levels of the individual cells. The only allowed charge-placement mechanism is a "push-to-the-top" operation, which takes a single cell of the set and makes it the top-charged cell. The resulting scheme eliminates the need for discrete cell levels, as well as overshoot errors, when programming cells. We present unrestricted Gray codes spanning all possible n-cell states and using only "push-to-the-top" operations, and also construct balanced Gray codes. One important application of the Gray codes is the realization of logic multilevel cells, which is useful in conventional storage solutions. We also investigate rewriting schemes for random data modification. We present both an optimal scheme for the worst case rewrite performance and an approximation scheme for the average-case rewrite performance. Index Terms--Asymmetric channel, flash memory, Gray codes, permutations, rank modulation.

Three new families of lowest density maximum-distance separable (MDS) array codes are constructed, which are cyclic or quasi-cyclic. In addition to their optimal redundancy (MDS) and optimal update complexity (lowest density), the symmetry offered by the new codes can be utilized for simplified implementation in storage applications. The proof of the code properties has an indirect structure: first MDS codes that are not cyclic are constructed, and then transformed to cyclic codes by a minimum-distance preserving transformation. Index Terms--Array codes, cyclic codes, low-density parity-check codes, maximum-distance separable (MDS) codes, systematically cyclic codes.

The existence of a perfect 1-factorization of the complete graph with n nodes, namely, [K.sub.n], for arbitrary even number n, is a 40-year-old open problem in graph theory. So far, two infinite families of perfect 1-factorizations have been shown to exist, namely, the factorizations of [K.sub.p+1] and [K.sub.2p], where p is an arbitrary prime number (p > 2). It was shown in previous work that finding a perfect 1-factorization of [K.sub.n] is related to a problem in coding, specifically, it can be reduced to constructing an MDS (Minimum Distance Separable), lowest density array code. In this paper, a new method for shortening arbitrary array codes is introduced. It is then used to derive the [K.sub.p+1] family of perfect 1-factorization from the [K.sub.2p] family. Namely, techniques from coding theory are used to prove a new result in graph theory--that the two factorization families are related. Index Terms--Array codes, error-correcting codes, graph theory, 1-factorization, perfect 1-factorization.

In this work, we study the computational perspective of network coding, focusing on two issues. First, we address the computational complexity of finding a network code for acyclic multicast networks. Second, we address the issue of reducing the amount of computation performed by network nodes. In particular, we consider the problem of finding a network code with the minimum possible number of encoding nodes, i.e., nodes that generate new packets by performing algebraic operations on packets received over incoming links. We present a deterministic algorithm that finds a feasible network code for a multicast network over an underlying graph G(V, E) in time O([absolute value of E]kh + [absolute value of V][k.sup.2]h.sup.2] + [h.sup.3][k.sup.3](k + h)), where k is the number of destinations and h is the number of packets. Our algorithm improves the best known running time for network code construction. In addition, our algorithm guarantees that the number of encoding nodes in the obtained network code is upper-bounded by O([h.sup.3][k.sup.2]). Next, we address the problem of finding integral and fractional network codes with the minimum number of encoding nodes. We prove that in the majority of settings this problem is NP-hard. However, we show that if h = O(1), h = O(1), and the underlying communication graph is acyclic, then there exists an algorithm that solves this problem in polynomial time. Index Terms--Algorithms, computational perspective, encoding complexity, fractional network coding, integer network coding, multicast connections.

We study broadcast systems that distribute a series of data updates to a large number of passive clients. The updates are sent over a broadcast channel in the form of discrete packets. We assume that clients periodically access the channel to obtain the most recent update. Such scenarios arise in many practical applications, such as distribution of traffic information and market updates to mobile wireless devices. Our goal is to design broadcast schedules that minimize the waiting time, i.e., the amount of time the client needs to wait in order to obtain the most recent update. We assume that each client has a different access pattern depending on the channel conditions, computing power, and storage capabilities. We introduce and analyze optimal universal schedules that guarantee low waiting time for any client, regardless of its behavior. Index Terms--Broadcast systems, data updates, universal schedules, waiting time.

We address the well-known problem of determining the capacity of constrained coding systems. While the one-dimensional case is well understood to the extent that there are techniques for rigorously deriving the exact capacity, in contrast, computing the exact capacity of a two-dimensional constrained coding system is still an elusive research challenge. The only known exception in the two-dimensional case is an exact (however, not rigorous) solution to the (1, [infinity])-run-length limited (RLL) system on the hexagonal lattice. Furthermore, only exponential-time algorithms are known for the related problem of counting the exact number of constrained two-dimensional information arrays. We present the first known rigorous technique that yields an exact capacity of a two-dimensional constrained coding system. In addition, we devise an efficient (polynomial time) algorithm for counting the exact number of constrained arrays of any given size. Our approach is a composition of a number of ideas and techniques: describing the capacity problem as a solution to a counting problem in networks of relations, graph-theoretic tools originally developed in the field of statistical mechanics, techniques for efficiently simulating quantum circuits, as well as ideas from the theory related to the spectral distribution of Toeplitz matrices. Using our technique, we derive a closed-form solution to the capacity related to the Path-Cover constraint in a two-dimensional triangular array (the resulting calculated capacity is 0.72399217 ...). Path-Cover is a generalization of the well known one-dimensional (0, 1)-RLL constraint for which the capacity is known to be 0.69424.... Index Terms--Capacity of constrained systems, capacity of two-dimensional constrained systems, Fisher-Kasteleyn-Temperley (FKT) method, holographic reductions, networks of relations, spectral distribution of Toeplitz matrices.

In the multicast network coding problem, a source s needs to deliver h packets to a set of k terminals over an underlying communication network G. The nodes of the multicast network can be broadly categorized into two groups. The first group incudes encoding nodes, i.e., nodes that generate new packets by combining data received from two or more incoming links. The second group includes forwarding nodes that can only duplicate and forward the incoming packets. Encoding nodes are, in general, more expensive due to the need to equip them with encoding capabilities. In addition, encoding nodes incur delay and increase the overall complexity of the network. Accordingly, in this paper, we study the design of multicast coding networks with a limited number of encoding nodes. We prove that in a directed acyclic coding network, the number of encoding nodes required to achieve the capacity of the network is bounded by [h.sup.3][k.sup.2]. Namely, we present (efficiently constructible) network codes that achieve capacity in which the total number of encoding nodes is independent of the size of the network and is bounded by [h.sup.3][k.sup.2]. We show that the number of encoding nodes may depend both on h and k by presenting acyclic coding networks that require [OMEGA]([h.sup.2k]) encoding nodes. In the general case of coding networks with cycles, we show that the number of encoding nodes is limited by the size of the minimum feedback link set, i.e., the minimum number of links that must be removed from the network in order to eliminate cycles. We prove that the number of encoding nodes is bounded by (2B + 1)[h.sup.3][k.sup.2], where B is the minimum size of a feedback link set. Finally, we observe that determining or even crudely approximating the minimum number of required encoding nodes is an NP-hard problem. Index Terms--Coding networks, encoding links, encoding nodes, multicast, network coding.

Interleaving codewords is an important method not only for combatting burst errors, but also for distributed data retrieval. This paper introduces the concept of multicluster interleaving (MCI), a generalization of traditional interleaving problems. MCI problems for paths and cycles are studied. The following problem is solved: how to interleave integers on a path or cycle such that any m (m [greater than or equal to] 2) nonoverlapping clusters of order 2 in the path or cycle have at least three distinct integers. We then present a scheme using a "hierarchical-chain structure" to solve the following more general problem for paths: how to interleave integers on a path such that any m (m[greater than or equal to] 2) nonoverlapping clusters of order L (L [greater than or equal to] 2) in the path have at least L + 1 distinct integers. It is shown that the scheme solves the second interleaving problem for paths that are asymptotically as long as the longest path on which an MCI exists, and clearly, for shorter paths as well. Index Terms--Burst error, cluster, cycle, file placement, interleaving, multicluster interleaving (MCI), path.

This paper shows that a reasonably accurate description of propagation loss in small urban cells can be obtained with a simple stochastic model based on the theory of random walks, that accounts for only two parameters: the amount of clutter and the amount of absorption in the environment. Despite the simplifications of the model, the derived analytical solution correctly describes the smooth transition of power attenuation from an inverse square law with the distance to the transmitter, to an exponential attenuation as this distance is increased--as it is observed in practice. Our analysis suggests using a simple exponential path loss formula as an alternative to the empirical formulas that are often used for prediction. Results are validated by comparison with experimental data collected in a small urban cell. Index Terms--Microcellular systems, path loss, random media, random walks, wave propagation.

In this paper, we study a model that mimics the programming operation of memory cells. This model was first introduced by Lastras-Montano et al. for continuous-alphabet channels, and later by Bunte and Lapidoth for discrete memoryless channels (DMC). Under this paradigm we assume that cells are programmed sequentially and individually. The programming process is modeled as transmission over a channel, such that it is possible to read the cell state in order to determine its programming success, and in case of programming failure, to reprogram the cell again. Reprogramming a cell can reduce the bit error rate, however this comes with the price of increasing the overall programming time and thereby affecting the writing speed of the memory. An iterative programming scheme is an algorithm which specifies the number of attempts to program each cell. Given the programming channel and constraints on the average and maximum number of attempts to program a cell, we study programming schemes which maximize the number of bits that can be reliably stored in the memory. We extend the results by Bunte and Lapidoth and study this problem when the programming channel is either discrete-input memoryless symmetric channel (including the BSC,BEC, BI-AWGN) or the $Z$ channel. For the BSC and the BEC our analysis is also extended for the case where the error probabilities on consecutive writes are not necessarily the same. Lastly, we also study a related model which is motivated by the synthesis process of DNA molecules. [ABSTRACT FROM AUTHOR]

The broadcast disk provides an effective way to transmit information from a server to many clients. Work has been done to schedule the broadcast of information in a way that minimizes the expected waiting time of the clients. Much of this work has treated the information as indivisible blocks. We look at splitting items into smaller pieces that need not be broadcast consecutively. This allows us to have better schedules with lower expected waiting times. We look at the case of two items of the same length, each split into two halves, and show how to achieve optimal performance. We prove the surprising result that there are only two possible types of optimal cyclic schedules for items 1 and 2. These start with 1122 and 122122. For example, with demand probabilities [p.sub.1] = 0.08 and [p.sub.2] = 0.92, the best order to use in broadcasting the halves of items 1 and 2 is a cyclic schedule with cycle 122122222. We also look at items of different lengths and show that much of the analysis remains the same, resulting in a similar set of optimal schedules. Index terms--Asymmetric communication, broadcast disk, mobile computing, scheduling, splitting, wireless.

An important issue in analog circuit design is the problem of digital-to-analog conversion, i.e., the encoding of Boolean variables into a single analog value which contains enough information to reconstruct the values of the Boolean variables. A natural question is: What is the complexity of implementing the digital-to-analog encoding function? That question was recently answered by Wegener, who proved matching lower and upper bounds on the size of the circuit for the encoding function. In particular, it was proven that [(3n - 1)/2] 2-input arithmetic gates are necessary and sufficient for implementing the encoding function of n Boolean variables. However, the proof of the upper bound is not constructive. In this paper, we present an explicit construction of a digital-to-analog encoder that is optimal in the number of 2-input arithmetic gates. In addition, we present an efficient analog-to-digital decoding algorithm. Namely, given the encoded analog value, our decoding algorithm reconstructs the original Boolean values. Our construction is suboptimal in that it uses constants of maximum size n log n bits; the nonconstructive proof uses constants of maximum size 2n + [log n] bits. Index Terms - Complexity, construction, decoding, digital-to-analog, encoding.

A study was conducted to develop programmable threshold elements on silicon using floating gates to store weights. A neuron-based circuit that supported an arbitrary Boolean function was utilized in the study. The 16-input threshold element was then determined using a conventional 2 mu-m double-poly, analog process. Results indicated that the system's storage permitted the modification of weights through tunneling and injection processes.

A deterministic majority voting algorithm for N Modular Redundant systems was developed. The effectiveness of the algorithm can be enhanced by selecting parameters of the error-correcting code that correspond to the probability of the computational faults. The algorithm, which required two or three rounds of communication, was then applied to a network of workstations, for which the results agreed well with theoretical predictions.

Proposed efficient algorithms for two all-to-all communication operations in message-passing systems, namely, index and concatenation, are presented. A model of a fully connected message-passing system, in which the performance of any point-to-point communication is independent of the sender-receiver pair, is assumed. It is also assume that each processor has k > or - 1 ports. Experimental results featuring the performance funeability of index algorithms on the IBM SP-1 parallel system are presented. Also presented is a concatenation algorithm that is optimal for most values of n.

Hypercubes, meshes, tori, and Omega networks are well-known interconnection networks for parallel computers. The structure of those graphs can be described in a more general framework called cube graphs. The idea is to assume that every node in a graph with [q.sup.l] nodes is represented by a unique string of l symbols over GF (q). The edges are specified by a set of offsets, those are vectors of length l over GF (q), where the two endpoints of an edge are an offset apart. We study techniques for tolerating edge faults in cube graphs that are based on adding redundant edges. The redundant graph has the property that the structure of the original graph can be maintained in the presence of edge faults. Our main contribution is a technique for adding the redundant edges that utilizes constructions of error-correcting codes and generalizes existing ad hoc techniques. Index Terms - Fault tolerance, parallel computing, interconnection networks, hypercubes, omega networks, error-correcting codes.

The postal model, developed for design and use of broadcast operations and global combine operations, improves their performance prediction and tuning. A trade-off is present between the delay-receive and delay-send methods. Efficient algorithms estimate the latency and the number of nodes as parameters. Techniques to estimate the communication latency parameter are proposed.

Current approach for the detection of cancer is based on identifying genetic mutations typical to tumor cells. This approach is effective only when cancer has already emerged, however, it might be in a stage too advanced for effective treatment. Cancer is caused by the continuous accumulation of mutations; is it possible to measure the time-dependent information of mutation accumulation and predict the emergence of cancer? We hypothesize that the mutation history derived from the tandem repeat regions in blood-derived DNA carries information about the accumulation of the cancer driver mutations in other tissues. To validate our hypothesis, we computed the mutation histories from the tandem repeat regions in blood-derived exomic DNA of 3874 TCGA patients with different cancer types and found a statistically significant signal with specificity ranging from 66% to 93% differentiating Glioblastoma patients from other cancer patients. Our approach and findings offer a new direction for future cancer prediction and early cancer detection based on information derived from blood-derived DNA. [ABSTRACT FROM AUTHOR]

A multiport postal model, used in a message-passing system, has three parameters: the number of processors, number of ports per processor and communication latency. In message-passing systems, global combine operation is very commonly used. A newly developed optimal algorithm, used for solving the global combine problem, uses the fewest communication rounds. The time required to send and receive messages is reduced considerably.

A Collective Communication Library (CCL) developed for scalable parallel computers involves functions such as scatter, broadcast, synchronize, gather, reduce, concatenate and shift. The parallel application programming interface of the IBM 9076 Scalable POWERparallel system 1 includes the CCL. The performance and correctness of the CCL with special reference to incorporation of process groups, description of correctness-ensuring semantics and development of tunable algorithms are discussed.