Pseudorandomness for network algorithms

DOI10.1145/195058.195190zbMath1345.68269OpenAlexW2011438986MaRDI QIDQ2817628

Avi Wigderson, Russell Impagliazzo, Noam Nisan

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/195058.195190

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed algorithms (68W15)

Related Items (45)

Universal traversal sequences with backtracking. ⋮ Partition expanders ⋮ A New Pseudorandom Generator from Collision-Resistant Hash Functions ⋮ Low discrepancy sets yield approximate min-wise independent permutation families ⋮ Unnamed Item ⋮ A dichotomy for local small-bias generators ⋮ Memory Efficient Anonymous Graph Exploration ⋮ Random oracles and non-uniformity ⋮ Cryptographic hardness of random local functions. Survey ⋮ Fooling Polytopes ⋮ Pseudorandomness via the Discrete Fourier Transform ⋮ Randomness-efficient non-interactive zero knowledge ⋮ Trading locality for time: certifiable randomness from low-depth circuits ⋮ On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape ⋮ Pseudorandom generators for combinatorial checkerboards ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ How strong is Nisan's pseudo-random generator? ⋮ Expander graphs and their applications ⋮ Simple Optimal Hitting Sets for Small-Success RL ⋮ Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting) ⋮ Unnamed Item ⋮ Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs ⋮ Weak derandomization of weak algorithms: explicit versions of Yao's lemma ⋮ Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs ⋮ Randomness buys depth for approximate counting ⋮ Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification ⋮ Bounded Independence Plus Noise Fools Products ⋮ Preserving Randomness for Adaptive Algorithms ⋮ Impact of memory size on graph exploration capability ⋮ Improved Explicit Hitting-Sets for ROABPs ⋮ Highly symmetric expanders ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Explicit list-decodable codes with optimal rate for computationally bounded channels ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ Approximating hyper-rectangles: Learning and pseudorandom sets ⋮ Unnamed Item ⋮ Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace ⋮ Unnamed Item ⋮ Graph exploration by a finite automaton ⋮ Pseudorandom Functions: Three Decades Later

This page was built for publication: Pseudorandomness for network algorithms