Expanders, randomness, or time versus space

DOI10.1016/0022-0000(88)90035-9MaRDI QIDQ1107314zbMATH OpenOpenAlexFDO

Authors Michael Sipser

Publication date 1988

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(88)90035-9

zbMATH Keywords

expander graphpolynomial time boundrandomness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 3980487
• Expanders that beat the eigenvalue bound: Explicit construction and applications
• Recursive construction for 3-regular expanders
• scientific article; zbMATH DE number 1263224
• Local expanders

Cites work

• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• On Time Versus Space

Cited in

(22)

• Pseudorandom generators for space-bounded computation
• Extracting randomness: A survey and new constructions
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• On the complexity of approximating the VC dimension.
• Simulating BPP using a general weak random source
• Improved non-approximability results for minimum vertex cover with density constraints
• Realistic analysis of some randomized algorithms
• Explicit two-source extractors and resilient functions
• Computation of best possible low degree expanders
• Extractors from Reed-Muller codes
• scientific article; zbMATH DE number 3980487 (Why is no real title available?)
• Quasi‐random classes of hypergraphs
• Construction of expanders and superconcentrators using Kolmogorov complexity
• Extractors for weak random sources and their applications
• Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?
• Extracting all the randomness and reducing the error in Trevisan's extractors
• Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?
• Sparse and limited wavelength conversion in all-optical tree networks
• Constructions of strongly regular Cayley graphs derived from weakly regular bent functions
• When Arthur has neither random coins nor time to spare: superfast derandomization of proof systems
• Optimal explicit small-depth formulas for the coin problem
• Simulating time with square-root space

This page was built for publication: Expanders, randomness, or time versus space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107314)