Skip to main content

Lower bounds for subgraph isomorphism

Publication ,  Conference
Rossman, B
Published in: Proceedings of the International Congress of Mathematicians, ICM 2018
January 1, 2018

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 Scholars

Published In

Proceedings of the International Congress of Mathematicians, ICM 2018

ISBN

9789813272934

Publication Date

January 1, 2018

Volume

4

Start / End Page

3443 / 3464
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Rossman, B. (2018). Lower bounds for subgraph isomorphism. In Proceedings of the International Congress of Mathematicians, ICM 2018 (Vol. 4, pp. 3443–3464).
Rossman, B. “Lower bounds for subgraph isomorphism.” In Proceedings of the International Congress of Mathematicians, ICM 2018, 4:3443–64, 2018.
Rossman B. Lower bounds for subgraph isomorphism. In: Proceedings of the International Congress of Mathematicians, ICM 2018. 2018. p. 3443–64.
Rossman, B. “Lower bounds for subgraph isomorphism.” Proceedings of the International Congress of Mathematicians, ICM 2018, vol. 4, 2018, pp. 3443–64.
Rossman B. Lower bounds for subgraph isomorphism. Proceedings of the International Congress of Mathematicians, ICM 2018. 2018. p. 3443–3464.

Published In

Proceedings of the International Congress of Mathematicians, ICM 2018

ISBN

9789813272934

Publication Date

January 1, 2018

Volume

4

Start / End Page

3443 / 3464