The power of adaptiveness and additional queries in random-self- reductions

DOI10.1007/BF01202287zbMath0808.68060OpenAlexW3214325496MaRDI QIDQ1332664

Lance J. Fortnow, Joan Feigenbaum, Carstent Lund, Daniel A. Spielman

Publication date: 1 September 1994

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01202287

zbMATH Keywords

adaptivenessrandom-self-reducibility

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The power of adaptiveness and additional queries in random-self- reductions, Collapsing and separating completeness notions under average-case and worst-case hypotheses, On the autoreducibility of functions, Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions

Cites Work

• Unnamed Item
• Unnamed Item
• Non-deterministic exponential time has two-prover interactive protocols
• Probabilistic encryption
• Random oracles separate PSPACE from the polynomial-time hierarchy
• On hiding information from an oracle
• Self-testing/correcting with applications to numerical problems
• The power of adaptiveness and additional queries in random-self- reductions
• Random-Self-Reducibility of Complete Sets
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• The Knowledge Complexity of Interactive Proof Systems
• Algebraic methods for interactive proof systems
• IP = PSPACE
• Designing programs that check their work