Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?
From MaRDI portal
Publication:6113106
DOI10.1007/s00037-023-00238-9OpenAlexW3082917772WikidataQ124819395 ScholiaQ124819395MaRDI QIDQ6113106
Publication date: 10 July 2023
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-023-00238-9
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Boosting and hard-core set construction
- Pseudorandomness and average-case complexity via uniform reductions
- If NP languages are hard on the worst-case, then it is easy to find their hard instances
- On basing one-way functions on NP-hardness
- On Yao’s XOR-Lemma
- Random-Self-Reducibility of Complete Sets
- The Complexity of Local List Decoding
- Limitations of Hardness vs. Randomness under Uniform Reductions
- Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
- Worst-Case to Average-Case Reductions Revisited
- On the Complexity of Hardness Amplification
- On the Composition of Zero-Knowledge Proof Systems
- Parity helps to compute majority
- A fixed-depth size-hierarchy theorem for AC 0 [⊕ via the coin problem]
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Hardness Amplification Proofs Require Majority
- On Worst‐Case to Average‐Case Reductions for NP Problems
- Theory of Cryptography
- Pseudorandom generators without the XOR lemma
This page was built for publication: Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?
