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

More deterministic simulation in logspace

Published: 01 June 1993 Publication History
First page of PDF

References

[1]
M. Ajtai, J. Komlos, and E. Szemeredi, "Deterministic Simulation of Logspace, 19th STOC, 1987, pp. 132-140.]]
[2]
L. Babai, N. Nisan, and M. Szegedy. Multiparty Protocols and Logspace-hard pseudorandom sequences. In Proceedings of the 22"a Annual A CM Symposium on Theory of Computing, 1990.]]
[3]
M. Bellare, O. Goldreich, and S. Goldwasser, "Randomness in interactive Proofs," 31st FOCS, 1990, pp. 563-572.]]
[4]
B. Berger and J. Rompel, "Simulating (logc n)-Wise Independence in NC," JACM, 38(4):1026-1046, 1991o]]
[5]
L. Carter and M. Wegman, "Universal Hash Functions," J. Comp. and Syst. Sci., 18(2): 143-154, 1979.]]
[6]
B. Chor and O. Goldreich, "Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity," SIAM j. Comput., 17(2)'230-261, 1988.]]
[7]
B. Chor and O. Goldreich, "On the Power of Two-Point Based Sampling," Journal of Complexity, 5:96-I06, 1989.]]
[8]
A. Cohen and A. Wigderson, "Dispersers, Deterministic Amplification, and Weak Random Sources," 30th FOCS, 1989, pp. 14-19.]]
[9]
R. Impagliazzo, L. Levin, and M. Luby, "Pseudo-Random Generation from One- Way Functions," 21st STOC, 1989, pp. 12- 24.]]
[10]
R. Impagliazzo and D. Zuckerman, "How to Recycle Random Bits," 30th FOCS, 1989, pp. 248-253.]]
[11]
M. Luby, "Removing Randomness in Parallel Computation Without a Processor Penalty," 29th FOCS, 1988.]]
[12]
R. Motwani, J. Naor, and M. Naor, "The Probabilistic Method Yields Deterministic Parallel Algorithms," 30th FOCS, 1989, pp. 8-13.]]
[13]
N. Nisan. Pseudorandom generators for space-bounded computation. In Proceedings of the 22st Annual A CM Symposium on Theory of Computing, 1990.]]
[14]
N. Nisan. RL C SC. 24th STOC, 1992, pp. 619-623.]]
[15]
W.J. Saviteh. Relationships between nondeterministic and deterministic space complexities. J. Comp. and Syst. Sci., 4(2)'177- 192, 1970.]]
[16]
J.P. Sehmidt, A. Siegel, A. Srinivasan, "Chernoff-Hoeffding Bounds for Applications with Limited Independence," to appear in 4th SODA, 1993.]]
[17]
A. Wigderson and D. Zuckerman, "Expanders that Beat the Eigenvalue Bound" Explicit Construction and Applications," 25th STOC, 1993, to appear.]]
[18]
D. Zuekerman, "General Weak Random Sources," 31st FOCS, 1990, pp. 534-543.]]
[19]
D. Zuckerman, "Simulating BPP Using a General Weak Random Source," 32nd FOCS, 1991, pp. 79-89.]]

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
STOC '93: Proceedings of the twenty-fifth annual ACM symposium on Theory of Computing
June 1993
812 pages
ISBN:0897915917
DOI:10.1145/167088
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 June 1993

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

STOC93
Sponsor:
STOC93: 25th Annual ACM Symposium on the Theory of Computing
May 16 - 18, 1993
California, San Diego, USA

Acceptance Rates

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)80
  • Downloads (Last 6 weeks)17
Reflects downloads up to 14 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)An Overview of Postprocessing in Quantum Key DistributionMathematics10.3390/math1214224312:14(2243)Online publication date: 18-Jul-2024
  • (2021)Hardness of KT characterizes parallel cryptographyProceedings of the 36th Computational Complexity Conference10.4230/LIPIcs.CCC.2021.35Online publication date: 20-Jul-2021
  • (2020)Extracting Randomness from Extractor-Dependent SourcesAdvances in Cryptology – EUROCRYPT 202010.1007/978-3-030-45721-1_12(313-342)Online publication date: 10-May-2020
  • (2019)Seedless Fruit Is the Sweetest: Random Number Generation, RevisitedAdvances in Cryptology – CRYPTO 201910.1007/978-3-030-26948-7_8(205-234)Online publication date: 1-Aug-2019
  • (2018)Fuzzy Password-Authenticated Key ExchangeAdvances in Cryptology – EUROCRYPT 201810.1007/978-3-319-78372-7_13(393-424)Online publication date: 31-Mar-2018
  • (2016)Dimension, pseudorandomness and extraction of pseudorandomnessComputability10.3233/COM-1600666:3(277-305)Online publication date: 6-Sep-2016
  • (2015)Condensed UnpredictabilityAutomata, Languages, and Programming10.1007/978-3-662-47672-7_85(1046-1057)Online publication date: 20-Jun-2015
  • (2014)NON-MALLEABLE RANDOMNESS EXTRACTORSNational Security Studies10.37055/sbn/1352326:2(227-238)Online publication date: 5-Dec-2014
  • (2014)Non-malleable Codes against Constant Split-State TamperingProceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science10.1109/FOCS.2014.40(306-315)Online publication date: 18-Oct-2014
  • (2013)Pseudorandomness for Regular Branching Programs via Fourier AnalysisApproximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques10.1007/978-3-642-40328-6_45(655-670)Online publication date: 2013
  • 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