Worst-Case to Average-Case Reductions for Subclasses of P

DOI10.1007/978-3-030-43662-9_15MaRDI QIDQ5098780zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Guy N. Rothblum

Publication date 30 August 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-43662-9_15

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• Relativized worlds without worst-case to average-case reductions for NP
• Relativized worlds without worst-case to average-case reductions for NP
• Worst-Case to Average-Case Reductions Revisited
• Structural average case complexity
• scientific article; zbMATH DE number 5081744

Cites work

• scientific article; zbMATH DE number 4191094 (Why is no real title available?)
• scientific article; zbMATH DE number 51893 (Why is no real title available?)
• scientific article; zbMATH DE number 1304313 (Why is no real title available?)
• scientific article; zbMATH DE number 2019635 (Why is no real title available?)
• scientific article; zbMATH DE number 2019636 (Why is no real title available?)
• scientific article; zbMATH DE number 742944 (Why is no real title available?)
• Average-case fine-grained hardness
• Boolean function complexity. Advances and frontiers.
• Chinese remaindering with errors
• Computational Complexity
• Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two
• Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• On Worst‐Case to Average‐Case Reductions for NP Problems
• On Yao's XOR-lemma
• On average time hierarchies
• Pseudorandom generators without the XOR lemma
• Random oracles separate PSPACE from the polynomial-time hierarchy
• Random-Self-Reducibility of Complete Sets
• Randomness vs time: Derandomization under a uniform assumption
• Robust Characterizations of Polynomials with Applications to Program Testing
• Secure Computation of Constant-Depth Circuits with Applications to Database Search Problems
• Simple Constructions of Almost k-wise Independent Random Variables
• Simple doubly-efficient interactive proof systems for locally-characterizable sets
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Uniform direct product theorems: simplified, optimized, and derandomized
• BPP has subexponential time simulations unless EXPTIME has publishable proofs
• \(\Sigma_ 1^ 1\)-formulae on finite structures

Cited in

(2)

• Improved Merlin-Arthur protocols for central problems in fine-grained complexity
• The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs

This page was built for publication: Worst-Case to Average-Case Reductions for Subclasses of P

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