Michael Luby

Proceedings of the Randomization and Approximation Techniques in Computer Science, 1998

Feedback-free multicast prefix protocols.

[BibT_eX]

[DOI]

Proceedings of the Third IEEE Symposium on Computers and Communications (ISCC 1998), June 30, 1998

Combinatorial Bounds for Broadcast Encryption.

[BibT_eX]

[DOI]

Jessica Staddon

Proceedings of the Advances in Cryptology - EUROCRYPT '98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31, 1998

1997

Foreword.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1997

Efficient Construction of a Small Hitting Set for Combinatorial Rectangles in High Dimension.

[BibT_eX]

[DOI]

Comb., 1997

An Optimal Approximation Algorithm for Bayesian Inference.

[BibT_eX]

[DOI]

Paul Dagum

Artif. Intell., 1997

Approximately Counting Up To Four (Extended Abstract).

[BibT_eX]

[DOI]

Eric Vigoda

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Practical Loss-Resilient Codes.

[BibT_eX]

[DOI]

Mohammad Amin Shokrollahi

Michael Mitzenmacher

Daniel A. Spielman

Volker Stemann

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

A Modular Analysis of Network Transmission Protocols.

[BibT_eX]

[DOI]

Proceedings of the Fifth Israel Symposium on Theory of Computing and Systems, 1997

Security of Blind Digital Signatures (Extended Abstract).

[BibT_eX]

[DOI]

Ari Juels

Rafail Ostrovsky

Proceedings of the Advances in Cryptology, 1997

1996

A linear time erasure-resilient code with nearly optimal recovery.

[BibT_eX]

[DOI]

Noga Alon

IEEE Trans. Inf. Theory, 1996

Priority encoding transmission.

[BibT_eX]

[DOI]

IEEE Trans. Inf. Theory, 1996

SICACT Treasurer's Report.

[BibT_eX]

[DOI]

SIGACT News, 1996

Tight Bounds for Dynamic Storage Allocation.

[BibT_eX]

[DOI]

Joseph Naor

Ariel Orda

SIAM J. Discret. Math., 1996

On Deterministic Approximation of DNF.

[BibT_eX]

[DOI]

Boban Velickovic

Algorithmica, 1996

Introduction to Special Issue on Randomized and Derandomized Algorithms.

[BibT_eX]

[DOI]

Algorithmica, 1996

Efficient PRAM Simulation on a Distributed Memory Machine.

[BibT_eX]

[DOI]

Friedhelm Meyer auf der Heide

Algorithmica, 1996

Pseudorandomness and cryptographic applications.

[BibT_eX]

Princeton computer science notes, Princeton University Press, ISBN: 978-0-691-02546-9, 1996

1995

PET - Priority Encoding Transmission: A New, Robust and Efficient Video Broadcast Technology (Video).

[BibT_eX]

[DOI]

Proceedings of the Third ACM International Conference on Multimedia '95, 1995

Markov Chain Algorithms for Planar Lattice Structures (Extended Abstract).

[BibT_eX]

[DOI]

Dana Randall

Alistair Sinclair

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

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

[BibT_eX]

[DOI]

Noga Alon

Jeff Edmonds

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

PET - priority encoding transmission.

[BibT_eX]

Andres Albanese

