The power of natural properties as oracles
DOI10.1007/s00037-023-00241-0zbMath1529.68111OpenAlexW3198583770MaRDI QIDQ6116834
Valentine Kabanets, Russell Impagliazzo, Ilya Volkovich
Publication date: 16 August 2023
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/8882/
learning algorithmscircuit lower boundsobfuscationnatural propertieshardness of MCSPindistinguishability obfuscatorsminimal circuit size problem (MCSP)
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Networks and circuits as models of computation; circuit complexity (68Q06)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of computing the permanent
- Non-deterministic exponential time has two-prover interactive protocols
- On best-possible obfuscation
- \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs
- Hardness vs randomness
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Oracles and queries that are sufficient for exact learning
- A generic time hierarchy with one bit of advice
- Pseudorandomness and average-case complexity via uniform reductions
- Efficient learning algorithms yield circuit lower bounds
- Zero Knowledge and Circuit Minimization
- The Minimum Oracle Circuit Size Problem.
- Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
- Random-Self-Reducibility of Complete Sets
- Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
- Circuit minimization problem
- PP is as Hard as the Polynomial-Time Hierarchy
- Circuit Lower Bounds for Merlin–Arthur Classes
- Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
- A theory of the learnable
- On relativized exponential and probabilistic complexity classes
- New Collapse Consequences of NP Having Small Circuits
- Algebraic methods for interactive proof systems
- A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
- Circuit lower bounds from NP-hardness of MCSP under turing reductions
- On Learning, Lower Bounds and (un)Keeping Promises
- On the NP-Completeness of the Minimum Circuit Size Problem.
- Computational Complexity
- Learning algorithms from natural proofs
- Power from Random Strings
- Natural proofs
- Pseudo-random generators for all hardnesses
- On pseudorandomness and resource-bounded measure
- Indistinguishability obfuscation from well-founded assumptions
