More Web Proxy on the site http://driver.im/

Article

Loss-less condensers, unbalanced expanders, and extractors

Authors:

Christopher Umans,

David ZuckermanAuthors Info & Claims

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

Pages 143 - 152

https://doi.org/10.1145/380752.380790

Published: 06 July 2001 Publication History

Abstract

An extractor is a procedure which extracts randomness from a detective random source using a few additional random bits. Explicit extractor constructions have numerous applications and obtaining such constructions is an important derandomization goal. Trevisan recently introduced an elegant extractor construction, but the number of truly random bits required is suboptimal when the input source has low-min-entropy. Significant progress toward overcoming this bottleneck has been made, but so far has required complicated recursive techniques that lose the simplicity of Trevisan's construction.

We give a clean method for overcoming this bottleneck by constructing {\em loss-less condensers}. which compress the n-bit input source without losing any min-entropy, using O(\log n) additional random bits. Our condensers are built using a simple modification of Trevisan's construction, and yield the best extractor constructions to date.

Loss-less condensers also produce unbalanced bipartite expander graphs with small (polylogarithmic) degree D and very strong expansion of (1-\epilon)D. We give other applications of our construction, including dispersers with entropy loss O(\log n), depth two super-concentrators whose size is within a polylog of optimal, and an improved hardness of approximation result.

References

[1]

M. Ajtai, J. Komlos, and E. Szemeredi. Sorting in clogn parallel steps. Combinatorica, 3:1-19, 1983.

Digital Library

[2]

M. Ajtai, J. Komlos, and E. Szemeredi. Deterministic simulation in Logspace. In 19th STOC, pages 132-140, 1987.

Digital Library

[3]

N. Alon, 1999. Personal communication.

[4]

S. Arora, F. T. Leighton, and B. M. Maggs. On-line algorithms for path selection in a nonblocking network. SIAM Journal on Computing, 25(3):600-625, June 1996.

Digital Library

[5]

H. Buhrman, P.B. Miltersen, J. Radhakrishnan, and S. Venkatesh. Are bitvectors optimal? In 32nd STOC, pages 449-458, 2000.

Digital Library

[6]

P. Feldman, J. Friedman, and N. Pippenger. Wide-sense nonblocking networks. SIAM Journal on Discrete Mathematics, 1:158-173, 1988.

Digital Library

[7]

O. Gabber and Z. Galil. Explicit construction of linear sized superconcentrators. Journal of Computer and System Sciences, 22:407-420, 1981.

[8]

O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesan, and D. Zuckerman. Security preserving amplification of hardness. In 31st FOCS, pages 318-326, 1990.

Digital Library

[9]

R. Impagliazzo, R. Shaltiel, and A. Wigderson. Near-optimal conversion of hardness into pseudo-randomness. In 40th FOCS, pages 181-190, 1999.

Digital Library

[10]

R. Impagliazzo, R. Shaltiel, and A. Wigderson. Extractors and pseudo-random generators with optimal seed length. In 32nd STOC, pages 1-10, 2000.

Digital Library

[11]

N. Kahale. Eigenvalues and expansion of regular graphs. Journal of the ACM, 42:1091-1106, 1995.

Digital Library

[12]

G.A. Margulis. Explicit construction of concentrators. Problems of Inform. Transmission, 9:325-332, 1973.

[13]

N. Nisan and A. Ta-Shma. Extracting randomness: A survey and new constructions. Journal of Computer and System Sciences, 58:148-173, 1999.

Digital Library

[14]

N. Nisan and A. Wigderson. Hardness vs. randomness. Journal of Computer and System Sciences, 49:149-167, 1994.

Digital Library

[15]

N. Nisan and D. Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43-52, 1996.

Digital Library

[16]

N. Pippenger. Sorting and selecting in rounds. SIAM Journal on Computing, 16(6):1032-1038, December 1987.

Digital Library

[17]

J. Radhakrishnan and A. Ta-Shma. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM Journal on Discrete Mathematics, 13(1):2-24, 2000.

Digital Library

[18]

R. Raz and O. Reingold. On recycling the randomness of states in space bounded computation. In 31st STOC, pages 159-168, 1999.

Digital Library

[19]

R. Raz, O. Reingold, and S. Vadhan. Extracting all the randomness and reducing the error in Trevisan's extractors. In 31st STOC, pages 149-158, 1999.

Digital Library

[20]

O. Reingold, R. Shaltiel, and A. Wigderson. Extracting randomness via repeated condensing. In 41st FOCS, pages 22-31, 2000.

Digital Library

[21]

M. Saks, A. Srinivasan, and S. Zhou. Explicit OR-dispersers with polylog degree. Journal of the ACM, 45:123-154, 1998.

Digital Library

[22]

M. Santha. On using deterministic functions in probabilistic algorithms. Information and Computation, 74(3):241-249, 1987.

Digital Library

[23]

M. Sipser. Expanders, randomness, or time vs. space. Journal of Computer and System Sciences, 36:379-383, 1988.

Digital Library

[24]

M. Sipser and D. A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710-1722, 1996.

Digital Library

[25]

A. Srinivasan and D. Zuckerman. Computing with very weak random sources. SIAM Journal on Computing, 28:1433-1459, 1999.

Digital Library

[26]

