Arrow Research search

Author name cluster

Michael Luby

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

33 papers
2 author rows

Possible papers

33

FOCS Conference 2002 Conference Paper

LT Codes

  • Michael Luby

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

Details

AIJ Journal 1997 Journal Article

An optimal approximation algorithm for Bayesian inference

  • Paul Dagum
  • Michael Luby

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.

Details DOI

FOCS Conference 1995 Conference Paper

An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract)

  • Paul Dagum
  • Richard M. Karp
  • Michael Luby
  • Sheldon M. Ross

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.

Details

FOCS Conference 1995 Conference Paper

Linear Time Erasure Codes with Nearly Optimal Recovery (Extended Abstract)

  • Noga Alon
  • Jeff Edmonds
  • Michael Luby

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.

Details

FOCS Conference 1995 Conference Paper

Markov Chain Algorithms for Planar Lattice Structures (Extended Abstract)

  • Michael Luby
  • Dana Randall
  • Alistair Sinclair

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.

Details

FOCS Conference 1994 Conference Paper

Priority Encoding Transmission

  • Andres Albanese
  • Johannes Blömer
  • Jeff Edmonds
  • Michael Luby
  • Madhu Sudan 0001

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. >

Details

AIJ Journal 1993 Journal Article

Approximating probabilistic inference in Bayesian belief networks is NP-hard

  • Paul Dagum
  • Michael Luby

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.

Details DOI

TCS Journal 1992 Journal Article

Approximating the permanent of graphs with large factors

  • Paul Dagum
  • Michael Luby

Let G=(U, V, E) be a bipartite graph with |U|=|V|=n. The factor size of G, f, is the maximum number of edge disjoint perfect matchings in G. We characterize the complexity of counting the number of perfect matchings in classes of graphs parameterized by factor size. We describe the simple algorithm, which is an approximation algorithm for the permanent that is a natural simplification of the algorithm suggested by Broder (1986) and analyzed by Jerrum and Sinclair (1988a, b). Compared to the algorithm by Jerrum and Sinclair (1988a, b), the simple algorithm achieves a polynomial speed up in the running time to compute the permanent. A combinatorial lemma is used to prove that the simple algorithm runs in time n O(n/f). Thus: (1) for all constants α>0, the simple algorithm runs in polynomial time for graphs with factor size at least αn; (2) for some constant c, the simple algorithm is the fastest known approximation for graphs with factor size at least c log n. (Compare with the approximation algorithms described in Karmarkar (1988).) We prove the following complementary hardness results. For functions f such that 3⩽f(n)⩽n−3, the exact counting problem for f(n)-regular bipartite graphs is #P-complete. For and ε>0, for any function f such that 3⩽f(n)⩽n 1−ε, approximate counting for f(n)-regular bipartite graphs is as hard as approximate counting for all bipartite graphs. An announcement of these results appears in Dagum (1988).

Details DOI

STOC Conference 1992 Conference Paper

Approximations of General Independent Distributions

  • Guy Even
  • Oded Goldreich 0001
  • Michael Luby
  • Noam Nisan
  • Boban Velickovic

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.

Details

FOCS Conference 1989 Conference Paper

Network Decomposition and Locality in Distributed Computation

  • Baruch Awerbuch
  • Andrew V. Goldberg
  • Michael Luby
  • Serge A. Plotkin

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. >

Details

STOC Conference 1989 Conference Paper

On the Theory of Average Case Complexity

  • Shai Ben-David
  • Benny Chor
  • Oded Goldreich 0001
  • Michael Luby

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 under reductions which preserve average polynomial-time; a proof that if all 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); definitions and basic theorems regarding other complexity classes such as average log-space.

Details

FOCS Conference 1989 Conference Paper

One-way Functions are Essential for Complexity Based Cryptography (Extended Abstract)

  • Russell Impagliazzo
  • Michael Luby

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. >

Details

FOCS Conference 1988 Conference Paper

On the Existence of Pseudorandom Generators (Extended Abstract)

  • Oded Goldreich 0001
  • Hugo Krawczyk
  • Michael Luby

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. >

Details

FOCS Conference 1988 Conference Paper

Polytopes, Permanents and Graphs with Large Factors

  • Paul Dagum
  • Michael Luby
  • Milena Mihail
  • Umesh V. Vazirani

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. >

Details

FOCS Conference 1988 Conference Paper

Removing Randomness in Parallel Computation Without a Processor Penalty

  • Michael Luby

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. >

Details

STOC Conference 1985 Conference Paper

A Simple Parallel Algorithm for the Maximal Independent Set Problem

  • Michael Luby

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.

Details

FOCS Conference 1983 Conference Paper

How to Simultaneously Exchange a Secret Bit by Flipping a Symmetrically-Biased Coin

  • Michael Luby
  • Silvio Micali
  • Charles Rackoff

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.

Details
v2026.09.13