Non-Black-Box Worst-Case to Average-Case Reductions Within NP

DOI10.1137/19M124705XMaRDI QIDQ6140986zbMATH OpenFDO

Authors Shuichi Hirahara

Publication date 2 January 2024

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/19M124705X

zbMATH Keywords

average-case complexityminimum circuit size problemnon-black-box reductiontime-bounded Kolmogorov complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Cryptography (94A60)

Recommendations

• Worst-Case to Average-Case Reductions Revisited
• Relativized worlds without worst-case to average-case reductions for NP
• On Worst‐Case to Average‐Case Reductions for NP Problems
• Relativized worlds without worst-case to average-case reductions for NP
• If NP languages are hard on the worst-case, then it is easy to find their hard instances

Cites work

• BPP has subexponential time simulations unless EXPTIME has publishable proofs
• A Pseudorandom Generator from any One-way Function
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• Algebrization: a new barrier in complexity theory
• An Unconditional Study of Computational Zero Knowledge
• Average Case Complete Problems
• Average-case hardness of NP from exponential worst-case hardness assumptions
• Circuit minimization problem
• Complexity theory. Abstracts from the workshop held November 15--21, 2015
• Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness
• Decoding of Reed Solomon codes beyond the error-correction bound
• Extracting all the randomness and reducing the error in Trevisan's extractors
• Extractors and pseudorandom generators
• Foundations of Cryptography
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Hardness vs randomness
• scientific article; zbMATH DE number 5899254 (Why is no real title available?)
• scientific article; zbMATH DE number 5081744 (Why is no real title available?)
• scientific article; zbMATH DE number 3960854 (Why is no real title available?)
• scientific article; zbMATH DE number 3489106 (Why is no real title available?)
• scientific article; zbMATH DE number 1256724 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• scientific article; zbMATH DE number 7250145 (Why is no real title available?)
• scientific article; zbMATH DE number 7250147 (Why is no real title available?)
• scientific article; zbMATH DE number 7650416 (Why is no real title available?)
• scientific article; zbMATH DE number 7758317 (Why is no real title available?)
• If NP languages are hard on the worst-case, then it is easy to find their hard instances
• Language compression and pseudorandom generators
• Lattice problems in NP ∩ coNP
• Learning algorithms from natural proofs
• Limits of minimum circuit size problem as oracle
• Lossless condensers, unbalanced expanders, and extractors
• Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table
• Minimum circuit size, graph isomorphism, and related problems
• Natural proofs
• New insights on the (non-)hardness of circuit minimization and related problems
• On basing one-way functions on NP-hardness
• On basing size-verifiable one-way functions on NP-hardness
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
• On the average-case complexity of MCSP and its variants
• On the Complexity of Learning Minimum Time-Bounded Turing Machines
• On the limits of nonapproximability of lattice problems
• On the NP-Completeness of the Minimum Circuit Size Problem.
• On Worst‐Case to Average‐Case Reductions for NP Problems
• Power from Random Strings
• Pseudorandom generators without the XOR lemma
• Pseudorandomness and average-case complexity via uniform reductions
• Random-Self-Reducibility of Complete Sets
• Randomness vs time: Derandomization under a uniform assumption
• Relations between average case complexity and approximation complexity
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Some results on derandomization
• Tensor-based hardness of the shortest vector problem to within almost polynomial factors
• The minimum oracle circuit size problem
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
• Zero knowledge and circuit minimization

Cited in

(1)

• Complexity theory. Abstracts from the workshop held June 2--7, 2024

This page was built for publication: Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6140986)