On the $AC^0$ Complexity of Subgraph Isomorphism

DOI10.1137/14099721XzbMath1370.68135OpenAlexW2618244641MaRDI QIDQ5737815

Benjamin Rossman, Yu'an Li, Alexander A. Razborov

Publication date: 30 May 2017

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/14099721x

zbMATH Keywords

treewidthsubgraph isomorphismconstant-depth circuitsthreshold exponent

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Tree-Depth and the Formula Complexity of Subgraph Isomorphism ⋮ Disordered systems insights on computational hardness ⋮ Monotone arithmetic complexity of graph homomorphism polynomials ⋮ Combinatorics, probability and computing. Abstracts from the workshop held April 24--30, 2022 ⋮ Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics ⋮ Unnamed Item ⋮ Beating treewidth for average-case subgraph isomorphism ⋮ The descriptive complexity of subgraph isomorphism without numerics

Cites Work

• \(k\)-subgraph isomorphism on \(\text{AC}^{0}\) circuits
• Boolean function complexity. Advances and frontiers.
• Graph minors. X: Obstructions to tree-decomposition
• Optimal depth, very small size circuits for symmetric functions in \(AC^ 0\)
• Coupling and Poisson approximation
• Diameter and treewidth in minor-closed graph families
• On tree width, bramble size, and expansion
• Linear time low tree-width partitions and algorithmic consequences
• Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).
• Sparse Balanced Partitions and the Complexity of Subgraph Problems
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Poisson approximation for large deviations
• Color-coding
• Subgraph Isomorphism in Planar Graphs and Related Problems
• One hierarchy spawns another
• Polynomial bounds for the grid-minor theorem
• SOFSEM 2005: Theory and Practice of Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item