Worst-Case to Average-Case Reductions for Subclasses of P
From MaRDI portal
Publication:5098780
DOI10.1007/978-3-030-43662-9_15OpenAlexW2767824041MaRDI QIDQ5098780
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
Related Items (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
Cites Work
- Boolean function complexity. Advances and frontiers.
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Random oracles separate PSPACE from the polynomial-time hierarchy
- On average time hierarchies
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Randomness vs time: Derandomization under a uniform assumption
- On Yao’s XOR-Lemma
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Random-Self-Reducibility of Complete Sets
- Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
- Simple Constructions of Almost k-wise Independent Random Variables
- Chinese remaindering with errors
- Robust Characterizations of Polynomials with Applications to Program Testing
- Average-case fine-grained hardness
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two
- Secure Computation of Constant-Depth Circuits with Applications to Database Search Problems
- On Worst‐Case to Average‐Case Reductions for NP Problems
- Computational Complexity
- Pseudorandom generators without the XOR lemma
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Worst-Case to Average-Case Reductions for Subclasses of P