A. Ta-Shma. On extracting randomness from weak random sources. In 28th STOC, pages 276-285, 1996.

Digital Library

[27]

A. Ta-Shma. Almost optimal dispersers. In 30th STOC, pages 196-202, 1998.

Digital Library

[28]

L. Trevisan. Construction of extractors using pseudo-random generators. In 31st STOC, pages 141-148, 1999.

Digital Library

[29]

C. Umans. Hardness of approximating p2 minimization problems. In 40th FOCS, pages 465-474, 1999.

Digital Library

[30]

L.G. Valiant. Graph theoretic properties in computational complexity. Journal of Computer and System Sciences, 13:278-285, 1976.

Digital Library

[31]

A. Wigderson and D. Zuckerman. Expanders that beat the eigenvalue bound: Explicit construction and applications. Combinatorica, 19(1):125-138, 1999.

[32]

D. Zuckerman. General weak random sources. In 31st FOCS, pages 534-543, 1990.

Digital Library

[33]

D. Zuckerman. Simulating BPP using a general weak random source. Algorithmica, 16:367-391, 1996.

[34]

D. Zuckerman. Randomness-optimal oblivious sampling. Random Structures and Algorithms, 11:345-367, 1997.

Digital Library

Cited By

Hradovich EKlonowski MKowalski D(2020)Contention resolution on a restrained channel2020 IEEE 26th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS51040.2020.00022(89-98)Online publication date: Dec-2020
https://doi.org/10.1109/ICPADS51040.2020.00022
Agrikola TCouteau GIshai YJarecki SSahai A(2020)On Pseudorandom EncodingsTheory of Cryptography10.1007/978-3-030-64381-2_23(639-669)Online publication date: 9-Dec-2020
https://doi.org/10.1007/978-3-030-64381-2_23
Aviv NTa-Shma A(2019)On the Entropy Loss and Gap of CondensersACM Transactions on Computation Theory10.1145/331769111:3(1-14)Online publication date: 9-Apr-2019
https://dl.acm.org/doi/10.1145/3317691
Show More Cited By

Index Terms

Loss-less condensers, unbalanced expanders, and extractors
1. Mathematics of computing
  1. Discrete mathematics
  2. Probability and statistics

Recommendations

Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes

We give an improved explicit construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Both the degree and the number of right-hand vertices are ...
Lossless Condensers, Unbalanced Expanders, And Extractors

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 lossless condenser is a probabilistic map using only O(logn)...
Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes
CCC '07: Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity

We give an improved explicit construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Both the degree and the number of right-hand vertices are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

July 2001

755 pages

ISBN:1581133499

DOI:10.1145/380752

Copyright © 2001 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC01

Sponsor:

SIGACT

STOC01: 33rd ACM Symposium on Theory of Computing

Hersonissos, Greece

Acceptance Rates

STOC '01 Paper Acceptance Rate 83 of 230 submissions, 36%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

66
Total Citations
View Citations
61
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)2

Reflects downloads up to 01 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hradovich EKlonowski MKowalski D(2020)Contention resolution on a restrained channel2020 IEEE 26th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS51040.2020.00022(89-98)Online publication date: Dec-2020
https://doi.org/10.1109/ICPADS51040.2020.00022
Agrikola TCouteau GIshai YJarecki SSahai A(2020)On Pseudorandom EncodingsTheory of Cryptography10.1007/978-3-030-64381-2_23(639-669)Online publication date: 9-Dec-2020
https://doi.org/10.1007/978-3-030-64381-2_23
Aviv NTa-Shma A(2019)On the Entropy Loss and Gap of CondensersACM Transactions on Computation Theory10.1145/331769111:3(1-14)Online publication date: 9-Apr-2019
https://dl.acm.org/doi/10.1145/3317691
Cheraghchi MIndyk P(2017)Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard TransformACM Transactions on Algorithms10.1145/302905013:3(1-36)Online publication date: 6-Mar-2017
https://dl.acm.org/doi/10.1145/3029050
Cheraghchi MIndyk P(2016)Nearly optimal deterministic algorithm for sparse walsh-hadamard transformProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884458(298-317)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884458
Romashchenko A(2014)Pseudo-Random Graphs and Bit Probe Schemes with One-Sided ErrorTheory of Computing Systems10.1007/s00224-012-9425-055:2(313-329)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1007/s00224-012-9425-0
Cheraghchi M(2013)Noise-resilient group testingDiscrete Applied Mathematics10.1016/j.dam.2012.07.022161:1-2(81-95)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1016/j.dam.2012.07.022
Ben-Aroya ATa-Shma A(2012)Better short-seed quantum-proof extractorsTheoretical Computer Science10.1016/j.tcs.2011.11.036419(17-25)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1016/j.tcs.2011.11.036
Aumann YLewenstein MLewenstein NTsur D(2011)Finding witnesses by peelingACM Transactions on Algorithms10.1145/1921659.19216707:2(1-15)Online publication date: 31-Mar-2011
https://dl.acm.org/doi/10.1145/1921659.1921670
Georgiou CGilbert SKowalski D(2011)Meeting the deadlineDistributed Computing10.1007/s00446-011-0144-624:5(223-244)Online publication date: 1-Dec-2011
https://dl.acm.org/doi/10.1007/s00446-011-0144-6
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten