Query complexity in errorless hardness amplification
From MaRDI portal
Recommendations
- Query complexity in errorless hardness amplification
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
- Hardness Amplification Proofs Require Majority
- On the Complexity of Hardness Amplification
Cites work
- scientific article; zbMATH DE number 5081744 (Why is no real title available?)
- scientific article; zbMATH DE number 1306886 (Why is no real title available?)
- scientific article; zbMATH DE number 2081105 (Why is no real title available?)
- scientific article; zbMATH DE number 1559537 (Why is no real title available?)
- A Lower Bound on List Size for List Decoding
- Average Case Complete Problems
- Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read
- Boosting and hard-core set construction
- Hardness Amplification Proofs Require Majority
- Hardness amplification within NP
- Hardness amplification within NP against deterministic algorithms
- How much are increasing sets positively correlated?
- Improved hardness amplification in NP
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
- On Yao's XOR-lemma
- On the Complexity of Hardness Amplification
- On uniform amplification of hardness in NP
- One way functions and pseudorandom generators
- Query complexity in errorless hardness amplification
- Uniform direct product theorems: simplified, optimized, and derandomized
- Upper bounds on generalized distances
- Using Nondeterminism to Amplify Hardness
Cited in
(9)- Erasures versus errors in local decoding and property testing
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
- Computing and Combinatorics
- Query complexity in errorless hardness amplification
- On uniform amplification of hardness in NP
- scientific article; zbMATH DE number 7029312 (Why is no real title available?)
- The Zero-Error Randomized Query Complexity of the Pointer Function
- Adaptivity vs. postselection, and hardness amplification for polynomial approximation
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
This page was built for publication: Query complexity in errorless hardness amplification
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q901934)
