Lower bounds for subgraph isomorphism


Conference Paper

© ICM 2018.All rights reserved. We consider the problem of determining whether an ErdÅ‘s–Rényi random graph contains a subgraph isomorphic to a fixed pattern, such as a clique or cycle of constant size. The computational complexity of this problem is tied to fundamental open questions including P vs. NP and NC1 vs. L. We give an overview of unconditional average-case lower bounds for this problem (and its colored variant) in a few important restricted classes of Boolean circuits.

Duke Authors

Cited Authors

  • Rossman, B

Published Date

  • January 1, 2018

Published In

  • Proceedings of the International Congress of Mathematicians, Icm 2018

Volume / Issue

  • 4 /

Start / End Page

  • 3443 - 3464

International Standard Book Number 13 (ISBN-13)

  • 9789813272934

Citation Source

  • Scopus