A primary objective of a distributed storage system is to reliably store huge amounts of source data for long periods of time using a large number of high storage capacity nodes. Storage nodes are prone to permanent failures, where such node failures cause all stored data to be permanently lost, and failed nodes are replaced with nodes that initially store no data. To maintain recoverability of the source data as storage nodes fail and are replaced, a total amount of storage capacity that is larger than the source data size is allocated to store the source data, and a repairer continually reads data from and writes data to the storage nodes as they fail and are replaced. We prove information-theoretic lower bounds on the rate at which a repairer reads data from the storage system as a function of the rate at which nodes fail and the amount by which the allocated storage capacity exceeds the source data size. These lower bounds hold for any repairer, i.e., any repairer that does not read data at or above the lower bound rate will provably not maintain recoverability of the source data. The bounds are provably tight asymptotically as the number of storage nodes grows and the allocated storage capacity approaches the source data size.

A liquid system provides durable object storage based on spreading redundantly generated data across a network of hundreds to thousands of potentially unreliable storage nodes. A liquid system uses a combination of a large code , lazy repair , and flow storage organization . We show that a liquid system can be operated to enable flexible and essentially optimal combinations of storage durability, storage overhead, repair bandwidth usage, and access performance.

Over the past few years there has been significant progress towards realizing the vision of a converged Internet and Broadcast media delivery system. Convergence means providing a seamless user experience and reusing the same technologies to provide common functionality (reducing costs and increasing compatibilities), while maintaining the personalization benefits of the Internet and the scalability benefits of Broadcast. In this talk I will describe some of the technologies employed for Internet and Broadcast media delivery, describing commonalities as well as differences.

A review of a collaborative body of work focused on coding theory with applications to scalable media delivery.

This paper provides an overview on the challenges of mobile video streaming focusing on overload situations, variable bandwidth and power consumption issues. Dynamic Adaptive Streaming over HTTP (DASH) is introduced as an enabler to address a significant portion of these challenges. The applicability of the formats to 3G and 4G unicast distribution is provided. Also the applicability of DASH formats for multicast distribution in MBMS is shown. Finally, the usage of DASH in hybrid unicast/multicast is introduced to provide a flexible extension to support different business and delivery models. An outlook to ongoing and future work is provided.

Suppose that we have two users each of which has a k-dimensional vector over a field FQ. Their goal is to communicate their vectors to a common receiver. At the time of reception, the receiver is given side information consisting of some of the entries of the first vector, some entries of the second vector, and the knowledge that some other entries of the two vectors are equal. The task is to design encoders for the two users in such a way that the receiver is able to recover the two vectors when given the side information and some of the entries of the encoded vectors. We call this problem the simultaneous erasure Slepian-Wolf problem, and we provide an optimal solution to this problem using rank-metric codes, provided that the field size.

In this work we address reliablefile delivery over mobile broadcast networks, concentrating on the Raptor codes as specified for Multimedia Broadcast/Multicast Services (MBMS) within 3GPP. We start by describing Luby-Transform (LT) codes, which are the first practical fountain codes. Then, using a natural and easy to understand linear algebra notation, we describe Raptor codes as a powerful extension of LT codes. We provide some insight into the Raptor code structure and some guidelines for implementation of encoders and decoders. Finally, some selected simulations verify the good performance of file distribution with Raptor codes as specified in 3GPP. References to a complete set of simulation results are also provided. I. INTRODUCTION

Third Generation Partnership Project (3GPP) and Digital Video Broadcasting (DVB) have just recently specified the use Raptor codes in their mobile broadcast file delivery engine. Until today, investigations of the applicability of these codes to the mentioned systems have been carried out by assuming almost exclusively quite simple loss models such as statistically independent radio packet losses. Furthermore, the combination and tradeoffs between physical layer parameters such as transmit power or physical layer for-ward error correction code rates in system design has been completely ignored. In this work we investigate the end-to-end system performance by analyzing the trade-off between physical layer parameters and application layer code. In particular we are interested in determining the optimal system operating points for optimized broadcast file delivery. Parameters such as power allocation, mobility model, physical layer Turbo code rate, raptor code expansion ratio are investigated and a single performance criteria is defined, namely the required energy to deliver a file to at least some high percentage of users. It is shown that typically considered system configurations with high transmit power and low physical layer code rates - resulting in low radio block loss rates - are in general suboptimal for efficient delivery. A careful tradeoff the system parameters can reduce the required resources in the order of a magnitude.

