LOWER BOUNDS FOR SUBGRAPH ISOMORPHISM

DOI10.1142/9789813272880_0187zbMath1490.68113OpenAlexW2972593553MaRDI QIDQ5122162

Benjamin Rossman

Publication date: 22 September 2020

Published in: Proceedings of the International Congress of Mathematicians (ICM 2018) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/9789813272880_0187

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (7)

Tree-Depth and the Formula Complexity of Subgraph Isomorphism ⋮ Disordered systems insights on computational hardness ⋮ Monotone arithmetic complexity of graph homomorphism polynomials ⋮ Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics ⋮ The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs ⋮ Beating treewidth for average-case subgraph isomorphism ⋮ Unnamed Item

This page was built for publication: LOWER BOUNDS FOR SUBGRAPH ISOMORPHISM