Random-Self-Reducibility of Complete Sets

DOI10.1137/0222061zbMath0789.68057OpenAlexW2062965695MaRDI QIDQ3142589

Joan Feigenbaum, Lance J. Fortnow

Publication date: 20 December 1993

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0222061

zbMATH Keywords

interactive proof systemscomplexity classesprogram checkersrandom self-reduction

Mathematics Subject Classification ID

Related Items (30)

The power of adaptiveness and additional queries in random-self- reductions ⋮ An information-theoretic treatment of random-self-reducibility ⋮ Towards Non-Black-Box Separations of Public Key Encryption and One Way Function ⋮ Computational barriers to estimation from low-degree polynomials ⋮ Unprovable security of perfect NIZK and non-interactive non-malleable commitments ⋮ Can we locally compute sparse connected subgraphs? ⋮ On building fine-grained one-way functions from strong average-case hardness ⋮ Average-case intractability vs. worst-case intractability ⋮ On algorithmic applications of the immersion order: An overview of ongoing work presented at the Third Slovenian International Conference on Graph Theory ⋮ Proofs of Work from worst-case assumptions ⋮ Algebraic generalization of Diffie-Hellman key exchange ⋮ Worst-Case to Average-Case Reductions for Subclasses of P ⋮ Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? ⋮ The power of natural properties as oracles ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On Nonadaptive Reductions to the Set of Random Strings and Its Dense Subsets ⋮ A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Arithmetization: A new method in structural complexity theory ⋮ On the autoreducibility of functions ⋮ Pseudorandom generators without the XOR lemma ⋮ Unnamed Item ⋮ Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions ⋮ Exponential lower bound for 2-query locally decodable codes via a quantum argument ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification ⋮ Unnamed Item

This page was built for publication: Random-Self-Reducibility of Complete Sets