scientific article; zbMATH DE number 7561559
From MaRDI portal
Publication:5091223
DOI10.4230/LIPIcs.ICALP.2019.66MaRDI QIDQ5091223
Avishay Tal, Alexander Golovnev, Russell Impagliazzo, Rahul Ilango, Valentine Kabanets, Antonina Kolokolova
Publication date: 21 July 2022
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
circuit lower boundscoin problemhybrid argumentAC\(^0[p\)]biased random Boolean functionsminimum circuit size problem (MCSP)MKTP
Related Items (7)
Algorithms and lower bounds for comparator circuits from shrinkage ⋮ MCSP is hard for read-once nondeterministic branching programs ⋮ Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity ⋮ Unnamed Item ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ The non-hardness of approximating circuit size ⋮ Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
Cites Work
- Boolean function complexity. Advances and frontiers.
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Complexity of Boolean functions over bases with unbounded fan-in gates
- In search of an easy witness: Exponential time vs. probabilistic polynomial time.
- Zero Knowledge and Circuit Minimization
- The Minimum Oracle Circuit Size Problem.
- Circuit minimization problem
- Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
- A taxonomy of problems with fast parallel algorithms
- Information theory and the complexity of boolean functions
- Circuit lower bounds for nondeterministic quasi-polytime: an easy witness lemma for NP and NQP
- On the NP-Completeness of the Minimum Circuit Size Problem.
- Learning algorithms from natural proofs
- Hardness Amplification Proofs Require Majority
- Power from Random Strings
- Natural proofs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication:
