k-subgraph isomorphism on AC^0 circuits

DOI10.1007/S00037-010-0288-YMaRDI QIDQ626676zbMATH OpenOpenAlexFDO

Authors 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

\(k\)-cliquecircuit complexityconstant depth circuitslower boundsupper bounds

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Random graphs (graph-theoretic aspects) (05C80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Lower bounds for subgraph isomorphism
• On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
• The monotone complexity of \(k\)-clique on random graphs
• The monotone circuit complexity of Boolean functions
• Fundamentals of Computation Theory

Cited in

(10)

• Beating treewidth for average-case subgraph isomorphism
• Certifying polynomials for \(\mathsf{AC}^0[\oplus]\) circuits, with applications to lower bounds and circuit compression
• scientific article; zbMATH DE number 6866317 (Why is no real title available?)
• A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
• A quadratic size-hierarchy theorem for small-depth multilinear formulas
• Lower bounds for subgraph isomorphism
• The monotone complexity of \(k\)-clique on random graphs
• On the \(\mathrm{AC}^0\) complexity of subgraph isomorphism
• Tree-Depth and the Formula Complexity of Subgraph Isomorphism
• Parameterized complexity of DPLL search procedures

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q626676)