Expanders, randomness, or time versus space
From MaRDI portal
Publication:1107314
DOI10.1016/0022-0000(88)90035-9zbMath0652.68050OpenAlexW2155506366MaRDI QIDQ1107314
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
On the complexity of approximating the VC dimension., Quasi‐random classes of hypergraphs, Extractors for weak random sources and their applications, Efficient construction of a small hitting set for combinatorial rectangles in high dimension, Simulating BPP using a general weak random source, Constructions of strongly regular Cayley graphs derived from weakly regular bent functions, Improved non-approximability results for minimum vertex cover with density constraints, Computation of best possible low degree expanders, Pseudorandom generators for space-bounded computation, Construction of expanders and superconcentrators using Kolmogorov complexity, Extractors from Reed-Muller codes, Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?, Realistic analysis of some randomized algorithms, Injective trapdoor functions via derandomization: how strong is Rudich's black-box barrier?, Sparse and limited wavelength conversion in all-optical tree networks, Extracting all the randomness and reducing the error in Trevisan's extractors, Explicit two-source extractors and resilient functions, Extracting randomness: A survey and new constructions
Cites Work
