Input locality and hardness amplification
type: Item
instance of: scholarly article
title: Input locality and hardness amplification
zbMATH Open document ID: 1291.94059
author: Andrej Bogdanov
author: Alon Rosen
published in: Journal of Cryptology
publication date: 2013-04-15T00:00:00Z
full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 6153969
MaRDI profile type: Publication
OpenAlex ID: W2031699542
cites work: Q4004078
cites work: Cryptography with Constant Input Locality
cites work: Public-key cryptography from different assumptions
cites work: The rank of sparse random matrices over finite fields
cites work: Noise-tolerant learning, the parity problem, and the statistical query model
cites work: On the Security of Goldreich’s One-Way Function
cites work: Goldreich’s One-Way Function Candidate and Myopic Backtracking Algorithms
cites work: Concentration of Measure for the Analysis of Randomized Algorithms
cites work: On the Existence of Pseudorandom Generators
cites work: On the Power of the Randomized Iterate
cites work: The computational complexity of universal hashing
cites work: Theory of Cryptography
DOI: 10.1007/S00145-011-9117-Y
Recommended article: Input Locality and Hardness Amplification
Recommended article: Q5875699
Recommended article: Locality from Circuit Lower Bounds
Recommended article: Beyond Natural Proofs: Hardness Magnification and Locality
Recommended article: Q5875777
Recommended article: Q5002725
Recommended article: New techniques and tighter bounds for local computation algorithms
Recommended article: Local Computation
Recommended article: Q3751515
Recommended article: On the Locality of Some NP-Complete Problems
description: scientific article; zbMATH DE number 6153969