Derandomized constructions of k-wise (almost) independent permutations
From MaRDI portal
Publication:2391191
Recommendations
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- scientific article; zbMATH DE number 5771375
- A derandomization using min-wise independent permutations
- scientific article; zbMATH DE number 1775418
- On (ε,k)‐min‐wise independent permutations
- Almost \(k\)-wise vs. \(k\)-wise independent permutations, and uniformity for general group actions
- Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions
- An Almost m-wise Independent Random Permutation of the Cube
- On restricted min‐wise independence of permutations
Cites work
- Advances in Cryptology - CRYPTO 2003
- Advances in Cryptology - EUROCRYPT 2004
- Advances in Cryptology – CRYPTO 2004
- Algorithmic derandomization via complexity theory
- Almost random graphs with simple hash functions
- An Almost m-wise Independent Random Permutation of the Cube
- Approximating probability distributions using small sample spaces
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Automata, Languages and Programming
- Composition Does Not Imply Adaptive Security
- Constructing Small Sample Spaces Satisfying Given Constraints
- Fast, small-space algorithms for approximate histogram maintenance
- Finite Permutation Groups and Finite Simple Groups
- How to Construct Pseudorandom Permutations from Pseudorandom Functions
- scientific article; zbMATH DE number 5771375 (Why is no real title available?)
- scientific article; zbMATH DE number 2009979 (Why is no real title available?)
- scientific article; zbMATH DE number 2079924 (Why is no real title available?)
- scientific article; zbMATH DE number 2086703 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- scientific article; zbMATH DE number 1418263 (Why is no real title available?)
- scientific article; zbMATH DE number 1445297 (Why is no real title available?)
- scientific article; zbMATH DE number 4185033 (Why is no real title available?)
- Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
- Min-wise independent permutations
- Nonrandom Shuffling with Applications to the Game of Faro
- On the construction of pseudorandom permutations: Luby-Rackoff revisited
- On the implementation of huge random objects
- On the sample size of k -restricted min-wise independent permutations and other k -wise distributions
- On Universal Classes of Extremely Random Constant-Time Hash Functions
- Pseudorandom generators for space-bounded computation
- Pseudorandom walks on regular digraphs and the RL vs. L problem
- Randomness is linear in space
- Shuffling Cards and Stopping Times
- Simple permutations mix even better
- Symmetric groups and expanders
- The mixing time of the Thorp shuffle
- Theory of Cryptography
- Undirected ST-connectivity in log-space
- Uniform hashing in constant time and linear space
Cited in
(32)- Deterministic public-key encryption for adaptively-chosen plaintext distributions
- Explicit list-decodable codes with optimal rate for computationally bounded channels
- Indifferentiability of truncated random permutations
- Hardness-preserving reductions via cuckoo hashing
- A unified approach to deterministic encryption: new constructions and a connection to computational entropy
- Simple and optimal randomized fault-tolerant rumor spreading
- Random permutations using switching networks
- Almost \(k\)-wise vs. \(k\)-wise independent permutations, and uniformity for general group actions
- Sparser Johnson-Lindenstrauss transforms
- Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions
- An Almost m-wise Independent Random Permutation of the Cube
- Local random quantum circuits are approximate polynomial-designs
- A recursive construction of t-wise uniform permutations
- Automata, Languages and Programming
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Space-efficient local computation algorithms
- Sparser Johnson-Lindenstrauss transforms
- Explicit Near-Ramanujan Graphs of Every Degree
- Dynamic dictionaries for multisets and counting filters with constant time operations
- Layout graphs, random walks and the t-wise independence of SPN block ciphers
- Complexity theory. Abstracts from the workshop held June 2--7, 2024
- Succinct filters for sets of unknown sizes
- Pseudorandomness properties of random reversible circuits
- Multidimensional quantum walks, with application to k-distinctness
- Iceberg hashing: optimizing many hash-table criteria at once
- Error correcting codes for uncompressed messages
- Spectrum preserving short cycle removal on regular graphs
- Exact expressions for the maximal probability that all k-wise independent bits are 1
- Pseudodistributions that beat all pseudorandom generators
- Quantum pseudorandom scramblers
- Almost pairwise independence and resilience to deep learning attacks
- Dynamic dictionaries for multisets and counting filters with constant time operations
This page was built for publication: Derandomized constructions of \(k\)-wise (almost) independent permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2391191)
