AL-FEC for Improved Mobile Reception of MPEG-2 DVB-T Transport Streams (2009)
David Gozálvez, David Gómez-Barquero, Thomas Stockhammer, Michael Luby
We investigate the use of application layer FEC protection in DVB-T (Digital Video Broadcasting-Terrestrial) networks for the provision of mobile services. Mobile reception is characterized by...
AL-FEC for Improved Mobile Reception of MPEG-2 DVB-T Transport Streams (2009)
David Gozálvez, David Gómez-Barquero, Thomas Stockhammer, Michael Luby
We investigate the use of application layer FEC protection in DVB-T (Digital Video Broadcasting-Terrestrial) networks for the provision of mobile services. Mobile reception is characterized by...
Michael Luby, Avi Wigderson, Trends R In
Published, sold and distributed by: now Publishers Inc.
Fine-Grained Layered Multicast with STAIR (2008)
John W. Byers, Gu-in Kwon, Michael Luby, Michael Mitzenmacher
Abstract—Traditional approaches to receiver-driven layered multicast have advocated the benefits of cumulative layering, which can enable coarse-grained congestion control that complies with...
ABSTRACT FLID-DL: Congestion Control for Layered Multicast (2008)
John Byers, Michael Frumin, Gavin Horn, Michael Luby, Michael Mitzenmacher, Alex Roetter, ...
Abstract A Digital Fountain Approach to Reliable Distribution of Bulk Data (2008)
John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege
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,...
SUBMITTED TO IEEE/ACM TRANSACTIONS ON NETWORKING 1 Fine-Grained Layered Multicast with STAIR (2008)
John W. Byers, Gu-in Kwon, Michael Luby, Michael Mitzenmacher
Abstract—Traditional approaches to receiver-driven layered multicast have advocated the benefits of cumulative layering, which can enable coarse-grained congestion control that complies with...
Security of Blind Digital Signatures (Revised Extended Abstract) (2008)
Ari Juels, Michael Luby, Rafail Ostrovsky
Abstract. Blind digital signatures were introduced by Chaum. In this paper, we show how security and blindness properties for blind digital signatures, can be simultaneously defined and satisfied in...
Application Layer Forward Error Correction for Mobile Multimedia Broadcasting (2008)
Stockhammer, Thomas, Shokrollahi, Amin, Watson, Mark, Luby, Michael, Gasiba, Tiago
Application Layer Forward Error Correction (AL-FEC) is an innovative way to provide reliability in mobile broadcast systems. Conventional data such as multimedia files or multimedia streams are...
1 Fine-Grained Layered Multicast (2007)
John Byers, Michael Luby, Michael Mitzenmacher
Abstract--- Traditional approaches to receiver-driven layered multicast have advocated the benefits of cumulative layering, which enables coarse-grained congestion control and complies with...
1 Fine-Grained Layered Multicast (2007)
John Byers, Michael Luby, Michael Mitzenmacher
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...
Verification Codes: Simple Low-Density Parity-Check Codes for Large Alphabets (2007)
Michael Luby, Michael Mitzenmacher
Most work in low-density parity-check codes focuses on bit-level errors. In this paper, we introduce and analyze verification codes, which are simple low-density parity-check codes specifically...
Abstract A Digital Fountain Approach to Reliable Distribution of Bulk Data (2007)
John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege
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,...
Manuel Blum, Michael Luby, Ronitt Rubinfeld
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)...
Competitive Paging Algorithms Amos Fiat 1 (2007)
Richard M. Karp, Michael Luby, Lyle A. Mcgeoch, Daniel D. Sleator, Neal E. Young
The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. We develop the marking algorithm, a randomized on-line algorithm for...
We describe Fair Layered Increase/Decrease with Dynamic (2007)
John W. Byers, Gavin Horn, Michael Luby, Michael Mitzenmacher, William Shaver
We describe Fair Layered Increase/Decrease with Dynamic Layering (FLID-DL), a new multi-rate congestion control algorithm for layered multicast sessions. FLIDDL generalizes the receiver-driven...
Wave and Equation Based Rate Control Using (2007)
Multicast Round, Trip Time, Michael Luby, Vivek K Goyal
Wave and Equation Based Rate Control (WEBRC) is a new equation-based, multiple rate congestion control protocol that is naturally suited to multicast but also applicable to unicast. No previous...
Wave and equation based rate control using multicast round trip time (2002)
Michael Luby, Vivek K Goyal, Simon Skaria, Gavin B. Horn
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...
A Digital Fountain Approach to Asynchronous Reliable Multicast (2002)
John W. Byers, Michael Luby, Michael Mitzenmacher
Abstract—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....
A Digital Fountain Approach to Asynchronous Reliable Multicast (2002)
John W. Byers, Michael Luby, Michael Mitzenmacher
Abstract 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...
Michael Luby, Michael Mitzenmacher
Most work in low-density parity-check codes focuses on bit-level errors. In this paper, we introduce and analyze verification codes, which are simple low-density parity-check codes specifically...
A Digital Fountain Approach to Asynchronous Reliable Multicast (2002)
John W. Byers, Michael Luby, Michael Mitzenmacher
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...
Fine-grained layered multicast (2001)
John Byers, Michael Luby, Michael Mitzenmacher
Abstract--- Traditional approaches to receiver-driven layered multicast have advocated the benefits of cumulative layering, which can enable coarse-grained congestion control that complies with...
Fine-grained layered multicast (2001)
John Byers, Michael Luby, Michael Mitzenmacher
Abstract--- Traditional approaches to receiver-driven layered multicast have advocated the benefits of cumulative layering, which can enable coarse-grained congestion control that complies with...
Fine-grained layered multicast (2001)
John Byers, Michael Luby, Michael Mitzenmacher
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...
Improved low-density parity-check codes using irregular graphs (2001)
Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, Dan Spielman, Michael G. Luby, Daniel A. Spielman
We construct new families of error-correcting codes based on Gallager’s low-density parity-check codes, which we call irregular codes. When decoded using belief propagation, our codes can correct...
Improved low-density parity-check codes using irregular graphs (2001)
Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, Dan Spielman, Michael G. Luby, Daniel A. Spielman
We construct new families of error-correcting codes based on Gallager’s low-density parity-check codes, which we call irregular codes. When decoded using belief propagation, our codes can correct...
Improved low-density parity-check codes using irregular graphs (2001)
Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, Dan Spielman, Michael G. Luby, Daniel A. Spielman
We construct new families of error-correcting codes based on Gallager’s low-density parity-check codes, which we call irregular codes. When decoded using belief propagation, our codes can correct...
Flid-dl: Congestion control for layered multicast (2000)
John W. Byers, Gavin Horn, Michael Luby, Michael Mitzenmacher, William Shaver
Abstract—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...
FLID-DL: Congestion Control for Layered Multicast (2000)
John Byers, Michael Frumin, Gavin Horn, Michael Luby, Michael Mitzenmacher, Alex Roetter, ...
We describe Fair Layered Increase/Decrease with Dynamic Layering (FLID-DL), a new multi-rate congestion control algorithm for layered multicast sessions. FLID-DL generalizes the receiver-driven...
FLID-DL: Congestion Control for Layered Multicast (2000)
John Byers Michael, Michael Frumin, Gavin Horn, Michael Luby, Michael Mitzenmacher, Alex Roetter, ...
We describe Fair Layered Increase/Decrease with Dynamic Layering (FLID-DL), a new multi-rate congestion control algorithm for layered multicast sessions. FLID-DL generalizes the receiver-driven...
A Pseudorandom Generator from any One-way Function (1999)
Johan Håstad, Russell Impagliazzo, Leonid A. Levin, Michael Luby
Pseudorandom generators are fundamental to many theoretical and applied aspects of computing. We show how to construct a pseudorandom generator from any oneway function. Since it is easy to construct...
A Pseudorandom Generator from any One-way Function (1999)
Johan Håstad, Leonid A. Levin, Michael Luby
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...
Fast Convergence of the Glauber Dynamics for Sampling Independent Sets: Part I (1999)
We consider the problem of sampling independent sets of a graph with maximum degree ffi. The weight of each independent set is expressed in terms of a fixed positive parameter 2 ffi\Gamma2 , where...
Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed Up Downloads (1999)
John Byers, Michael Luby, Michael Mitzenmacher
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...
Combinatorial Bounds for Broadcast Encryption (1998)
Abstract. A broadcast encryption system allows a center to communi-cate securely over a broadcast channel with selected sets of users. Each time the set of privileged users changes, the center enacts...
A digital fountain approach to reliable distribution of bulk data (1998)
John W. Byers, Michael Luby, Michael Mitzenmacher
Abstract—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...
A Digital Fountain Approach to Reliable Distribution of Bulk Data (1998)
John W. Byers, John W. Byers, Michael Luby, Michael Luby, Michael Mitzenmacher, Michael Mitzenmacher, ...
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,...
Improved Low-Density Parity-Check Codes Using Irregular Graphs and Belief Propagation (1998)
Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, Dan Spielman, Daniel A. Spielman
We construct new families of error-correcting codes based on Gallager's low-density parity-check codes, which we call irregular codes. When decoded using belief propagation, our codes can...
Accessing Multiple Mirror Sites in Parallel: Using Tornado Codes to Speed Up Downloads (1998)
John W. Byers, Michael Luby, Michael Mitzenmacher
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...
Combinatorial Bounds for Broadcast Encryption (1998)
. A broadcast encryption system allows a center to communicate securely over a broadcast channel with selected sets of users. Each time the set of privileged users changes, the center enacts a...
Practical Loss-Resilient Codes (1998)
Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, Daniel Spielman, Volker Stemann
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...
Feedback-Free Multicast Prefix Protocols (1998)
Yair Bartal John, John W. Byers, Michael Luby, Danny Raz
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...
Efficient Approximation of Product Distributions (1998)
Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic
We describe efficient constructions of small probability spaces that approximate the joint distribution of general random variables. Previous work on efficient constructions concentrate on...
Feedback-Free Multicast Prefix Protocols (1998)
Yair Bartal, John W. Byers, Michael Luby, Danny Raz
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...
A Digital Fountain Approach to Reliable Distribution of Bulk Data (1998)
John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege
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,...
A Digital Fountain Approach to Reliable Distribution of Bulk Data (1998)
John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege
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,...
John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege
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,...
Improved Low-Density Parity-Check Codes Using Irregular Graphs and Belief Propagation (1998)
Michael Luby, Michael Mitzenmacher, M. Amin Shokrollahi, M. Amin, Daniel A. Spielman
We construct new families of error-correcting codes based on Gallager's low-density parity-check codes, which we call irregular codes. When decoded using belief propagation, our codes can...
A Digital Fountain Approach to Reliable Distribution of Bulk Data (1998)
John Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege
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,...
A Digital Fountain Approach to Reliable Distribution of Bulk Data (1998)
John W. Byers, Michael Luby, Michael Mitzenmacher, Ashutosh Rege
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,...
A digital fountain approach to reliable distribution of bulk data (1998)
John W. Byers, John W. Byers, Michael Luby, Michael Luby, Michael Mitzenmacher, Michael Mitzenmacher, ...
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,...
A digital fountain approach to reliable distribution of bulk data (1998)
John W. Byers, John W. Byers, Michael Luby, Michael Luby, Michael Mitzenmacher, Michael Mitzenmacher, ...
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,...
A digital fountain approach to reliable distribution of bulk data (1998)
John W. Byers, John W. Byers, Michael Luby, Michael Luby, Michael Mitzenmacher, Michael Mitzenmacher, ...
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,...
Practical Loss-Resilient Codes (1997)
Michael Luby, Michael Mitzenmacher, Amin Shokrollahi, Daniel Spielman, Volker Stemann
We present a randomized construction 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...
Security of Blind Digital Signatures (1997)
Exte Nd Ed, Ari Juels, Michael Luby, Rafail Ostrovsky
) Ari Juels 1? Michael Luby 2 Rafail Ostrovsky 3 1 RSA Laboratories. Email: ari@rsa.com. 2 Digital Equipment Corporation, 130 Lytton Avenue, Palo Alto, CA 94301-1044. Email: luby@pa.dec.com. 3 Bell...
An Optimal Approximation Algorithm For Bayesian Inference (1997)
Approximating the inference probability Pr[X = xjE = 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...
Efficient Approximation of General Product Distributions (1997)
Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovic
We describe efficient constructions of small probability spaces that approximate the joint distribution of general random variables. Previous work on efficient constructions concentrate on...
On the Theory of Average Case Complexity (1997)
Shai Ben-david, Benny Chor, Oded Goldreich, 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...
A Modular Analysis of Network Transmission Protocols (1997)
Micah Adler, Yair Bartal, John W. Byers, Michael Luby, Danny Raz
We propose a new model for the analysis of data transmission protocols in lossy communication networks. The overall goal of a data transmission protocol is to successfully transmit a message from the...
Security of Blind Digital Signatures (Extended Abstract) (1997)
Ari Juels, Michael Luby, Rafail Ostrovsky
) Ari Juels 1? Michael Luby 2 Rafail Ostrovsky 3 1 RSA Laboratories. Email: ari@rsa.com. 2 Digital Equipment Corporation, 130 Lytton Avenue, Palo Alto, CA 94301-1044. Email: luby@pa.dec.com. 3 Bell...
A Modular Analysis of Network Transmission Protocols (1997)
Micah Adler, Yair Bartal, John W. Byers, Michael Luby, Danny Raz
We propose a new model for the analysis of data transmission protocols in lossy communication networks. The overall goal of a data transmission protocol is to successfully transmit a message from the...
Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension (1997)
Nathan Linial, Michael Luby, Michael Saks, David Zuckerman, Michael Saks
We describe a deterministic algorithm which, on input integers d, m and real number ffl 2 (0; 1), produces a subset S of [m] d = f1; 2; 3; : : : ; mg d that hits every combinatorial rectangle in [m]...
Security of blind digital signatures (extended abstract (1997)
Ari Juels, Michael Luby, Rafail Ostrovsky
Abstract. Blind digital signatures were introduced by Chaum. In this paper, we show how security and blindness properties for blind digital signatures, can be simultaneously de ned and satis ed,...
An optimal approximation algorithm for Bayesian inference (1997)
Approximating the inference probability Pr[X = xjE = 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...
A linear time erasure-resilient code with nearly optimal recovery (1996)
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...
Priority encoding transmission (1996)
Andres Albanese, Johannes Blomer, Jeff Edmonds, Michael Luby
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...
Priority encoding transmission (1996)
Andres Albanese, Johannes Blomer, Jeff Edmonds, Michael Luby
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...
A linear time erasure-resilient code with nearly optimal recovery (1996)
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...
A Geometric Proof of a Formula for the Number of Young Tableaux of a Given Shape (1996)
Michael Luby International, Michael Luby
This paper contains a short proof of a formula by Frame, Robinson, and Thrall [1] which counts the number of Young tableaux of a given shape. The proof is based on a simple but novel geometric way of...
Linear Time Erasure Codes With Nearly Optimal Recovery (1995)
Noga Alon, Jeff Edmonds, Michael Luby
An (n, c, ℓ, r)-erasure code consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of ℓ-bit packets of total length cn...
Markov chain algorithms for planar lattice structures (1995)
Michael Luby, Dana Randall, Alistair Sinclair
Consider the following Markov chain, whose states are all domino tilings of a 2n \Theta 2n chessboard: starting from some arbitrary tiling, pick a 2 \Theta 2 window uniformly at random. If the four...
An XOR-Based Erasure-Resilient Coding Scheme (1995)
Johannes Blömer, Malik Kalfane, Richard Karp, Marek Karpinski, Michael Luby, David Zuckerman
An (m; n; b; r)-erasure-resilient coding scheme consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of n packets each...
Approximately Counting Up To Four (Extended Abstract) (1995)
) Michael Luby Eric Vigoda y Abstract 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...
An Optimal Algorithm for Monte Carlo Estimation (1995)
Paul Dagum, Richard Karp, Michael Luby, Sheldon Ross
A typical approach to estimate an unknown quantity is to design an experiment that produces a random variable Z distributed in [0; 1] with E[Z] = , run this experiment independently a number of times...
PET - Priority Encoding Transmission: A New, Robust and Efficient Video Broadcast Technology (1995)
Bernd Lamparter, Andres Albanese, Malik Kalfane, Michael Luby
This paper presents a new Forward Error Correction Scheme with several priority levels. It is useful for applications dealing with real-time transport streams like video and audio. Those streams...
Pairwise Independence and Derandomization (1995)
This set of notes gives several applications of the following paradigm. The paradigm consists of two complementary parts. The first part is to design a probabilistic algorithm described by a sequence...
Linear Time Erasure Codes with Nearly Optimal Recovery (1995)
Noga Alon, Jeff Edmonds, Michael Luby
) Noga Alon Jeff Edmonds y Michael Luby z Abstract An (n; c; `; r)-erasure code consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm...
Markov Chain Algorithms for Planar Lattice Structures (1995)
Michael Luby, Dana Randall, Alistair Sinclair
Consider the following Markov chain, whose states are all domino tilings of a 2n \Theta 2n chessboard: starting from some arbitrary tiling, pick a 2 \Theta 2 window uniformly at random. If the four...
Markov Chain Algorithms for Planar Lattice Structures (Extended Abtract) (1995)
Michael Luby, Dana Randall, Alistair Sinclair
) Michael Luby Dana Randall y Alistair Sinclair z Abstract Consider the following Markov chain, whose states are all domino tilings of a 2n \Theta 2n chessboard: starting from some arbitrary tiling,...
Pairwise Independence and Derandomization (1995)
This set of notes gives several applications of the following paradigm. The paradigm consists of two complementary parts. The first part is to design a probabilistic algorithm described by a sequence...
Johannes Blomer, Malik Kalfane, Richard Karp, Marek Karpinski, Michael Luby, David Zuckerman
An (m; n; b; r)-erasure-resilient coding scheme consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of n packets each...
Markov Chain Algorithms for Planar Lattice Structures (Extended (1995)
Nd Ed, Michael Luby, Dana Randall, Alistair Sinclair
) Michael Luby Dana Randall y Alistair Sinclair z Abstract Consider the following Markov chain, whose states are all domino tilings of a 2n \Theta 2n chessboard: starting from some arbitrary tiling,...
Abstract This set of notes gives several applications of the following paradigm. The paradigm consists of two complementary parts. The first part is to design a probabilistic algorithm described by a...
Priority Encoding Transmission (1994)
Andres Albanese Johannes, Johannes Blomer, Jeff Edmonds, Michael Luby
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...
Efficient PRAM Simulation on a Distributed Memory Machine (1994)
We present algorithms for the randomized simulation of a shared memory machine (PRAM) on a Distributed Memory Machine (DMM). In a PRAM, memory conflicts occur only through concurrent access to the...
Priority Encoding Transmission (1994)
Andres Albanese, Johannes Blömer, Jeff Edmonds, Michael Luby
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...
Optimal Parallelization of Las Vegas Algorithms (1993)
Let A be a Las Vegas algorithm, i.e., A is a randomized algorithm that always produces the correct answer when it stops but whose running time is a random variable. In [1] a method was developed for...
On Deterministic Approximation of DNF (1993)
Michael Luby, Boban Velickovic
We develop efficient deterministic algorithms for approximating the fraction of truth assignments that satisfy a disjunctive normal form formula. Although the algorithms themselves are deterministic,...
Optimal Parallelization of Las Vegas Algorithms (1993)
Let A be a Las Vegas algorithm, i.e., A is a randomized algorithm that always produces the correct answer when it stops but whose running time is a random variable. In [1] a method was developed for...
Deterministic Approximate Counting of Depth-2 Circuits (1993)
Michael Luby, Boban Velickovic, Avi Wigderson
We describe deterministic algorithms which for a given depth-2 circuit F approximate the probability that on a random input F outputs a specific value α. Our approach gives an algorithm...
Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension (1993)
Nati Linial, Michael Luby, Michael Saks, David Zuckerman
Given d, m and epsilon, we deterministically produce a sequence of points S that hits every combinatorial rectangle in [m]^d of volume at least epsilon. Both the running time of the algorithm and |S|...
A Parallel Approximation Algorithm for Positive Linear Programming (1993)
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...
A Parallel Approximation Algorithm for Positive Linear Programming (1993)
Michael Luby Noam, Michael Luby, Noam Nisan
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...
On Removing Randomness from a Parallel Algorithm for Minimum Cuts (Extended Abstract) (1993)
Michael Luby, Joseph Naor, Moni Naor
) Michael Luby Joseph Naor y Moni Naor z TR-93-007 February 1993 Abstract The weighted minimum cut problem in a graph is a fundamental problem in combinatorial optimization. Recently, Karger...
Approximating the Number of Solutions of a GF(2) Polynomial (1993)
We develop a polynomial time Monte-Carlo algorithm for estimating the number of solutions to a multivariate polynomial over GF (2). This gives the first efficient method for estimating the number of...
Approximating the Number of Zeroes of a GF[2] Polynomial (1993)
We develop a probabilistic polynomial time algorithm which on input a polynomial g(x 1 ; : : : ; xn ) over GF[2], ffl and ffi , outputs an approximation to the number of zeroes of g with relative...
Optimal Speedup of Las Vegas Algorithms (1993)
Michael Luby, Alistair Sinclair, David Zuckerman
Let A be a Las Vegas algorithm, i.e., A is a randomized algorithm that always produces the correct answer when it stops but whose running time is a random variable. We consider the problem of...
Construction of a Pseudo-Random Generator From Any One-Way Function (1993)
Johan Håstad, Russell Impagliazzo, Leonid A. Levin, Michael Luby
There are many natural examples of conjectured one-way functions, whereas pseudorandom generators have a number of important applications, including the construction of a private key cryptosystem...
Optimal Speedup of Las Vegas Algorithms (1993)
Michael Luby, Alistair Sinclair, David Zuckerman
Let A be a Las Vegas algorithm, i.e., A is a randomized algorithm that always produces the correct answer when it stops but whose running time is a random variable. We consider the problem of...
Efficient PRAM Simulation on a Distributed Memory Machine (1992)
We present algorithms for the randomized simulation of a shared memory machine (PRAM) on a Distributed Memory Machine (DMM). In a PRAM, memory conflicts occur only through concurrent access to the...
Approximations of General Independent Distributions (1992)
Guy Even, Oded Goldreich, Michael Luby, Noam Nisan, Boban Velickovi'c
We describe efficient constructions of small probability spaces that approximate the independent distribution for general random variables. Previous work on efficient constructions concentrate on...
Approximating the Permanent of Graphs with Large Factors (1992)
Let G = (U; V; E) be a bipartite graph with jU j = jV j = 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...
Public Randomness in Cryptography (1992)
The main contribution of this paper is the introduction of a formal notion of public randomness in the context of cryptography. We show how this notion affects the definition of the security of a...
Inductive Learning of Compact Rule Sets by Using Efficient Hypotheses Reduction (1992)
Thomas Koch, Klaus-peter Jantke, Michael Luby
A method is described which reduces the hypotheses space with an efficient and easily interpretable reduction criteria called α-reduction. A learning algorithm is described based on...
Efficient PRAM Simulation on a Distributed Memory Machine (1992)
We present algorithms for the randomized simulation of a shared memory machine (PRAM) on a Distributed Memory Machine (DMM). In a PRAM, memory conflicts occur only through concurrent access to the...
On Deterministic Approximation of DNF (1991)
Michael Luby Boban, Michael Luby
We develop several quasi-polynomial time deterministic algorithms for approximating the fraction of truth assignments that satisfy a disjunctive normal form formula. The most efficient algorithm...
Self-Testing/Correcting with Applications to Numerical Problems (1990)
Manuel Blum, Michael Luby, Ronitt Rubinfeld
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 for f allows us...
Manuel Blum, Michael Luby, Ronitt Rubinfeld
) Manuel Blum Computer Science Division U.C. Berkeley Berkeley, California 94720 Michael Luby International Computer Science Institute Berkeley, California 94704 Ronitt Rubinfeld y Computer Science...
Network Decomposition and Locality in Distributed Computation (Extended Abstract) (1989)
Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, Serge A. Plotkin
) Baruch Awerbuch Department of Mathematics and Laboratory for Computer Science M.I.T. Cambridge, MA 02139 Andrew V. Goldberg y Department of Computer Science Stanford University Stanford, CA 94305...
Network Decomposition and Locality in Distributed Computation (1989)
Baruch Awerbuch Andrew, Andrew V. Goldberg, Michael Luby, Serge A. Plotkin
We introduce a concept of network decomposition, a partitioning of an arbitrary graph into smalldiameter connected components, such that the graph created by contracting each component into a single...
JOURNAL OF ALGORITHMS 12,685-699 (1991) Competitive Paging Algorithms (1988)
Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. Mcgeoch, Daniel D. Sleator, Neal E. Young
The paging problem is that of deciding which pages to keep in a memory of k pages in order to minimize the number of page faults. We develop the marking algorithm, a randomized on-line algorithm for...
Removing Randomness in Parallel Computation Without a Processor Penalty (1988)
We develop some general techniques for converting randomized parallel algorithms into deterministic parallel algorithms without a blowup in the number of processors. One of the requirements for the...