Pseudorandomness for network algorithms

DOI10.1145/195058.195190zbMATH Open1345.68269OpenAlexW2011438986MaRDI QIDQ2817628FDOQ2817628

Authors: Russell Impagliazzo, Noam Nisan, A. Wigderson 

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

Recommendations

• Randomized broadcast in networks
• Ergodic Randomized Algorithms and Dynamics Over Networks
• Pseudorandom Graphs in Data Structures
• Network-oblivious algorithms
• Deterministic Sampling Algorithms for Network Design
• Deterministic sampling algorithms for network design
• Randomness in distribution protocols
• Randomness in distribution protocols
• Network Decomposition and Distributed Derandomization (Invited Paper)

Mathematics Subject Classification ID

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

Cited In (50)

• On probabilistic space-bounded machines with multiple access to random tape
• Random oracles and non-uniformity
• Pseudorandom generators for combinatorial checkerboards
• Fourier bounds and pseudorandom generators for product tests
• Title not available (Why is that?)
• Title not available (Why is that?)
• Highly symmetric expanders
• Preserving randomness for adaptive algorithms
• Title not available (Why is that?)
• Paradigms for Unconditional Pseudorandom Generators
• Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
• Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification
• Randomness-efficient non-interactive zero knowledge
• Title not available (Why is that?)
• Improved Explicit Hitting-Sets for ROABPs
• Space pseudorandom generators by communication complexity lower bounds
• Low discrepancy sets yield approximate min-wise independent permutation families
• Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
• Memory Efficient Anonymous Graph Exploration
• Explicit list-decodable codes with optimal rate for computationally bounded channels
• Weak derandomization of weak algorithms: explicit versions of Yao's lemma
• Local and global expansion in random geometric graphs
• A dichotomy for local small-bias generators
• Simple optimal hitting sets for small-success RL
• Title not available (Why is that?)
• Approximating hyper-rectangles: Learning and pseudorandom sets
• Pseudorandom functions: three decades later
• Trading locality for time: certifiable randomness from low-depth circuits
• Cryptographic hardness of random local functions. Survey
• Universal traversal sequences with backtracking.
• Pseudorandom pseudo-distributions with near-optimal error for read-once branching programs
• Graph exploration by a finite automaton
• How strong is Nisan's pseudo-random generator?
• Randomness buys depth for approximate counting
• Partition expanders
• Title not available (Why is that?)
• Approximating iterated multiplication of stochastic matrices in small space
• Near-optimal derandomization of medium-width branching programs
• Bounded independence plus noise fools products
• Expander graphs and their applications
• Title not available (Why is that?)
• More on bounded independence plus noise: pseudorandom generators for read-once polynomials
• A new pseudorandom generator from collision-resistant hash functions
• Randomness extraction in \(\mathsf{AC}^0\) and with small locality
• Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• Limitations of the Impagliazzo-Nisan-Wigderson pseudorandom generator against permutation branching programs
• Fooling Polytopes
• Pseudorandomness via the discrete Fourier transform
• Impact of memory size on graph exploration capability

This page was built for publication: Pseudorandomness for network algorithms

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