Derandomized constructions of \(k\)-wise (almost) independent permutations
From MaRDI portal
Publication:2391191
DOI10.1007/s00453-008-9267-yzbMath1180.68200OpenAlexW2163814013MaRDI QIDQ2391191
Moni Naor, Eyal Kaplan, Omer Reingold
Publication date: 24 July 2009
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-008-9267-y
Permutations, words, matrices (05A05) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Simple and optimal randomized fault-tolerant rumor spreading ⋮ Dynamic dictionaries for multisets and counting filters with constant time operations ⋮ Sparser Johnson-Lindenstrauss Transforms ⋮ Hardness-preserving reductions via cuckoo hashing ⋮ Layout graphs, random walks and the \(t\)-wise independence of SPN block ciphers ⋮ Dynamic dictionaries for multisets and counting filters with constant time operations ⋮ Local random quantum circuits are approximate polynomial-designs ⋮ Non-malleable coding against bit-wise and split-state tampering ⋮ Deterministic public-key encryption for adaptively-chosen plaintext distributions ⋮ Explicit list-decodable codes with optimal rate for computationally bounded channels ⋮ A unified approach to deterministic encryption: new constructions and a connection to computational entropy ⋮ Explicit Near-Ramanujan Graphs of Every Degree ⋮ Unnamed Item ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Pseudorandom generators for space-bounded computation
- On the construction of pseudorandom permutations: Luby-Rackoff revisited
- Approximating probability distributions using small sample spaces
- Min-wise independent permutations
- Randomness is linear in space
- Pseudorandom walks on regular digraphs and the RL vs. L problem
- Simple permutations mix even better
- Algorithmic derandomization via complexity theory
- Fast, small-space algorithms for approximate histogram maintenance
- Uniform hashing in constant time and linear space
- Almost random graphs with simple hash functions
- On the sample size of k -restricted min-wise independent permutations and other k -wise distributions
- Undirected ST-connectivity in log-space
- The mixing time of the thorp shuffle
- Shuffling Cards and Stopping Times
- How to Construct Pseudorandom Permutations from Pseudorandom Functions
- Finite Permutation Groups and Finite Simple Groups
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Constructing Small Sample Spaces Satisfying Given Constraints
- On Universal Classes of Extremely Random Constant-Time Hash Functions
- Symmetric groups and expanders
- An Almost m-wise Independent Random Permutation of the Cube
- Nonrandom Shuffling with Applications to the Game of Faro
- Advances in Cryptology - EUROCRYPT 2004
- Advances in Cryptology – CRYPTO 2004
- On the Implementation of Huge Random Objects
- Advances in Cryptology - CRYPTO 2003
- Composition Does Not Imply Adaptive Security
- Automata, Languages and Programming
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Theory of Cryptography
