The power of adaptiveness and additional queries in random-self- reductions
type: Item
instance of: scholarly article
title: The power of adaptiveness and additional queries in random-self- reductions
zbMATH Open document ID: 0808.68060
DOI: 10.1007/BF01202287
author: Joan Feigenbaum
author: Lance Fortnow
author: C. Lund
author: Daniel A. Spielman
published in: Computational Complexity
publication date: 1994-09-01T00:00:00Z
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 627639
zbMATH Keywords: adaptiveness
zbMATH Keywords: random-self-reducibility
MaRDI profile type: Publication
cites work: On hiding information from an oracle
cites work: Random oracles separate PSPACE from the polynomial-time hierarchy
cites work: Non-deterministic exponential time has two-prover interactive protocols
cites work: Q4279564
cites work: Designing programs that check their work
cites work: Self-testing/correcting with applications to numerical problems
cites work: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
cites work: Q4287358
cites work: Random-Self-Reducibility of Complete Sets
cites work: Probabilistic encryption
cites work: The Knowledge Complexity of Interactive Proof Systems
cites work: Algebraic methods for interactive proof systems
cites work: IP = PSPACE
full work available at URL: https://doi.org/10.1007/bf01202287
OpenAlex ID: W3214325496
Recommended article: Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
Recommended article: Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
Recommended article: Adaptive versus nonadaptive queries to NP and P-selective sets
Recommended article: Q4942646
Recommended article: The global power of additional queries to random oracles
Recommended article: The Density of Weakly Complete Problems under Adaptive Reductions
Recommended article: The global power of additional queries to \(p\)-random oracles
Recommended article: The Power of Self-Reducibility: Selectivity, Information, and Approximation
Recommended article: Q2754207
Recommended article: Randomizing Reductions of Search Problems
description: scientific article; zbMATH DE number 627639