Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? (Q6113106): Difference between revisions

Latest revision as of 18:34, 30 December 2024

scientific article; zbMATH DE number 7709620

Language	Label	Description	Also known as
English	Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle?	scientific article; zbMATH DE number 7709620

Statements

instance of

scholarly article

0 references

title

Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? (English)

0 references

author

Ronen Shaltiel

0 references

published in

Computational Complexity

0 references

publication date

10 July 2023

0 references

zbMATH Keywords

average-case complexity

0 references

Yao's XOR lemma

0 references

black-box reductions

0 references

MaRDI profile type

MaRDI publication profile

0 references

full work available at URL

https://doi.org/10.1007/s00037-023-00238-9

0 references

cites work

\(\Sigma_ 1^ 1\)-formulae on finite structures

0 references

On basing one-way functions on NP-hardness

0 references

Incompressible functions, relative-error extractors, and the power of nondeterministic reductions

0 references

Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification

0 references

On Worst‐Case to Average‐Case Reductions for NP Problems

0 references

Q3191596

0 references

Random-Self-Reducibility of Complete Sets

0 references

On the Composition of Zero-Knowledge Proof Systems

0 references

On Yao’s XOR-Lemma

0 references

Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy

0 references

The Complexity of Local List Decoding

0 references

If NP languages are hard on the worst-case, then it is easy to find their hard instances

0 references

Worst-Case to Average-Case Reductions Revisited

0 references

Limitations of Hardness vs. Randomness under Uniform Reductions

0 references

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

0 references

Q4252738

0 references

Q5750403

0 references

Q4526985

0 references

Boosting and hard-core set construction

0 references

A fixed-depth size-hierarchy theorem for AC <sup>0</sup> [⊕] via the coin problem

0 references

On the Complexity of Hardness Amplification

0 references

Parity helps to compute majority

0 references

Lower bounds on the size of bounded depth circuits over a complete basis with logical addition

0 references

Theory of Cryptography

0 references

Hardness Amplification Proofs Require Majority

0 references

Pseudorandom generators without the XOR lemma

0 references

Pseudorandomness and average-case complexity via uniform reductions

0 references

Identifiers

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

10.1007/S00037-023-00238-9

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6113106

@@ Property / DOI @@
-.1007/s00037-023-00238-9
@@ Property / DOI: 10.1007/s00037-023-00238-9 / rank @@
-Normal rank
@@ Property / cites work @@
+\(\Sigma_ 1^ 1\)-formulae on finite structures
@@ Property / cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures / rank @@
+Normal rank
@@ Property / cites work @@
+On basing one-way functions on NP-hardness
@@ Property / cites work: On basing one-way functions on NP-hardness / rank @@
+Normal rank
@@ Property / cites work @@
+Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
+Normal rank
@@ Property / cites work @@
+Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
+Normal rank
@@ Property / cites work @@
+On Worst‐Case to Average‐Case Reductions for NP Problems
+Normal rank
@@ Property / cites work @@
+Q3191596
@@ Property / cites work: Q3191596 / rank @@
+Normal rank
@@ Property / cites work @@
+Random-Self-Reducibility of Complete Sets
@@ Property / cites work: Random-Self-Reducibility of Complete Sets / rank @@
+Normal rank
@@ Property / cites work @@
+On the Composition of Zero-Knowledge Proof Systems
+Normal rank
@@ Property / cites work @@
+On Yao’s XOR-Lemma
@@ Property / cites work: On Yao’s XOR-Lemma / rank @@
+Normal rank
@@ Property / cites work @@
+Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy
+Normal rank
@@ Property / cites work @@
+The Complexity of Local List Decoding
@@ Property / cites work: The Complexity of Local List Decoding / rank @@
+Normal rank
@@ Property / cites work @@
+If NP languages are hard on the worst-case, then it is easy to find their hard instances
+Normal rank
@@ Property / cites work @@
+Worst-Case to Average-Case Reductions Revisited
@@ Property / cites work: Worst-Case to Average-Case Reductions Revisited / rank @@
+Normal rank
@@ Property / cites work @@
+Limitations of Hardness vs. Randomness under Uniform Reductions
+Normal rank
@@ Property / cites work @@
+Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
+Normal rank
@@ Property / cites work @@
+Q4252738
@@ Property / cites work: Q4252738 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5750403
@@ Property / cites work: Q5750403 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4526985
@@ Property / cites work: Q4526985 / rank @@
+Normal rank
@@ Property / cites work @@
+Boosting and hard-core set construction
@@ Property / cites work: Boosting and hard-core set construction / rank @@
+Normal rank
@@ Property / cites work @@
+A fixed-depth size-hierarchy theorem for AC             <sup>0</sup>             [⊕] via the coin problem
+Normal rank
@@ Property / cites work @@
+On the Complexity of Hardness Amplification
@@ Property / cites work: On the Complexity of Hardness Amplification / rank @@
+Normal rank
@@ Property / cites work @@
+Parity helps to compute majority
@@ Property / cites work: Parity helps to compute majority / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
+Normal rank
@@ Property / cites work @@
+Theory of Cryptography
@@ Property / cites work: Theory of Cryptography / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness Amplification Proofs Require Majority
@@ Property / cites work: Hardness Amplification Proofs Require Majority / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandom generators without the XOR lemma
@@ Property / cites work: Pseudorandom generators without the XOR lemma / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandomness and average-case complexity via uniform reductions
+Normal rank
@@ Property / DOI @@
+.1007/S00037-023-00238-9
@@ Property / DOI: 10.1007/S00037-023-00238-9 / rank @@
+Normal rank