skip to main content
10.1145/237814.237878acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article
Free access

Randomness-optimal sampling, extractors, and constructive leader election

Published: 01 July 1996 Publication History
First page of PDF

References

[1]
M. Ajtai, J. Koml6s, and E. Szemerddi. Deterministic simulation in Logspace. In Proceedings of the 19th Annual A CM Symposium on Theory of Computing, pages 132- 140, 1987.
[2]
N. Alon and M. Naor. Coin-flipping games immune against linear-sized coalitions. SiAM Journal on Computing, 22:403- 417, 1993.
[3]
R. Armoni and A. Wigderson. Pseudorandomness for space-bounded computations. Unpublished manuscript.
[4]
M. Bellare, O. Goldreich, and S. Goldwasser. Randomness in interactive proofs. Computational Complexity, 3(4):319-354, 1993.
[5]
M. Blum. Independent unbiased coin flips from a correlated biased source: a finite Markov chain. Combinatorica, 6(2):97-108, 1986.
[6]
R. Boppana and B. Narayanan. Perfectinformation leader election with optimal resilience. Unpublished manuscript.
[7]
M. Bellare and J. Rompel. Randomnessefficient oblivious sampling. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, pages 276-287, 1994.
[8]
R. Canetti, G. Even, and O. Goldreich. Lower bounds for sampling algorithms for estimating the average. Information Processing Letters, 53:17-25, 1995.
[9]
B. Chor and O. Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing, 17(2):230-261, 1988.
[10]
B. Chor and O. Goldreich. On the power of two-point sampling. Journal of Complexity, 5:96-106, 1989.
[11]
B. Chor, O. Goldreich, J. H~stad, J. Friedman, S. Rudich, and R. Smolensky. The bit extraction problem or t-resilient functions. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, pages 396-407, 1985.`
[12]
J. Cooper and N. Linial. Fast perfectinformation leader-election protocol with linear immunity. In Proceedings of the 25th Annual A CM Symposium on Theory of Computing, pages 662-671, 1993.
[13]
A. Cohen and A. Wigderson. Dispersers, deterministic amplification, and weak random sources. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pages 14-19, 1989.
[14]
P. Feldman and S. Micali. Optimal algorithms for Byzantine agreement. In Proceedings of the ~Oth Annual A CM Symposium on Theory of Computing, pages 148-161, 1988.
[15]
R. Impagliazzo and D. Zuckerman. How to recycle random bits. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, pages 248-253, 1989.
[16]
M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM Journal on Computing, 15(4):1036- 1053, 1986.
[17]
N. Nisan. Pseudorandom generators for space-bounded computation. Combinatorlea, 12(4):449-461, 1992.
[18]
N. Nisan and D. Zuckerman. More deterministic simulation in Logspace. in Proceedings of the ~Sth Annual A CM Symposium on Theory of Computing, pages 235-244, 1993. To appear in J CSS under the title "Randomness is Linear in Space".
[19]
R. Ostrovsky, S. Rajagopalan, and U. Vazirani. Simple and efficient leader election in the full information model. In Proceedings of the 26th Annual A CM Symposium on Theory of Computing, pages 234-242, 1994.
[20]
M. Saks. A robust noncryptographic protocol for collective coin flipping. SIAM Journal on Discrete Mathematics, 6:240-244, 1989.
[21]
M. Semtha. On using deterministic functions in probabilistic algorithms. Information and Computation, 74(3):241-249, 1987.
[22]
M. Sipser. Expanders, randomness or time vs. space. Journal of Computer and System Sciences, 36:379-383, 1988.
[23]
M. Saks, A. Srinivasan, and S. Zhou. Explicit dispersers with polylog degree. In Proceedings of the ~Tth Annual A CM Symposium on Theory of Computing, pages 479- 488, 1995.
[24]
M. Santha and U. V. Vazirani. Generating quasi-random sequences from semi-random sources, journal of Computer and System Sciences, 33:75-87, 1986.
[25]
A. Srinivasan and D. Zuckerman. Computing with very weak random sources. In Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, pages 264-275, 1994.
[26]
A. Ta-Shma. On extracting randomness from weak random sources. In Proceedings of the 28th Annual A CM Symposium on Theory of Computing, 1996.
[27]
A. Wigderson and D. Zuckerman. Expanders that beat the eigenvalue bound: Ex~ plicit construction and applications. Technical Report TR-95-21, Department of Computer Sciences, The University of Texas at Austin, June 1995. Submitted for journal publication. Preliminary version appeared in Proceedings of the 25th Annual A CM Symposium on Theory of Computing, pages 245-251, 1993
[28]
D. Zuckerman. General weak random sources. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 534-543, 1990.
[29]
D. Zuckerman. Simulating BPP using a general weak random source. Algorithmica. To appear. Preliminary version in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science, pages 79-89, 1991.

Cited By

View all
  • (2021)Game-Theoretic Fairness Meets Multi-party Protocols: The Case of Leader ElectionAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84245-1_1(3-32)Online publication date: 11-Aug-2021
  • (2018)Fair Leader Election for Rational Agents in Asynchronous Rings and NetworksProceedings of the 2018 ACM Symposium on Principles of Distributed Computing10.1145/3212734.3212767(217-226)Online publication date: 23-Jul-2018
  • (2013)Stochastic coalescence in logarithmic timeThe Annals of Applied Probability10.1214/11-AAP83223:2Online publication date: 1-Apr-2013
  • Show More Cited By

Index Terms

  1. Randomness-optimal sampling, extractors, and constructive leader election

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing
    July 1996
    661 pages
    ISBN:0897917855
    DOI:10.1145/237814
    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

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 01 July 1996

    Permissions

    Request permissions for this article.

    Check for updates

    Qualifiers

    • Article

    Conference

    STOC96
    Sponsor:
    STOC96: ACM Symposium on Theory of Computing
    May 22 - 24, 1996
    Pennsylvania, Philadelphia, USA

    Acceptance Rates

    STOC '96 Paper Acceptance Rate 74 of 201 submissions, 37%;
    Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

    Upcoming Conference

    STOC '25
    57th Annual ACM Symposium on Theory of Computing (STOC 2025)
    June 23 - 27, 2025
    Prague , Czech Republic

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)40
    • Downloads (Last 6 weeks)10
    Reflects downloads up to 13 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2021)Game-Theoretic Fairness Meets Multi-party Protocols: The Case of Leader ElectionAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84245-1_1(3-32)Online publication date: 11-Aug-2021
    • (2018)Fair Leader Election for Rational Agents in Asynchronous Rings and NetworksProceedings of the 2018 ACM Symposium on Principles of Distributed Computing10.1145/3212734.3212767(217-226)Online publication date: 23-Jul-2018
    • (2013)Stochastic coalescence in logarithmic timeThe Annals of Applied Probability10.1214/11-AAP83223:2Online publication date: 1-Apr-2013
    • (2012)Stochastic coalescence in logarithmic timeProceedings of the twenty-third annual ACM-SIAM symposium on Discrete algorithms10.5555/2095116.2095162(541-550)Online publication date: 17-Jan-2012
    • (2010)Improved fault tolerance and secure computation on sparse networksProceedings of the 37th international colloquium conference on Automata, languages and programming: Part II10.5555/1880999.1881026(249-260)Online publication date: 6-Jul-2010
    • (2010)Improved Fault Tolerance and Secure Computation on Sparse NetworksAutomata, Languages and Programming10.1007/978-3-642-14162-1_21(249-260)Online publication date: 2010
    • (2007)How many oblivious transfers are needed for secure multiparty computation?Proceedings of the 27th annual international cryptology conference on Advances in cryptology10.5555/1777777.1777801(284-302)Online publication date: 19-Aug-2007
    • (2007)Towards optimal and efficient perfectly secure message transmissionProceedings of the 4th conference on Theory of cryptography10.5555/1760749.1760772(311-322)Online publication date: 21-Feb-2007
    • (2007)How Many Oblivious Transfers Are Needed for Secure Multiparty Computation?Advances in Cryptology - CRYPTO 200710.1007/978-3-540-74143-5_16(284-302)Online publication date: 2007
    • (2005)Worst-case hardness suffices for derandomization: A new method for hardness-randomness trade-offsAutomata, Languages and Programming10.1007/3-540-63165-8_175(177-187)Online publication date: 8-Jun-2005
    • Show More Cited By

    View Options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Login options

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media