Query complexity in errorless hardness amplification
type: Item
instance of: scholarly article
title: Query complexity in errorless hardness amplification
zbMATH Open document ID: 1333.68128
author: N. E. Zubov
published in: Computational Complexity
publication date: 2016-01-06T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 6526938
zbMATH Keywords: query complexity
zbMATH Keywords: errorless hardness amplification
MaRDI profile type: Publication
full work available at URL: s00037-015-0117-4
OpenAlex ID: W3097675677
cites work: Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
cites work: Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read
cites work: On the Complexity of Hardness Amplification
cites work: Q3413362
cites work: One way functions and pseudorandom generators
cites work: Upper bounds on generalized distances
cites work: On Yao’s XOR-Lemma
cites work: Hardness amplification within NP against deterministic algorithms
cites work: Q4474218
cites work: A Lower Bound on List Size for List Decoding
cites work: Using Nondeterminism to Amplify Hardness
cites work: Q4252738
cites work: Boosting and hard-core set construction
cites work: Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
cites work: Q4526985
cites work: Average Case Complete Problems
cites work: Improved hardness amplification in NP
cites work: Hardness amplification within NP
cites work: Hardness Amplification Proofs Require Majority
cites work: How much are increasing sets positively correlated?
cites work: On uniform amplification of hardness in NP
cites work: Query Complexity in Errorless Hardness Amplification
DOI: 10.1007/S00037-015-0117-4
description: scientific article; zbMATH DE number 6526938