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

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (35)

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 ⋮ When Arthur has neither random coins nor time to spare: superfast derandomization of proof systems ⋮ Capturing one-way functions via NP-hardness of meta-complexity ⋮ NP-hardness of approximating meta-complexity: a cryptographic approach ⋮ 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 ⋮ Complexity theory. Abstracts from the workshop held June 2--7, 2024 ⋮ Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification ⋮ On building fine-grained one-way functions from strong average-case hardness ⋮ 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