We show, using a probabilistic argument, that for any y with 01+y)

In this paper we extend the double verification algorithm of Luby and Mitzenmacher to the class of Raptor codes, analyze it, and design Raptor codes that perform very well with respect to this algorithm

We introduce and analyze verification-based decoding for low-density parity-check (LDPC) codes, an approach specifically designed to manipulate data in packet-sized units. Verification-based decoding requires only linear time for both encoding and decoding and succeeds with high probability under random errors. We describe how to utilize code scrambling to extend our results to channels with errors controlled by an oblivious adversary.

This paper provides an efficient method for analyzing the error probability of the belief propagation (BP) decoder applied to LT Codes. Each output symbol is generated independently by sampling from a distribution and adding the input symbols corresponding to the support of the sampled vector.

We introduce LT codes, the first rateless erasure codes that are very efficient as the data length grows.

This paper introduces Wave and Equation Based Rate Control (WEBRC), the first multiple rate multicast congestion control protocol to be equation based. The equation-based approach enforces fairness to TCP with the benefit that fluctuations in the flow rate are small in comparison to TCP.This paper also introduces the multicast round trip time (MRTT), a multicast analogue of the unicast round trip time (RTT). The MRTT is fundamental to the equation-based protocol that each receiver uses to adjust its reception rate. Each receiver independently measures its own MRTT without placing any added messaging burden on the receiver, the sender or the intermediate network elements. Benefits provided by the MRTT include those that the RTT provides to TCP, e.g., reduced reception rates in reaction to buffer filling and fair sharing of bottleneck links. In addition, the use of MRTT is shown to synchronize and equalize the reception rates of proximate receivers and to cause reception rates to increase as the density of receivers increases.Another innovation of WEBRC is the idea of transmitting data with waves: the transmission rate on a channel is periodic, with an exponentially decreasing form during an active period followed by a quiescent period. Benefits of using waves include insensitivity to large IGMP leave latency; a frequency of joins and leaves by each receiver that is small and independent of the receiver reception rate; the use of a small number of multicast channels; fine-grained control over the receiver reception rate; and minimal, at times nonexistent, losses due to buffer overflow.

We describe fair layered increase/decrease with dynamic layering (FLID-DL): a new multirate congestion control algorithm for layered multicast sessions. FLID-DL generalizes the receiver-driven layered congestion control protocol (RLC) introduced by Vicisano et al. (Proc. IEEE INFOCOM, San Francisco, CA, , p.996-1003, Mar. 1998)ameliorating the problems associated with large Internet group management protocol (IGMP) leave latencies and abrupt rate increases. Like RLC, FLID-DL, is a scalable, receiver-driven congestion control mechanism in which receivers add layers at sender-initiated synchronization points and leave layers when they experience congestion. FLID-DL congestion control coexists with transmission control protocol (TCP) flows as well as other FLID-DL sessions and supports general rates on the different multicast layers. We demonstrate via simulations that our congestion control scheme exhibits better fairness properties and provides better throughput than previous methods. A key contribution that enables FLID-DL and may be useful elsewhere is dynamic layering (DL), which mitigates the negative impact of long IGMP leave latencies and eliminates the need for probe intervals present in RLC. We use DL to respond to congestion much faster than IGMP leave operations, which have proven to be a bottleneck in practice for prior work.

The proliferation of applications that must reliably distribute large, rich content to a vast number of autonomous receivers motivates the design of new multicast and broadcast protocols. We describe an ideal, fully scalable protocol for these applications that we call a digital fountain. A digital fountain allows any number of heterogeneous receivers to acquire content with optimal efficiency at times of their choosing. Moreover, no feedback channels are needed to ensure reliable delivery, even in the face of high loss rates. We develop a protocol that closely approximates a digital fountain using two new classes of erasure codes that for large block sizes are orders of magnitude faster than standard erasure codes. We provide performance measurements that demonstrate the feasibility of our approach and discuss the design, implementation, and performance of an experimental system.

