Pseudorandom Generators for Polynomial Threshold Functions (2009)
We study the natural question of constructing pseudorandom generators (PRGs) for low-degree polynomial threshold functions (PTFs). We give a PRG with seed-length log n/eps^{O(d)} fooling degree d...
Optimal Testing of Reed-Muller Codes (2009)
Bhattacharyya, Arnab, Kopparty, Swastik, Schoenebeck, Grant, Sudan, Madhu, Zuckerman, David
We consider the problem of testing if a given function $f : \F_2^n \to \F_2$ is close to any degree $d$ polynomial in $n$ variables, also known as the Reed-Muller testing problem. Alon et al....
Abstract Network Extractor Protocols (2009)
Yael Tauman Kalai, Xin Li, David Zuckerman, Anup Rao
We design efficient protocols for processors to extract private randomness over a network with Byzantine faults, when each processor has access to an independent weakly-random n-bit source of...
Extractors for Three Uneven-Length Sources (2009)
Abstract. We construct an efficient 3-source extractor that requires one of the sources to be significantly shorter than the min-entropy of the other two sources. Our extractors work even when the...
Low Discrepancy Sets Yield Approximate Min-Wise Independent Permutation Families \Lambda (2008)
Michael Saksy, Aravind Srinivasanz, Shiyu Zhoux, David Zuckerman
j Pr[minfss(K)g = ss(x)] \Gamma 1jKj j ^ ffljKj: We show connections of such families with low discrepancy sets for geometric rectangles, and give explicit constructions of such families F of size...
ABSTRACT Deterministic Extractors For Small-Space Sources (2008)
Jesse Kamp, Salil Vadhan, Anup Rao, David Zuckerman
We give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space s sources on {0, 1} n as sources generated by width 2 s branching programs: For...
Hartmut Klauck, Ashwin Nayak, David Zuckerman
One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet in some scenarios...
Charanjit S. Jutla, Atri Rudra, Anindya C. Patthak, David Zuckerman
We present an efficient randomized algorithm to test if a given function f: F n p → Fp (where p is a prime) is a low-degree polynomial. This gives a local test for Generalized Reed-Muller codes �...
Applications of Probabilistic Analysis and Game Theory (2008)
Nedialko Boyanov Dimitrov, C. Greg Plaxton, Adam Klivans, David Morton, Peter Stone, David Zuckerman, ...
To my family, friends and mentors: Thank you. – Ned.
Michael Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman
Motivated by a problem of filtering near-duplicate Web documents, Broder, Charikar, Frieze & Mitzenmacher defined the following notion of #-approximate min-wise independent permutation families....
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Bpp Ph, Oded Goldreich, Rehovot Israel, David Zuckerman
We provide another proof of the Sipser--Lautemann Theorem by which BPP ` MA (` PH). The current proof is based on strong results regarding the amplification of BPP , due to Zuckerman. Given these...
1 Interaction in Quantum Communication and the Complexity of Set Disjointness (2007)
Hartmut Klauck, Ashwin Nayak, Amnon Ta-shma, David Zuckerman
2 One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet in some scenarios...
My main interest is the role of randomization in computer science. For example, it is very useful in ffl Simulations, such as Monte Carlo simulations. ffl Cryptography. Here it is often provably...
y Computer Science Dept. (2007)
Hartmut Klauck, Ashwin Nayak, Amnon Ta-shma, David Zuckerman
One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet in some scenarios...
Loss-less Condensers, Unbalanced Expanders, and Extractors (2007)
Amnon Ta-Shma, Christopher Umans, David Zuckerman
An extractor is a procedure which extracts randomness from a defective random source using a few additional random bits. Explicit extractor constructions havenumerous applications and obtaining such...
Interaction in Quantum Communication (2007)
Hartmut Klauck, Ashwin Nayak, Amnon Ta-shma, David Zuckerman
In some scenarios there are ways of conveying information with much fewer, even exponentially fewer, qubits than possible classically [1], [2], [3]. Moreover, some of these methods have a very simple...
Sparse Random Graphs Methods, Structure, and Heuristics Publication No. (2007)
Daniel Turrin Fernholz, Vijaya Ramachandran Supervisor, Luis Caffarelli, Adam Klivans, Greg Plaxton, David Zuckerman, ...
This dissertation is an algorithmic study of sparse random graphs which are parametrized by the distribution of vertex degrees. Our contributions include: a formula for the diameter of various sparse...
Interaction in Quantum Communication (2006)
Klauck, Hartmut, Nayak, Ashwin, Ta-Shma, Amnon, Zuckerman, David
In some scenarios there are ways of conveying information with many fewer, even exponentially fewer, qubits than possible classically. Moreover, some of these methods have a very simple...
Ronen Gradwohl, Salil Vadhan, David Zuckerman
We consider the problem of random selection, where p players follow a protocol to jointly select a random element of a universe of size n. However, some of the players may be adversarial and collude...
Ronen Gradwohl, Salil Vadhan, David Zuckerman
We consider the problem of random selection, where p players follow a protocol to jointly select a random element of a universe of size n. However, some of the players may be adversarial and collude...
Random selection with an adversarial majority (2006)
Ronen Gradwohl, Salil Vadhan, David Zuckerman
Abstract. We consider the problem of random selection, where p players follow a protocol to jointly select a random element of a universe of size n. However, some of the players may be adversarial...
Deterministic extractors for smallspace sources (2006)
Jesse Kamp, Anup Rao, Salil Vadhan, David Zuckerman
We give polynomial-time, deterministic randomness extractors for sources generated in small space, where we model space s sources on {0, 1} n as sources generated by width 2 s branching programs. For...
Linear degree extractors and the inapproximability of max clique and chromatic number (2005)
Chromatic Number, David Zuckerman
that for all ε> 0, approximating MAX CLIQUE and CHROMATIC NUMBER to within n1−ε are NP-hard. We further derandomize results of Khot (FOCS ’01) and show that for some γ> 0, no...
Compression of samplable sources (2004)
Luca Trevisan, Salil Vadhan, David Zuckerman
Abstract. We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose...
Electronic Colloquium on Computational Complexity, Report No. 12 (2005) (2004)
Luca Trevisan, Salil Vadhan, David Zuckerman
We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a...
Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography (2003)
Abstract. We give an efficient deterministic algorithm that extracts Ω(n2γ) almost-random bits from sources where n 1 2 +γ of the n bits are uniformly random and the rest are fixed in advance....
Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography (2003)
We give an efficient deterministic algorithm that extracts Ω(n 2γ) almost-random bits from sources where n 1 2 +γ of the n bits are uniformly random and the rest are fixed in advance. This...
Extractors from Reed-Muller Codes (2003)
Amnon Ta-Shma, David Zuckerman, Shmuel Safra
Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. Previous research has focused on two approaches, one related to hashing and...
Interaction in Quantum Communication and the Complexity of Set Disjointness (2003)
Hartmut Klauck, Ashwin Nayak, Amnon Ta-shma, David Zuckerman
One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet in some scenarios...
Expander graphs for digital stream authentication and robust overlay networks (2002)
Dawn Song, David Zuckerman, J. D. Tygar
We use expander graphs to provide ecient new constructions for two security applications: authentication of long digital streams over lossy networks and building scalable, robust overlay networks....
Loss-less condensers, unbalanced expanders, and extractors (2001)
Amnon Ta-shma, Christopher Umans, David Zuckerman
Abstract Trevisan showed that many pseudorandom generator constructions give rise to constructionsof explicit extractors. We show how to use such constructions to obtain explicit lossless condensers....
Amnon Ta-shma, David Zuckerman
We define new error correcting codes based on extractors. We show that for certain choices of parameters these codes have better list decoding properties than are known for other codes, and are...
Interaction in quantum communication and the complexity of set disjointness (2001)
Hartmut Klauck, Ashwin Nayak, Amnon Ta-shma, David Zuckerman
One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet in some scenarios...
Interaction in quantum communication and the complexity of set disjointness (2001)
Ashwin Nayak, Amnon Ta-shma, David Zuckerman
One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet in some scenarios...
Amnon Ta-shma, David Zuckerman
We define new error correcting codes based on extractors. We show that for certain choices of parameters these codes have better list decoding properties than are known for other codes, and are...
Extractors from Reed-Muller codes (2001)
Amnon Ta-shma, David Zuckerman, Shmuel Safra
Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. This research has focused on two approaches, one related to hashing and the...
Loss-less condensers, unbalanced expanders, and extractors (2001)
Amnon Ta-shma, Christopher Umans, David Zuckerman
z An extractor is a procedure which extracts randomness from a defective random source using a few additional random bits. Explicit extractor constructions have numerous applications and obtaining...
Loss-less Condensers, Unbalanced Expanders, and Extractors (2001)
Amnon Ta-shma, Christopher Umans, David Zuckerman
An extractor is a procedure which extracts randomness from a defective random source using a few additional random bits. Explicit extractor constructions have numerous applications and obtaining such...
Extractors from Reed-Muller Codes (2001)
Amnon Ta-Shma, David Zuckerman, Shmuel Safra
Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. This research has focused on two approaches, one related to hashing and the...
Amnon Ta-shma, Shmuel Safra, David Zuckerman
Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. This research has focused on two approaches, one related to hashing and the...
Extractors from Reed-Muller Codes (2001)
Amnon Ta-shma, David Zuckerman, Shmuel Safra
Finding explicit extractors is an important derandomization goal that has received a lot of attention in the past decade. Previous research has focused on two approaches, one related to hashing and...
Loss-less condensers, unbalanced expanders, and extractors (2001)
Amnon Ta-shma, Christopher Umans, David Zuckerman
Trevisan showed that many pseudorandom generator constructions give rise to constructions of explicit extractors. We show how to use such constructions to obtain explicit lossless condensers. A...
Loss-less condensers, unbalanced expanders, and extractors (2001)
Amnon Ta-shma, Christopher Umans, David Zuckerman
Trevisan showed that many pseudorandom generator constructions give rise to constructions of explicit extractors. We show how to use such constructions to obtain explicit lossless condensers. A...
Interaction in Quantum Communication Complexity (2000)
Nayak, Ashwin, Ta-Shma, Amnon, Zuckerman, David
One of the most intriguing facts about communication using quantum states is that these states cannot be used to transmit more classical bits than the number of qubits used, yet there are ways of...
On rounds in quantum communication (2000)
Hartmut Klauck, Ashwin Nayak, Amnon Ta-shma, David Zuckerman
1 In some scenarios there are ways of conveying information with many fewer, even exponentially fewer, qubits than possible classically [1], [2], [3]. Moreover, some of these methods have a very...
Combinatorial bounds for list decoding (2000)
Venkatesan Guruswami, Johan Hastad, Madhu Sudan, David Zuckerman
Abstract--- Informally, an error-correcting code has "nice " listdecodability properties if every Hamming ball of "large " radius has a "small "...
Combinatorial bounds for list decoding (2000)
Venkatesan Guruswami, Johan Hastad, Madhu Sudan, David Zuckerman
Abstract--- Informally, an error-correcting code has "nice " listdecodability properties if every Hamming ball of "large " radius has a "small "...
Combinatorial bounds for list decoding (2000)
Venkatesan Guruswami, Johan Hastad, David Zuckerman
Informally, an error-correcting code has "nice " list-decodability properties if every Hamming ball of "large " radius has a "small " number of...
Combinatorial bounds for list decoding (2000)
Venkatesan Guruswami, David Zuckerman
Informally, an error-correcting code has \nice " list-decodability properties if every Hamming ball of \large " radius has a \small " number of codewords in it. Here, we...
Combinatorial bounds for list decoding (2000)
Venkatesan Guruswami, Johan Hastad, David Zuckerman
Informally, an error-correcting code has "nice " list-decodability properties if every Hamming ball of "large " radius has a "small " number of...
Combinatorial bounds for list decoding (2000)
Venkatesan Guruswami, Johan Hastad, Madhu Sudan, David Zuckerman
Abstract--- Informally, an error-correcting code has "nice " listdecodability properties if every Hamming ball of "large " radius has a "small "...
Combinatorial bounds for list decoding (2000)
Venkatesan Guruswami, David Zuckerman
Informally, an error-correcting code has \nice " list-decodability properties if every Hamming ball of \large " radius has a \small " number of codewords in it. Here, we...
Asymptotically good codes correcting insertions, deletions, and transpositions (1999)
Schulman, Leonard J., Zuckerman, David
We present simple, polynomial time encodable and decodable codes which are asymptotically good for channels allowing insertions, deletions, and transpositions. As a corollary, they achieve...
Asymptotically good codes correcting insertions, deletions, and transpositions (1999)
Leonard J. Schulman, David Zuckerman
We present simple, polynomial-time encodable and decodable codes which are asymptotically good for channels allowing insertions, deletions and transpositions. As a corollary, they achieve exponential...
Low discrepancy sets yield approximate min-wise independent permutation families (1999)
Michael Saks, Aravind Srinivasan, Shiyu Zhou, David Zuckerman
Motivated by a problem of filtering near-duplicate Web documents, Broder, Charikar, Frieze & Mitzenmacher defined the following notion of ffl-approximate min-wise independent permutation...
Computing with very weak random sources (1999)
Abstract. We give an efficient algorithm to extract randomness from a very weak random source using a small additional number t of truly random bits. Our work extends that of Nisan & Zuckerman in...
Expanders that beat the eigenvalue bound: Explicit construction and applications (1999)
Avi Wigderson, David Zuckerman
For every n and 0! ffi! 1, we construct graphs on n nodes such that every two sets of size n ffi share an edge, having essentially optimal maximum degree n 1\Gammaffi+o(1). Using known and new...
Asymptotically good codes correcting insertions, deletions, and transpositions (1999)
Leonard J. Schulman, David Zuckerman
We present simple, polynomial-time encodable and decodable codes which are asymptotically good for channels allowing insertions, deletions and transpositions. As a corollary, they achieve exponential...
Alexander Russell Computer, Alexander Russell, Michael Saks, David Zuckerman
Collective coin-flipping is the problem of producing common random bits in a distributed computing environment with adversarial faults. We consider the perfect information model: all communication is...
Alexander Russell, Michael Saks, David Zuckerman
Collective coin-flipping is the problem of producing common random bits in a distributed computing environment with adversarial faults. We consider the perfect information model: all communication is...
TIGHT ANALYSES OF TWO LOCAL LOAD BALANCING ALGORITHMS (1999)
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Perfect information leader election in log (1998)
N O( Rounds, Alexander Russell, David Zuckerman
In the leader election problem, n players wish to elect a random leader. The difficulty is that some coalition of players may conspire to elect one of its own members. We adopt the perfect...
Perfect Information Leader Election in log* n + O(1) Rounds (1998)
N+o( Rounds, Alexander Russell, David Zuckerman
In the leader election problem, n players wish to elect a random leader. The difficulty is that some coalition of players may conspire to elect one of its own members. We adopt the perfect...
Randomness-Optimal Oblivious Sampling (1997)
We present the first efficient oblivious sampler that uses an optimal number of random bits, up to an arbitrary constant factor bigger than 1. Specifically, for any ff ? 0, it uses (1 + ff)(m + log...
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]...
On the Time to Traverse All Edges of a Graph (1997)
The expected time for a random walk on an undirected graph G = (V; E) to visit all the vertices is O(jV jjEj) [AKLLR], and is O(jV j 2 ) for regular graphs [KLNS]. Here we show that both bounds hold...
Another proof that BPP \subseteq PH (and more) (1997)
Oded Goldreich, Rehovot Israel, David Zuckerman
We provide another proof of the Sipser--Lautemann Theorem by which BPP ` MA (` PH). The current proof is based on strong results regarding the amplification of BPP , due to Zuckerman. Given these...
Computing with very weak random sources / (1996)
Srinivasan, Aravind., Zuckerman, David.
Abstract: "We study how to run randomized algorithms when the source of randomness is very defective (weak). For any fixed [epsilon]> 0, we show how to simulate RP algorithms in time n[superscript...
Randomness is linear in space (1996)
We show that any randomized algorithm that runs in space S and time T and uses poly(S) random bits can be simulated using only O(S) random bits in space S and time T + poly(S). A deterministic...
Derandomized Graph Products (1996)
Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman
Berman and Schnitger [10] gave a randomized reduction from approximating MAXSNP problems [24] within constant factors arbitrarily close to 1 to approximating clique within a factor of n^ε...
Peter Winkler, David Zuckerman
Motivated by applications in Markov estimation and distributed computing, we define the blanket time of an undirected graph G to be the expected time for a random walk to hit every vertex of G within...
Simulating BPP Using a General Weak Random Source (1996)
We show how to simulate BPP and approximation algorithms in polynomial time using the output from a ffi-source. A ffi-source is a weak random source that is asked only once for R bits, and must...
Peter Winkler, David Zuckerman
Motivated by applications in Markov estimation and distributed computing, we define the blanket time of an undirected graph G to be the expected time for a random walk to hit every vertex of G within...
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...
Tight Analyses of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh Leighton, Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, ...
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
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...
Tight Analyses of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
. This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Tight Analyses of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh, F.T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Tight Analyses of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
. This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Derandomized Graph Products (1995)
Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman
. Berman and Schnitger gave a randomized reduction from approximating MAX-SNP problems within constant factors arbitrarily close to 1 to approximating clique within a factor of n ffl (for some ffl)....
Derandomized Graph Products (1995)
Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman
Berman and Schnitger [10] gave a randomized reduction from approximating MAX-SNP problems [24] within constant factors arbitrarily close to 1 to approximating clique within a factor of n ɛ (for some...
Expanders that Beat the Eigenvalue Bound: Explicit Construction and Applications (1993)
Avi Wigderson, David Zuckerman
For every n and 0 ! ffi ! 1, we construct graphs on n nodes such that every two sets of size n ffi share an edge, having essentially optimal maximum degree n 1\Gammaffi+o(1) . We use them to...
Optimal Speedup of Las Vegas Algorithms (1993)
Michael Luby Alistair, 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...
Optimal Speedup of Las Vegas Algorithms (1993)
Michael Luby Alistair, 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 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|...
Randomness is Linear in Space (1993)
Noam Nisan David, David Zuckerman
We show that any randomized algorithm that runs in space S and time T and uses poly(S) random bits can be simulated using only O(S) random bits in space S and time T + poly(S). A deterministic...
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...
Lower Bounds for Randomized Mutual Exclusion (1993)
Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, David Zuckerman
We establish, for the first time, lower bounds for randomized mutual-exclusion algorithms (with a read-modify-write operation). Our main result is that a constant size shared-variable cannot...
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...
Lower Bounds for Randomized Mutual Exclusion (1993)
Eyal Kushilevitz, Yishay Mansour, Michael O. Rabin, David Zuckerman
We establish, for the first time, lower bounds for randomized mutual exclusion algorithms (with a read-modify-write operation). Our main result is that a constant-size shared variable cannot...
A Technique for Lower Bounding the Cover Time (1992)
We give a general technique for proving lower bounds on expected covering times of random walks on graphs in terms of expected hitting times between vertices. We use this technique to prove: i) A...
Security Preserving Amplification of Hardness (1990)
Oded Goldreich, Russell Impagliazzo, Leonid Levin, Ramarathnam Venkatesan, David Zuckerman
We consider the task of transforming a weak one-way function (which may be easily inverted on all but a polynomial fraction of the range) into a strong one-way function (which can be easily inverted...
Security Preserving Amplification of Hardness (1990)
Oded Goldreich, Russell Impagliazzo, Leonid Levin, Ramarathnam Venkatesan, David Zuckerman
We consider the task of transforming a weak one-way function (which may be easily inverted on all but a polynomial fraction of the range) into a strong one-way function (which can be easily inverted...
How to Recycle Random Bits (1989)
Russell Impagliazzo, David Zuckerman
We show that modified versions of the linear congruential generator and the shift register generator are provably good for amplifying the correctness of a probabilistic algorithm. More precisely, if...
On Unapproximable Versions of NP-Complete Problems
. We prove that all of Karp's 21 original NP-complete problems have a version that's hard to approximate. These versions are obtained from the original problems by adding essentially the...