Query complexity in errorless hardness amplification
From MaRDI portal
Publication:901934
DOI10.1007/s00037-015-0117-4zbMath1333.68128OpenAlexW3097675677MaRDI QIDQ901934
Publication date: 6 January 2016
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-015-0117-4
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (1)
Cites Work
- Hardness amplification within NP against deterministic algorithms
- Improved hardness amplification in NP
- One way functions and pseudorandom generators
- Boosting and hard-core set construction
- How much are increasing sets positively correlated?
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
- Query Complexity in Errorless Hardness Amplification
- On Yao’s XOR-Lemma
- Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read
- On uniform amplification of hardness in NP
- Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
- On the Complexity of Hardness Amplification
- Average Case Complete Problems
- Upper bounds on generalized distances
- A Lower Bound on List Size for List Decoding
- Hardness Amplification Proofs Require Majority
- Using Nondeterminism to Amplify Hardness
- Hardness amplification within NP
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Query complexity in errorless hardness amplification
