Random-Self-Reducibility of Complete Sets
From MaRDI portal
Recommendations
- The power of adaptiveness and additional queries in random-self- reductions
- On Worst‐Case to Average‐Case Reductions for NP Problems
- Probabilistic autoreductions
- An information-theoretic treatment of random-self-reducibility (extended abstract)
- On coherence, random-self-reducibility, and self-correction
Cited in
(50)- On coherence, random-self-reducibility, and self-correction
- The power of adaptiveness and additional queries in random-self- reductions
- 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
- p-selective self-reducible sets: a new characterization of P
- Computational barriers to estimation from low-degree polynomials
- On building fine-grained one-way functions from strong average-case hardness
- Can we locally compute sparse connected subgraphs?
- Random reduction consistency of the Weber set, the core and the anti-core
- Algebraic generalization of Diffie-Hellman key exchange
- Lower Bounds on the Query Complexity of Non-uniform and Adaptive Reductions Showing Hardness Amplification
- Towards non-black-box separations of public key encryption and one way function
- On nonadaptive reductions to the set of random strings and its dense subsets
- Unprovable security of perfect NIZK and non-interactive non-malleable commitments
- A nearly tight sum-of-squares lower bound for the planted clique problem
- scientific article; zbMATH DE number 1929940 (Why is no real title available?)
- Fine-grained derandomization: from problem-centric to resource-centric complexity
- An information-theoretic treatment of random-self-reducibility (extended abstract)
- scientific article; zbMATH DE number 7561748 (Why is no real title available?)
- Worst-Case to Average-Case Reductions for Subclasses of P
- scientific article; zbMATH DE number 7250147 (Why is no real title available?)
- The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs
- Exponential lower bound for 2-query locally decodable codes via a quantum argument
- Pseudorandom generators without the XOR lemma
- Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions
- Average-case intractability vs. worst-case intractability
- scientific article; zbMATH DE number 7758312 (Why is no real title available?)
- scientific article; zbMATH DE number 7758317 (Why is no real title available?)
- 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}\)
- 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
- On building fine-grained one-way functions from strong average-case hardness
- Complexity theory. Abstracts from the workshop held June 2--7, 2024
- On completeness under random reductions
- Arithmetization: A new method in structural complexity theory
- Consequences of randomized reductions from SAT to time-bounded Kolmogorov complexity
- The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
- NP-hardness of approximating meta-complexity: a cryptographic approach
- Leakage resilience, targeted pseudorandom generators, and mild derandomization of Arthur-Merlin protocols
- On the structure of learnability beyond \textsf{P/poly}
- Locally computing edge orientations
- SAT reduces to the minimum circuit size problem with a random oracle
- Kolmogorov complexity characterizes statistical zero knowledge
- Permanental rank vs determinantal rank of random matrices over finite fields
- Lower bounds on the query complexity of non-uniform and adaptive reductions showing hardness amplification
- Padding, commitment and self-reducibility
- On the autoreducibility of functions
This page was built for publication: Random-Self-Reducibility of Complete Sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3142589)