Traditional approaches to receiver-driven layered multicast have advocated the benefits of cumulative layering, which can enable coarse-grained congestion control that complies with TCP-friendliness equations over large time scales. In this paper, we quantify the costs and benefits of using non-cumulative layering and present a new, scalable multicast congestion control scheme which provides a fine-grained approximation to the behavior of TCP additive increase/multiplicative decrease (AIMD). In contrast to the conventional wisdom, we demonstrate that fine-grained rate adjustment can be achieved with only modest increases in the number of layers and aggregate bandwidth consumption, while using only a small constant number of control messages to perform either additive increase or multiplicative decrease.

Consider the following Markov chain, whose states are all domino tilings of a 2n× 2n chessboard: starting from some arbitrary tiling, pick a 2×2 window uniformly at random. If the four squares appearing in this window are covered by two parallel dominoes, rotate the dominoes $90^{\rm o}$ in place. Repeat many times. This process is used in practice to generate a random tiling and is a widely used tool in the study of the combinatorics of tilings and the behavior of dimer systems in statistical physics. Analogous Markov chains are used to randomly generate other structures on various two-dimensional lattices. This paper presents techniques which prove for the first time that, in many interesting cases, a small number of random moves suffice to obtain a uniform distribution.

We introduce a simple erasure recovery algorithm for codes derived from cascades of sparse bipartite graphs and analyze the algorithm by analyzing a corresponding discrete-time random process. As a result, we obtain a simple criterion involving the fractions of nodes of different degrees on both sides of the graph which is necessary and sufficient for the decoding process to finish successfully with high probability. By carefully designing these graphs we can construct for any given rate R and any given real number /spl epsiv/ a family of linear codes of rate R which can be encoded in time proportional to ln(1//spl epsiv/) times their block length n. Furthermore, a codeword can be recovered with high probability from a portion of its entries of length (1+/spl epsiv/)Rn or more. The recovery algorithm also runs in time proportional to n ln(1//spl epsiv/). Our algorithms have been implemented and work well in practice; various implementation issues are discussed.

We construct new families of error-correcting codes based on Gallager's (1973) low-density parity-check codes. We improve on Gallager's results by introducing irregular parity-check matrices and a new rigorous analysis of hard-decision decoding of these codes. We also provide efficient methods for finding good irregular structures for such decoding algorithms. Our rigorous analysis based on martingales, our methodology for constructing good irregular codes, and the demonstration that irregular structure improves performance constitute key points of our contribution. We also consider irregular codes under belief propagation. We report the results of experiments testing the efficacy of irregular codes on both binary-symmetric and Gaussian channels. For example, using belief propagation, for rate 1/4 codes on 16000 bits over a binary-symmetric channel, previous low-density parity-check codes can correct up to approximately 16% errors, while our codes correct over 17%. In some cases our results come very close to reported results for turbo codes, suggesting that variations of irregular low density parity-check codes may be able to match or beat turbo code performance.

A typical approach to estimate an unknown quantity $\mu$ is to design an experiment that produces a random variable Z, distributed in [0,1] with E[Z]=\mu$, run this experiment independently a number of times, and use the average of the outcomes as the estimate. In this paper, we consider the case when no a priori information about Z is known except that is distributed in [0,1]. We describe an approximation algorithm ${\cal A}{\cal A}$ which, given $\epsilon$ and $\delta$, when running independent experiments with respect to any Z, produces an estimate that is within a factor $1+\epsilon$ of $\mu$ with probability at least $1-\delta$. We prove that the expected number of experiments run by ${\cal A}{\cal A}$ (which depends on Z) is optimal to within a constant factor {for every} Z.

Mirror sites enable client requests to be serviced by any of a number of servers, reducing load at individual servers and dispersing network load. Typically, a client requests service from a single mirror site. We consider enabling a client to access a file from multiple mirror sites in parallel to speed up the download. To eliminate complex client-server negotiations that a straightforward implementation of this approach would require, we develop a feedback-free protocol based on erasure codes. We demonstrate that a protocol using fast Tornado codes can deliver dramatic speedups at the expense of transmitting a moderate number of additional packets into the network. This scalable solution extends naturally to allow multiple clients to access data from multiple mirror sites simultaneously. The approach applies naturally to wireless networks and satellite networks as well.

Pseudorandom generators are fundamental to many theoretical and applied aspects of computing. We show how to construct a pseudorandom generator from any one-way function. Since it is easy to construct a one-way function from a pseudorandom generator, this result shows that there is a pseudorandom generator if and only if there is a one-way function.

Developing scalable, reliable multicast protocols for lossy networks presents an array of challenges. In this work we focus on scheduling policies which determine what data the sender places into each sent packet. Our objective is to develop scalable policies which provably deliver a long intact prefix of the message to each receiver at each point in time during the transmission. To accurately represent conditions in existing networks, our theoretical model of the network allows bursty periods of packet loss which can vary widely and arbitrarily over time. Under this general model, we give a proof that there is an inherent performance gap between algorithms which use encoding schemes such as forward error correction (FEC) and those which do not. We then present simple, feedback-free policies which employ FEC and have guaranteed worst-case performance. Our analytic results are complemented by trace-driven simulations which demonstrate the effectiveness of our approach in practice.

The proliferation of applications that must reliably distribute bulk data to a large number of autonomous clients motivates the design of new multicast and broadcast protocols. We describe an ideal, fully scalable protocol for these applications that we call a digital fountain. A digital fountain allows any number of heterogeneous clients to acquire bulk data with optimal efficiency at times of their choosing. Moreover, no feedback channels are needed to ensure reliable delivery, even in the face of high loss rates. We develop a protocol that closely approximates a digital fountain using a new class of erasure codes that are orders of magnitude faster than standard erasure codes. We provide performance measurements that demonstrate the feasibility of our approach and discuss the design, implementation and performance of an experimental system. 1 Introduction Software companies that plan to efficiently disseminate new software over the Internet to millions of users simultaneously will ...

In [6], Gallager introduces a family of codes based on sparse bipartite graphs, which he calls low-density parity-check codes. He suggests a natural decoding algorithm for these codes, and proves a good bound on the fraction of errors that can be corrected. As the codes that Gallager builds are derived from regular graphs, we refer to them as regular codes. Following the general approach introduced in [7] for the design and analysis of erasure codes, we consider error-correcting codes based on random irregular bipartite graphs, which we call irregular codes. We introduce tools based on linear programming for designing linear time irregular codes with better error-correcting capabilities than possible with regular codes. For example, the decoding algorithm for the rate 1/2 regular codes of Gallager can provably correct up to 5.17% errors asymptotically, whereas we have found irregular codes for which our decoding algorithm can provably correct up to 6.27 % errors asymptotically. We include the results of simulations demonstrating the effectiveness of our codes on systems of reasonable size. 1

Abstract | We present randomized constructions of linear-time encodable and decodable codes that can transmit over lossy channels at rates extremely close to capacity. The encoding and decoding algorithms for these codes have fast and simple software implementations. Implementations of our algorithms are faster by orders of magnitude than the software implementations of previous algorithms. We expect these codes will be extremely useful for applications where lossy channels are common and fast decoding is a requirement, e.g., satellite transmission and multicast transmission over the Internet. I.

We present a fully-polynomial scheme to approximate the number of independent sets in graphs with maximum degree four. In general, for graphs with maximum degree \\Delta 4, the scheme approximates a weighted sum of independent sets. The weight of each independent set is expressed in terms of a positive parameter 1 \\Delta\\Gamma3 , where the weight of independent set S is jSj . We also prove complementary hardness of approximation results, which show that it is hard to approximate the weighted sum for values of ? c \\Delta for some constant c > 0.

Approximating the inference probability Pr[X = x | E = e] in any sense, even for a single evidence node E, is NP-hard. This result holds for belief networks that are allowed to contain extreme conditional probabilities—that is, conditional probabilities arbitrarily close to 0. Nevertheless, all previous approximation algorithms have failed to approximate efficiently many inferences, even for belief networks without extreme conditional probabilities. We prove that we can approximate efficiently probabilistic inference in belief networks without extreme conditional probabilities. We construct a randomized approximation algorithm—the bounded-variance algorithm—that is a variant of the known likelihood-weighting algorithm. The bounded-variance algorithm is the first algorithm with provably fast inference approximation on all belief networks without extreme conditional probabilities. From the bounded-variance algorithm, we construct a deterministic approximation algorithm using current advances in the theory of pseudorandom generators. In contrast to the exponential worst-case behavior of all previous deterministic approximations, the deterministic bounded-variance algorithm approximates inference probabilities in worst-case time that is subexponential 2(log n) d, for some integer d that is a linear function of the depth of the belief network.

This paper is concerned with on-line storage allocation to processes in a dynamic environment. This problem has been extensively studied in the past. We provide a new, tighter bound for the competitive ratio of the well-known First Fit algorithm. This bound is obtained by considering a new parameter, namely the maximum number of concurrent active processes. We observe that this bound is also a lower bound on the competitive ratio of any deterministic on-line algorithm. Our second contribution is an on-line allocation algorithm that uses coloring techniques. We show that the competitive ratio of this algorithm is the same as that of First Fit. Furthermore, we indicate that this algorithm may be advantageous in certain applications. Our third contribution is to analyze the performance of randomized algorithms for this problem. We obtain lower bounds on the competitive ratio that are close to the best deterministic upper bounds.

We introduce a new method, called priority encoding transmission, for sending messages over lossy packet-based networks. When a message is to be transmitted, the user specifies a priority value for each part of the message. Based on the priorities, the system encodes the message into packets for transmission and sends them to (possibly multiple) receivers. The priority value of each part of the message determines the fraction of encoding packets sufficient to recover that part. Thus even if some of the encoding packets are lost en-route, each receiver is still able to recover the parts of the message for which a sufficient fraction of the encoding packets are received. For any set of priorities for a message, we define a natural quantity called the girth of the priorities. We develop systems for implementing any given set of priorities such that the total length of the encoding packets is equal to the girth. On the other hand, we give an information-theoretic lower bound that shows that for any set of priorities the total length of the encoding packets must be at least the girth. Thus the system we introduce is optimal in terms of the total encoding length. This work has immediate applications to multimedia and high-speed networks applications, especially in those with bursty sources and multiple receivers with heterogeneous capabilities. Implementations of the system show promise of being practical.

We develop an efficient scheme that produces an encoding of a given message such that the message can be decoded from any portion of the encoding that is approximately equal to the length of the message. More precisely, an (n,c,l,r)-erasure-resilient code consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of l-bit packets of total length cn from an n-bit message. The decoding algorithm is able to recover the message from any set of packets whose total length is r, i.e., from any set of r/l packets. We describe erasure-resilient codes where both the encoding and decoding algorithms run in linear time and where r is only slightly larger than n.

An (n,c,l,r) erasure code consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of l-bit packets of total length cn from an n-bit message. The decoding algorithm is able to recover the message from any set of packets whose total length is r, i.e., from any set of r/l packets. We describe erasure codes where both the encoding and decoding algorithms run in linear time and where r is only slightly larger than n.

A typical approach to estimate an unknown quantity /spl mu/ is to design an experiment that produces a random variable Z distributed in [O,1] with E[Z]=/spl mu/, run this experiment independently a number of times and use the average of the outcomes as the estimate. In this paper, we consider the case when no a priori information about Z is known except that is distributed in [0,1]. We describe an approximation algorithm AA which, given /spl epsiv/ and /spl delta/, when running independent experiments with respect to any Z, produces an estimate that is within a factor 1+/spl epsiv/ of /spl mu/ with probability at least 1-/spl delta/. We prove that the expected number of experiments ran by AA (which depends on Z) is optimal to within a constant factor for every Z.

Consider the following Markov chain, whose states are all domino tilings of a 2n/spl times/2n chessboard: starting from some arbitrary tiling, pick a 2/spl times/2 window uniformly at random. If the four squares appearing in this window are covered by two parallel dominoes, rotate the dominoes in place. Repeat many times. This process is used in practice to generate a random tiling and is a key tool in the study of the combinatorics of tilings and the behavior of dimer systems in statistical physics. Analogous Markov chains are used to randomly generate other structures on various two-dimensional lattices. The paper presents techniques which prove for the first time that, in many interesting cases, a small number of random moves suffice to obtain a uniform distribution.

No abstract available.

We introduce a novel approach for sending messages over lossy packet-based networks. The new method, called Priority Encoding Transmission, allows a user to specify a different priority on each segment of the message. Based on the priorities, the sender uses the system to encode the segments into packets for transmission. The system ensures recovery of the segments in order of their priority. The priority of a segment determines the minimum number of packets sufficient to recover the segment. We define a measure for a set of priorities, called the rate, which dictates how much information about the message must be contained in each bit of the encoding. We develop systems for implementing any set of priorities with rate equal to one. We also give an information-theoretic proof that there is no system that implements a set of priorities with rate greater than one. This work has applications to multi-media and high speed networks applications, especially in those with bursty sources and multiple receivers with heterogeneous capabilities.>

Given d, m and c, we deterministically produce a sequence of points S that hits every combinatorial rectangle in [m]d of volume at least 6.Both the running time of the algorithm and ISI are polynomial in m log(d) /c.This algorithm has applications to deterministic constructions of small sample spaces for general multivalued random variables.

We introduce a fast parallel approximation algorithm for the positive linear programming optimization problem, i.e. the special case of the linear programming optimization problem where the input constraint matrix and constraint vector consist entirely of positive entries.The algorithm is elementary, and has a simple parallel implementation that runs in polylog time using a linear number of processors.

It is known that exact computation of conditional probabilities in belief networks is NP-hard. Many investigators in the AI community have tacitly assumed that algorithms for performing approximate inference with belief networks are of polynomial complexity. Indeed, special cases of approximate inference can be performed in time polynomial in the input size. However, we have discovered that the general problem of approximating conditional probabilities with belief networks, like exact inference, resides in the NP-hard complexity class. We develop a complexity analysis to elucidate the difficulty of approximate probabilistic inference. More specifically, we show that the existence of a polynomial-time relative approximation algorithm for major classes of problem instances implies that NP ⊆ P. We present our proof and explore the implications of the result.

Pseudorandom generators (suggested and developed by Blum and Micali and Yao) are efficient deterministic programs that expand a randomly selected k-bit seed into a much longer pseudorandom bit sequence that is indistinguishable in polynomial time from an (equally long) sequence of unbiased coin tosses. A fundamental question is to find simple conditions, as the existence of one-way functions, which suffice for constructing pseudorandom generators. This paper considers regular functions, in which every image of a k-bit string has the same number of preimages of length k. This paper shows how to construct pseudorandom generators from any regular one-way function.

Let A be an $n \times n$ matrix with 0-1 valued entries, and let ${\operatorname{per}}(A)$ be the permanent of A. This paper describes a Monte-Carlo algorithm that produces a “good in the relative sense” estimate of ${\operatorname{per}}(A)$ and has running time ${\operatorname{poly}}(n)2^{{n / 2}} $, where ${\operatorname{poly}}(n)$ denotes a function that grows polynomially with n.

We describe efficient constructions of small probability spaces that approximate the independent distribution for general random variables. Previous work on efficient constructions concentrate on approximations of the independent distribution for the special case of uniform boolean-valued random variables. Our results yield efficient constructions of small sets with low discrepancy in high dimensional space and have applications to derandomizing randomized algorithms.

We present a randomized simulation of a nlog log (n) log (n)-processor shared memory machine (DMM) with optimal expected delay O(log log (n)) per step of simulation. The time bound for the delay is guaranteed with overwhelming probability. The algorithm is based on hashing and uses a novel simulation scheme. The best previous simulations use a simpler scheme based on hashing and have much larger expected delay: Θ(log(n)/log log (n)) for the simulation of an n-processor PRAM on an n processor DMM, and Θ(log(n)) in the case where the simulation preserves the processor-time product.

The best throw of the die is to throw the die away Chinese fortune cookie

Suppose someone gives us an extremely fast program P that we can call as a black box to compute a function f.Should we trust that P works correctly?A self-testing/correcting pair allows us to: (1) estimate the probability that P(x) 5~ f(x) when x is randomly chosen; (2) on any input x, compute f(x) correctly as long as P is not too faulty on average.Furthermore, both (1) and ( 2) take time only slightly more than the original running time of P.We present general techniques for constructing simple to program self-testing/correcting pairs for a variety of numerical problems, including integer multiplication, modular multiplication, matrix multiplication, inverting matrices, computing the determinant of a matrix, computing the rank of a matrix, integer division, modular exponentiation and polynomial multiplication.

The authors introduce a concept of network decomposition, a partitioning of an arbitrary graph into small-diameter connected components, such that the graph created by contracting each component into a single node has low chromatic number. They present an efficient distributed algorithm for constructing such a decomposition and demonstrate its use for design of efficient distributed algorithms. The method yields new deterministic distributed algorithms for finding a maximal independent set in an arbitrary graph and for ( Delta +1)-coloring of graphs with maximum degree Delta . These algorithms run in O(n/sup epsilon /) time for epsilon =O((log log n/log n)/sup 1/2/), whereas the best previously known deterministic algorithms required Omega (n) time. The techniques can also be used to remove randomness from the previously known most distributed breadth-first search algorithm.>

It is shown that many of the standard cryptographic tasks are equivalent to the usual definition of a one-way function. In particular, it is shown that for some of the standard cryptographic tasks any secure protocol for the task can be converted into a one-way function in the usual sense, and thus the security of any proposed protocol for these tasks is implicitly based on a function being 'one-way.' Thus, the usual definition of a one-way function is robust; any one-way function with respect to another definition on which a secure cryptographic protocol can be based can be used to construct a one-way function in the usual sense. The authors focus on private-key encryption, identification/authentication, bit commitment, and coin flipping by telephone. However, the proof techniques presented here can be easily adopted to prove analogous results for other cryptographic tasks.>

This paper takes the next step in developing the theory of average case complexity initiated by Leonid A Levin. Previous works [Levin 84, Gurevich 87, Venkatesan and Levin 88] have focused on the existence of complete problems. We widen the scope to other basic questions in computational complexity. Our results include: the equivalence of search and decision problems in the context of average case complexity; an initial analysis of the structure of distributional-NP (i.e. NP problems coupled with \\simple distributions") under reductions which preserve average polynomial-time; a proof that if all of distributional-NP is in average polynomial-time then non-deterministic exponential-time equals deterministic exponential time (i.e., a collapse in the worst case hierarchy); denitions and basic theorems regarding other complexity classes such as average log-space. An exposition of the basic denitions suggested by Levin and suggestions for some alternative de nitions are provided as well.

We show that the existence of one-way functions is necessary and sufficient for the existence of pseudo-random generators in the following sense. Let ƒ be an easily computable function such that when x is chosen randomly: (1) from ƒ(x) it is hard to recover an x1 with ƒ(x1) = ƒ(x) by a small circuit, or; (2) ƒ has small degeneracy and from ƒ(x) it is hard to recover x by a fast algorithm. From one-way functions of type (1) or (2) we show how to construct pseudo-random generators secure against small circuits or fast algorithms, respectively, and vice-versa. Previous results show how to construct pseudo-random generators from one-way functions that have special properties ([Blum, Micali 82], [Yao 82], [Levin 85], [Goldreich, Krawczyk, Luby 88]).

Randomized algorithms for approximating the number of perfect matchings in a graph are considered. An algorithm that is a natural simplification of one suggested and analyzed previously is introduced and analyzed. One of the key ideas is to view the analysis from a geometric perspective: it is proved that for any graph G the k-slice of the well-known Edmonds matching polytope has magnification 1. For a bipartite graph G=(U, V, E), mod U mod = mod V mod =n, with d edge-disjoint perfect matchings, it is proved that the ratio of the number of almost perfect matchings to the number of perfect matchings is at most n/sup 3n/d/. For any constant alpha >0 this yields a a fully polynomial randomized algorithm for approximating the number of perfect matchings in bipartite graphs with d>or= alpha n. Moreover, for some constant c>0 it is the fastest known approximation algorithm for bipartite graphs with d>or= clog n.>

Pseudorandom generators are known to exist, assuming the existence of functions that cannot be efficiently inverted on the distributions induced by applying the function iteratively polynomially many times. This sufficient condition is also necessary, but it is difficult to check whether particular functions, assumed to be one-way, are also one-way on their iterates. This raises the fundamental question of whether the mere existence of one-way functions suffices for the construction of pseudorandom generators. Progress toward resolving this question is presented. Regular functions in which every image of a k-bit string has the same number of preimages of length k are considered. It is shown that if a regular function is one-way, then pseudorandom generators do exist. In particular, assuming the intractability of general factoring, it can be proved that the pseudorandom generators do exist. Another application is the construction of a pseudorandom generator based on the assumed intractability of decoding random linear codes.>

Some general techniques are developed for removing randomness from randomized NC algorithms without a blowup in the number of processors. One of the requirements for the application of these techniques is that the analysis of the randomized algorithm uses only pairwise independence. The main new result is a parallel algorithm for the Delta +1 vertex coloring problem with running time O(log/sup 3/ nlog log n) using a linear number of processors on a concurrent-read-concurrent-write parallel random-access machine. The techniques also apply to several other problems, including the maximal-independent-set problem and the maximal-matching problem. The application of the general technique to these last two problems is mostly of academic interest, because NC algorithms using a linear number of processors that have better running times have been previously found.>

We show how to efficiently construct a pseudorandom invertible permutation generator from a pseudorandom function generator. Goldreich, Goldwasser and Micali [“How to construct random functions,” Proc. 25th Annual Symposium on Foundations of Computer Science, October 24–26, 1984.] introduce the notion of a pseudorandom function generator and show how to efficiently construct a pseudorandom function generator from a pseudorandom bit generator. We use some of the ideas behind the design of the Data Encryption Standard for our construction. A practical implication of our result is that any pseudorandom bit generator can be used to construct a block private key cryptosystem which is secure against chosen plaintext attack, which is one of the strongest known attacks against a cryptosystem.

GGM] prove that if there is a Pseudo-random number generator, then there is a pseudo-random function generator.We prove here that if there is a pseudo-random function generator, then there is a pseudo-random permutation generator.We also prove that if two permutation generators which are "slightly secure" are cryptographically composed, the result is more secure than either one alone.

Two basic design strategies are used to develop a very simple and fast parallel algorithms for the maximal independent set (MIS) problem. The first strategy consists of assigning identical copies of a simple algorithm to small local portions of the problem input. The algorithm is designed so that when the copies are executed in parallel the correct problem output is produced very quickly. A very simple Monte Carlo algorithm for the MIS problem is presented which is based upon this strategy. The second strategy is a general and powerful technique for removing randomization from algorithms. This strategy is used to convert the Monte Carlo algorithm for this MIS problem into a simple deterministic algorithm with the same parallel running time.

Simple parallel algorithms for the maximal independent set (MIS) problem are presented. The first algorithm is a Monte Carlo algorithm with a very local property. The local property of this algorithm may make it a useful protocol design tool in distributed computing environments and artificial intelligence. One of the main contributions of this paper is the development of powerful and general techniques for converting Monte Carlo algorithms into deterministic algorithms. These techniques are used to convert the Monte Carlo algorithm for the MIS problem into a simple deterministic algorithm with the same parallel running time.

This paper gives probabilistic analyses of two kinds of multidimensional bin packing problems: vector packing and rectangle packing. In the vector packing problem each of the d dimensions can be interpreted as a resource. A given object i consumes aijunits of the jthresource, and the objects packed in any given bin may not collectively consume more than one unit of any resource. Subject to this constraint, the objects are to be packed into a minimum number of bins. The rectangle packing problem is more geometric in character. The ithobject is a d-dimensional box whose jthside is of length aij, and the goal is to pack the objects into a minimum number of cubical boxes of side 1. We study these problems on the assumption that the aijare drawn independently from the uniform distribution over [0,1]. We study a vector packing heuristic called VPACK that tries to place two objects in each bin and a rectangle packing heuristic called RPACK that tries to pack one object into each of the 2d corners of each bin. We show that each of these heuristics tends to produce packings in which very little of the capacity of the bins is wasted. In the case of rectangle packing, we show that the results can be extended to a wide class of distributions of the piece sizes.

We present a cryptographic protocol allowing two mutually distrusting parties, A and B, each having a secret bit, to "simultaneously" exchange the values of those bits. It is assumed that initially each party presents a correct encryption of his secret bit to the other party. We develop a new tool to implement our protocol: a slightly biased symmetric coin. The key property of this coin is that from each flip A receives a piece of probabilistic information about B's secret bit which is symmetric to the piece of information B receives about A's secret bit.