Proceedings of the High-Speed Networking for Multimedia Applications [2nd Int. Workshop on Architecture and Protocols for High Performance Networks, 1995

1993

Optimal parallelization of Las Vegas algorithms

[BibT_eX]

[DOI]

Wolfgang Ertel

Forschungsberichte, TU Munich, 1993

A Monte-Carlo Algorithm for Estimating the Permanent.

[BibT_eX]

[DOI]

SIAM J. Comput., 1993

On the Existence of Pseudorandom Generators.

[BibT_eX]

[DOI]

Oded Goldreich

Hugo Krawczyk

SIAM J. Comput., 1993

Removing Randomness in Parallel Computation without a Processor Penalty.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1993

Self-Testing/Correcting with Applications to Numerical Problems.

[BibT_eX]

[DOI]

Manuel Blum

Ronitt Rubinfeld

J. Comput. Syst. Sci., 1993

Approximating the Number of Zeroes of a GF[2] Polynomial.

[BibT_eX]

[DOI]

Marek Karpinski

J. Algorithms, 1993

Optimal Speedup of Las Vegas Algorithms.

[BibT_eX]

[DOI]

Alistair Sinclair

David Zuckerman

Inf. Process. Lett., 1993

Approximating Probabilistic Inference in Bayesian Belief Networks is NP-Hard.

[BibT_eX]

[DOI]

Paul Dagum

Artif. Intell., 1993

A parallel approximation algorithm for positive linear programming.

[BibT_eX]

[DOI]

Noam Nisan

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

Deterministic Approximate Counting of Depth-2 Circuits.

[BibT_eX]

[DOI]

Boban Velickovic

Avi Wigderson

Proceedings of the Second Israel Symposium on Theory of Computing Systems, 1993

1992

Approximating the Permanent of Graphs with Large Factors.

[BibT_eX]

[DOI]

Paul Dagum

Theor. Comput. Sci., 1992

On the Theory of Average Case Complexity.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1992

Approximations of General Independent Distributions

[BibT_eX]

[DOI]

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Pubic Randomness in Cryptography.

[BibT_eX]

[DOI]

Amir Herzberg

Proceedings of the Advances in Cryptology, 1992

1991

Competitive Paging Algorithms.

[BibT_eX]

[DOI]

Daniel Dominic Sleator

Neal E. Young

J. Algorithms, 1991

Parallel Asynchronous Connected Components in a Mesh.

[BibT_eX]

[DOI]

Susanne E. Hambrusch

Inf. Process. Lett., 1991

Pseudo-random Generators from One-way Functions (Abstract).

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1991

1990

Parallel Search for Maximal Independence Given Minimal Dependence.

[BibT_eX]

[DOI]

Paul Beame

Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, 1990

1989

A Study of Password Security.

[BibT_eX]

[DOI]

J. Cryptol., 1989

Monte-Carlo Approximation Algorithms for Enumeration Problems.

[BibT_eX]

[DOI]

Neal Madras

J. Algorithms, 1989

A Bidirectional Shortest-Path Algorithm with Good Average-Case Behavior.

[BibT_eX]

[DOI]

Prabhakar Ragde

Algorithmica, 1989

Pseudo-random Generation from one-way functions (Extended Abstracts)

[BibT_eX]

[DOI]

Russell Impagliazzo

Leonid A. Levin

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

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

[BibT_eX]

[DOI]

Russell Impagliazzo

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Network Decomposition and Locality in Distributed Computation

[BibT_eX]

[DOI]

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

Program Result Checking against Adaptive Programs and in Cryptographic Settings.

[BibT_eX]

[DOI]

Manuel Blum

Ronitt Rubinfeld

Proceedings of the Distributed Computing And Cryptography, 1989

On the Theory of Average Case Complexity (abstract).

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988

How to Construct Pseudorandom Permutations from Pseudorandom Functions.

[BibT_eX]

[DOI]

SIAM J. Comput., 1988

A Simple Parallel Algorithm for Finding a Satisfying Truth Assignment to a 2-CNF Formula.

[BibT_eX]

[DOI]

Stephen A. Cook

Inf. Process. Lett., 1988

Steepest Descent Can Take Exponential Time for Symmetric Connection Networks.

[BibT_eX]

[DOI]

Armin Haken

Complex Syst., 1988

On the Existence of Pseudorandom Generators (Extended Abstract)

[BibT_eX]

[DOI]

Oded Goldreich

Hugo Krawczyk

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

Polytopes, Permanents and Graphs with Large Factors

[BibT_eX]

[DOI]

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1986

A Simple Parallel Algorithm for the Maximal Independent Set Problem.

[BibT_eX]

[DOI]

SIAM J. Comput., 1986

Pseudo-random Permutation Generators and Cryptographic Composition

[BibT_eX]

[DOI]

Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

1985

Monte-Carlo algorithms for the planar multiterminal network reliability problem.

[BibT_eX]

[DOI]

J. Complex., 1985

A Bidirectional Shortest-Path Algorithm With Good Average-Case Behavior (Preliminary Version).

[BibT_eX]

[DOI]

Prabhakar Ragde

Proceedings of the Automata, 1985

How to Construct Pseudo-Random Permutations from Pseudo-Random Functions (Abstract).

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 1985

1984

A Probabilistic Analysis of Multidimensional Bin Packing Problems

[BibT_eX]

[DOI]

Alberto Marchetti-Spaccamela

Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

1983

Finding Shortest Paths in Very Large Networks.

[BibT_eX]

Eugene L. Lawler

Michael George Luby

B. Parker

Proceedings of the WG '83, 1983

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

[BibT_eX]

[DOI]

Silvio Micali

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

Monte-Carlo Algorithms for Enumeration and Reliability Problems

[BibT_eX]

[DOI]