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

DOI10.1007/978-3-030-43662-9_15OpenAlexW2767824041MaRDI QIDQ5098780FDOQ5098780

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

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

Mathematics Subject Classification ID

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

Cites Work

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

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)