Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
type: Item
instance of: scholarly article
title: Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
zbMATH Open document ID: 1366.68070
author: Sergei Artemenko
author: Ronen Shaltiel
published in: Computational Complexity
publication date: 2014-09-25T00:00:00Z
full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 6347791
zbMATH Keywords: hardness amplification
zbMATH Keywords: black-box reductions
MaRDI profile type: Publication
OpenAlex ID: W2032791464
cites work: On basing one-way functions on NP-hardness
cites work: The complexity of constructing pseudorandom generators from hard functions
cites work: \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
cites work: On Worst‐Case to Average‐Case Reductions for NP Problems
cites work: Random-Self-Reducibility of Complete Sets
cites work: On Yao’s XOR-Lemma
cites work: Q3549643
cites work: Hardness amplification within NP against deterministic algorithms
cites work: Hardness amplification via space-efficient direct products
cites work: The Complexity of Local List Decoding
cites work: If NP languages are hard on the worst-case, then it is easy to find their hard instances
cites work: Worst-Case to Average-Case Reductions Revisited
cites work: Limitations of Hardness vs. Randomness under Uniform Reductions
cites work: Using Nondeterminism to Amplify Hardness
cites work: Q4252738
cites work: Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification
cites work: Chernoff-type direct product theorems
cites work: Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
cites work: Q4526985
cites work: Randomness vs time: Derandomization under a uniform assumption
cites work: Boosting and hard-core set construction
cites work: One way functions and pseudorandom generators
cites work: Q3210157
cites work: On the Complexity of Hardness Amplification
cites work: Complexity of hard-core set proofs
cites work: Hardness amplification within NP
cites work: A Parallel Repetition Theorem
cites work: Theory of Cryptography
cites work: Simple extractors for all min-entropies and a new pseudorandom generator
cites work: Hardness Amplification Proofs Require Majority
cites work: Pseudorandom generators without the XOR lemma
cites work: Pseudorandomness and average-case complexity via uniform reductions
cites work: Some Applications of Coding Theory in Computational Complexity
cites work: On uniform amplification of hardness in NP
cites work: Query Complexity in Errorless Hardness Amplification
DOI: 10.1007/S00037-012-0056-2
description: scientific article; zbMATH DE number 6347791