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

DOI10.1007/BFB0023486zbMATH Open1499.68125OpenAlexW1515378134MaRDI QIDQ5048951FDOQ5048951

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

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

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)

Cites Work

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