NP-hardness of approximating meta-complexity: a cryptographic approach
From MaRDI portal
Cites work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- BPP has subexponential time simulations unless EXPTIME has publishable proofs
- A Pseudorandom Generator from any One-way Function
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- A threshold of ln n for approximating set cover
- An introduction to Kolmogorov complexity and its applications
- Analytical approach to parallel repetition
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Candidate indistinguishability obfuscation and functional encryption for all circuits
- Candidate Multilinear Maps from Ideal Lattices
- Capturing one-way functions via NP-hardness of meta-complexity
- Circuit lower bounds from NP-hardness of MCSP under turing reductions
- Circuit minimization problem
- Computational Complexity
- Computational depth: Concept and applications
- Computationally Sound Proofs
- Constant depth formula and partial function versions of MCSP are hard
- Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity
- Discrete logarithm and minimum circuit size
- Foundations of Cryptography
- Fuzzy Identity-Based Encryption
- Hardness of approximate two-level logic minimization and PAC learning with membership queries
- Hardness of KT characterizes parallel cryptography
- How To Prove Yourself: Practical Solutions to Identification and Signature Problems
- scientific article; zbMATH DE number 3133387 (Why is no real title available?)
- scientific article; zbMATH DE number 3489106 (Why is no real title available?)
- scientific article; zbMATH DE number 1996402 (Why is no real title available?)
- scientific article; zbMATH DE number 2081089 (Why is no real title available?)
- scientific article; zbMATH DE number 7561750 (Why is no real title available?)
- scientific article; zbMATH DE number 7250145 (Why is no real title available?)
- scientific article; zbMATH DE number 7250147 (Why is no real title available?)
- scientific article; zbMATH DE number 7650382 (Why is no real title available?)
- scientific article; zbMATH DE number 7829297 (Why is no real title available?)
- scientific article; zbMATH DE number 7799585 (Why is no real title available?)
- Identity-based cryptosystems and signature schemes
- Identity-Based Encryption from the Weil Pairing
- Indistinguishability obfuscation from LPN over \(\mathbb{F}_p\), DLIN, and PRGs in \(NC^0\)
- Indistinguishability obfuscation from well-founded assumptions
- Limits of minimum circuit size problem as oracle
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Minimizing Disjunctive Normal Form Formulas and AC^0 Circuits Given a Truth Table
- Minimum circuit size, graph isomorphism, and related problems
- Minimum propositional proof length is NP-hard to linearly approximate
- Natural proofs
- New directions in cryptography
- New insights on the (non-)hardness of circuit minimization and related problems
- Non-black-box worst-case to average-case reductions within NP
- NP-hardness of learning programs and partial MCSP
- On one-way functions and Kolmogorov complexity
- On one-way functions from NP-complete problems
- On the (im)possibility of obfuscating programs
- On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
- On the average-case complexity of MCSP and its variants
- On the Complexity of Learning Minimum Time-Bounded Turing Machines
- On the hardness of approximating label-cover
- On the notion of infinite pseudorandom sequences
- On the NP-Completeness of the Minimum Circuit Size Problem.
- On the possibility of basing cryptography on \(\mathsf{EXP}\ne \mathsf{BPP} \)
- On Worst‐Case to Average‐Case Reductions for NP Problems
- One-way functions and (im)perfect obfuscation
- Parity, circuits, and the polynomial-time hierarchy
- Power from Random Strings
- Predictable arguments of knowledge
- Probabilistic checking of proofs
- Probabilistic encryption
- Probabilistic Kolmogorov complexity with applications to average-case complexity
- Proof verification and the hardness of approximation problems
- Pseudorandomness and average-case complexity via uniform reductions
- Random oracles and non-uniformity
- Random-Self-Reducibility of Complete Sets
- Reducibility among combinatorial problems
- Reviewing bounds on the circuit size of the hardest functions
- Robustness of average-case meta-complexity via pseudorandomness
- Secret-sharing for NP
- Secret-Sharing Schemes: A Survey
- Symmetry of information from meta-complexity
- The Complexity of Complexity
- The minimum oracle circuit size problem
- The non-hardness of approximating circuit size
- Three approaches to the quantitative definition of information*
- Unexpected hardness results for Kolmogorov complexity under uniform reductions
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
- Witness encryption and its applications
- Witness encryption and null-iO from evasive LWE
- ZAPs and non-interactive witness indistinguishability from indistinguishability obfuscation
- Zero knowledge and circuit minimization
This page was built for publication: NP-hardness of approximating meta-complexity: a cryptographic approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6939715)
