An information-theoretic treatment of random-self-reducibility (extended abstract)

DOI10.1007/BFB0023486MaRDI QIDQ5048951zbMATH OpenOpenAlexFDO

Authors Joan Feigenbaum, M. Strauss

Publication date 9 November 2022

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

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

Mathematics Subject Classification ID

Information theory (general) (94A15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Random-Self-Reducibility of Complete Sets
• On the reducibility of sets inside NP to sets with low information content
• The power of adaptiveness and additional queries in random-self- reductions
• Information Lower Bounds via Self-reducibility
• On Worst‐Case to Average‐Case Reductions for NP Problems

Cites work

• scientific article; zbMATH DE number 4191094 (Why is no real title available?)
• scientific article; zbMATH DE number 4213418 (Why is no real title available?)
• scientific article; zbMATH DE number 549854 (Why is no real title available?)
• Algebraic methods for interactive proof systems
• Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
• Designing programs that check their work
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• IP = PSPACE
• Non-deterministic exponential time has two-prover interactive protocols
• On hiding information from an oracle
• Probabilistic encryption
• Random oracles separate PSPACE from the polynomial-time hierarchy
• Random-Self-Reducibility of Complete Sets
• Self-testing/correcting with applications to numerical problems
• Some consequences of non-uniform conditions on uniform classes
• The Knowledge Complexity of Interactive Proof Systems
• The complexity of computing the permanent
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

Cited in

(5)

• Random-Self-Reducibility of Complete Sets
• The Power of Self-Reducibility: Selectivity, Information, and Approximation
• Information Lower Bounds via Self-reducibility
• scientific article; zbMATH DE number 1929940 (Why is no real title available?)
• Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions

This page was built for publication: An information-theoretic treatment of random-self-reducibility (extended abstract)

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