Input locality and hardness amplification
From MaRDI portal
Recommendations
- Input locality and hardness amplification
- scientific article; zbMATH DE number 7650354
- Locality from circuit lower bounds
- Beyond Natural Proofs: Hardness Magnification and Locality
- Beyond natural proofs: hardness magnification and locality
- On the probe complexity of local computation algorithms
- New techniques and tighter bounds for local computation algorithms
- Local computation: lower and upper bounds
- scientific article; zbMATH DE number 3987204
- On the locality of some NP-complete problems
Cites work
- Concentration of Measure for the Analysis of Randomized Algorithms
- Cryptography with Constant Input Locality
- Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
- scientific article; zbMATH DE number 53883 (Why is no real title available?)
- Noise-tolerant learning, the parity problem, and the statistical query model
- On the Existence of Pseudorandom Generators
- On the Power of the Randomized Iterate
- On the Security of Goldreich’s One-Way Function
- Public-key cryptography from different assumptions
- The computational complexity of universal hashing
- The rank of sparse random matrices over finite fields
- Theory of Cryptography
Cited in
(9)- Minimizing locality of one-way functions via semi-private randomized encodings
- Expander-based cryptography meets natural proofs
- Lossy functions do not amplify well
- Input locality and hardness amplification
- A dichotomy for local small-bias generators
- Fast pseudorandom functions based on expander graphs
- Cryptography with Constant Input Locality
- Expander-Based Cryptography Meets Natural Proofs
- scientific article; zbMATH DE number 7650354 (Why is no real title available?)
This page was built for publication: Input locality and hardness amplification
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1946597)
