scientific article; zbMATH DE number 7250147

DOI10.4230/LIPIcs.CCC.2018.7zbMath1441.68060MaRDI QIDQ5121895

Valentine Kabanets, Russell Impagliazzo, Ilya Volkovich

Publication date: 22 September 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

learning algorithmscircuit lower boundsobfuscationnatural propertieshardness of MCSPindistinguishability obfuscators (IO)minimal circuit-size problem (MCSP)

Mathematics Subject Classification ID

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)

Related Items (10)

The power of natural properties as oracles ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ The final nail in the coffin of statistically-secure obfuscator ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The non-hardness of approximating circuit size ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization ⋮ Relations and equivalences between circuit lower bounds and karp-lipton theorems ⋮ Hardness magnification near state-of-the-art lower bounds

Cites Work

• 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
• \(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
• Circuit-size lower bounds and non-reducibility to sparse sets
• PP is as Hard as the Polynomial-Time Hierarchy
• Circuit Lower Bounds for Merlin–Arthur Classes
• On Best-Possible Obfuscation
• 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
• 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

This page was built for publication: