\(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits

DOI10.1007/s00037-010-0288-yzbMath1213.68304OpenAlexW4251265810MaRDI QIDQ626676

Kazuyuki Amano

Publication date: 18 February 2011

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-010-0288-y

zbMATH Keywords

upper boundslower boundscircuit complexity\(k\)-cliqueconstant depth circuits

Mathematics Subject Classification ID

Related Items (9)

Tree-Depth and the Formula Complexity of Subgraph Isomorphism ⋮ A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas ⋮ On the $AC^0$ Complexity of Subgraph Isomorphism ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ Beating treewidth for average-case subgraph isomorphism ⋮ Parameterized Complexity of DPLL Search Procedures ⋮ The descriptive complexity of subgraph isomorphism without numerics ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: \(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits