Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification (Q3088109): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/978-3-642-22935-0_32
+Normal rank
@@ Property / OpenAlex ID @@
+W2401286301
@@ Property / OpenAlex ID: W2401286301 / 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 @@
+\(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
+Normal rank
@@ Property / cites work @@
+On Worst‐Case to Average‐Case Reductions for NP Problems
+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 @@
+Hardness amplification within NP against deterministic algorithms
+Normal rank
@@ Property / cites work @@
+Q3549643
@@ Property / cites work: Q3549643 / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness amplification via space-efficient direct products
+Normal rank
@@ Property / cites work @@
+On Yao’s XOR-Lemma
@@ Property / cites work: On Yao’s XOR-Lemma / rank @@
+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 @@
+Using Nondeterminism to Amplify Hardness
@@ Property / cites work: Using Nondeterminism to Amplify Hardness / rank @@
+Normal rank
@@ Property / cites work @@
+Approximate List-Decoding of Direct Product Codes and Uniform Hardness Amplification
+Normal rank
@@ Property / cites work @@
+Chernoff-type direct product theorems
@@ Property / cites work: Chernoff-type direct product theorems / rank @@
+Normal rank
@@ Property / cites work @@
+Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
+Normal rank
@@ Property / cites work @@
+Q4252738
@@ Property / cites work: Q4252738 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4526985
@@ Property / cites work: Q4526985 / rank @@
+Normal rank
@@ Property / cites work @@
+Randomness vs time: Derandomization under a uniform assumption
+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 @@
+One way functions and pseudorandom generators
@@ Property / cites work: One way functions and pseudorandom generators / rank @@
+Normal rank
@@ Property / cites work @@
+Q3210157
@@ Property / cites work: Q3210157 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Complexity of Hard-Core Set Constructions
@@ Property / cites work: On the Complexity of Hard-Core Set Constructions / rank @@
+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 @@
+Hardness amplification within NP
@@ Property / cites work: Hardness amplification within NP / rank @@
+Normal rank
@@ Property / cites work @@
+Theory of Cryptography
@@ Property / cites work: Theory of Cryptography / 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 @@
+Simple extractors for all min-entropies and a new pseudorandom generator
+Normal rank
@@ Property / cites work @@
+Hardness Amplification Proofs Require Majority
@@ Property / cites work: Hardness Amplification Proofs Require Majority / rank @@
+Normal rank
@@ Property / cites work @@
+Some Applications of Coding Theory in Computational Complexity
+Normal rank
@@ Property / cites work @@
+On uniform amplification of hardness in NP
@@ Property / cites work: On uniform amplification of hardness in NP / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandomness and average-case complexity via uniform reductions
+Normal rank
@@ Property / cites work @@
+The complexity of constructing pseudorandom generators from hard functions
+Normal rank
@@ Property / cites work @@
+Query Complexity in Errorless Hardness Amplification
+Normal rank